summaryrefslogblamecommitdiffstatshomepage
path: root/src/lib/util/pool.cpp
blob: 9712d8b6e00bc0bf8f2702311d1f8ae96dd66ca2 (plain) (tree)
1
2
3
4
5
6
7
8

                                





                                                                            



                                                                            
                   







                                                                            

                                







                                                                            
                    
 



                                                          



                        
                   
 







                                       



                            
                         

                                 
                                                      



                            
                  
 


                                                      
                                      

                                                         



                                        
                           
 


                                 








                                                                            
                                                                                        











                                                                            
                                           





                                                      

                                               

                                                   
                                                                                 


                             
                                                                           


                                        
                       











                                                                            
                                                              



                                                 
                                                    

                               

                                       

                                     
 
















                                                                                                                      
                               

                                          
                                                                    
                                       
























                                                                                     
                                   
 
                                                                       
                                                                      
         

                                             
 

                                                                       
 

                                                  
                                                                
                                       
         
 

                                                            



                                                   
                                               


                                                   
                                     







                                              
                                                                          





                                        
                                                                     


























                                                                                                                            
                            
         
                                                                                                                                                 



                                           
                              





                                                                                                                                      
                                      




                                                               
                                                                     

                                       
























                                                                                     
                                          
                                        
                                                     
                                    

                                             
 
                                                   
















                                                                       
                                                                                                       







                                                                                       
                                                            
                                                         
                                                                                  
                                                         



                                                                                  








                                                     
                       













                                                                         
                                                                                     





















                                                                                                       
                                                             

                               




                                       
                             










                                                                                                          
                                                  
                                  


                                                    
 
                                  
                                  
         
                                         
                                                
                                       
                                                    
                                       

                                                          





























                                                                                       
                                 










                                                                                                   
                           
                                                     
                                 












                                                                                           
                                                                                     
                           

































                                                                            
                                  






































                                                                            
   
                                   
  
                               
  
                   

   






                                 
                                            

                                      

                                             
 

                                                       
 

                                             
 

                                                       
 

                                                       
 

                                                     
 

                                                       



                                       
                                                                     


                                                                     
                            

                                
// license:BSD-3-Clause
// copyright-holders:Aaron Giles
/***************************************************************************

    pool.c

    Resource pool code

***************************************************************************/

#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 */
struct objtype_entry
{
	objtype_entry *     next;
	UINT32              type;
	const char *        friendly;
	void                (*destructor)(void *, size_t);
};


/* an entry in a pool */
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 */
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
-------------------------------------------------*/

static 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
-------------------------------------------------*/

static inline objtype_entry *get_object_type(object_pool *pool, object_type type)
{
	objtype_entry *entry;

	for (entry = pool->typelist; entry != nullptr; entry = entry->next)
		if (entry->type == type)
			return entry;

	return nullptr;
}



/***************************************************************************
    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 == nullptr)
		return nullptr;
	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 == nullptr)
	{
		/* allocate a new entry */
		newtype = (objtype_entry *)malloc(sizeof(*newtype));
		if (newtype == nullptr)
		{
			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 != nullptr; 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 = nullptr;
		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 != nullptr; block = nextblock)
	{
		nextblock = block->next;
		free(block);
	}

	/* free all types */
	for (type = pool->typelist; type != nullptr; 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 == nullptr)
	{
		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 == nullptr)
	{
		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 == nullptr)
	{
		object_entry_block *block;
		int entrynum;

		/* if we need a new block, allocate that now */
		block = (object_entry_block *)malloc(sizeof(*block));
		if (block == nullptr)
			return nullptr;
		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 != nullptr)
		pool->globallist->globalprev = entry;
	entry->globalprev = nullptr;
	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 != nullptr; 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 != nullptr)
				entry->globalprev->globalnext = entry->globalnext;
			if (entry->globalnext != nullptr)
				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 nullptr;
}


/*-------------------------------------------------
    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 != nullptr; 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 == nullptr)
		return nullptr;
	memset(iter, 0, sizeof(*iter));

	/* fill it in */
	iter->pool = pool;
	iter->type = type;
	iter->last = nullptr;
	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 == nullptr)
		iter->last = iter->pool->globallist;
	else
		iter->last = iter->last->globalnext;

	/* stop when we get one */
	if (iter->last != nullptr)
	{
		if (objectptr != nullptr)
			*objectptr = iter->last;
		if (sizeptr != nullptr)
			*sizeptr = iter->last->size;
		if (typeptr != nullptr)
			*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 != nullptr)
		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 != nullptr)
		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 != nullptr)
	{
		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
-------------------------------------------------*/

/**
 * @fn  int test_memory_pools(void)
 *
 * @brief   Tests memory pools.
 *
 * @return  An int.
 */

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;
}