summaryrefslogtreecommitdiffstatshomepage
path: root/trunk/src/lib/util/pool.c
diff options
context:
space:
mode:
Diffstat (limited to 'trunk/src/lib/util/pool.c')
-rw-r--r--trunk/src/lib/util/pool.c645
1 files changed, 645 insertions, 0 deletions
diff --git a/trunk/src/lib/util/pool.c b/trunk/src/lib/util/pool.c
new file mode 100644
index 00000000000..0067ceb43b7
--- /dev/null
+++ b/trunk/src/lib/util/pool.c
@@ -0,0 +1,645 @@
+/***************************************************************************
+
+ pool.c
+
+ Resource pool code
+
+****************************************************************************
+
+ Copyright Aaron Giles
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are
+ met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in
+ the documentation and/or other materials provided with the
+ distribution.
+ * Neither the name 'MAME' nor the names of its contributors may be
+ used to endorse or promote products derived from this software
+ without specific prior written permission.
+
+ THIS SOFTWARE IS PROVIDED BY AARON GILES ''AS IS'' AND ANY EXPRESS OR
+ IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL AARON GILES BE LIABLE FOR ANY DIRECT,
+ INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+ IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ POSSIBILITY OF SUCH DAMAGE.
+
+***************************************************************************/
+
+#include <stdarg.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include "pool.h"
+#include "coreutil.h"
+
+
+/***************************************************************************
+ CONSTANTS
+***************************************************************************/
+
+#define OBJECT_ENTRY_BLOCK 256
+#define POOL_HASH_SIZE 3797
+
+
+
+/***************************************************************************
+ TYPE DEFINITIONS
+***************************************************************************/
+
+/* an object type entry */
+typedef struct _objtype_entry objtype_entry;
+struct _objtype_entry
+{
+ objtype_entry * next;
+ UINT32 type;
+ const char * friendly;
+ void (*destructor)(void *, size_t);
+};
+
+
+/* an entry in a pool */
+typedef struct _object_entry object_entry;
+struct _object_entry
+{
+ object_entry * next;
+ object_entry * globalnext;
+ object_entry * globalprev;
+ objtype_entry * type;
+ void * object;
+ size_t size;
+ const char * file;
+ int line;
+};
+
+
+/* a block of entry items */
+typedef struct _object_entry_block object_entry_block;
+struct _object_entry_block
+{
+ object_entry_block *next;
+ object_entry entry[OBJECT_ENTRY_BLOCK];
+};
+
+
+/* the object pool itself */
+struct _object_pool
+{
+ object_entry * hashtable[POOL_HASH_SIZE];
+ object_entry * globallist;
+ object_entry * freelist;
+ object_entry_block *blocklist;
+ objtype_entry * typelist;
+ void (*fail)(const char *message);
+};
+
+
+/* an iterator over objects in a pool */
+struct _object_pool_iterator
+{
+ object_pool * pool;
+ object_type type;
+ object_entry * last;
+};
+
+
+
+/***************************************************************************
+ FUNCTION PROTOTYPES
+***************************************************************************/
+
+static void memory_destruct(void *object, size_t size);
+static void report_failure(object_pool *pool, const char *format, ...) ATTR_PRINTF(2,3);
+
+
+
+/***************************************************************************
+ INLINE FUNCTIONS
+***************************************************************************/
+
+/*-------------------------------------------------
+ hash_object - compute the hash for a given
+ object
+-------------------------------------------------*/
+
+INLINE int hash_object(void *object)
+{
+ return ((size_t)object >> 4) % POOL_HASH_SIZE;
+}
+
+
+/*-------------------------------------------------
+ get_object_type - return the type entry for
+ a given object type
+-------------------------------------------------*/
+
+INLINE objtype_entry *get_object_type(object_pool *pool, object_type type)
+{
+ objtype_entry *entry;
+
+ for (entry = pool->typelist; entry != NULL; entry = entry->next)
+ if (entry->type == type)
+ return entry;
+
+ return NULL;
+}
+
+
+
+/***************************************************************************
+ RESOURCE POOL MANAGEMENT
+***************************************************************************/
+
+/*-------------------------------------------------
+ pool_alloc - allocates a new memory pool
+-------------------------------------------------*/
+
+object_pool *pool_alloc_lib(void (*fail)(const char *message))
+{
+ object_pool *pool;
+
+ /* allocate memory for the pool itself */
+ pool = (object_pool *)malloc(sizeof(*pool));
+ if (pool == NULL)
+ return NULL;
+ memset(pool, 0, sizeof(*pool));
+
+ /* set the failure handler */
+ pool->fail = fail;
+
+ /* register the built-in types */
+ pool_type_register(pool, OBJTYPE_MEMORY, "Memory", memory_destruct);
+
+ return pool;
+}
+
+
+/*-------------------------------------------------
+ pool_type_register - register a new pool
+ type
+-------------------------------------------------*/
+
+void pool_type_register(object_pool *pool, object_type type, const char *friendly, void (*destructor)(void *, size_t))
+{
+ objtype_entry *newtype = get_object_type(pool, type);
+
+ /* if the type doesn't already exist... */
+ if (newtype == NULL)
+ {
+ /* allocate a new entry */
+ newtype = (objtype_entry *)malloc(sizeof(*newtype));
+ if (newtype == NULL)
+ {
+ report_failure(pool, "Error adding new type %s\n", friendly);
+ return;
+ }
+ memset(newtype, 0, sizeof(*newtype));
+
+ /* link us in */
+ newtype->next = pool->typelist;
+ pool->typelist = newtype;
+ }
+
+ /* fill in the type information */
+ newtype->type = type;
+ newtype->friendly = friendly;
+ newtype->destructor = destructor;
+}
+
+
+/*-------------------------------------------------
+ pool_clear - frees all contained memory blocks
+ in a pool
+-------------------------------------------------*/
+
+void pool_clear(object_pool *pool)
+{
+ object_entry *entry, *next;
+
+ /* iterate over all entries in the global list and free them */
+ for (entry = pool->globallist; entry != NULL; entry = next)
+ {
+ /* remember the next entry */
+ next = entry->globalnext;
+
+ /* call the destructor */
+ (*entry->type->destructor)(entry->object, entry->size);
+
+ /* add ourself to the free list */
+ entry->next = pool->freelist;
+ entry->globalnext = entry->globalprev = NULL;
+ pool->freelist = entry;
+ }
+
+ /* zap the hashtable */
+ memset(pool->hashtable, 0, sizeof(pool->hashtable));
+}
+
+
+/*-------------------------------------------------
+ pool_free_lib - frees a memory pool and all
+ contained memory blocks
+-------------------------------------------------*/
+
+void pool_free_lib(object_pool *pool)
+{
+ object_entry_block *block, *nextblock;
+ objtype_entry *type, *nexttype;
+
+ /* clear the pool */
+ pool_clear(pool);
+
+ /* free all entry blocks */
+ for (block = pool->blocklist; block != NULL; block = nextblock)
+ {
+ nextblock = block->next;
+ free(block);
+ }
+
+ /* free all types */
+ for (type = pool->typelist; type != NULL; type = nexttype)
+ {
+ nexttype = type->next;
+ free(type);
+ }
+
+ /* free the pool itself */
+ free(pool);
+}
+
+
+
+/***************************************************************************
+ OBJECT MANAGEMENT
+***************************************************************************/
+
+/*-------------------------------------------------
+ pool_object_add_file_line - add an object to
+ the resource pool
+-------------------------------------------------*/
+
+void *pool_object_add_file_line(object_pool *pool, object_type _type, void *object, size_t size, const char *file, int line)
+{
+ objtype_entry *type = get_object_type(pool, _type);
+ int hashnum = hash_object(object);
+ object_entry *entry;
+
+ /* if we have an invalid type, fail */
+ if (type == NULL)
+ {
+ report_failure(pool, "pool_object_add (via %s:%d): Attempted to add object of unknown type with size %d", file, line, (int)size);
+ return object;
+ }
+
+ /* if we get a NULL object, fail */
+ if (object == NULL)
+ {
+ report_failure(pool, "pool_object_add (via %s:%d): Attempted to add a NULL object of size %d", file, line, (int)size);
+ return object;
+ }
+
+ /* allocate a new entry */
+ if (pool->freelist == NULL)
+ {
+ object_entry_block *block;
+ int entrynum;
+
+ /* if we need a new block, allocate that now */
+ block = (object_entry_block *)malloc(sizeof(*block));
+ if (block == NULL)
+ return NULL;
+ memset(block, 0, sizeof(*block));
+
+ /* hook us into the blocklist */
+ block->next = pool->blocklist;
+ pool->blocklist = block;
+
+ /* add all entries to the free list */
+ for (entrynum = 0; entrynum < ARRAY_LENGTH(block->entry); entrynum++)
+ {
+ block->entry[entrynum].next = pool->freelist;
+ pool->freelist = &block->entry[entrynum];
+ }
+ }
+
+ /* remove the head of the freelist */
+ entry = pool->freelist;
+ pool->freelist = entry->next;
+
+ /* fill in the entry */
+ entry->type = type;
+ entry->object = object;
+ entry->size = size;
+ entry->file = file;
+ entry->line = line;
+
+ /* hook us into the global list */
+ if (pool->globallist != NULL)
+ pool->globallist->globalprev = entry;
+ entry->globalprev = NULL;
+ entry->globalnext = pool->globallist;
+ pool->globallist = entry;
+
+ /* hook up to the appropriate hash table */
+ entry->next = pool->hashtable[hashnum];
+ pool->hashtable[hashnum] = entry;
+ return object;
+}
+
+
+/*-------------------------------------------------
+ pool_object_remove - remove an entry from a
+ pool, optionally calling its destructor
+-------------------------------------------------*/
+
+void *pool_object_remove(object_pool *pool, void *object, int destruct)
+{
+ int hashnum = hash_object(object);
+ object_entry **entryptr;
+
+ /* find the object in question and remove it */
+ for (entryptr = &pool->hashtable[hashnum]; *entryptr != NULL; entryptr = &(*entryptr)->next)
+ if ((*entryptr)->object == object)
+ {
+ object_entry *entry = *entryptr;
+
+ /* call the destructor */
+ if (destruct)
+ (*entry->type->destructor)(entry->object, entry->size);
+
+ /* remove us from the global list */
+ if (entry->globalprev != NULL)
+ entry->globalprev->globalnext = entry->globalnext;
+ if (entry->globalnext != NULL)
+ entry->globalnext->globalprev = entry->globalprev;
+ if (pool->globallist == entry)
+ pool->globallist = entry->globalnext;
+
+ /* remove us from the list */
+ *entryptr = entry->next;
+
+ /* add us to the free list */
+ entry->next = pool->freelist;
+ pool->freelist = entry;
+ break;
+ }
+
+ return NULL;
+}
+
+
+/*-------------------------------------------------
+ pool_object_exists - return TRUE if an
+ object exists in the pool
+-------------------------------------------------*/
+
+int pool_object_exists(object_pool *pool, object_type type, void *object)
+{
+ int hashnum = hash_object(object);
+ object_entry *entry;
+
+ /* find the object in question */
+ for (entry = pool->hashtable[hashnum]; entry != NULL; entry = entry->next)
+ if (entry->object == object && (type == OBJTYPE_WILDCARD || entry->type->type == type))
+ return TRUE;
+
+ return FALSE;
+}
+
+
+
+/***************************************************************************
+ OBJECT ITERATORS
+***************************************************************************/
+
+/*-------------------------------------------------
+ pool_iterate_begin - begin iterating over
+ objects in an object pool
+-------------------------------------------------*/
+
+object_pool_iterator *pool_iterate_begin(object_pool *pool, object_type type)
+{
+ object_pool_iterator *iter;
+
+ /* allocate the iterator */
+ iter = (object_pool_iterator *)malloc(sizeof(*iter));
+ if (iter == NULL)
+ return NULL;
+ memset(iter, 0, sizeof(*iter));
+
+ /* fill it in */
+ iter->pool = pool;
+ iter->type = type;
+ iter->last = NULL;
+ return iter;
+}
+
+
+/*-------------------------------------------------
+ pool_iterate_next - get the next object in the
+ object pool
+-------------------------------------------------*/
+
+int pool_iterate_next(object_pool_iterator *iter, void **objectptr, size_t *sizeptr, object_type *typeptr)
+{
+ /* if no previous entry, find the first */
+ if (iter->last == NULL)
+ iter->last = iter->pool->globallist;
+ else
+ iter->last = iter->last->globalnext;
+
+ /* stop when we get one */
+ if (iter->last != NULL)
+ {
+ if (objectptr != NULL)
+ *objectptr = iter->last;
+ if (sizeptr != NULL)
+ *sizeptr = iter->last->size;
+ if (typeptr != NULL)
+ *typeptr = iter->last->type->type;
+ return TRUE;
+ }
+
+ /* nothing left */
+ return FALSE;
+}
+
+
+/*-------------------------------------------------
+ pool_iterate_end - finish iterating over
+ objects in an object pool
+-------------------------------------------------*/
+
+void pool_iterate_end(object_pool_iterator *iter)
+{
+ free(iter);
+}
+
+
+
+/***************************************************************************
+ MEMORY HELPERS
+***************************************************************************/
+
+/*-------------------------------------------------
+ pool_malloc_file_line - allocates memory in a
+ memory pool
+-------------------------------------------------*/
+
+void *pool_malloc_file_line(object_pool *pool, size_t size, const char *file, int line)
+{
+ void *ptr = malloc(size);
+ return pool_object_add_file_line(pool, OBJTYPE_MEMORY, ptr, size, file, line);
+}
+
+
+/*-------------------------------------------------
+ pool_realloc_file_line - reallocs memory in a
+ memory pool
+-------------------------------------------------*/
+
+void *pool_realloc_file_line(object_pool *pool, void *ptr, size_t size, const char *file, int line)
+{
+ if (ptr != NULL)
+ pool_object_remove(pool, ptr, FALSE);
+ ptr = realloc(ptr, size);
+ if (size != 0)
+ pool_object_add_file_line(pool, OBJTYPE_MEMORY, ptr, size, file, line);
+ return ptr;
+}
+
+
+/*-------------------------------------------------
+ pool_strdup_file_line - strdup in a memory
+ pool
+-------------------------------------------------*/
+
+char *pool_strdup_file_line(object_pool *pool, const char *str, const char *file, int line)
+{
+ char *ptr = (char *)pool_malloc_file_line(pool, strlen(str) + 1, file, line);
+ if (ptr != NULL)
+ strcpy(ptr, str);
+ return ptr;
+}
+
+
+
+/***************************************************************************
+ GENERIC DESTRUCTORS
+***************************************************************************/
+
+/*-------------------------------------------------
+ memory_destruct - generic destructor
+ that just does a free() on the object
+-------------------------------------------------*/
+
+static void memory_destruct(void *object, size_t size)
+{
+ free(object);
+}
+
+
+
+/***************************************************************************
+ INTERNAL FUNCTIONS
+***************************************************************************/
+
+/*-------------------------------------------------
+ report_failure - report a failure to the
+ failure callback
+-------------------------------------------------*/
+
+static void report_failure(object_pool *pool, const char *format, ...)
+{
+ /* only do the work if we have a callback */
+ if (pool->fail != NULL)
+ {
+ char message[1024];
+ va_list argptr;
+
+ /* generate the final message text */
+ va_start(argptr, format);
+ vsprintf(message, format, argptr);
+ va_end(argptr);
+
+ /* call the callback with the message */
+ (*pool->fail)(message);
+ }
+}
+
+
+
+/***************************************************************************
+ TESTING FUNCTIONS
+***************************************************************************/
+
+static int has_memory_error;
+
+
+/*-------------------------------------------------
+ memory_error - report a memory error
+-------------------------------------------------*/
+
+static void memory_error(const char *message)
+{
+ printf("memory test failure: %s\n", message);
+ has_memory_error = TRUE;
+}
+
+
+/*-------------------------------------------------
+ test_memory_pools - unit tests for memory
+ pool behavior
+-------------------------------------------------*/
+
+int test_memory_pools(void)
+{
+ object_pool *pool;
+ void *ptrs[16];
+ int i;
+
+ has_memory_error = FALSE;
+ pool = pool_alloc_lib(memory_error);
+ memset(ptrs, 0, sizeof(ptrs));
+
+ ptrs[0] = pool_malloc_lib(pool, 50);
+ ptrs[1] = pool_malloc_lib(pool, 100);
+
+ ptrs[0] = pool_realloc_lib(pool, ptrs[0], 150);
+ ptrs[1] = pool_realloc_lib(pool, ptrs[1], 200);
+
+ ptrs[2] = pool_malloc_lib(pool, 250);
+ ptrs[3] = pool_malloc_lib(pool, 300);
+
+ ptrs[0] = pool_realloc_lib(pool, ptrs[0], 350);
+ ptrs[1] = pool_realloc_lib(pool, ptrs[1], 400);
+
+ ptrs[2] = pool_realloc_lib(pool, ptrs[2], 450);
+ ptrs[3] = pool_realloc_lib(pool, ptrs[3], 500);
+
+ ptrs[0] = pool_realloc_lib(pool, ptrs[0], 0);
+ ptrs[1] = pool_realloc_lib(pool, ptrs[1], 0);
+
+ ptrs[2] = pool_realloc_lib(pool, ptrs[2], 550);
+ ptrs[3] = pool_realloc_lib(pool, ptrs[3], 600);
+
+ /* some heavier stress tests */
+ for (i = 0; i < 512; i++)
+ {
+ ptrs[i % ARRAY_LENGTH(ptrs)] = pool_realloc_lib(pool,
+ ptrs[i % ARRAY_LENGTH(ptrs)], rand() % 1000);
+ }
+
+ pool_free_lib(pool);
+ return has_memory_error;
+}