diff options
Diffstat (limited to 'src/lib/util/pool.c')
-rw-r--r-- | src/lib/util/pool.c | 614 |
1 files changed, 614 insertions, 0 deletions
diff --git a/src/lib/util/pool.c b/src/lib/util/pool.c new file mode 100644 index 00000000000..62b131416fb --- /dev/null +++ b/src/lib/util/pool.c @@ -0,0 +1,614 @@ +/*************************************************************************** + + pool.c + + Resource pool code + + Copyright (c) 1996-2007, Nicola Salmoria and the MAME Team. + Visit http://mamedev.org for licensing and usage restrictions. + +***************************************************************************/ + +#include <stdarg.h> +#include <stddef.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; + 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 * 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; + int hashnum; + object_entry * last; +}; + + + +/*************************************************************************** + FUNCTION PROTOTYPES +***************************************************************************/ + +static void memory_destruct(void *object, size_t size); +static void report_failure(object_pool *pool, const char *format, ...); + + + +/*************************************************************************** + 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; +} + + +/*------------------------------------------------- + hash_object - compute the hash for a given + object +-------------------------------------------------*/ + +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(void (*fail)(const char *message)) +{ + object_pool *pool; + + /* allocate memory for the pool itself */ + pool = malloc(sizeof(*pool)); + if (pool == NULL) + return NULL; + memset(pool, 0, sizeof(*pool)); + + /* 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 = 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) +{ + int hashnum; + + /* iterate over hash buckets */ + for (hashnum = 0; hashnum < ARRAY_LENGTH(pool->hashtable); hashnum++) + { + object_entry *entry, *next; + + /* iterate over entries in this hash bucket and free them */ + for (entry = pool->hashtable[hashnum]; entry != NULL; entry = next) + { + /* remember the next entry */ + next = entry->next; + + /* call the destructor */ + (*entry->type->destructor)(entry->object, entry->size); + + /* add ourself to the free list */ + entry->next = pool->freelist; + pool->freelist = entry; + } + + /* reset the list we just walked */ + pool->hashtable[hashnum] = NULL; + } +} + + +/*------------------------------------------------- + pool_free - frees a memory pool and all + contained memory blocks +-------------------------------------------------*/ + +void pool_free(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", 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 = 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 list */ + 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 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 = malloc(sizeof(*iter)); + if (iter == NULL) + return NULL; + memset(iter, 0, sizeof(*iter)); + + /* fill it in */ + iter->pool = pool; + iter->type = type; + iter->hashnum = 0; + 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) +{ + /* advance from the last one */ + while (iter->hashnum < ARRAY_LENGTH(iter->pool->hashtable)) + { + /* if the last entry is non-NULL, advance */ + if (iter->last == NULL) + iter->last = iter->pool->hashtable[iter->hashnum++]; + else + iter->last = iter->last->next; + + /* 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) +{ +#ifdef MALLOC_DEBUG + void *ptr = malloc_file_line(size, file, line); +#else + void *ptr = malloc(size); +#endif + 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); +#ifdef MALLOC_DEBUG + ptr = realloc_file_line(ptr, size, file, line); +#else + ptr = realloc(ptr, size); +#endif + 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 = 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(memory_error); + memset(ptrs, 0, sizeof(ptrs)); + + ptrs[0] = pool_malloc(pool, 50); + ptrs[1] = pool_malloc(pool, 100); + + ptrs[0] = pool_realloc(pool, ptrs[0], 150); + ptrs[1] = pool_realloc(pool, ptrs[1], 200); + + ptrs[2] = pool_malloc(pool, 250); + ptrs[3] = pool_malloc(pool, 300); + + ptrs[0] = pool_realloc(pool, ptrs[0], 350); + ptrs[1] = pool_realloc(pool, ptrs[1], 400); + + ptrs[2] = pool_realloc(pool, ptrs[2], 450); + ptrs[3] = pool_realloc(pool, ptrs[3], 500); + + ptrs[0] = pool_realloc(pool, ptrs[0], 0); + ptrs[1] = pool_realloc(pool, ptrs[1], 0); + + ptrs[2] = pool_realloc(pool, ptrs[2], 550); + ptrs[3] = pool_realloc(pool, ptrs[3], 600); + + /* some heavier stress tests */ + for (i = 0; i < 512; i++) + { + ptrs[i % ARRAY_LENGTH(ptrs)] = pool_realloc(pool, + ptrs[i % ARRAY_LENGTH(ptrs)], rand() % 1000); + } + + pool_free(pool); + return has_memory_error; +} |