From c574f7d1ea9a2e9118111fbf462ca0c6d428e97b Mon Sep 17 00:00:00 2001 From: Evan Huus Date: Sat, 6 Jul 2013 04:02:08 +0000 Subject: Simple growable array implementation for wmem. svn path=/trunk/; revision=50400 --- doc/README.wmem | 1 - epan/CMakeLists.txt | 1 + epan/wmem/Makefile.common | 2 + epan/wmem/wmem.h | 1 + epan/wmem/wmem_array.c | 143 ++++++++++++++++++++++++++++++++++++++++++++++ epan/wmem/wmem_array.h | 101 ++++++++++++++++++++++++++++++++ epan/wmem/wmem_test.c | 53 +++++++++++++++++ 7 files changed, 301 insertions(+), 1 deletion(-) create mode 100644 epan/wmem/wmem_array.c create mode 100644 epan/wmem/wmem_array.h 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 + * + * $Id$ + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * 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 +#include + +#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 + * + * $Id$ + * + * Wireshark - Network traffic analyzer + * By Gerald Combs + * 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 +#include + +#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 @@ -437,6 +437,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