Replace wmem slist (singly-linked) with wmem list (doubly-linked).

The overhead is not large, and it makes append much faster (O(1) vs O(n)).

It also will make a queue easy to add, which I need for a dissector I'm
writing...

svn path=/trunk/; revision=50744

8 files changed, 271 insertions, 232 deletions

diff --git a/epan/wmem/Makefile.common b/epan/wmem/Makefile.common
index f212ccd6a6..c86398aaf6 100644
--- a/epan/wmem/Makefile.common
+++ b/epan/wmem/Makefile.common
@@ -29,9 +29,9 @@ LIBWMEM_SRC =				\
 	wmem_allocator_block.c		\
 	wmem_allocator_simple.c		\
 	wmem_allocator_strict.c		\
+	wmem_list.c			\
 	wmem_miscutl.c			\
 	wmem_scopes.c			\
-	wmem_slist.c			\
 	wmem_stack.c			\
 	wmem_strbuf.c			\
 	wmem_strutl.c			\
@@ -46,9 +46,9 @@ LIBWMEM_INCLUDES =			\
 	wmem_allocator_block.h		\
 	wmem_allocator_simple.h		\
 	wmem_allocator_strict.h		\
+	wmem_list.h			\
 	wmem_miscutl.h			\
 	wmem_scopes.h			\
-	wmem_slist.h			\
 	wmem_stack.h			\
 	wmem_strbuf.h			\
 	wmem_strutl.h			\
diff --git a/epan/wmem/wmem.h b/epan/wmem/wmem.h
index 36a670cfc7..b1c3e37079 100644
--- a/epan/wmem/wmem.h
+++ b/epan/wmem/wmem.h
@@ -28,9 +28,9 @@
 
 #include "wmem_array.h"
 #include "wmem_core.h"
+#include "wmem_list.h"
 #include "wmem_miscutl.h"
 #include "wmem_scopes.h"
-#include "wmem_slist.h"
 #include "wmem_stack.h"
 #include "wmem_strbuf.h"
 #include "wmem_strutl.h"
diff --git a/epan/wmem/wmem_list.c b/epan/wmem/wmem_list.c
new file mode 100644
index 0000000000..f22b817889
--- /dev/null
+++ b/epan/wmem/wmem_list.c
@@ -0,0 +1,181 @@
+/* wmem_list.c
+ * Wireshark Memory Manager Doubly-Linked List
+ * Copyright 2012, Evan Huus <eapache@gmail.com>
+ *
+ * $Id$
+ *
+ * Wireshark - Network traffic analyzer
+ * By Gerald Combs <gerald@wireshark.org>
+ * Copyright 1998 Gerald Combs
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <string.h>
+#include <glib.h>
+
+#include "wmem_core.h"
+#include "wmem_list.h"
+
+struct _wmem_list_frame_t {
+    struct _wmem_list_frame_t *next, *prev;
+    void *data;
+};
+
+struct _wmem_list_t {
+    guint count;
+    wmem_list_frame_t  *head, *tail;
+    wmem_allocator_t   *allocator;
+};
+
+guint
+wmem_list_count(const wmem_list_t *list)
+{
+    return list->count;
+}
+
+wmem_list_frame_t *
+wmem_list_head(const wmem_list_t *list)
+{
+    return list->head;
+}
+
+wmem_list_frame_t *
+wmem_list_tail(const wmem_list_t *list)
+{
+    return list->tail;
+}
+
+wmem_list_frame_t *
+wmem_list_frame_next(const wmem_list_frame_t *frame)
+{
+    return frame->next;
+}
+
+wmem_list_frame_t *
+wmem_list_frame_prev(const wmem_list_frame_t *frame)
+{
+    return frame->prev;
+}
+
+void *
+wmem_list_frame_data(const wmem_list_frame_t *frame)
+{
+    return frame->data;
+}
+
+void
+wmem_list_remove(wmem_list_t *list, void *data)
+{
+    wmem_list_frame_t *frame;
+
+    frame = list->head;
+
+    while (frame && frame->data != data) {
+        frame = frame->next;
+    }
+
+    if (frame == NULL) {
+        return;
+    }
+
+    if (frame->prev) {
+        frame->prev->next = frame->next;
+    }
+    else {
+        list->head = frame->next;
+    }
+
+    if (frame->next) {
+        frame->next->prev = frame->prev;
+    }
+    else {
+        list->tail = frame->prev;
+    }
+
+    list->count--;
+    wmem_free(list->allocator, frame);
+}
+
+void
+wmem_list_prepend(wmem_list_t *list, void *data)
+{
+    wmem_list_frame_t *new_frame;
+
+    new_frame = wmem_new(list->allocator, wmem_list_frame_t);
+
+    new_frame->data = data;
+    new_frame->next = list->head;
+    new_frame->prev = NULL;
+
+    if (list->head) {
+        list->head->prev = new_frame;
+    }
+    else {
+        list->tail = new_frame;
+    }
+
+    list->head = new_frame;
+    list->count++;
+}
+
+void
+wmem_list_append(wmem_list_t *list, void *data)
+{
+    wmem_list_frame_t *new_frame;
+
+    new_frame = wmem_new(list->allocator, wmem_list_frame_t);
+    new_frame->data = data;
+    new_frame->next = NULL;
+    new_frame->prev = list->tail;
+
+    if (list->tail) {
+        list->tail->next = new_frame;
+    }
+    else {
+        list->head = new_frame;
+    }
+
+    list->tail = new_frame;
+    list->count++;
+}
+
+wmem_list_t *
+wmem_list_new(wmem_allocator_t *allocator)
+{
+    wmem_list_t *list;
+
+    list =  wmem_new(allocator, wmem_list_t);
+
+    list->count     = 0;
+    list->head      = NULL;
+    list->tail      = NULL;
+    list->allocator = allocator;
+
+    return list;
+}
+
+/*
+ * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
+ *
+ * Local variables:
+ * c-basic-offset: 4
+ * tab-width: 8
+ * indent-tabs-mode: nil
+ * End:
+ *
+ * vi: set shiftwidth=4 tabstop=8 expandtab:
+ * :indentSize=4:tabSize=8:noTabs=true:
+ */
diff --git a/epan/wmem/wmem_slist.h b/epan/wmem/wmem_list.h
index cd06e64d08..cb4cecf2f2 100644
--- a/epan/wmem/wmem_slist.h
+++ b/epan/wmem/wmem_list.h
@@ -1,5 +1,5 @@
-/* wmem_slist.h
- * Definitions for the Wireshark Memory Manager Singly-Linked List
+/* wmem_list.h
+ * Definitions for the Wireshark Memory Manager Doubly-Linked List
  * Copyright 2012, Evan Huus <eapache@gmail.com>
  *
  * $Id$
@@ -23,8 +23,8 @@
  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  */
 
-#ifndef __WMEM_SLIST_H__
-#define __WMEM_SLIST_H__
+#ifndef __WMEM_LIST_H__
+#define __WMEM_LIST_H__
 
 #include <string.h>
 #include <glib.h>
@@ -37,50 +37,58 @@ extern "C" {
 
 /** @addtogroup wmem
  *  @{
- *    @defgroup wmem-slist Singly-Linked List
+ *    @defgroup wmem-list Doubly-Linked List
  *
- *    A singly-linked list implementation on top of wmem.
+ *    A doubly-linked list implementation on top of wmem.
  *
  *    @{
  */
 
-struct _wmem_slist_t;
-struct _wmem_slist_frame_t;
+struct _wmem_list_t;
+struct _wmem_list_frame_t;
 
-typedef struct _wmem_slist_t       wmem_slist_t;
-typedef struct _wmem_slist_frame_t wmem_slist_frame_t;
+typedef struct _wmem_list_t       wmem_list_t;
+typedef struct _wmem_list_frame_t wmem_list_frame_t;
 
 WS_DLL_PUBLIC
 guint
-wmem_slist_count(const wmem_slist_t *slist);
+wmem_list_count(const wmem_list_t *list);
 
 WS_DLL_PUBLIC
-wmem_slist_frame_t *
-wmem_slist_front(const wmem_slist_t *slist);
+wmem_list_frame_t *
+wmem_list_head(const wmem_list_t *list);
 
 WS_DLL_PUBLIC
-wmem_slist_frame_t *
-wmem_slist_frame_next(const wmem_slist_frame_t *frame);
+wmem_list_frame_t *
+wmem_list_tail(const wmem_list_t *list);
+
+WS_DLL_PUBLIC
+wmem_list_frame_t *
+wmem_list_frame_next(const wmem_list_frame_t *frame);
+
+WS_DLL_PUBLIC
+wmem_list_frame_t *
+wmem_list_frame_prev(const wmem_list_frame_t *frame);
 
 WS_DLL_PUBLIC
 void *
-wmem_slist_frame_data(const wmem_slist_frame_t *frame);
+wmem_list_frame_data(const wmem_list_frame_t *frame);
 
 WS_DLL_PUBLIC
 void
-wmem_slist_remove(wmem_slist_t *slist, void *data);
+wmem_list_remove(wmem_list_t *list, void *data);
 
 WS_DLL_PUBLIC
 void
-wmem_slist_prepend(wmem_slist_t *slist, void *data);
+wmem_list_prepend(wmem_list_t *list, void *data);
 
 WS_DLL_PUBLIC
 void
-wmem_slist_append(wmem_slist_t *slist, void *data);
+wmem_list_append(wmem_list_t *list, void *data);
 
 WS_DLL_PUBLIC
-wmem_slist_t *
-wmem_slist_new(wmem_allocator_t *allocator)
+wmem_list_t *
+wmem_list_new(wmem_allocator_t *allocator)
 G_GNUC_MALLOC;
 
 /**   @}
@@ -90,7 +98,7 @@ G_GNUC_MALLOC;
 }
 #endif /* __cplusplus */
 
-#endif /* __WMEM_SLIST_H__ */
+#endif /* __WMEM_LIST_H__ */
 
 /*
  * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
diff --git a/epan/wmem/wmem_slist.c b/epan/wmem/wmem_slist.c
deleted file mode 100644
index 4e9354f1c9..0000000000
--- a/epan/wmem/wmem_slist.c
+++ /dev/null
@@ -1,167 +0,0 @@
-/* wmem_slist.c
- * Wireshark Memory Manager Singly-Linked List
- * Copyright 2012, Evan Huus <eapache@gmail.com>
- *
- * $Id$
- *
- * Wireshark - Network traffic analyzer
- * By Gerald Combs <gerald@wireshark.org>
- * Copyright 1998 Gerald Combs
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write to the Free Software Foundation, Inc.,
- * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
- */
-
-#include <string.h>
-#include <glib.h>
-
-#include "wmem_core.h"
-#include "wmem_slist.h"
-
-struct _wmem_slist_frame_t {
-    struct _wmem_slist_frame_t *next;
-    void *data;
-};
-
-struct _wmem_slist_t {
-    guint count;
-    wmem_slist_frame_t *front;
-    wmem_allocator_t   *allocator;
-};
-
-guint
-wmem_slist_count(const wmem_slist_t *slist)
-{
-    return slist->count;
-}
-
-wmem_slist_frame_t *
-wmem_slist_front(const wmem_slist_t *slist)
-{
-    return slist->front;
-}
-
-wmem_slist_frame_t *
-wmem_slist_frame_next(const wmem_slist_frame_t *frame)
-{
-    return frame->next;
-}
-
-void *
-wmem_slist_frame_data(const wmem_slist_frame_t *frame)
-{
-    return frame->data;
-}
-
-static wmem_slist_frame_t **
-wmem_slist_tail(wmem_slist_t *slist)
-{
-    wmem_slist_frame_t **cur;
-
-    cur = &(slist->front);
-
-    while (*cur) {
-        cur = &((*cur)->next);
-    }
-
-    return cur;
-}
-
-static wmem_slist_frame_t **
-wmem_slist_find(wmem_slist_t *slist, void *data)
-{
-    wmem_slist_frame_t **cur;
-
-    cur = &(slist->front);
-
-    while (*cur && (*cur)->data != data) {
-        cur = &((*cur)->next);
-    }
-
-    return cur;
-}
-
-void
-wmem_slist_remove(wmem_slist_t *slist, void *data)
-{
-    wmem_slist_frame_t *frame;
-    wmem_slist_frame_t **link;
-
-    link = wmem_slist_find(slist, data);
-    frame = *link;
-
-    if (frame == NULL) {
-        return;
-    }
-
-    *link = frame->next;
-    slist->count--;
-    wmem_free(slist->allocator, frame);
-}
-
-void
-wmem_slist_prepend(wmem_slist_t *slist, void *data)
-{
-    wmem_slist_frame_t *new_frame;
-
-    new_frame = wmem_new(slist->allocator, wmem_slist_frame_t);
-
-    new_frame->data = data;
-    new_frame->next = slist->front;
-
-    slist->front = new_frame;
-    slist->count++;
-}
-
-void
-wmem_slist_append(wmem_slist_t *slist, void *data)
-{
-    wmem_slist_frame_t *new_frame, **tail;
-
-    tail = wmem_slist_tail(slist);
-
-    new_frame = wmem_new(slist->allocator, wmem_slist_frame_t);
-    new_frame->data = data;
-    new_frame->next = NULL;
-
-    *tail = new_frame;
-    slist->count++;
-}
-
-wmem_slist_t *
-wmem_slist_new(wmem_allocator_t *allocator)
-{
-    wmem_slist_t *slist;
-
-    slist =  wmem_new(allocator, wmem_slist_t);
-
-    slist->count     = 0;
-    slist->front     = NULL;
-    slist->allocator = allocator;
-
-    return slist;
-}
-
-/*
- * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
- *
- * Local variables:
- * c-basic-offset: 4
- * tab-width: 8
- * indent-tabs-mode: nil
- * End:
- *
- * vi: set shiftwidth=4 tabstop=8 expandtab:
- * :indentSize=4:tabSize=8:noTabs=true:
- */
diff --git a/epan/wmem/wmem_stack.c b/epan/wmem/wmem_stack.c
index 4fd1d0c3f7..cf124a2930 100644
--- a/epan/wmem/wmem_stack.c
+++ b/epan/wmem/wmem_stack.c
@@ -28,20 +28,20 @@
 
 #include "wmem_core.h"
 #include "wmem_stack.h"
-#include "wmem_slist.h"
+#include "wmem_list.h"
 
-/* Wmem stack is implemented as a simple wrapper over Wmem slist */
+/* Wmem stack is implemented as a simple wrapper over Wmem list */
 
 void *
 wmem_stack_peek(const wmem_stack_t *stack)
 {
-    wmem_slist_frame_t *frame;
+    wmem_list_frame_t *frame;
 
-    frame = wmem_slist_front(stack);
+    frame = wmem_list_head(stack);
 
     g_assert(frame);
 
-    return wmem_slist_frame_data(frame);
+    return wmem_list_frame_data(frame);
 }
 
 void *
@@ -51,7 +51,7 @@ wmem_stack_pop(wmem_stack_t *stack)
 
     data = wmem_stack_peek(stack);
 
-    wmem_slist_remove(stack, data);
+    wmem_list_remove(stack, data);
 
     return data;
 }
@@ -59,7 +59,7 @@ wmem_stack_pop(wmem_stack_t *stack)
 void
 wmem_stack_push(wmem_stack_t *stack, void *data)
 {
-    wmem_slist_prepend(stack, data);
+    wmem_list_prepend(stack, data);
 }
 
 /*
diff --git a/epan/wmem/wmem_stack.h b/epan/wmem/wmem_stack.h
index a85c47a3a5..569ae9455a 100644
--- a/epan/wmem/wmem_stack.h
+++ b/epan/wmem/wmem_stack.h
@@ -30,7 +30,7 @@
 #include <glib.h>
 
 #include "wmem_core.h"
-#include "wmem_slist.h"
+#include "wmem_list.h"
 
 #ifdef __cplusplus
 extern "C" {
@@ -45,10 +45,10 @@ extern "C" {
  *    @{
  */
 
-/* Wmem stack is implemented as a simple wrapper over Wmem slist */
-typedef wmem_slist_t wmem_stack_t;
+/* Wmem stack is implemented as a simple wrapper over Wmem list */
+typedef wmem_list_t wmem_stack_t;
 
-#define wmem_stack_count(X) wmem_slist_count(X)
+#define wmem_stack_count(X) wmem_list_count(X)
 
 WS_DLL_PUBLIC
 void *
@@ -62,7 +62,7 @@ WS_DLL_PUBLIC
 void
 wmem_stack_push(wmem_stack_t *stack, void *data);
 
-#define wmem_stack_new(ALLOCATOR) wmem_slist_new(ALLOCATOR)
+#define wmem_stack_new(ALLOCATOR) wmem_list_new(ALLOCATOR)
 
 /**   @}
  *  @} */
diff --git a/epan/wmem/wmem_test.c b/epan/wmem/wmem_test.c
index 06a7769d7e..42abba0d37 100644
--- a/epan/wmem/wmem_test.c
+++ b/epan/wmem/wmem_test.c
@@ -520,64 +520,81 @@ wmem_test_array(void)
 }
 
 static void
-wmem_test_slist(void)
+wmem_test_list(void)
 {
-    wmem_allocator_t   *allocator;
-    wmem_slist_t       *slist;
-    wmem_slist_frame_t *frame;
-    unsigned int        i;
+    wmem_allocator_t  *allocator;
+    wmem_list_t       *list;
+    wmem_list_frame_t *frame;
+    unsigned int       i;
 
     allocator = wmem_allocator_force_new(WMEM_ALLOCATOR_STRICT);
 
-    slist = wmem_slist_new(allocator);
-    g_assert(slist);
-    g_assert(wmem_slist_count(slist) == 0);
+    list = wmem_list_new(allocator);
+    g_assert(list);
+    g_assert(wmem_list_count(list) == 0);
 
-    frame = wmem_slist_front(slist);
+    frame = wmem_list_head(list);
     g_assert(frame == NULL);
 
     for (i=0; i<CONTAINER_ITERS; i++) {
-        wmem_slist_prepend(slist, GINT_TO_POINTER(i));
-        g_assert(wmem_slist_count(slist) == i+1);
+        wmem_list_prepend(list, GINT_TO_POINTER(i));
+        g_assert(wmem_list_count(list) == i+1);
 
-        frame = wmem_slist_front(slist);
+        frame = wmem_list_head(list);
         g_assert(frame);
-        g_assert(wmem_slist_frame_data(frame) == GINT_TO_POINTER(i));
+        g_assert(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
     }
     wmem_strict_check_canaries(allocator);
 
     i = CONTAINER_ITERS - 1;
-    frame = wmem_slist_front(slist);
+    frame = wmem_list_head(list);
     while (frame) {
-        g_assert(wmem_slist_frame_data(frame) == GINT_TO_POINTER(i));
+        g_assert(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
         i--;
-        frame = wmem_slist_frame_next(frame);
+        frame = wmem_list_frame_next(frame);
+    }
+
+    i = 0;
+    frame = wmem_list_tail(list);
+    while (frame) {
+        g_assert(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
+        i++;
+        frame = wmem_list_frame_prev(frame);
     }
 
     i = CONTAINER_ITERS - 2;
-    while (wmem_slist_count(slist) > 1) {
-        wmem_slist_remove(slist, GINT_TO_POINTER(i));
+    while (wmem_list_count(list) > 1) {
+        wmem_list_remove(list, GINT_TO_POINTER(i));
         i--;
     }
-    wmem_slist_remove(slist, GINT_TO_POINTER(CONTAINER_ITERS - 1));
-    g_assert(wmem_slist_count(slist) == 0);
-    g_assert(wmem_slist_front(slist) == NULL);
+    wmem_list_remove(list, GINT_TO_POINTER(CONTAINER_ITERS - 1));
+    g_assert(wmem_list_count(list) == 0);
+    g_assert(wmem_list_head(list) == NULL);
+    g_assert(wmem_list_tail(list) == NULL);
 
     for (i=0; i<CONTAINER_ITERS; i++) {
-        wmem_slist_append(slist, GINT_TO_POINTER(i));
-        g_assert(wmem_slist_count(slist) == i+1);
+        wmem_list_append(list, GINT_TO_POINTER(i));
+        g_assert(wmem_list_count(list) == i+1);
 
-        frame = wmem_slist_front(slist);
+        frame = wmem_list_head(list);
         g_assert(frame);
     }
     wmem_strict_check_canaries(allocator);
 
     i = 0;
-    frame = wmem_slist_front(slist);
+    frame = wmem_list_head(list);
     while (frame) {
-        g_assert(wmem_slist_frame_data(frame) == GINT_TO_POINTER(i));
+        g_assert(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
         i++;
-        frame = wmem_slist_frame_next(frame);
+        frame = wmem_list_frame_next(frame);
+    }
+
+    i = CONTAINER_ITERS - 1;
+    frame = wmem_list_tail(list);
+    while (frame) {
+        g_assert(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
+        i--;
+        frame = wmem_list_frame_prev(frame);
     }
 
     wmem_destroy_allocator(allocator);
@@ -864,7 +881,7 @@ main(int argc, char **argv)
     g_test_add_func("/wmem/utils/strings", wmem_test_strutls);
 
     g_test_add_func("/wmem/datastruct/array",  wmem_test_array);
-    g_test_add_func("/wmem/datastruct/slist",  wmem_test_slist);
+    g_test_add_func("/wmem/datastruct/list",   wmem_test_list);
     g_test_add_func("/wmem/datastruct/stack",  wmem_test_stack);
     g_test_add_func("/wmem/datastruct/strbuf", wmem_test_strbuf);
     g_test_add_func("/wmem/datastruct/tree",   wmem_test_tree);