On Mon, 11 Apr 2011 12:05:13 +0200 (CEST) Vincent Torri <vto...@univ-evry.fr> wrote:
> > > 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) > > { > > > > but we are still 10 years from another release... -- Mike Blumenkrantz Zentific: NULL pointer dereferences now 50% off! ------------------------------------------------------------------------------ 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
