From c4706bb744181cbf9b608ddf241f008f0be76864 Mon Sep 17 00:00:00 2001
From: cedric <cedric@7cbeb6ba-43b4-40fd-8cce-4c39aea84d33>
Date: Wed, 25 May 2011 13:18:21 +0000
Subject: [PATCH] eina: fix eina_inlist_sorted_insert and improve its tests.

git-svn-id: svn+ssh://svn.enlightenment.org/var/svn/e/trunk/eina@59669 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33
---
 src/lib/eina_inlist.c        | 14 +++++----
 src/tests/eina_test_inlist.c | 74 +++++++++++++++++++++++---------------------
 2 files changed, 46 insertions(+), 42 deletions(-)

diff --git a/src/lib/eina_inlist.c b/src/lib/eina_inlist.c
index bf30de9..d7d5a91 100644
--- a/src/lib/eina_inlist.c
+++ b/src/lib/eina_inlist.c
@@ -454,7 +454,7 @@ eina_inlist_sorted_insert(Eina_Inlist *list,
     * 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 @@ eina_inlist_sorted_insert(Eina_Inlist *list,
    sup = jump_limit - 1;
    cur = 0;
    ct = jump_table[cur];
+   cmp = func(ct, item);
 
    while (inf <= sup)
      {
@@ -509,22 +510,23 @@ 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_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)
      {
diff --git a/src/tests/eina_test_inlist.c b/src/tests/eina_test_inlist.c
index 5c7166c..4100f91 100644
--- a/src/tests/eina_test_inlist.c
+++ b/src/tests/eina_test_inlist.c
@@ -138,69 +138,71 @@ END_TEST
 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;
-
-  EINA_INLIST_FOREACH(list, t)
-    {
-      fail_if(t->value < last_value);
-      last_value = t->value;
-    }
+   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;
+     }
 }
 
 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
 
-- 
2.7.4