From 441b912feaeba7f07dcee353feed9b39343dba27 Mon Sep 17 00:00:00 2001 From: cedric Date: Wed, 14 Sep 2011 22:04:37 +0000 Subject: [PATCH] eina: fix eina inlist sorted insert (with and without state) git-svn-id: svn+ssh://svn.enlightenment.org/var/svn/e/trunk/eina@63398 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33 --- src/include/eina_inlist.h | 3 +- src/lib/eina_inlist.c | 105 +++++++++++++++++++++++++------------------ src/tests/eina_test_inlist.c | 42 ++++++++++++++++- 3 files changed, 105 insertions(+), 45 deletions(-) diff --git a/src/include/eina_inlist.h b/src/include/eina_inlist.h index c388211..75207dc 100644 --- a/src/include/eina_inlist.h +++ b/src/include/eina_inlist.h @@ -674,13 +674,14 @@ EAPI Eina_Inlist_Sorted_State *eina_inlist_sorted_state_new(void); * * @param state The state to update * @param list The list to match + * @return The number of item in the actually in the list * @since 1.1.0 * * See eina_inlist_sorted_state_insert() for more information. This function is * usefull if you didn't use eina_inlist_sorted_state_insert() at some point, but * still think you have a sorted list. It will only correctly work on a sorted list. */ -EAPI void eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list); +EAPI int eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list); /** * @brief Free an Eina_Inlist_Sorted_State. diff --git a/src/lib/eina_inlist.c b/src/lib/eina_inlist.c index 73aa2e2..89a93a2 100644 --- a/src/lib/eina_inlist.c +++ b/src/lib/eina_inlist.c @@ -190,6 +190,21 @@ eina_inlist_sort_rebuild_prev(Eina_Inlist *list) return prev; } +static void +_eina_inlist_sorted_state_compact(Eina_Inlist_Sorted_State *state) +{ + unsigned short i, j; + + /* compress the jump table */ + state->jump_div *= 2; + state->jump_limit /= 2; + + for (i = 2, j = 1; + i < EINA_INLIST_JUMP_SIZE; + i += 2, j++) + state->jump_table[j] = state->jump_table[i]; +} + /** * @endcond */ @@ -434,7 +449,7 @@ eina_inlist_count(const Eina_Inlist *list) return i; } -EAPI void +EAPI int eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list) { Eina_Inlist *ct = NULL; @@ -451,16 +466,7 @@ eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list { if (state->jump_limit == EINA_INLIST_JUMP_SIZE) { - unsigned short i, j; - - /* compress the jump table */ - state->jump_div *= 2; - state->jump_limit /= 2; - - for (i = 2, j = 1; - i < EINA_INLIST_JUMP_SIZE; - i += 2, j++) - state->jump_table[j] = state->jump_table[i]; + _eina_inlist_sorted_state_compact(state); } state->jump_table[state->jump_limit] = ct; @@ -468,6 +474,9 @@ eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list jump_count = 0; } } + + state->inserted = count; + return count; } EAPI Eina_Inlist_Sorted_State * @@ -496,6 +505,7 @@ _eina_inlist_sorted_state_insert(Eina_Inlist_Sorted_State *state, { Eina_Inlist *last; int jump_count; + int start; state->inserted++; @@ -505,27 +515,35 @@ _eina_inlist_sorted_state_insert(Eina_Inlist_Sorted_State *state, state->jump_table[index] = state->jump_table[index]->prev; } - last = state->jump_table[state->jump_limit - 1]; - for (jump_count = 0; last != NULL; last = last->next) - jump_count++; + start = state->jump_limit - 3; + if (start < 0) + start = 0; - if (jump_count == state->jump_div + 1) + last = state->jump_table[start]; + start++; + + /* Correctly rebuild end of list */ + for (jump_count = 0; last->next != NULL; last = last->next, jump_count++) { - if (state->jump_limit == EINA_INLIST_JUMP_SIZE) + if (jump_count == state->jump_div) { - unsigned short i, j; - - /* compress the jump table */ - state->jump_div *= 2; - state->jump_limit /= 2; + if (state->jump_limit == start) + { + if (state->jump_limit == EINA_INLIST_JUMP_SIZE) + { + _eina_inlist_sorted_state_compact(state); + start = state->jump_limit - 1; + continue ; + } + else + { + state->jump_limit++; + } + } - for (i = 2, j = 1; - i < EINA_INLIST_JUMP_SIZE; - i += 2, j++) - state->jump_table[j] = state->jump_table[i]; + state->jump_table[start++] = last; + jump_count = 0; } - state->jump_table[state->jump_limit] = state->jump_table[0]->last; - state->jump_limit++; } } @@ -539,7 +557,7 @@ eina_inlist_sorted_insert(Eina_Inlist *list, int cmp = 0; int inf, sup; int cur = 0; - int count = 0; + int count; if (!list) return eina_inlist_append(NULL, item); @@ -554,7 +572,7 @@ eina_inlist_sorted_insert(Eina_Inlist *list, state.jump_div = 1; state.jump_limit = 0; - eina_inlist_sorted_state_init(&state, list); + count = eina_inlist_sorted_state_init(&state, list); /* * now do a dychotomic search directly inside the jump_table. @@ -600,8 +618,8 @@ eina_inlist_sorted_insert(Eina_Inlist *list, * Now do a dychotomic search between two entries inside the jump_table */ cur *= state.jump_div; - inf = cur - state.jump_div; - sup = cur + state.jump_div; + inf = cur - state.jump_div - 1; + sup = cur + state.jump_div + 1; if (sup > count - 1) sup = count - 1; if (inf < 0) inf = 0; @@ -632,7 +650,7 @@ eina_inlist_sorted_insert(Eina_Inlist *list, break; } - if (cmp < 0) + if (cmp <= 0) return eina_inlist_append_relative(list, item, ct); return eina_inlist_prepend_relative(list, item, ct); } @@ -647,7 +665,7 @@ eina_inlist_sorted_state_insert(Eina_Inlist *list, int cmp = 0; int inf, sup; int cur = 0; - int count = 0; + int count; unsigned short head; unsigned int offset; @@ -676,6 +694,8 @@ eina_inlist_sorted_state_insert(Eina_Inlist *list, return eina_inlist_prepend(list, item); } + count = state->inserted; + /* * now do a dychotomic search directly inside the jump_table. */ @@ -728,12 +748,11 @@ eina_inlist_sorted_state_insert(Eina_Inlist *list, * Now do a dychotomic search between two entries inside the jump_table */ cur *= state->jump_div; - inf = cur - state->jump_div; - sup = cur + state->jump_div; + inf = cur - state->jump_div - 1; + sup = cur + state->jump_div + 1; if (sup > count - 1) sup = count - 1; - if (inf < 0) - inf = 0; + if (inf < 0) inf = 0; while (inf <= sup) { @@ -761,20 +780,20 @@ eina_inlist_sorted_state_insert(Eina_Inlist *list, break; } - if (cmp < 0) + if (cmp <= 0) { cur++; - head = cur / state->jump_div; - offset = cur % state->jump_div; ct = eina_inlist_append_relative(list, item, ct); - _eina_inlist_sorted_state_insert(state, head, offset); - return ct; } + else + { + ct = eina_inlist_prepend_relative(list, item, ct); + } + head = cur / state->jump_div; offset = cur % state->jump_div; - ct = eina_inlist_prepend_relative(list, item, ct); _eina_inlist_sorted_state_insert(state, head, offset); return ct; } diff --git a/src/tests/eina_test_inlist.c b/src/tests/eina_test_inlist.c index 4100f91..c27f393 100644 --- a/src/tests/eina_test_inlist.c +++ b/src/tests/eina_test_inlist.c @@ -53,6 +53,8 @@ START_TEST(eina_inlist_simple) Eina_Test_Inlist *prev; int i = 0; + fail_if(!eina_init()); + tmp = _eina_test_inlist_build(42); lst = eina_inlist_append(lst, EINA_INLIST_GET(tmp)); fail_if(!lst); @@ -132,6 +134,8 @@ START_TEST(eina_inlist_simple) while (lst) lst = eina_inlist_remove(lst, lst); + + eina_shutdown(); } END_TEST @@ -172,9 +176,11 @@ START_TEST(eina_inlist_sorted) Eina_Inlist *sorted = NULL; int i; + fail_if(!eina_init()); + srand(time(NULL)); - for (i = 0; i < 1000; ++i) + for (i = 0; i < 2000; ++i) { tmp = malloc(sizeof (Eina_Test_Inlist_Sorted)); if (!tmp) continue ; @@ -203,6 +209,39 @@ START_TEST(eina_inlist_sorted) } _eina_test_inlist_check(sorted); + + eina_shutdown(); +} +END_TEST + +START_TEST(eina_inlist_sorted_state) +{ + Eina_Test_Inlist_Sorted *tmp; + Eina_Inlist_Sorted_State *state; + Eina_Inlist *list = NULL; + int i; + + fail_if(!eina_init()); + + state = eina_inlist_sorted_state_new(); + fail_if(!state); + + for (i = 0; i < 2000; ++i) + { + tmp = malloc(sizeof (Eina_Test_Inlist_Sorted)); + if (!tmp) continue ; + + tmp->value = rand(); + + list = eina_inlist_sorted_state_insert(list, EINA_INLIST_GET(tmp), _eina_test_inlist_cmp, state); + _eina_test_inlist_check(list); + } + + _eina_test_inlist_check(list); + + eina_inlist_sorted_state_free(state); + + eina_shutdown(); } END_TEST @@ -211,4 +250,5 @@ eina_test_inlist(TCase *tc) { tcase_add_test(tc, eina_inlist_simple); tcase_add_test(tc, eina_inlist_sorted); + tcase_add_test(tc, eina_inlist_sorted_state); } -- 2.7.4