/*************************************************************************** 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 #include #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; }