Implement a basic singly-linked for wmem.

Re-implement the stack as a wrapper for that.

svn path=/trunk/; revision=46607

8 files changed, 259 insertions, 58 deletions

diff --git a/doc/README.wmem b/doc/README.wmem
index d68dc39fbe..e85aee95da 100644
--- a/doc/README.wmem
+++ b/doc/README.wmem
@@ -93,12 +93,29 @@ to the lifetime of the pinfo struct.
  - wmem_stack_peek
  - wmem_stack_count
 
-2.5 Slab
+2.5 Singly-Linked List
+
+ - wmem_slist_new
+ - wmem_slist_prepend
+ - wmem_slist_remove
+ - wmem_slist_front
+ - wmem_slist_frame_next
+ - wmem_slist_frame_data
+ - wmem_slist_count
+
+2.6 Slab
 
  - wmem_slab_new
  - wmem_slab_alloc
  - wmem_slab_free
 
+2.7 String-Buffers
+
+ - wmem_strbuf_new
+ - wmem_strbuf_sized_new
+ - wmem_strbuf_get_str
+ - wmem_strbuf_get_len
+
 3. Usage for Producers
 
 NB: If you're just writing a dissector, you probably don't need to read
@@ -236,7 +253,6 @@ The following is a list of things that emem doesn't provide but that it might
 be nice if wmem did provide them:
 
  - radix tree
- - linked list
  - dynamic array
  - realloc
 
diff --git a/epan/CMakeLists.txt b/epan/CMakeLists.txt
index cb03b70294..6658ab5ccd 100644
--- a/epan/CMakeLists.txt
+++ b/epan/CMakeLists.txt
@@ -1355,6 +1355,7 @@ set(WMEM_FILES
 	wmem/wmem_allocator_simple.c
 	wmem/wmem_scopes.c
 	wmem/wmem_slab.c
+	wmem/wmem_slist.c
 	wmem/wmem_stack.c
 	wmem/wmem_strbuf.c
 	wmem/wmem_strutl.c
diff --git a/epan/wmem/Makefile.common b/epan/wmem/Makefile.common
index 77c5cb6b22..0e8f719579 100644
--- a/epan/wmem/Makefile.common
+++ b/epan/wmem/Makefile.common
@@ -29,6 +29,7 @@ LIBWMEM_SRC =				\
 	wmem_allocator_simple.c		\
 	wmem_scopes.c			\
 	wmem_slab.c			\
+	wmem_slist.c			\
 	wmem_stack.c			\
 	wmem_strbuf.c			\
 	wmem_strutl.c
@@ -41,6 +42,7 @@ LIBWMEM_INCLUDES =			\
 	wmem_allocator_simple.h		\
 	wmem_scopes.h			\
 	wmem_slab.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 048d1e3035..253eff8179 100644
--- a/epan/wmem/wmem.h
+++ b/epan/wmem/wmem.h
@@ -28,6 +28,7 @@
 
 #include "wmem_core.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_slist.c b/epan/wmem/wmem_slist.c
new file mode 100644
index 0000000000..e4cd15d042
--- /dev/null
+++ b/epan/wmem/wmem_slist.c
@@ -0,0 +1,139 @@
+/* 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_slab.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_slab_t *slab;
+};
+
+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_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_slab_free(slist->slab, frame);
+}
+
+void
+wmem_slist_prepend(wmem_slist_t *slist, void *data)
+{
+    wmem_slist_frame_t *new;
+
+    new = (wmem_slist_frame_t *) wmem_slab_alloc(slist->slab);
+
+    new->data = data;
+    new->next = slist->front;
+
+    slist->front = new;
+    slist->count++;
+}
+
+wmem_slist_t *
+wmem_slist_new(wmem_allocator_t *allocator)
+{
+    wmem_slist_t *slist;
+
+    slist = (wmem_slist_t *) wmem_alloc(allocator, sizeof(wmem_slist_t));
+
+    slist->count = 0;
+    slist->front = NULL;
+    slist->slab  = wmem_slab_new(allocator, sizeof(wmem_slist_frame_t));
+
+    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_slist.h b/epan/wmem/wmem_slist.h
new file mode 100644
index 0000000000..c1e8fa3241
--- /dev/null
+++ b/epan/wmem/wmem_slist.h
@@ -0,0 +1,82 @@
+/* wmem_slist.h
+ * Definitions for the 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.
+ */
+
+#ifndef __WMEM_SLIST_H__
+#define __WMEM_SLIST_H__
+
+#include <string.h>
+#include <glib.h>
+
+#include "wmem_core.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+struct _wmem_slist_t;
+struct _wmem_slist_frame_t;
+
+typedef struct _wmem_slist_t       wmem_slist_t;
+typedef struct _wmem_slist_frame_t wmem_slist_frame_t;
+
+guint
+wmem_slist_count(const wmem_slist_t *slist);
+
+wmem_slist_frame_t *
+wmem_slist_front(const wmem_slist_t *slist);
+
+wmem_slist_frame_t *
+wmem_slist_frame_next(const wmem_slist_frame_t *frame);
+
+void *
+wmem_slist_frame_data(const wmem_slist_frame_t *frame);
+
+void
+wmem_slist_remove(wmem_slist_t *slist, void *data);
+
+void
+wmem_slist_prepend(wmem_slist_t *slist, void *data);
+
+wmem_slist_t *
+wmem_slist_new(wmem_allocator_t *allocator);
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* __WMEM_SLIST_H__ */
+
+/*
+ * 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 8581f51d2c..2dbd910ae4 100644
--- a/epan/wmem/wmem_stack.c
+++ b/epan/wmem/wmem_stack.c
@@ -29,47 +29,30 @@
 #include "wmem_core.h"
 #include "wmem_slab.h"
 #include "wmem_stack.h"
+#include "wmem_slist.h"
 
-typedef struct _wmem_stack_frame_t {
-    struct _wmem_stack_frame_t *next;
-    void *data;
-} wmem_stack_frame_t;
-
-struct _wmem_stack_t {
-    guint count;
-    wmem_stack_frame_t *top;
-    wmem_slab_t *slab;
-};
-
-guint
-wmem_stack_count(const wmem_stack_t *stack)
-{
-    return stack->count;
-}
+/* Wmem stack is implemented as a simple wrapper over Wmem slist */
 
 void *
 wmem_stack_peek(const wmem_stack_t *stack)
 {
-    g_assert(stack->top != NULL);
-    g_assert(stack->count > 0);
+    wmem_slist_frame_t *frame;
+
+    frame = wmem_slist_front(stack);
 
-    return stack->top->data;
+    g_assert(frame);
+
+    return wmem_slist_frame_data(frame);
 }
 
 void *
 wmem_stack_pop(wmem_stack_t *stack)
 {
-    wmem_stack_frame_t *top;
     void *data;
 
-    g_assert(stack->top != NULL);
-    g_assert(stack->count > 0);
+    data = wmem_stack_peek(stack);
 
-    top = stack->top;
-    stack->top = top->next;
-    stack->count--;
-    data = top->data;
-    wmem_slab_free(stack->slab, top);
+    wmem_slist_remove(stack, data);
 
     return data;
 }
@@ -77,28 +60,7 @@ wmem_stack_pop(wmem_stack_t *stack)
 void
 wmem_stack_push(wmem_stack_t *stack, void *data)
 {
-    wmem_stack_frame_t *new;
-
-    new = (wmem_stack_frame_t *) wmem_slab_alloc(stack->slab);
-
-    new->data = data;
-    new->next = stack->top;
-    stack->top = new;
-    stack->count++;
-}
-
-wmem_stack_t *
-wmem_stack_new(wmem_allocator_t *allocator)
-{
-    wmem_stack_t *stack;
-
-    stack = (wmem_stack_t *) wmem_alloc(allocator, sizeof(wmem_stack_t));
-
-    stack->count = 0;
-    stack->top   = NULL;
-    stack->slab  = wmem_slab_new(allocator, sizeof(wmem_stack_frame_t));
-
-    return stack;
+    wmem_slist_prepend(stack, data);
 }
 
 /*
diff --git a/epan/wmem/wmem_stack.h b/epan/wmem/wmem_stack.h
index 42ed4f3295..a11c26f584 100644
--- a/epan/wmem/wmem_stack.h
+++ b/epan/wmem/wmem_stack.h
@@ -30,17 +30,16 @@
 #include <glib.h>
 
 #include "wmem_core.h"
+#include "wmem_slist.h"
 
 #ifdef __cplusplus
 extern "C" {
 #endif /* __cplusplus */
 
-struct _wmem_stack_t;
+/* Wmem stack is implemented as a simple wrapper over Wmem slist */
+typedef wmem_slist_t wmem_stack_t;
 
-typedef struct _wmem_stack_t wmem_stack_t;
-
-guint
-wmem_stack_count(const wmem_stack_t *stack);
+#define wmem_stack_count(X) wmem_slist_count(X)
 
 void *
 wmem_stack_peek(const wmem_stack_t *stack);
@@ -51,8 +50,7 @@ wmem_stack_pop(wmem_stack_t *stack);
 void
 wmem_stack_push(wmem_stack_t *stack, void *data);
 
-wmem_stack_t *
-wmem_stack_new(wmem_allocator_t *allocator);
+#define wmem_stack_new(ALLOCATOR) wmem_slist_new(ALLOCATOR)
 
 #ifdef __cplusplus
 }