summaryrefslogtreecommitdiff
path: root/src/bin
diff options
context:
space:
mode:
authorJean-Philippe Andre <jp.andre@samsung.com>2013-07-24 10:59:51 +0900
committerJean-Philippe Andre <jp.andre@samsung.com>2013-10-28 15:47:13 +0900
commit315c2fd161b1a552c5589bae6f7a488ffea1d318 (patch)
tree43e4c99929123cb6fb04f09d81e76d761b200921 /src/bin
parentd0e647fee3b5ebe6e5c2905a4053a51283f27014 (diff)
evas/cserve2: binary search in Shared_Array
Diffstat (limited to 'src/bin')
-rw-r--r--src/bin/evas/evas_cserve2_index.c35
1 files changed, 29 insertions, 6 deletions
diff --git a/src/bin/evas/evas_cserve2_index.c b/src/bin/evas/evas_cserve2_index.c
index fd95aa510d..dd335d8ce2 100644
--- a/src/bin/evas/evas_cserve2_index.c
+++ b/src/bin/evas/evas_cserve2_index.c
@@ -38,9 +38,9 @@ struct _Shared_Array_Header
38 int32_t count; 38 int32_t count;
39 int32_t generation_id; 39 int32_t generation_id;
40 int32_t emptyidx; 40 int32_t emptyidx;
41 int32_t sortedidx;
41 int32_t _reserved1; 42 int32_t _reserved1;
42 int32_t _reserved2; 43 int32_t _reserved2;
43 int32_t _reserved3;
44}; 44};
45 45
46struct _Shared_Array 46struct _Shared_Array
@@ -280,8 +280,9 @@ cserve2_shared_array_new(int tag, int elemsize, int initcount)
280 sa->header->elemsize = elemsize; 280 sa->header->elemsize = elemsize;
281 sa->header->generation_id = 1; 281 sa->header->generation_id = 1;
282 sa->header->emptyidx = 0; 282 sa->header->emptyidx = 0;
283 sa->header->sortedidx = 0;
283 sa->header->tag = tag; 284 sa->header->tag = tag;
284 memset(&sa->header->_reserved1, 0, sizeof(int32_t) * 3); 285 memset(&sa->header->_reserved1, 0, sizeof(int32_t) * 2);
285 286
286 return sa; 287 return sa;
287} 288}
@@ -449,6 +450,7 @@ cserve2_shared_array_repack(Shared_Array *sa,
449 450
450 // Finalize & return 451 // Finalize & return
451 sa2->header->emptyidx = newcount; 452 sa2->header->emptyidx = newcount;
453 sa2->header->sortedidx = newcount;
452 sa2->header->tag = sa->header->tag; 454 sa2->header->tag = sa->header->tag;
453 return sa2; 455 return sa2;
454} 456}
@@ -462,12 +464,33 @@ cserve2_shared_array_item_find(Shared_Array *sa, void *data,
462 464
463 if (!sa || !cmp) return -1; 465 if (!sa || !cmp) return -1;
464 466
465 // TODO: Fast search in the sorted zone 467 // Binary search
466 468 if (sa->header->sortedidx > 0)
467 ptr = sa->ds->data + sizeof(Shared_Array_Header); 469 {
470 int low = 0;
471 int high = sa->header->sortedidx;
472 int prev = -1;
473 int r;
474 k = high / 2;
475 while (prev != k)
476 {
477 ptr = cserve2_shared_array_item_data_get(sa, k);
478 r = cmp(ptr, data);
479 if (!r)
480 return k;
481 else if (r > 0)
482 high = k;
483 else
484 low = k;
485 prev = k;
486 k = low + (high - low) / 2;
487 }
488 }
468 489
469 // Linear search O(n) 490 // Linear search O(n)
470 for (k = 0; k < sa->header->emptyidx; k++) 491 k = sa->header->sortedidx;
492 ptr = sa->ds->data + sizeof(Shared_Array_Header) + k * sa->header->elemsize;
493 for (; k < sa->header->emptyidx; k++)
471 { 494 {
472 if (!cmp(ptr, data)) 495 if (!cmp(ptr, data))
473 return k; 496 return k;