From 9e42653f09a27b5f6fdb3f130a5da31bc2f019de Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Sat, 19 Jul 2014 00:08:30 -0400 Subject: [PATCH] Added reference counting to list implementation --- premake4.lua | 41 +++++++++++++------------- source/list/list.c | 63 +++++++++++++++++----------------------- source/list/list.h | 37 ++++------------------- source/mem/mem.c | 60 ++++++++++++++++++++++++++++++++++++++ source/mem/mem.h | 71 +++++++++++++++++++++++++++++++++++++++++++++ source/vector/vec.c | 4 +-- 6 files changed, 186 insertions(+), 90 deletions(-) create mode 100644 source/mem/mem.c create mode 100644 source/mem/mem.h diff --git a/premake4.lua b/premake4.lua index 36e5da4..8560e02 100644 --- a/premake4.lua +++ b/premake4.lua @@ -13,29 +13,30 @@ project "cds" language "C" location "build" files { "source/**.*" } + includedirs { "source/**" } -project "tests" - kind "ConsoleApp" - language "C++" - location "build" - links { "UnitTest++", "cds" } - includedirs { "source/*", "tools/UnitTest++/**" } - files { "tests/**.c*" } - postbuildcommands { "./tests.exe" } +--project "tests" +-- kind "ConsoleApp" +-- language "C++" +-- location "build" +-- links { "UnitTest++", "cds" } +-- includedirs { "source/*", "tools/UnitTest++/**" } +-- files { "tests/**.c*" } +-- postbuildcommands { "./tests.exe" } ------------------------------------------------------------------------------- -- UnitTest++ - A C++ unit testing library ------------------------------------------------------------------------------- -project "UnitTest++" - kind "SharedLib" - language "C++" - location "build" - files { - "tools/UnitTest++/src/*.*", - } - if os.is "windows" then - files { "tools/UnitTest++/src/Win32/**.*" } - else - files { "tools/UnitTest++/src/Posix/**.*" } - end +--project "UnitTest++" +-- kind "SharedLib" +-- language "C++" +-- location "build" +-- files { +-- "tools/UnitTest++/src/*.*", +-- } +-- if os.is "windows" then +-- files { "tools/UnitTest++/src/Win32/**.*" } +-- else +-- files { "tools/UnitTest++/src/Posix/**.*" } +-- end diff --git a/source/list/list.c b/source/list/list.c index 67f3100..7642362 100644 --- a/source/list/list.c +++ b/source/list/list.c @@ -1,9 +1,14 @@ #include #include "list.h" +#include "mem.h" + +static void list_free(void* p_list); + +static void list_node_free(void* p_node); list_t* list_new(void) { - list_t* list = (list_t*)malloc( sizeof( list_t ) ); + list_t* list = (list_t*)mem_allocate(sizeof(list_t), NULL); list->head = NULL; list->tail = NULL; return list; @@ -11,33 +16,12 @@ list_t* list_new(void) list_node_t* list_new_node(void* contents) { - list_node_t* node = (list_node_t*)malloc( sizeof( list_node_t ) ); + list_node_t* node = (list_node_t*)mem_allocate(sizeof(list_node_t), NULL); node->contents = contents; node->next = NULL; return node; } -void list_free(list_t* list, bool free_contents) -{ - list_node_t* node = list->head; - while( NULL != node ) - { - list_node_t* next = node->next; - list_free_node( node, free_contents ); - node = next; - } - free( list ); -} - -void list_free_node(list_node_t* node, bool free_contents) -{ - if( free_contents ) - { - free( node->contents ); - } - free( node ); -} - list_node_t* list_front( list_t* list ) { return list->head; @@ -65,7 +49,6 @@ bool list_empty(list_t* list) return ((NULL == list->head) && (NULL == list->tail)); } - list_node_t* list_at(list_t* list, size_t index) { list_node_t* node = NULL; @@ -176,7 +159,7 @@ list_node_t* list_insert( list_t* list, size_t index, void* contents) return new_node; } -list_node_t* list_delete( list_t* list, size_t index, bool free_contents) +list_node_t* list_delete( list_t* list, size_t index) { list_node_t* node = NULL; @@ -185,7 +168,8 @@ list_node_t* list_delete( list_t* list, size_t index, bool free_contents) node = list_pop_front(list); if (NULL != node) { - list_free_node(node,free_contents); + node->next = NULL; + mem_release(node); node = list_front(list); } } @@ -200,7 +184,8 @@ list_node_t* list_delete( list_t* list, size_t index, bool free_contents) { list->tail = prev; } - list_free_node(node,free_contents); + node->next = NULL; + mem_release(node); node = prev->next; } } @@ -208,17 +193,23 @@ list_node_t* list_delete( list_t* list, size_t index, bool free_contents) return node; } -list_t* list_clear(list_t* list, bool free_contents) +void list_clear(list_t* list) { - list_node_t* node = list->head; - while(NULL != node) - { - list_node_t* next = node->next; - list_free_node(node,free_contents); - node = next; - } + mem_release((void*)list->head); list->head = NULL; list->tail = NULL; - return list; } +static void list_free(void* p_list) +{ + if (NULL != ((list_t*)p_list)->head) + mem_release(((list_t*)p_list)->head); +} + +static void list_node_free(void* p_node) +{ + if (NULL != ((list_node_t*)p_node)->contents) + mem_release(((list_node_t*)p_node)->contents); + if (NULL != ((list_node_t*)p_node)->next) + mem_release(((list_node_t*)p_node)->next); +} diff --git a/source/list/list.h b/source/list/list.h index 5a146c2..029c4f3 100644 --- a/source/list/list.h +++ b/source/list/list.h @@ -41,28 +41,6 @@ extern list_t* list_new(void); */ list_node_t* list_new_node(void* contents); -/** - * @brief Frees all memory used by a linked list. - * - * This function loops through the supplied list and frees all nodes. - * Also frees contents if free_contents is passed a non-zero value. - * - * @param list The list to be freed. - * @param free_contents Whether or not to also free the contents of each node. - **/ -void list_free(list_t* list, bool free_contents); - -/** - * @brief Frees all memory used by a node. - * - * This function frees all memory allocated to a node. Also frees contents if - * the free_contents is 1. - * - * @param node - * @param free_contents - */ -void list_free_node(list_node_t* node, bool free_contents); - /** * @brief Returns pointer to first node in the list * @@ -147,7 +125,7 @@ list_node_t* list_push_back( list_t* list, void* contents ); * This function removes the first node from the list and frees it's associated * memory. * - * @param list The lsit to operate on. + * @param list The lsit to operate on. * * @return Pointer to the newly added node. **/ @@ -159,7 +137,7 @@ list_node_t* list_pop_front( list_t* list ); * This function removes the last node from the list and frees it's associated * memory. * - * @param list The list to operate on. + * @param list The list to operate on. * * @return Pointer to the newly added node. **/ @@ -185,26 +163,21 @@ list_node_t* list_insert( list_t* list, size_t index, void* contents); * * This function traverses the list to the desired index and frees the memory * allocated for that node. If the deleted node has a child then the child is - * reattached to the deleted node's parent. If free_contents is passed a - * non-zero value then the node's contents pointer is also freed. + * reattached to the deleted node's parent. * * @param list The list to operate on. * @param index The index of the node to delete. - * @param free_contents Whether or not to also free the contents of the node. * * @return Pointer to the node that is now at the supplied index. **/ -list_node_t* list_delete( list_t* list, size_t index, bool free_contents); +list_node_t* list_delete(list_t* list, size_t index); /** * @brief Deletes all elements in the provided list * * @param list The list to be cleared - * @param free_contents Whether or not to also free the contents of every node. - * - * @return A pointer to the cleared list. */ -list_t* list_clear(list_t* list, bool free_contents); +void list_clear(list_t* list); #ifdef __cplusplus } diff --git a/source/mem/mem.c b/source/mem/mem.c new file mode 100644 index 0000000..f1b2d86 --- /dev/null +++ b/source/mem/mem.c @@ -0,0 +1,60 @@ +#include "mem.h" +#include + +typedef struct { + int refcount; + destructor_t p_finalize; +} obj_t; + +typedef struct { + intptr_t val; +} box_t; + +void* mem_allocate(size_t size, destructor_t p_destruct_fn) +{ + obj_t* p_obj = (obj_t*)malloc(sizeof(obj_t) + size); + p_obj->refcount = 1; + p_obj->p_finalize = p_destruct_fn; + return (void*)(p_obj+1); +} + +void mem_retain(void* p_obj) +{ + obj_t* p_hdr = (((obj_t*)p_obj)-1); + p_hdr->refcount += 1; +} + +void mem_release(void* p_obj) +{ + obj_t* p_hdr = (((obj_t*)p_obj)-1); + p_hdr->refcount -= 1; + if(p_hdr->refcount < 1) + { + if(p_hdr->p_finalize) + { + p_hdr->p_finalize(p_obj); + } + free(p_hdr); + } +} + +void mem_autorelease(void* p_obj) +{ +} + +void mem_releaseall(void) +{ +} + +void* mem_box(intptr_t val) +{ + box_t* p_box = (box_t*)mem_allocate(sizeof(box_t), NULL); + p_box->val = val; + return (void*)p_box; +} + +intptr_t mem_unbox(void* p_box) +{ + return ((box_t*)p_box)->val; +} + diff --git a/source/mem/mem.h b/source/mem/mem.h new file mode 100644 index 0000000..3d99bb7 --- /dev/null +++ b/source/mem/mem.h @@ -0,0 +1,71 @@ +/** + @file mem.h + @brief TODO: Describe this file + $Revision$ + $HeadURL$ + */ +#ifndef MEM_H +#define MEM_H + +#include +#include + +/** A function pointer for object destructors */ +typedef void (*destructor_t)(void* p_val); + +/** + * @brief Allocates a new reference counted object of the given size which will + * be destructed with the given function before it's memory is reclaimed. + * + * @param size The number of bytes to allocate for this object. + * @param p_destruct_fn The function to call when reclaiming this object. + * + * @return Pointer to the newly allocated object + */ +void* mem_allocate(size_t size, destructor_t p_destruct_fn); + +/** + * @brief Increments the reference count for the given object. + * + * @param p_obj The object to be retained. + */ +void mem_retain(void* p_obj); + +/** + * @brief Decrements the reference count for a given object. + * + * @param p_obj The object to be released. + */ +void mem_release(void* p_obj); + +/** + * @brief Schedules an object to be released at a later time when more convenient. + * + * @param p_obj The object to be released. + */ +void mem_autorelease(void* p_obj); + +/** + * @brief Release all objects scheduled to be released reclaiming their memory + * if necessary. + */ +void mem_releaseall(void); + +/** + * @brief Create a reference counted box holding the given value so that it can + * be placed in a container. + * + * @param val The value to be boxed. + * + * @return The pointer to the newly allocated box. + */ +void* mem_box(intptr_t val); + +/** + * @brief Release a reference counted box and return it's contained value. + * + * @return The boxed value. + */ +intptr_t mem_unbox(void* p_box); + +#endif /* MEM_H */ diff --git a/source/vector/vec.c b/source/vector/vec.c index 298f685..591d134 100644 --- a/source/vector/vec.c +++ b/source/vector/vec.c @@ -71,7 +71,7 @@ void vec_resize(vec_t* p_vec, size_t size, void* data) if (size > p_vec->size) { vec_reserve(p_vec,vec_next_capacity(size)); - for (p_vec->size; p_vec->size < size; p_vec->size++) + for (; p_vec->size < size; p_vec->size++) { p_vec->p_buffer[ p_vec->size ] = data; } @@ -155,7 +155,7 @@ bool vec_insert(vec_t* p_vec, size_t index, size_t num_elements, ...) /* insert the new items */ va_start(elements, num_elements); new_size = index + num_elements; - for (index; index < new_size; index++) + for (; index < new_size; index++) { p_vec->p_buffer[index] = va_arg(elements,void*); } -- 2.54.0