From f977f3a88ccb2fe2e3bf158457f3b6f107cdbc3f Mon Sep 17 00:00:00 2001 From: cedric Date: Mon, 5 Sep 2011 20:15:12 +0000 Subject: [PATCH] eina: add eina_inlist_sorted_state_insert and helper. Note: this function help keep a jump table so we reduce the need to walk over the complete list to insert one element. It's of course doesn't make it an O(log(n)) in access time, but it increase it's cost more slowly. With 10000 items, you can count around 50 pointers dereferencing and with with 50000 items around 200 pointers dereferencing. Of course the comparison stay in O(log(n)). git-svn-id: http://svn.enlightenment.org/svn/e/trunk/eina@63213 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33 --- ChangeLog | 4 + src/include/eina_inlist.h | 69 ++++++++++- src/lib/eina_inlist.c | 288 ++++++++++++++++++++++++++++++++++++++++------ src/lib/eina_private.h | 2 + 4 files changed, 327 insertions(+), 36 deletions(-) diff --git a/ChangeLog b/ChangeLog index 53e1b39..c0063a4 100644 --- a/ChangeLog +++ b/ChangeLog @@ -126,3 +126,7 @@ 2011-08-03 Myungjae Lee * Fix eina_share_common_del and eina_share_common_ref to release lock on failure. + +2011-09-05 Cedric Bail + + * Add eina_inlist_sorted_state_insert and helper. diff --git a/src/include/eina_inlist.h b/src/include/eina_inlist.h index b2d7e77..3211801 100644 --- a/src/include/eina_inlist.h +++ b/src/include/eina_inlist.h @@ -396,6 +396,7 @@ * Inlined list type. */ typedef struct _Eina_Inlist Eina_Inlist; +typedef struct _Eina_Inlist_Sorted_State Eina_Inlist_Sorted_State; /** * @struct _Eina_Inlist @@ -645,8 +646,7 @@ EAPI Eina_Accessor *eina_inlist_accessor_new(const Eina_Inlist *in_list) EINA_MA * returned. Otherwise, the old pointer is returned. See eina_error_get(). * * @note O(log2(n)) comparisons (calls to @p func) average/worst case - * performance as it uses eina_list_search_sorted_near_list() and thus - * is bounded to that. As said in eina_list_search_sorted_near_list(), + * performance. As said in eina_list_search_sorted_near_list(), * lists do not have O(1) access time, so walking to the correct node * can be costly, consider worst case to be almost O(n) pointer * dereference (list walk). @@ -654,6 +654,71 @@ EAPI Eina_Accessor *eina_inlist_accessor_new(const Eina_Inlist *in_list) EINA_MA EAPI Eina_Inlist *eina_inlist_sorted_insert(Eina_Inlist *list, Eina_Inlist *item, Eina_Compare_Cb func) EINA_ARG_NONNULL(2, 3) EINA_WARN_UNUSED_RESULT; /** + * @brief Create state with valid data in it. + * + * @return A valid Eina_Inlist_Sorted_State. + * @since 1.1.0 + * + * See eina_inlist_sorted_state_insert() for more information. + */ +EAPI Eina_Inlist_Sorted_State *eina_inlist_sorted_state_new(void); + +/** + * @brief Force an Eina_Inlist_Sorted_State to match the content of a list. + * + * @param state The state to update + * @param list The list to match + * @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); + +/** + * @brief Free an Eina_Inlist_Sorted_State. + * + * @param state The state to destroy + * @since 1.1.0 + * + * See eina_inlist_sorted_state_insert() for more information. + */ +EAPI void eina_inlist_sorted_state_free(Eina_Inlist_Sorted_State *state); + +/** + * @brief Insert a new node into a sorted list. + * + * @param list The given linked list, @b must be sorted. + * @param item list node to insert, must not be NULL. + * @param func The function called for the sort. + * @param state The current array for initial dichotomic search + * @return A list pointer. + * @since 1.1.0 + * + * This function inserts item into a linked list assuming @p state match + * the exact content order of the list. It use @p state to do a fast + * first step dichotomic search before starting to walk the inlist itself. + * This make this code much faster than eina_inlist_sorted_insert() as it + * doesn't need to walk the list at all. The result is of course a sorted + * list with an updated state.. If @p list is @c NULLL, item + * is returned. On success, a new list pointer that should be + * used in place of the one given to this function is + * returned. Otherwise, the old pointer is returned. See eina_error_get(). + * + * @note O(log2(n)) comparisons (calls to @p func) average/worst case + * performance. As said in eina_list_search_sorted_near_list(), + * lists do not have O(1) access time, so walking to the correct node + * can be costly, but this version try to minimize that by making it a + * O(log2(n)) for number small number. After n == 256, it start to add a + * linear cost again. Consider worst case to be almost O(n) pointer + * dereference (list walk). + */ +EAPI Eina_Inlist *eina_inlist_sorted_state_insert(Eina_Inlist *list, + Eina_Inlist *item, + Eina_Compare_Cb func, + Eina_Inlist_Sorted_State *state); +/** * @brief Sort a list according to the ordering func will return. * * @param list The list handle to sort. diff --git a/src/lib/eina_inlist.c b/src/lib/eina_inlist.c index e2dac4a..73aa2e2 100644 --- a/src/lib/eina_inlist.c +++ b/src/lib/eina_inlist.c @@ -23,6 +23,8 @@ #include #include +#include + #include "eina_config.h" #include "eina_private.h" #include "eina_error.h" @@ -64,6 +66,16 @@ struct _Eina_Accessor_Inlist unsigned int index; }; +struct _Eina_Inlist_Sorted_State +{ + Eina_Inlist *jump_table[EINA_INLIST_JUMP_SIZE]; + + unsigned short jump_limit; + int jump_div; + + int inserted; +}; + static Eina_Bool eina_inlist_iterator_next(Eina_Iterator_Inlist *it, void **data) { if (!it->current) @@ -422,7 +434,100 @@ eina_inlist_count(const Eina_Inlist *list) return i; } -#define EINA_INLIST_JUMP_SIZE 256 +EAPI void +eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list) +{ + Eina_Inlist *ct = NULL; + int count = 0; + int jump_count = 1; + + /* + * prepare a jump table to avoid doing unnecessary rewalk + * of the inlist as much as possible. + */ + for (ct = list; ct; ct = ct->next, jump_count++, count++) + { + if (jump_count == state->jump_div) + { + 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]; + } + + state->jump_table[state->jump_limit] = ct; + state->jump_limit++; + jump_count = 0; + } + } +} + +EAPI Eina_Inlist_Sorted_State * +eina_inlist_sorted_state_new(void) +{ + Eina_Inlist_Sorted_State *r; + + r = calloc(1, sizeof (Eina_Inlist_Sorted_State)); + if (!r) return NULL; + + r->jump_div = 1; + + return r; +} + +EAPI void +eina_inlist_sorted_state_free(Eina_Inlist_Sorted_State *state) +{ + free(state); +} + +static void +_eina_inlist_sorted_state_insert(Eina_Inlist_Sorted_State *state, + unsigned short index, + int offset) +{ + Eina_Inlist *last; + int jump_count; + + state->inserted++; + + if (offset != 0) index++; + for (; index < state->jump_limit; index++) + { + 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++; + + if (jump_count == state->jump_div + 1) + { + 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]; + } + state->jump_table[state->jump_limit] = state->jump_table[0]->last; + state->jump_limit++; + } +} EAPI Eina_Inlist * eina_inlist_sorted_insert(Eina_Inlist *list, @@ -430,14 +535,11 @@ eina_inlist_sorted_insert(Eina_Inlist *list, Eina_Compare_Cb func) { Eina_Inlist *ct = NULL; - Eina_Inlist *jump_table[EINA_INLIST_JUMP_SIZE]; + Eina_Inlist_Sorted_State state; int cmp = 0; int inf, sup; int cur = 0; int count = 0; - unsigned short jump_limit = 0; - int jump_div = 1; - int jump_count = 1; if (!list) return eina_inlist_append(NULL, item); @@ -450,47 +552,143 @@ eina_inlist_sorted_insert(Eina_Inlist *list, return eina_inlist_prepend(list, item); } + state.jump_div = 1; + state.jump_limit = 0; + eina_inlist_sorted_state_init(&state, list); + /* - * prepare a jump table to avoid doing unnecessary rewalk - * of the inlist as much as possible. + * now do a dychotomic search directly inside the jump_table. */ - for (ct = list; ct; ct = ct->next, jump_count++, count++) + inf = 0; + sup = state.jump_limit - 1; + cur = 0; + ct = state.jump_table[cur]; + cmp = func(ct, item); + + while (inf <= sup) { - if (jump_count == jump_div) + cur = inf + ((sup - inf) >> 1); + ct = state.jump_table[cur]; + + cmp = func(ct, item); + if (cmp == 0) + break ; + else if (cmp < 0) + inf = cur + 1; + else if (cmp > 0) { - if (jump_limit == EINA_INLIST_JUMP_SIZE) - { - unsigned short i, j; + if (cur > 0) + sup = cur - 1; + else + break; + } + else + break; + } - /* compress the jump table */ - jump_div *= 2; - jump_limit /= 2; + /* If at the beginning of the table and cmp < 0, + * insert just after the head */ + if (cur == 0 && cmp > 0) + return eina_inlist_prepend_relative(list, item, ct); - for (i = 2, j = 1; - i < EINA_INLIST_JUMP_SIZE; - i += 2, j++) - jump_table[j] = jump_table[i]; - } + /* If at the end of the table and cmp >= 0, + * just append the item to the list */ + if (cmp < 0 && ct == list->last) + return eina_inlist_append(list, item); - jump_table[jump_limit] = ct; - jump_limit++; - jump_count = 0; + /* + * 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; + + if (sup > count - 1) sup = count - 1; + if (inf < 0) inf = 0; + + while (inf <= sup) + { + int tmp = cur; + + cur = inf + ((sup - inf) >> 1); + if (tmp < cur) + for (; tmp != cur; tmp++, ct = ct->next); + else if (tmp > cur) + for (; tmp != cur; tmp--, ct = ct->prev); + + cmp = func(ct, item); + if (cmp == 0) + break ; + else if (cmp < 0) + inf = cur + 1; + else if (cmp > 0) + { + if (cur > 0) + sup = cur - 1; + else + break; } + else + break; + } + + if (cmp < 0) + return eina_inlist_append_relative(list, item, ct); + return eina_inlist_prepend_relative(list, item, ct); +} + +EAPI Eina_Inlist * +eina_inlist_sorted_state_insert(Eina_Inlist *list, + Eina_Inlist *item, + Eina_Compare_Cb func, + Eina_Inlist_Sorted_State *state) +{ + Eina_Inlist *ct = NULL; + int cmp = 0; + int inf, sup; + int cur = 0; + int count = 0; + unsigned short head; + unsigned int offset; + + if (!list) + { + state->inserted = 1; + state->jump_limit = 1; + state->jump_table[0] = item; + return eina_inlist_append(NULL, item); + } + + if (!list->next) + { + cmp = func(list, item); + + state->jump_limit = 2; + state->inserted = 2; + + if (cmp < 0) + { + state->jump_table[1] = item; + return eina_inlist_append(list, item); + } + state->jump_table[1] = state->jump_table[0]; + state->jump_table[0] = item; + return eina_inlist_prepend(list, item); } /* * now do a dychotomic search directly inside the jump_table. */ inf = 0; - sup = jump_limit - 1; + sup = state->jump_limit - 1; cur = 0; - ct = jump_table[cur]; + ct = state->jump_table[cur]; cmp = func(ct, item); while (inf <= sup) { cur = inf + ((sup - inf) >> 1); - ct = jump_table[cur]; + ct = state->jump_table[cur]; cmp = func(ct, item); if (cmp == 0) @@ -511,22 +709,31 @@ eina_inlist_sorted_insert(Eina_Inlist *list, /* If at the beginning of the table and cmp < 0, * insert just after the head */ if (cur == 0 && cmp > 0) - return eina_inlist_prepend_relative(list, item, ct); + { + ct = eina_inlist_prepend_relative(list, item, ct); + _eina_inlist_sorted_state_insert(state, 0, 0); + return ct; + } /* If at the end of the table and cmp >= 0, * just append the item to the list */ if (cmp < 0 && ct == list->last) - return eina_inlist_append(list, item); + { + ct = eina_inlist_append(list, item); + _eina_inlist_sorted_state_insert(state, state->jump_limit - 1, 1); + return ct; + } /* * Now do a dychotomic search between two entries inside the jump_table */ - cur *= jump_div; - inf = cur - jump_div; - sup = cur + jump_div; + cur *= state->jump_div; + inf = cur - state->jump_div; + sup = cur + state->jump_div; if (sup > count - 1) sup = count - 1; - if (inf < 0) inf = 0; + if (inf < 0) + inf = 0; while (inf <= sup) { @@ -555,8 +762,21 @@ eina_inlist_sorted_insert(Eina_Inlist *list, } if (cmp < 0) - return eina_inlist_append_relative(list, item, ct); - return eina_inlist_prepend_relative(list, item, ct); + { + 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; + } + 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; } EAPI Eina_Inlist * diff --git a/src/lib/eina_private.h b/src/lib/eina_private.h index 936060e..78a1b7d 100644 --- a/src/lib/eina_private.h +++ b/src/lib/eina_private.h @@ -48,6 +48,8 @@ max) (((x) > (max)) ? (max) : (((x) < (min)) ? (min) : (x))) #endif +#define EINA_INLIST_JUMP_SIZE 256 + #define READBUFSIZ 65536 #define EINA_LOG_COLOR_DEFAULT "\033[36m" -- 2.7.4