chngelog ? backport ? Vincent
On Wed, 25 May 2011, Enlightenment SVN wrote: > Log: > eina: fix eina_inlist_sorted_insert and improve its tests. > > > Author: cedric > Date: 2011-05-25 06:18:21 -0700 (Wed, 25 May 2011) > New Revision: 59669 > Trac: http://trac.enlightenment.org/e/changeset/59669 > > Modified: > trunk/eina/src/lib/eina_inlist.c trunk/eina/src/tests/eina_test_inlist.c > > Modified: trunk/eina/src/lib/eina_inlist.c > =================================================================== > --- trunk/eina/src/lib/eina_inlist.c 2011-05-25 12:42:29 UTC (rev 59668) > +++ trunk/eina/src/lib/eina_inlist.c 2011-05-25 13:18:21 UTC (rev 59669) > @@ -454,7 +454,7 @@ > * prepare a jump table to avoid doing unecessary rewalk > * of the inlist as much as possible. > */ > - for (ct = list->next; ct; ct = ct->next, jump_count++, count++) > + for (ct = list; ct; ct = ct->next, jump_count++, count++) > { > if (jump_count == jump_div) > { > @@ -485,6 +485,7 @@ > sup = jump_limit - 1; > cur = 0; > ct = jump_table[cur]; > + cmp = func(ct, item); > > while (inf <= sup) > { > @@ -509,22 +510,23 @@ > > /* If at the beginning of the table and cmp < 0, > * insert just after the head */ > - if (cur == 0 && cmp < 0) > - return eina_inlist_append_relative(list, item, list->next); > + if (cur == 0 && cmp > 0) > + return eina_inlist_prepend_relative(list, item, ct); > > /* If at the end of the table and cmp >= 0, > * just append the item to the list */ > - if (cmp >= 0 && ct == list->last) > + if (cmp < 0 && ct == list->last) > return eina_inlist_append(list, item); > > /* > * Now do a dychotomic search between two entries inside the jump_table > */ > cur *= jump_div; > - inf = cur; > - sup = inf + jump_div; > + inf = cur - jump_div; > + sup = cur + jump_div; > > if (sup > count - 1) sup = count - 1; > + if (inf < 0) inf = 0; > > while (inf <= sup) > { > > Modified: trunk/eina/src/tests/eina_test_inlist.c > =================================================================== > --- trunk/eina/src/tests/eina_test_inlist.c 2011-05-25 12:42:29 UTC (rev > 59668) > +++ trunk/eina/src/tests/eina_test_inlist.c 2011-05-25 13:18:21 UTC (rev > 59669) > @@ -138,69 +138,71 @@ > typedef struct _Eina_Test_Inlist_Sorted Eina_Test_Inlist_Sorted; > struct _Eina_Test_Inlist_Sorted > { > - EINA_INLIST; > + EINA_INLIST; > > - int value; > + int value; > }; > > static int > _eina_test_inlist_cmp(const void *d1, const void *d2) > { > - const Eina_Test_Inlist_Sorted *t1 = d1; > - const Eina_Test_Inlist_Sorted *t2 = d2; > + const Eina_Test_Inlist_Sorted *t1 = d1; > + const Eina_Test_Inlist_Sorted *t2 = d2; > > - return t1->value - t2->value; > + return t1->value - t2->value; > } > > static void > _eina_test_inlist_check(const Eina_Inlist *list) > { > - const Eina_Test_Inlist_Sorted *t; > - int last_value = 0; > + const Eina_Test_Inlist_Sorted *t; > + int last_value = 0; > > - EINA_INLIST_FOREACH(list, t) > - { > - fail_if(t->value < last_value); > - last_value = t->value; > - } > + EINA_INLIST_FOREACH(list, t) > + { > + fail_if(t->value < last_value); > + last_value = t->value; > + } > } > > START_TEST(eina_inlist_sorted) > { > - Eina_Inlist *list = NULL; > - Eina_Inlist *sorted = NULL; > - int i; > + Eina_Test_Inlist_Sorted *tmp; > + Eina_Inlist *list = NULL; > + Eina_Inlist *sorted = NULL; > + int i; > > - srand(time(NULL)); > + srand(time(NULL)); > > - for (i = 0; i < 5000; ++i) > - { > - Eina_Test_Inlist_Sorted *tmp; > + for (i = 0; i < 1000; ++i) > + { > + tmp = malloc(sizeof (Eina_Test_Inlist_Sorted)); > + if (!tmp) continue ; > > - tmp = malloc(sizeof (Eina_Test_Inlist_Sorted)); > - if (!tmp) continue ; > + tmp->value = rand(); > > - tmp->value = rand(); > + list = eina_inlist_prepend(list, EINA_INLIST_GET(tmp)); > + } > > - list = eina_inlist_prepend(list, EINA_INLIST_GET(tmp)); > - } > + list = eina_inlist_sort(list, _eina_test_inlist_cmp); > > - list = eina_inlist_sort(list, _eina_test_inlist_cmp); > + _eina_test_inlist_check(list); > > - _eina_test_inlist_check(list); > + EINA_INLIST_FOREACH(list, tmp) > + tmp->value = rand(); > > - i = 0; > - while (list) > - { > - Eina_Inlist *tmp = list; > + i = 0; > + while (list) > + { > + Eina_Inlist *p = list; > > - list = eina_inlist_remove(list, list); > + list = eina_inlist_remove(list, list); > > - sorted = eina_inlist_sorted_insert(sorted, tmp, _eina_test_inlist_cmp); > - _eina_test_inlist_check(sorted); > - } > + sorted = eina_inlist_sorted_insert(sorted, p, _eina_test_inlist_cmp); > + _eina_test_inlist_check(sorted); > + } > > - _eina_test_inlist_check(sorted); > + _eina_test_inlist_check(sorted); > } > END_TEST > > > > ------------------------------------------------------------------------------ > vRanger cuts backup time in half-while increasing security. > With the market-leading solution for virtual backup and recovery, > you get blazing-fast, flexible, and affordable data protection. > Download your free trial now. > http://p.sf.net/sfu/quest-d2dcopy1 > _______________________________________________ > enlightenment-svn mailing list > [email protected] > https://lists.sourceforge.net/lists/listinfo/enlightenment-svn > > ------------------------------------------------------------------------------ vRanger cuts backup time in half-while increasing security. With the market-leading solution for virtual backup and recovery, you get blazing-fast, flexible, and affordable data protection. Download your free trial now. http://p.sf.net/sfu/quest-d2dcopy1 _______________________________________________ enlightenment-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
