maybe it's time to update the NEWS file, with something like
Eina 1.1 New features: **** **** API additions: **** **** Vincent On Mon, 11 Apr 2011, Enlightenment SVN wrote: > Log: > eina: add eina_inlist_sort (merge sort based on eina_list code). > > > Author: cedric > Date: 2011-04-11 02:55:27 -0700 (Mon, 11 Apr 2011) > New Revision: 58540 > Trac: http://trac.enlightenment.org/e/changeset/58540 > > Modified: > trunk/eina/ChangeLog trunk/eina/src/include/eina_inlist.h > trunk/eina/src/lib/eina_inlist.c > > Modified: trunk/eina/ChangeLog > =================================================================== > --- trunk/eina/ChangeLog 2011-04-11 09:38:24 UTC (rev 58539) > +++ trunk/eina/ChangeLog 2011-04-11 09:55:27 UTC (rev 58540) > @@ -41,3 +41,7 @@ > 2011-04-06 Gustavo Sverzut Barbieri > > * Add Simple XML parser API. > + > +2011-05-11 Cedric Bail > + > + * Add eina_inlist_sort. > > Modified: trunk/eina/src/include/eina_inlist.h > =================================================================== > --- trunk/eina/src/include/eina_inlist.h 2011-04-11 09:38:24 UTC (rev > 58539) > +++ trunk/eina/src/include/eina_inlist.h 2011-04-11 09:55:27 UTC (rev > 58540) > @@ -361,6 +361,53 @@ > */ > EAPI Eina_Accessor *eina_inlist_accessor_new(const Eina_Inlist *in_list) > EINA_MALLOC EINA_WARN_UNUSED_RESULT; > > +/** > + * @brief Sort a list according to the ordering func will return. > + * > + * @param list The list handle to sort. > + * @param func A function pointer that can handle comparing the list data > + * nodes. > + * @return the new head of list. > + * > + * This function sorts all the elements of @p list. @p func is used to > + * compare two elements of @p list. If @p list or @p func are @c NULL, > + * this function returns @c NULL. > + * > + * @note @b in-place: this will change the given list, so you should > + * now point to the new list head that is returned by this function. > + * > + * @note worst case is O(n * log2(n)) comparisons (calls to func()), > + * O(n) comparisons average case. That means that for 1,000,000 list > + * elements, sort will usually do 1,000,000 comparisons, but may do up > + * to 20,000,000. > + * > + * Example: > + * @code > + * typedef struct _Sort_Ex Sort_Ex; > + * struct _Sort_Ex > + * { > + * INLIST; > + * const char *text; > + * }; > + * > + * int > + * sort_cb(const Inlist *l1, const Inlist *l2) > + * { > + * const Sort_Ex *x1; > + * const Sort_Ex *x2; > + * > + * x1 = EINA_INLIST_CONTAINER_GET(l1, Sort_Ex); > + * x2 = EINA_INLIST_CONTAINER_GET(l2, Sort_Ex); > + * > + * return(strcmp(x1->text, x2->text)); > + * } > + * extern Eina_Inlist *list; > + * > + * list = eina_inlist_sort(list, sort_cb); > + * @endcode > + */ > +EAPI Eina_Inlist *eina_inlist_sort(Eina_Inlist *head, Eina_Compare_Cb func); > + > /* This two macros are helpers for the _FOREACH ones, don't use them */ > #define _EINA_INLIST_OFFSET(ref) ((char *)&(ref)->__in_list - (char > *)(ref)) > #define _EINA_INLIST_CONTAINER(ref, ptr) (void *)((char *)(ptr) - \ > > Modified: trunk/eina/src/lib/eina_inlist.c > =================================================================== > --- trunk/eina/src/lib/eina_inlist.c 2011-04-11 09:38:24 UTC (rev 58539) > +++ trunk/eina/src/lib/eina_inlist.c 2011-04-11 09:55:27 UTC (rev 58540) > @@ -42,6 +42,8 @@ > * @cond LOCAL > */ > > +#define EINA_INLIST_SORT_STACK_SIZE 32 > + > typedef struct _Eina_Iterator_Inlist Eina_Iterator_Inlist; > typedef struct _Eina_Accessor_Inlist Eina_Accessor_Inlist; > > @@ -141,6 +143,41 @@ > free(it); > } > > +static Eina_Inlist * > +eina_inlist_sort_merge(Eina_Inlist *a, Eina_Inlist *b, Eina_Compare_Cb func) > +{ > + Eina_Inlist *first, *last; > + > + if (func(a, b) < 0) > + a = (last = first = a)->next; > + else > + b = (last = first = b)->next; > + > + while (a && b) > + if (func(a, b) < 0) > + a = (last = last->next = a)->next; > + else > + b = (last = last->next = b)->next; > + > + last->next = a ? a : b; > + > + return first; > +} > + > +static Eina_Inlist * > +eina_inlist_sort_rebuild_prev(Eina_Inlist *list) > +{ > + Eina_Inlist *prev = NULL; > + > + for (; list; list = list->next) > + { > + list->prev = prev; > + prev = list; > + } > + > + return prev; > +} > + > /** > * @endcond > */ > @@ -385,6 +422,61 @@ > return i; > } > > +EAPI Eina_Inlist * > +eina_inlist_sort(Eina_Inlist *head, Eina_Compare_Cb func) > +{ > + unsigned int i = 0; > + unsigned int n = 0; > + Eina_Inlist *tail = head; > + Eina_Inlist *unsort = NULL; > + Eina_Inlist *stack[EINA_INLIST_SORT_STACK_SIZE]; > + > + EINA_SAFETY_ON_NULL_RETURN_VAL(head, NULL); > + EINA_SAFETY_ON_NULL_RETURN_VAL(func, head); > + > + while (tail) > + { > + unsigned int idx, tmp; > + > + Eina_Inlist *a = tail; > + Eina_Inlist *b = tail->next; > + > + if (!b) > + { > + stack[i++] = a; > + break; > + } > + > + tail = b->next; > + > + if (func(a, b) < 0) > + ((stack[i++] = a)->next = b)->next = 0; > + else > + ((stack[i++] = b)->next = a)->next = 0; > + > + tmp = n++; > + for (idx = n ^ tmp; idx &= idx - 1; i--) > + stack[i - 2] = eina_inlist_sort_merge(stack[i - 2], stack[i - 1], func); > + } > + > + while (i-- > 1) > + stack[i - 1] = eina_inlist_sort_merge(stack[i - 1], stack[i], func); > + > + head = stack[0]; > + tail = eina_inlist_sort_rebuild_prev(head); > + > + if (unsort) > + { > + tail->next = unsort; > + unsort->prev = tail; > + } > + > + head->last = tail; > + > + return head; > + > +} > + > EAPI Eina_Iterator * > eina_inlist_iterator_new(const Eina_Inlist *list) > { > > > ------------------------------------------------------------------------------ > Xperia(TM) PLAY > It's a major breakthrough. An authentic gaming > smartphone on the nation's most reliable network. > And it wants your games. > http://p.sf.net/sfu/verizon-sfdev > _______________________________________________ > enlightenment-svn mailing list > enlightenment-...@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/enlightenment-svn > > ------------------------------------------------------------------------------ Xperia(TM) PLAY It's a major breakthrough. An authentic gaming smartphone on the nation's most reliable network. And it wants your games. http://p.sf.net/sfu/verizon-sfdev _______________________________________________ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
