wmem_list: add wmem_list_insert_sorted.

This mimics the function g_list_insert_sorted.

Change-Id: I6f7ac01155588006662c8c0c138d88cea753868c
Reviewed-on: https://code.wireshark.org/review/19978
Reviewed-by: Dario Lombardo <lomato@gmail.com>

3 files changed, 115 insertions, 0 deletions

diff --git a/epan/wmem/wmem_list.c b/epan/wmem/wmem_list.c
index d494b6ff1d..c1e9fa1dad 100644
--- a/epan/wmem/wmem_list.c
+++ b/epan/wmem/wmem_list.c
@@ -183,6 +183,52 @@ wmem_list_append(wmem_list_t *list, void *data)
     list->count++;
 }
 
+void
+wmem_list_insert_sorted(wmem_list_t *list, void* data, GCompareFunc func)
+{
+    wmem_list_frame_t *new_frame;
+    wmem_list_frame_t *cur;
+    wmem_list_frame_t *prev;
+
+    new_frame = wmem_new(list->allocator, wmem_list_frame_t);
+    new_frame->data = data;
+    new_frame->next = NULL;
+    new_frame->prev = NULL;
+
+    if (!list->head) {
+        list->head = new_frame;
+        list->tail = new_frame;
+        return;
+    }
+
+    cur = list->head;
+    prev = list->head;
+
+    if (func(cur->data, data) >= 0) {
+        cur->prev = new_frame;
+        new_frame->next = cur;
+        list->head = new_frame;
+        return;
+    }
+
+    do {
+        prev = cur;
+        cur = cur->next;
+    } while (cur && func(cur->data, data) <= 0);
+
+    if (!cur) {
+        prev->next = new_frame;
+        new_frame->prev = prev;
+        list->tail = new_frame;
+        return;
+    }
+
+    new_frame->prev = prev;
+    new_frame->next = cur;
+    new_frame->prev->next = new_frame;
+    new_frame->next->prev = new_frame;
+}
+
 wmem_list_t *
 wmem_list_new(wmem_allocator_t *allocator)
 {
@@ -226,6 +272,7 @@ wmem_list_foreach(wmem_list_t *list, GFunc foreach_func, gpointer user_data)
         cur = cur->next;
     }
 }
+
 /*
  * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
  *
diff --git a/epan/wmem/wmem_list.h b/epan/wmem/wmem_list.h
index 5b510c2977..0f6034ef56 100644
--- a/epan/wmem/wmem_list.h
+++ b/epan/wmem/wmem_list.h
@@ -100,6 +100,11 @@ void
 wmem_list_append(wmem_list_t *list, void *data);
 
 WS_DLL_PUBLIC
+void
+wmem_list_insert_sorted(wmem_list_t *list, void* data, GCompareFunc func);
+
+
+WS_DLL_PUBLIC
 wmem_list_t *
 wmem_list_new(wmem_allocator_t *allocator)
 G_GNUC_MALLOC;
diff --git a/epan/wmem/wmem_test.c b/epan/wmem/wmem_test.c
index 96338946c5..fb46a83501 100644
--- a/epan/wmem/wmem_test.c
+++ b/epan/wmem/wmem_test.c
@@ -711,6 +711,18 @@ check_val_list(gpointer val, gpointer val_to_check)
     g_assert(val == val_to_check);
 }
 
+static gint
+int_compare(gconstpointer a, gconstpointer b)
+{
+    return GPOINTER_TO_INT(a) - GPOINTER_TO_INT(b);
+}
+
+static gint
+str_compare(gconstpointer a, gconstpointer b)
+{
+    return strcmp((const char*)a, (const char*)b);
+}
+
 static void
 wmem_test_list(void)
 {
@@ -718,6 +730,10 @@ wmem_test_list(void)
     wmem_list_t       *list;
     wmem_list_frame_t *frame;
     unsigned int       i;
+    int                int1;
+    int                int2;
+    char*              str1;
+    char*              str2;
 
     allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
 
@@ -805,6 +821,53 @@ wmem_test_list(void)
     }
     wmem_list_foreach(list, check_val_list, GINT_TO_POINTER(1));
     wmem_destroy_list(list);
+
+    list = wmem_list_new(NULL);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(5), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(8), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(1), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(2), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(9), int_compare);
+    frame = wmem_list_head(list);
+    int1 = GPOINTER_TO_INT(wmem_list_frame_data(frame));
+    while ((frame = wmem_list_frame_next(frame))) {
+        int2 = GPOINTER_TO_INT(wmem_list_frame_data(frame));
+        g_assert(int1 <= int2);
+        int1 = int2;
+    }
+    wmem_destroy_list(list);
+
+    list = wmem_list_new(NULL);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(5), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(1), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(7), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(3), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(2), int_compare);
+    wmem_list_insert_sorted(list, GINT_TO_POINTER(2), int_compare);
+    frame = wmem_list_head(list);
+    int1 = GPOINTER_TO_INT(wmem_list_frame_data(frame));
+    while ((frame = wmem_list_frame_next(frame))) {
+        int2 = GPOINTER_TO_INT(wmem_list_frame_data(frame));
+        g_assert(int1 <= int2);
+        int1 = int2;
+    }
+    wmem_destroy_list(list);
+
+    list = wmem_list_new(NULL);
+    wmem_list_insert_sorted(list, "abc", str_compare);
+    wmem_list_insert_sorted(list, "bcd", str_compare);
+    wmem_list_insert_sorted(list, "aaa", str_compare);
+    wmem_list_insert_sorted(list, "bbb", str_compare);
+    wmem_list_insert_sorted(list, "zzz", str_compare);
+    wmem_list_insert_sorted(list, "ggg", str_compare);
+    frame = wmem_list_head(list);
+    str1 = (char*)wmem_list_frame_data(frame);
+    while ((frame = wmem_list_frame_next(frame))) {
+        str2 = (char*)wmem_list_frame_data(frame);
+        g_assert(strcmp(str1, str2) <= 0);
+        str1 = str2;
+    }
+    wmem_destroy_list(list);
 }
 
 void