you have forgotten to comment typedef struct _Eina_Inlist_Sorted_State Eina_Inlist_Sorted_State;
and do not forget @since Vincent On Mon, 5 Sep 2011, Enlightenment SVN wrote: > Log: > 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)). > > > Author: cedric > Date: 2011-09-05 13:15:12 -0700 (Mon, 05 Sep 2011) > New Revision: 63213 > Trac: http://trac.enlightenment.org/e/changeset/63213 > > Modified: > trunk/eina/ChangeLog trunk/eina/src/include/eina_inlist.h > trunk/eina/src/lib/eina_inlist.c trunk/eina/src/lib/eina_private.h > > Modified: trunk/eina/ChangeLog > =================================================================== > --- trunk/eina/ChangeLog 2011-09-05 20:09:02 UTC (rev 63212) > +++ trunk/eina/ChangeLog 2011-09-05 20:15:12 UTC (rev 63213) > @@ -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. > > Modified: trunk/eina/src/include/eina_inlist.h > =================================================================== > --- trunk/eina/src/include/eina_inlist.h 2011-09-05 20:09:02 UTC (rev > 63212) > +++ trunk/eina/src/include/eina_inlist.h 2011-09-05 20:15:12 UTC (rev > 63213) > @@ -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 @@ > * 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_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. > > Modified: trunk/eina/src/lib/eina_inlist.c > =================================================================== > --- trunk/eina/src/lib/eina_inlist.c 2011-09-05 20:09:02 UTC (rev 63212) > +++ trunk/eina/src/lib/eina_inlist.c 2011-09-05 20:15:12 UTC (rev 63213) > @@ -23,6 +23,8 @@ > #include <stdlib.h> > #include <assert.h> > > +#include <stdio.h> > + > #include "eina_config.h" > #include "eina_private.h" > #include "eina_error.h" > @@ -64,6 +66,16 @@ > 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,22 +434,112 @@ > 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, > Eina_Inlist *item, > 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 @@ > 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 @@ > /* 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 @@ > } > > 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 * > > Modified: trunk/eina/src/lib/eina_private.h > =================================================================== > --- trunk/eina/src/lib/eina_private.h 2011-09-05 20:09:02 UTC (rev 63212) > +++ trunk/eina/src/lib/eina_private.h 2011-09-05 20:15:12 UTC (rev 63213) > @@ -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" > > > ------------------------------------------------------------------------------ > Special Offer -- Download ArcSight Logger for FREE! > Finally, a world-class log management solution at an even better > price-free! And you'll get a free "Love Thy Logs" t-shirt when you > download Logger. Secure your free ArcSight Logger TODAY! > http://p.sf.net/sfu/arcsisghtdev2dev > _______________________________________________ > enlightenment-svn mailing list > enlightenment-...@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/enlightenment-svn > > ------------------------------------------------------------------------------ Special Offer -- Download ArcSight Logger for FREE! Finally, a world-class log management solution at an even better price-free! And you'll get a free "Love Thy Logs" t-shirt when you download Logger. Secure your free ArcSight Logger TODAY! http://p.sf.net/sfu/arcsisghtdev2dev _______________________________________________ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
