Simple growable array implementation for wmem.

svn path=/trunk/; revision=50400

7 files changed, 301 insertions, 1 deletions

diff --git a/doc/README.wmem b/doc/README.wmem
index d49dfb7b11..f203e74fd3 100644
--- a/doc/README.wmem
+++ b/doc/README.wmem
@@ -334,7 +334,6 @@ The following is a list of things that emem didn't provide but that it might
 be nice if wmem did:
 
  - radix tree
- - dynamic array
  - hash table
 
 /*
diff --git a/epan/CMakeLists.txt b/epan/CMakeLists.txt
index d8b1fb3ebd..3ee44cdec1 100644
--- a/epan/CMakeLists.txt
+++ b/epan/CMakeLists.txt
@@ -1382,6 +1382,7 @@ set(FTYPE_FILES
 )
 
 set(WMEM_FILES
+	wmem/wmem_array.c
 	wmem/wmem_core.c
 	wmem/wmem_allocator_block.c
 	wmem/wmem_allocator_simple.c
diff --git a/epan/wmem/Makefile.common b/epan/wmem/Makefile.common
index d5b0d9d0e9..f212ccd6a6 100644
--- a/epan/wmem/Makefile.common
+++ b/epan/wmem/Makefile.common
@@ -24,6 +24,7 @@
 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 
 LIBWMEM_SRC =				\
+	wmem_array.c   			\
 	wmem_core.c    			\
 	wmem_allocator_block.c		\
 	wmem_allocator_simple.c		\
@@ -39,6 +40,7 @@ LIBWMEM_SRC =				\
 
 LIBWMEM_INCLUDES =			\
 	wmem.h				\
+	wmem_array.h   			\
 	wmem_core.h    			\
 	wmem_allocator.h       		\
 	wmem_allocator_block.h		\
diff --git a/epan/wmem/wmem.h b/epan/wmem/wmem.h
index b749a3b53b..36a670cfc7 100644
--- a/epan/wmem/wmem.h
+++ b/epan/wmem/wmem.h
@@ -26,6 +26,7 @@
 #ifndef __WMEM_H__
 #define __WMEM_H__
 
+#include "wmem_array.h"
 #include "wmem_core.h"
 #include "wmem_miscutl.h"
 #include "wmem_scopes.h"
diff --git a/epan/wmem/wmem_array.c b/epan/wmem/wmem_array.c
new file mode 100644
index 0000000000..da0a034e06
--- /dev/null
+++ b/epan/wmem/wmem_array.c
@@ -0,0 +1,143 @@
+/* wmem_array.c
+ * Wireshark Memory Manager Array
+ * Copyright 2013, 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 "config.h"
+
+#include "wmem_core.h"
+#include "wmem_array.h"
+
+/* Holds a wmem-allocated array.
+ *  elem_len is the size of each element
+ *  elem_count is the number of used elements
+ *  alloc_count is the length (in elems) of the raw buffer pointed to by buf,
+ *      regardless of how many elems are used (the contents)
+ */
+struct _wmem_array_t {
+    wmem_allocator_t *allocator;
+
+    guint8 *buf;
+
+    gsize elem_size;
+
+    guint elem_count;
+    guint alloc_count;
+};
+
+wmem_array_t *
+wmem_array_sized_new(wmem_allocator_t *allocator, gsize elem_size,
+                     guint alloc_count)
+{
+    wmem_array_t *array;
+
+    array = wmem_new(allocator, wmem_array_t);
+
+    array->allocator   = allocator;
+    array->elem_size   = elem_size;
+    array->elem_count  = 0;
+    array->alloc_count = alloc_count ? alloc_count : 1;
+
+    array->buf = (guint8 *)wmem_alloc(array->allocator,
+            array->elem_size * array->alloc_count);
+
+    return array;
+}
+
+wmem_array_t *
+wmem_array_new(wmem_allocator_t *allocator, const gsize elem_size)
+{
+    wmem_array_t *array;
+
+    array = wmem_array_sized_new(allocator, elem_size, 1);
+
+    return array;
+}
+
+static void
+wmem_array_grow(wmem_array_t *array, const guint to_add)
+{
+    guint new_alloc_count, new_count;
+
+    new_alloc_count = array->alloc_count;
+    new_count = array->elem_count + to_add;
+
+    while (new_alloc_count < new_count) {
+        new_alloc_count *= 2;
+    }
+
+    if (new_alloc_count == array->alloc_count) {
+        return;
+    }
+
+    array->buf = (guint8 *)wmem_realloc(array->allocator, array->buf,
+            new_alloc_count * array->elem_size);
+
+    array->alloc_count = new_alloc_count;
+}
+
+void
+wmem_array_append(wmem_array_t *array, const void *in, guint count)
+{
+    wmem_array_grow(array, count);
+
+    memcpy(&array->buf[array->elem_count * array->elem_size], in,
+            count * array->elem_size);
+
+    array->elem_count += count;
+}
+
+void *
+wmem_array_index(wmem_array_t *array, guint index)
+{
+    g_assert(index < array->elem_count);
+    return &array->buf[index * array->elem_size];
+}
+
+void *
+wmem_array_get_raw(wmem_array_t *array)
+{
+    return array->buf;
+}
+
+guint
+wmem_array_get_count(wmem_array_t *array)
+{
+    return array->elem_count;
+}
+
+/*
+ * 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_array.h b/epan/wmem/wmem_array.h
new file mode 100644
index 0000000000..a71ec4d363
--- /dev/null
+++ b/epan/wmem/wmem_array.h
@@ -0,0 +1,101 @@
+/* wmem_array.h
+ * Definitions for the Wireshark Memory Manager Array
+ * Copyright 2013, 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_ARRAY_H__
+#define __WMEM_ARRAY_H__
+
+#include <string.h>
+#include <glib.h>
+
+#include "wmem_core.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+/** @addtogroup wmem
+ *  @{
+ *    @defgroup wmem-array Array
+ *
+ *    A resizable array implementation on top of wmem.
+ *
+ *    @{
+ */
+
+struct _wmem_array_t;
+
+typedef struct _wmem_array_t wmem_array_t;
+
+WS_DLL_PUBLIC
+wmem_array_t *
+wmem_array_sized_new(wmem_allocator_t *allocator, gsize elem_size,
+                     guint alloc_count)
+G_GNUC_MALLOC;
+
+WS_DLL_PUBLIC
+wmem_array_t *
+wmem_array_new(wmem_allocator_t *allocator, const gsize elem_size)
+G_GNUC_MALLOC;
+
+WS_DLL_PUBLIC
+void
+wmem_array_append(wmem_array_t *array, const void *in, guint count);
+
+#define wmem_array_append_one(ARRAY, VAL) \
+    wmem_array_append((ARRAY), &(VAL), 1)
+
+WS_DLL_PUBLIC
+void *
+wmem_array_index(wmem_array_t *array, guint index);
+
+WS_DLL_PUBLIC
+void *
+wmem_array_get_raw(wmem_array_t *array);
+
+WS_DLL_PUBLIC
+guint
+wmem_array_get_count(wmem_array_t *array);
+
+/**   @}
+ *  @} */
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* __WMEM_ARRAY_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_test.c b/epan/wmem/wmem_test.c
index 710ff551a8..cf43a3acff 100644
--- a/epan/wmem/wmem_test.c
+++ b/epan/wmem/wmem_test.c
@@ -438,6 +438,58 @@ wmem_test_strutls(void)
 /* DATA STRUCTURE TESTING FUNCTIONS (/wmem/datastruct/) */
 
 static void
+wmem_test_array(void)
+{
+    wmem_allocator_t   *allocator;
+    wmem_array_t       *array;
+    unsigned int        i, j;
+    guint32             val, *buf;
+    guint32             vals[8];
+
+    allocator = wmem_allocator_force_new(WMEM_ALLOCATOR_STRICT);
+
+    array = wmem_array_new(allocator, sizeof(guint32));
+    g_assert(array);
+    g_assert(wmem_array_get_count(array) == 0);
+
+    for (i=0; i<CONTAINER_ITERS; i++) {
+        val = i;
+        wmem_array_append_one(array, val);
+        g_assert(wmem_array_get_count(array) == i+1);
+
+        val = *(guint32*)wmem_array_index(array, i);
+        g_assert(val == i);
+    }
+    wmem_strict_check_canaries(allocator);
+
+    for (i=0; i<CONTAINER_ITERS; i++) {
+        val = *(guint32*)wmem_array_index(array, i);
+        g_assert(val == i);
+    }
+
+    array = wmem_array_sized_new(allocator, sizeof(guint32), 73);
+
+    for (i=0; i<CONTAINER_ITERS; i++) {
+        for (j=0; j<8; j++) {
+            vals[j] = i+j;
+        }
+
+        wmem_array_append(array, vals, 8);
+        g_assert(wmem_array_get_count(array) == 8*(i+1));
+    }
+    wmem_strict_check_canaries(allocator);
+
+    buf = (guint32*)wmem_array_get_raw(array);
+    for (i=0; i<CONTAINER_ITERS; i++) {
+        for (j=0; j<8; j++) {
+            g_assert(buf[i*8 + j] == i+j);
+        }
+    }
+
+    wmem_destroy_allocator(allocator);
+}
+
+static void
 wmem_test_slist(void)
 {
     wmem_allocator_t   *allocator;
@@ -781,6 +833,7 @@ main(int argc, char **argv)
     g_test_add_func("/wmem/utils/misc",    wmem_test_miscutls);
     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/stack",  wmem_test_stack);
     g_test_add_func("/wmem/datastruct/strbuf", wmem_test_strbuf);