Sun, 09 Apr 2023 19:03:58 +0200
refactoring of collections to make use of destructors in map implementations
src/CMakeLists.txt | file | annotate | diff | comparison | revisions | |
src/array_list.c | file | annotate | diff | comparison | revisions | |
src/cx/allocator.h | file | annotate | diff | comparison | revisions | |
src/cx/array_list.h | file | annotate | diff | comparison | revisions | |
src/cx/collection.h | file | annotate | diff | comparison | revisions | |
src/cx/hash_map.h | file | annotate | diff | comparison | revisions | |
src/cx/linked_list.h | file | annotate | diff | comparison | revisions | |
src/cx/list.h | file | annotate | diff | comparison | revisions | |
src/cx/map.h | file | annotate | diff | comparison | revisions | |
src/cx/string.h | file | annotate | diff | comparison | revisions | |
src/hash_map.c | file | annotate | diff | comparison | revisions | |
src/linked_list.c | file | annotate | diff | comparison | revisions | |
src/list.c | file | annotate | diff | comparison | revisions | |
tests/test_list.cpp | file | annotate | diff | comparison | revisions | |
tests/test_map.cpp | file | annotate | diff | comparison | revisions |
--- a/src/CMakeLists.txt Fri Apr 07 11:30:28 2023 +0200 +++ b/src/CMakeLists.txt Sun Apr 09 19:03:58 2023 +0200 @@ -19,6 +19,7 @@ cx/string.h cx/allocator.h cx/iterator.h + cx/collection.h cx/list.h cx/array_list.h cx/linked_list.h
--- a/src/array_list.c Fri Apr 07 11:30:28 2023 +0200 +++ b/src/array_list.c Sun Apr 09 19:03:58 2023 +0200 @@ -150,6 +150,7 @@ typedef struct { struct cx_list_s base; void *data; + size_t capacity; struct cx_array_reallocator_s reallocator; } cx_array_list; @@ -186,17 +187,17 @@ // do we need to move some elements? if (index < list->size) { char const *first_to_move = (char const *) arl->data; - first_to_move += index * list->itemsize; + first_to_move += index * list->item_size; size_t elems_to_move = list->size - index; size_t start_of_moved = index + n; if (CX_ARRAY_COPY_SUCCESS != cx_array_copy( &arl->data, &list->size, - &list->capacity, + &arl->capacity, start_of_moved, first_to_move, - list->itemsize, + list->item_size, elems_to_move, &arl->reallocator )) { @@ -213,10 +214,10 @@ if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( &arl->data, &list->size, - &list->capacity, + &arl->capacity, index, array, - list->itemsize, + list->item_size, n, &arl->reallocator )) { @@ -249,7 +250,7 @@ ); if (result == 0 && prepend != 0) { iter->index++; - iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize; + iter->elem_handle = ((char *) iter->elem_handle) + list->item_size; } return result; } else { @@ -271,11 +272,7 @@ } // content destruction - if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { - char *ptr = arl->data; - ptr += index * list->itemsize; - cx_list_invoke_destructor(list, ptr); - } + cx_invoke_destructor(list, ((char*)arl->data) + index * list->item_size); // short-circuit removal of last element if (index == list->size - 1) { @@ -287,10 +284,10 @@ int result = cx_array_copy( &arl->data, &list->size, - &list->capacity, + &arl->capacity, index, - ((char *) arl->data) + (index + 1) * list->itemsize, - list->itemsize, + ((char *) arl->data) + (index + 1) * list->item_size, + list->item_size, list->size - index - 1, &arl->reallocator ); @@ -307,26 +304,20 @@ cx_array_list *arl = (cx_array_list *) list; char *ptr = arl->data; - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - for (size_t i = 0; i < list->size; i++) { - cx_list_invoke_simple_destructor(list, ptr); - ptr += list->itemsize; - } - break; + if (list->simple_destructor) { + for (size_t i = 0; i < list->size; i++) { + cx_invoke_simple_destructor(list, ptr); + ptr += list->item_size; } - case CX_DESTRUCTOR_ADVANCED: { - for (size_t i = 0; i < list->size; i++) { - cx_list_invoke_advanced_destructor(list, ptr); - ptr += list->itemsize; - } - break; + } + if (list->advanced_destructor) { + for (size_t i = 0; i < list->size; i++) { + cx_invoke_advanced_destructor(list, ptr); + ptr += list->item_size; } - case CX_DESTRUCTOR_NONE: - break; // nothing } - memset(arl->data, 0, list->size * list->itemsize); + memset(arl->data, 0, list->size * list->item_size); list->size = 0; } @@ -337,7 +328,7 @@ ) { if (i >= list->size || j >= list->size) return 1; cx_array_list *arl = (cx_array_list *) list; - cx_array_swap(arl->data, list->itemsize, i, j); + cx_array_swap(arl->data, list->item_size, i, j); return 0; } @@ -348,7 +339,7 @@ if (index < list->size) { cx_array_list const *arl = (cx_array_list const *) list; char *space = arl->data; - return space + index * list->itemsize; + return space + index * list->item_size; } else { return NULL; } @@ -365,7 +356,7 @@ if (0 == list->cmpfunc(elem, cur)) { return i; } - cur += list->itemsize; + cur += list->item_size; } return list->size; @@ -375,7 +366,7 @@ assert(list->cmpfunc != NULL); qsort(((cx_array_list *) list)->data, list->size, - list->itemsize, + list->item_size, list->cmpfunc ); } @@ -393,8 +384,8 @@ if (d != 0) { return d; } - left += list->itemsize; - right += other->itemsize; + left += list->item_size; + right += other->item_size; } return 0; } else { @@ -407,7 +398,7 @@ void *data = ((cx_array_list const *) list)->data; size_t half = list->size / 2; for (size_t i = 0; i < half; i++) { - cx_array_swap(data, list->itemsize, i, list->size - 1 - i); + cx_array_swap(data, list->item_size, i, list->size - 1 - i); } } @@ -433,7 +424,7 @@ iter->index++; iter->elem_handle = ((char *) iter->elem_handle) - + ((struct cx_list_s const *) iter->src_handle)->itemsize; + + ((struct cx_list_s const *) iter->src_handle)->item_size; } } @@ -448,7 +439,7 @@ iter->index--; if (iter->index < list->base.size) { iter->elem_handle = ((char *) list->data) - + iter->index * list->base.itemsize; + + iter->index * list->base.item_size; } } @@ -500,7 +491,7 @@ CxList *cxArrayListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size, size_t initial_capacity ) { @@ -514,10 +505,10 @@ list->base.cl = &cx_array_list_class; list->base.allocator = allocator; list->base.cmpfunc = comparator; - list->base.capacity = initial_capacity; + list->capacity = initial_capacity; if (item_size > 0) { - list->base.itemsize = item_size; + list->base.item_size = item_size; } else { item_size = sizeof(void*); cxListStorePointers((CxList *) list);
--- a/src/cx/allocator.h Fri Apr 07 11:30:28 2023 +0200 +++ b/src/cx/allocator.h Sun Apr 09 19:03:58 2023 +0200 @@ -133,41 +133,6 @@ ) __attribute__((__nonnull__(2))); /** - * Structure holding an advanced destructor function and the desired payload. - * Invocations of func should use data as first argument. - */ -typedef struct { - /** - * A pointer to the data that SHALL be used to invoke func. - */ - void *data; - /** - * A pointer to the function to invoke. - */ - cx_destructor_func2 func; -} cx_advanced_destructor; - -/** - * Specifies the type of destructor to use. - */ -enum cx_destructor_type { - /** - * Do not use a destructor function. - */ - CX_DESTRUCTOR_NONE, - /** - * Use a simple destructor. - * @see cx_destructor_func - */ - CX_DESTRUCTOR_SIMPLE, - /** - * Use an advanced destructor. - * @see cx_advanced_destructor - */ - CX_DESTRUCTOR_ADVANCED -}; - -/** * Allocate \p n bytes of memory. * * @param allocator the allocator
--- a/src/cx/array_list.h Fri Apr 07 11:30:28 2023 +0200 +++ b/src/cx/array_list.h Sun Apr 09 19:03:58 2023 +0200 @@ -165,7 +165,7 @@ */ CxList *cxArrayListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size, size_t initial_capacity );
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/cx/collection.h Sun Apr 09 19:03:58 2023 +0200 @@ -0,0 +1,139 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 THE COPYRIGHT HOLDER OR CONTRIBUTORS 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. + */ +/** + * \file collection.h + * \brief Common definitions for various collection implementations. + * \author Mike Becker + * \author Olaf Wintermann + * \version 3.0 + * \copyright 2-Clause BSD License + */ + +#ifndef UCX_COLLECTION_H +#define UCX_COLLECTION_H + +#include "common.h" +#include "allocator.h" +#include "iterator.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * Special constant used for creating collections that are storing pointers. + */ +#define CX_STORE_POINTERS 0 + +/** + * A comparator function comparing two collection elements. + */ +typedef int(*cx_compare_func)( + void const *left, + void const *right +); + +/** + * Use this macro to declare common members for a collection structure. + */ +#define CX_COLLECTION_MEMBERS \ + /** \ + * The allocator to use. \ + */ \ + CxAllocator const *allocator; \ + /** \ + * The comparator function for the elements. \ + */ \ + cx_compare_func cmpfunc; \ + /** \ + * The size of each element. \ + */ \ + size_t item_size; \ + /** \ + * The number of currently stored elements. \ + */ \ + size_t size; \ + /** \ + * An optional simple destructor for the collection's elements. \ + * \ + * @attention Read the documentation of the particular collection implementation \ + * whether this destructor shall only destroy the contents or also free the memory. \ + */ \ + cx_destructor_func simple_destructor; \ + /** \ + * An optional advanced destructor for the collection's elements. \ + * \ + * @attention Read the documentation of the particular collection implementation \ + * whether this destructor shall only destroy the contents or also free the memory. \ + */ \ + cx_destructor_func2 advanced_destructor; \ + /** \ + * The pointer to additional data that is passed to the advanced destructor. \ + */ \ + void *destructor_data; \ + /** \ + * Indicates if this instance of a collection is supposed to store pointers \ + * instead of copies of the actual objects. \ + */ \ + bool store_pointer; + +/** + * Invokes the simple destructor function for a specific element. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. + * + * @param c the collection + * @param e the element + */ +#define cx_invoke_simple_destructor(c, e) \ + (c)->simple_destructor((c)->store_pointer ? (*((void **) e)) : e) + +/** + * Invokes the advanced destructor function for a specific element. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. + * + * @param c the collection + * @param e the element + */ +#define cx_invoke_advanced_destructor(c, e) \ + (c)->advanced_destructor((c)->destructor_data, \ + (c)->store_pointer ? (*((void **) e)) : e) + + +#define cx_invoke_destructor(c, e) \ + if ((c)->simple_destructor) cx_invoke_simple_destructor(c,e); \ + if ((c)->advanced_destructor) cx_invoke_advanced_destructor(c,e) + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif // UCX_COLLECTION_H
--- a/src/cx/hash_map.h Fri Apr 07 11:30:28 2023 +0200 +++ b/src/cx/hash_map.h Sun Apr 09 19:03:58 2023 +0200 @@ -70,7 +70,7 @@ * * If \p buckets is zero, an implementation defined default will be used. * - * If \p itemsize is CX_STORE_POINTERS, the created map will be created as if + * If \p item_size is CX_STORE_POINTERS, the created map will be created as if * cxMapStorePointers() was called immediately after creation. * * @note Iterators provided by this hash map implementation provide the remove operation.
--- a/src/cx/linked_list.h Fri Apr 07 11:30:28 2023 +0200 +++ b/src/cx/linked_list.h Sun Apr 09 19:03:58 2023 +0200 @@ -66,7 +66,7 @@ */ CxList *cxLinkedListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size ); @@ -124,7 +124,7 @@ void const *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, - CxListComparator cmp_func, + cx_compare_func cmp_func, void const *elem ) __attribute__((__nonnull__)); @@ -368,7 +368,7 @@ ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - CxListComparator cmp_func + cx_compare_func cmp_func ) __attribute__((__nonnull__(1, 6))); @@ -390,7 +390,7 @@ void const *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, - CxListComparator cmp_func + cx_compare_func cmp_func ) __attribute__((__nonnull__(5))); /**
--- a/src/cx/list.h Fri Apr 07 11:30:28 2023 +0200 +++ b/src/cx/list.h Sun Apr 09 19:03:58 2023 +0200 @@ -37,29 +37,12 @@ #ifndef UCX_LIST_H #define UCX_LIST_H -#include "common.h" -#include "allocator.h" -#include "iterator.h" +#include "collection.h" #ifdef __cplusplus extern "C" { #endif -#ifndef CX_STORE_POINTERS -/** - * Special constant used for creating collections that are storing pointers. - */ -#define CX_STORE_POINTERS 0 -#endif - -/** - * A comparator function comparing two list elements. - */ -typedef int(*CxListComparator)( - void const *left, - void const *right -); - /** * List class type. */ @@ -69,6 +52,7 @@ * Structure for holding the base data of a list. */ struct cx_list_s { + CX_COLLECTION_MEMBERS /** * The list class definition. */ @@ -77,50 +61,6 @@ * The actual implementation in case the list class is delegating. */ cx_list_class const *climpl; - /** - * The allocator to use. - */ - CxAllocator const *allocator; - /** - * The comparator function for the elements. - */ - CxListComparator cmpfunc; - /** - * The size of each element (payload only). - */ - size_t itemsize; - /** - * The size of the list (number of currently stored elements). - */ - size_t size; - /** - * The capacity of the list (maximum number of elements). - */ - size_t capacity; - union { - /** - * An optional simple destructor for the list contents that admits the free() interface. - * - * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE. - * - * @attention Read the documentation of the particular list implementation - * whether this destructor shall only destroy the contents or also free the memory. - */ - cx_destructor_func simple_destructor; - /** - * An optional advanced destructor for the list contents providing additional data. - * - * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED. - * - * @attention Read the documentation of the particular list implementation - * whether this destructor shall only destroy the contents or also free the memory. - */ - cx_advanced_destructor advanced_destructor; - }; - /** - * The type of destructor to use. - */ - enum cx_destructor_type content_destructor_type; }; /** @@ -234,51 +174,6 @@ typedef struct cx_list_s CxList; /** - * Invokes the configured destructor function for a specific element. - * - * Usually only used by list implementations. There should be no need - * to invoke this function manually. - * - * @param list the list - * @param elem the element - */ -__attribute__((__nonnull__)) -void cx_list_invoke_destructor( - struct cx_list_s const *list, - void *elem -); - -/** - * Invokes the simple destructor function for a specific element. - * - * Usually only used by list implementations. There should be no need - * to invoke this function manually. - * - * @param list the list - * @param elem the element - */ -__attribute__((__nonnull__)) -void cx_list_invoke_simple_destructor( - struct cx_list_s const *list, - void *elem -); - -/** - * Invokes the advanced destructor function for a specific element. - * - * Usually only used by list implementations. There should be no need - * to invoke this function manually. - * - * @param list the list - * @param elem the element - */ -__attribute__((__nonnull__)) -void cx_list_invoke_advanced_destructor( - struct cx_list_s const *list, - void *elem -); - -/** * Advises the list to store copies of the objects (default mode of operation). * * Retrieving objects from this list will yield pointers to the copies stored @@ -309,11 +204,24 @@ * Returns true, if this list is storing pointers instead of the actual data. * * @param list - * @return + * @return true, if this list is storing pointers * @see cxListStorePointers() */ __attribute__((__nonnull__)) -bool cxListIsStoringPointers(CxList const *list); +static inline bool cxListIsStoringPointers(CxList const *list) { + return list->store_pointer; +} + +/** + * Returns the number of elements currently stored in the list. + * + * @param list the list + * @return the number of currently stored elements + */ +__attribute__((__nonnull__)) +static inline size_t cxListSize(CxList const *list) { + return list->size; +} /** * Adds an item to the end of the list.
--- a/src/cx/map.h Fri Apr 07 11:30:28 2023 +0200 +++ b/src/cx/map.h Sun Apr 09 19:03:58 2023 +0200 @@ -37,22 +37,13 @@ #ifndef UCX_MAP_H #define UCX_MAP_H -#include "common.h" -#include "allocator.h" -#include "iterator.h" +#include "collection.h" #include "hash_key.h" #ifdef __cplusplus extern "C" { #endif -#ifndef CX_STORE_POINTERS -/** - * Special constant used for creating collections that are storing pointers. - */ -#define CX_STORE_POINTERS 0 -#endif - /** Type for the UCX map. */ typedef struct cx_map_s CxMap; @@ -73,7 +64,7 @@ /** * The size of an element. */ - size_t itemsize; + size_t item_size; /** * True, if this map shall store pointers instead * of copies of objects. @@ -205,7 +196,7 @@ __attribute__((__nonnull__)) static inline void cxMapStorePointers(CxMap *map) { map->store_pointers = true; - map->itemsize = sizeof(void *); + map->item_size = sizeof(void *); }
--- a/src/cx/string.h Fri Apr 07 11:30:28 2023 +0200 +++ b/src/cx/string.h Sun Apr 09 19:03:58 2023 +0200 @@ -660,7 +660,7 @@ /** * Compares two strings. * - * This function has a compatible signature for the use as a CxListComparator. + * This function has a compatible signature for the use as a cx_compare_func. * * @param s1 the first string * @param s2 the second string @@ -676,7 +676,7 @@ /** * Compares two strings ignoring case. * - * This function has a compatible signature for the use as a CxListComparator. + * This function has a compatible signature for the use as a cx_compare_func. * * @param s1 the first string * @param s2 the second string
--- a/src/hash_map.c Fri Apr 07 11:30:28 2023 +0200 +++ b/src/hash_map.c Sun Apr 09 19:03:58 2023 +0200 @@ -103,13 +103,13 @@ if (map->store_pointers) { memcpy(elm->data, &value, sizeof(void *)); } else { - memcpy(elm->data, value, map->itemsize); + memcpy(elm->data, value, map->item_size); } } else { // allocate new element struct cx_hash_map_element_s *e = cxMalloc( allocator, - sizeof(struct cx_hash_map_element_s) + map->itemsize + sizeof(struct cx_hash_map_element_s) + map->item_size ); if (e == NULL) { return -1; @@ -119,7 +119,7 @@ if (map->store_pointers) { memcpy(e->data, &value, sizeof(void *)); } else { - memcpy(e->data, value, map->itemsize); + memcpy(e->data, value, map->item_size); } // copy the key @@ -434,10 +434,10 @@ if (itemsize > 0) { map->base.store_pointers = false; - map->base.itemsize = itemsize; + map->base.item_size = itemsize; } else { map->base.store_pointers = true; - map->base.itemsize = sizeof(void *); + map->base.item_size = sizeof(void *); } return (CxMap *) map;
--- a/src/linked_list.c Fri Apr 07 11:30:28 2023 +0200 +++ b/src/linked_list.c Sun Apr 09 19:03:58 2023 +0200 @@ -60,7 +60,7 @@ void const *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, - CxListComparator cmp_func, + cx_compare_func cmp_func, void const *elem ) { assert(start != NULL); @@ -291,7 +291,7 @@ void *ls, void *le, void *re, - CxListComparator cmp_func + cx_compare_func cmp_func ) { void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? @@ -343,7 +343,7 @@ ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - CxListComparator cmp_func + cx_compare_func cmp_func ) { assert(begin != NULL); assert(loc_next >= 0); @@ -403,7 +403,7 @@ void const *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, - CxListComparator cmp_func + cx_compare_func cmp_func ) { void const *left = begin_left, *right = begin_right; @@ -494,14 +494,14 @@ // create the new new_node cx_linked_list_node *new_node = cxMalloc(list->allocator, - sizeof(cx_linked_list_node) + list->itemsize); + sizeof(cx_linked_list_node) + list->item_size); // sortir if failed if (new_node == NULL) return 1; // initialize new new_node new_node->prev = new_node->next = NULL; - memcpy(new_node->payload, elem, list->itemsize); + memcpy(new_node->payload, elem, list->item_size); // insert cx_linked_list *ll = (cx_linked_list *) list; @@ -542,7 +542,7 @@ // we can add the remaining nodes and immedately advance to the inserted node char const *source = array; for (size_t i = 1; i < n; i++) { - source += list->itemsize; + source += list->item_size; if (0 != cx_ll_insert_at(list, node, source)) { return i; } @@ -570,9 +570,7 @@ if (node == NULL) return 1; // element destruction - if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { - cx_list_invoke_destructor(list, node->payload); - } + cx_invoke_destructor(list, node->payload); // remove cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, @@ -592,38 +590,12 @@ cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_node *node = ll->begin; - - // looks super redundant, but avoids repeatedly checking - // the destructor type for each element - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - while (node != NULL) { - cx_list_invoke_simple_destructor(list, node->payload); - cx_linked_list_node *next = node->next; - cxFree(list->allocator, node); - node = next; - } - break; - } - case CX_DESTRUCTOR_ADVANCED: { - while (node != NULL) { - cx_list_invoke_advanced_destructor(list, node->payload); - cx_linked_list_node *next = node->next; - cxFree(list->allocator, node); - node = next; - } - break; - } - case CX_DESTRUCTOR_NONE: { - while (node != NULL) { - cx_linked_list_node *next = node->next; - cxFree(list->allocator, node); - node = next; - } - break; - } + while (node != NULL) { + cx_invoke_destructor(list, node->payload); + cx_linked_list_node *next = node->next; + cxFree(list->allocator, node); + node = next; } - ll->begin = ll->end = NULL; list->size = 0; } @@ -708,7 +680,7 @@ } } - if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { + if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { cx_linked_list_node *prev = nleft->prev; cx_linked_list_node *next = nright->next; cx_linked_list_node *midstart = nleft->next; @@ -740,9 +712,9 @@ } else { // swap payloads to avoid relinking char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; - memcpy(buf, nleft->payload, list->itemsize); - memcpy(nleft->payload, nright->payload, list->itemsize); - memcpy(nright->payload, buf, list->itemsize); + memcpy(buf, nleft->payload, list->item_size); + memcpy(nleft->payload, nright->payload, list->item_size); + memcpy(nright->payload, buf, list->item_size); } return 0; @@ -803,9 +775,7 @@ cx_linked_list *ll = iter->src_handle; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; - if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { - cx_list_invoke_destructor(list, node->payload); - } + cx_invoke_destructor(list, node->payload); cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); list->size--; @@ -828,9 +798,7 @@ cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->prev; iter->index--; - if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { - cx_list_invoke_destructor(list, node->payload); - } + cx_invoke_destructor(list, node->payload); cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); list->size--; @@ -927,7 +895,7 @@ CxList *cxLinkedListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size ) { if (allocator == NULL) { @@ -940,10 +908,9 @@ list->base.cl = &cx_linked_list_class; list->base.allocator = allocator; list->base.cmpfunc = comparator; - list->base.capacity = SIZE_MAX; if (item_size > 0) { - list->base.itemsize = item_size; + list->base.item_size = item_size; } else { cxListStorePointers((CxList *) list); }
--- a/src/list.c Fri Apr 07 11:30:28 2023 +0200 +++ b/src/list.c Sun Apr 09 19:03:58 2023 +0200 @@ -32,7 +32,7 @@ // <editor-fold desc="Store Pointers Functionality"> -static _Thread_local CxListComparator cx_pl_cmpfunc_impl; +static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; static int cx_pl_cmpfunc( void const *l, @@ -179,6 +179,7 @@ }; void cxListStoreObjects(CxList *list) { + list->store_pointer = false; if (list->climpl != NULL) { list->cl = list->climpl; list->climpl = NULL; @@ -186,75 +187,28 @@ } void cxListStorePointers(CxList *list) { - list->itemsize = sizeof(void *); + list->item_size = sizeof(void *); + list->store_pointer = true; list->climpl = list->cl; list->cl = &cx_pointer_list_class; } -bool cxListIsStoringPointers(CxList const *list) { - return list->climpl != NULL; -} - // </editor-fold> -void cx_list_invoke_destructor( - CxList const *list, - void *elem -) { - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - cx_list_invoke_simple_destructor(list, elem); - break; +void cxListDestroy(CxList *list) { + if (list->simple_destructor) { + CxIterator iter = cxListIterator(list); + cx_foreach(void*, elem, iter) { + // already correctly resolved pointer - immediately invoke dtor + list->simple_destructor(elem); } - case CX_DESTRUCTOR_ADVANCED: { - cx_list_invoke_advanced_destructor(list, elem); - break; - } - case CX_DESTRUCTOR_NONE: - break; // nothing - } -} - -void cx_list_invoke_simple_destructor( - CxList const *list, - void *elem -) { - if (cxListIsStoringPointers(list)) { - elem = *((void **) elem); } - list->simple_destructor(elem); -} - -void cx_list_invoke_advanced_destructor( - CxList const *list, - void *elem -) { - if (cxListIsStoringPointers(list)) { - elem = *((void **) elem); - } - list->advanced_destructor.func(list->advanced_destructor.data, elem); -} - -void cxListDestroy(CxList *list) { - switch (list->content_destructor_type) { - case CX_DESTRUCTOR_SIMPLE: { - CxIterator iter = cxListIterator(list); - cx_foreach(void*, elem, iter) { - // already correctly resolved pointer - immediately invoke dtor - list->simple_destructor(elem); - } - break; + if (list->advanced_destructor) { + CxIterator iter = cxListIterator(list); + cx_foreach(void*, elem, iter) { + // already correctly resolved pointer - immediately invoke dtor + list->advanced_destructor(list->destructor_data, elem); } - case CX_DESTRUCTOR_ADVANCED: { - CxIterator iter = cxListIterator(list); - cx_foreach(void*, elem, iter) { - // already correctly resolved pointer - immediately invoke dtor - list->advanced_destructor.func(list->advanced_destructor.data, elem); - } - break; - } - case CX_DESTRUCTOR_NONE: - break; // nothing } list->cl->destructor(list);
--- a/tests/test_list.cpp Fri Apr 07 11:30:28 2023 +0200 +++ b/tests/test_list.cpp Sun Apr 09 19:03:58 2023 +0200 @@ -592,8 +592,7 @@ ) { auto len = testdata_len; cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0); - EXPECT_EQ(list->size, len); - EXPECT_GE(list->capacity, list->size); + EXPECT_EQ(cxListSize(list), len); cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); cx_for_n (i, len) ++testdata.data[i]; if (as_pointer) { @@ -607,17 +606,16 @@ int a = 5, b = 47, c = 13, d = 42; EXPECT_NE(cxListInsert(list, 1, &a), 0); - EXPECT_EQ(list->size, 0); + EXPECT_EQ(cxListSize(list), 0); EXPECT_EQ(cxListInsert(list, 0, &a), 0); - EXPECT_EQ(list->size, 1); + EXPECT_EQ(cxListSize(list), 1); EXPECT_EQ(cxListInsert(list, 0, &b), 0); - EXPECT_EQ(list->size, 2); + EXPECT_EQ(cxListSize(list), 2); EXPECT_EQ(cxListInsert(list, 1, &c), 0); - EXPECT_EQ(list->size, 3); + EXPECT_EQ(cxListSize(list), 3); EXPECT_EQ(cxListInsert(list, 3, &d), 0); - ASSERT_EQ(list->size, 4); - EXPECT_GE(list->capacity, list->size); + ASSERT_EQ(cxListSize(list), 4); EXPECT_EQ(*(int *) cxListAt(list, 0), 47); EXPECT_EQ(*(int *) cxListAt(list, 1), 13); @@ -672,8 +670,7 @@ void verifyRemove(CxList *list) const { EXPECT_EQ(cxListRemove(list, 2), 0); EXPECT_EQ(cxListRemove(list, 4), 0); - EXPECT_EQ(list->size, testdata_len - 2); - EXPECT_GE(list->capacity, list->size); + EXPECT_EQ(cxListSize(list), testdata_len - 2); EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]); EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]); EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]); @@ -681,8 +678,7 @@ EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]); EXPECT_EQ(cxListRemove(list, 0), 0); - EXPECT_EQ(list->size, testdata_len - 3); - EXPECT_GE(list->capacity, list->size); + EXPECT_EQ(cxListSize(list), testdata_len - 3); EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]); EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]); @@ -691,7 +687,7 @@ static void verifyClear(CxList *list) { cxListClear(list); - EXPECT_EQ(0, list->size); + EXPECT_EQ(0, cxListSize(list)); } static unsigned destr_test_ctr; @@ -717,33 +713,33 @@ cxListRemove(list, 15); EXPECT_EQ(1, destr_test_ctr); EXPECT_EQ(testdata.data[15], destr_last_value + off); - EXPECT_EQ(testdata_len - destr_test_ctr, list->size); + EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); cxListRemove(list, 47); EXPECT_EQ(2, destr_test_ctr); EXPECT_EQ(testdata.data[48], destr_last_value + off); - EXPECT_EQ(testdata_len - destr_test_ctr, list->size); + EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); auto iter = cxListMutIteratorAt(list, 7); cxIteratorNext(iter); EXPECT_EQ(2, destr_test_ctr); EXPECT_EQ(testdata.data[48], destr_last_value + off); - EXPECT_EQ(testdata_len - destr_test_ctr, list->size); + EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); cxIteratorFlagRemoval(iter); cxIteratorNext(iter); EXPECT_EQ(3, destr_test_ctr); EXPECT_EQ(testdata.data[8], destr_last_value + off); - EXPECT_EQ(testdata_len - destr_test_ctr, list->size); + EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); iter = cxListMutBackwardsIteratorAt(list, 5); cxIteratorNext(iter); EXPECT_EQ(3, destr_test_ctr); EXPECT_EQ(testdata.data[8], destr_last_value + off); - EXPECT_EQ(testdata_len - destr_test_ctr, list->size); + EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); cxIteratorFlagRemoval(iter); cxIteratorNext(iter); EXPECT_EQ(4, destr_test_ctr); EXPECT_EQ(testdata.data[4], destr_last_value + off); - EXPECT_EQ(testdata_len - destr_test_ctr, list->size); + EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); cxListClear(list); EXPECT_EQ(testdata_len, destr_test_ctr); @@ -754,20 +750,18 @@ void verifySimpleDestructor(CxList *list) { destr_test_ctr = 0; - list->content_destructor_type = CX_DESTRUCTOR_SIMPLE; list->simple_destructor = simple_destr_test_fun; verifyAnyDestructor(list); } void verifyAdvancedDestructor(CxList *list) { destr_test_ctr = 0; - list->content_destructor_type = CX_DESTRUCTOR_ADVANCED; - list->advanced_destructor.func = advanced_destr_test_fun; + list->advanced_destructor = advanced_destr_test_fun; verifyAnyDestructor(list); } static void verifySwap(CxList *list) { - ASSERT_EQ(list->size, 0); + ASSERT_EQ(cxListSize(list), 0); int original[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; int swapped[16] = {8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13}; @@ -816,11 +810,11 @@ void verifyAt(CxList *list) const { auto len = testdata_len; - EXPECT_EQ(list->size, len); + EXPECT_EQ(cxListSize(list), len); cx_for_n (i, len) { EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); } - EXPECT_EQ(cxListAt(list, list->size), nullptr); + EXPECT_EQ(cxListAt(list, cxListSize(list)), nullptr); } void verifyFind(CxList *list) const { @@ -838,7 +832,7 @@ } int notinlist = -1; - EXPECT_EQ(list->size, cxListFind(list, ¬inlist)); + EXPECT_EQ(cxListSize(list), cxListFind(list, ¬inlist)); } void verifySort(CxList *list) const { @@ -856,7 +850,7 @@ EXPECT_EQ(*x, testdata.data[iter.index]); i++; } - ASSERT_EQ(i, list->size); + ASSERT_EQ(i, cxListSize(list)); iter = cxListBackwardsIterator(list); cx_foreach(int*, x, iter) { ASSERT_EQ(i - 1, iter.index); @@ -887,7 +881,7 @@ j++; } ASSERT_EQ(i, 0); - ASSERT_EQ(list->size, len / 2); + ASSERT_EQ(cxListSize(list), len / 2); cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]); } @@ -912,11 +906,11 @@ EXPECT_TRUE(cxIteratorValid(iter)); EXPECT_EQ(iter.index, 1); EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0); - iter = cxListMutIteratorAt(list, list->size); + iter = cxListMutIteratorAt(list, cxListSize(list)); cxListInsertBefore(&iter, &newdata[3]); EXPECT_FALSE(cxIteratorValid(iter)); EXPECT_EQ(iter.index, 9); - iter = cxListMutIteratorAt(list, list->size); + iter = cxListMutIteratorAt(list, cxListSize(list)); cxListInsertAfter(&iter, &newdata[4]); EXPECT_FALSE(cxIteratorValid(iter)); EXPECT_EQ(iter.index, 10); @@ -939,16 +933,16 @@ EXPECT_EQ(cxListCompare(left, right), 0); int x = 42; cxListAdd(left, &x); - ASSERT_GT(left->size, right->size); + ASSERT_GT(cxListSize(left), cxListSize(right)); EXPECT_GT(cxListCompare(left, right), 0); EXPECT_LT(cxListCompare(right, left), 0); cxListAdd(right, &x); - ASSERT_EQ(left->size, right->size); + ASSERT_EQ(cxListSize(left), cxListSize(right)); EXPECT_EQ(cxListCompare(left, right), 0); int a = 5, b = 10; cxListInsert(left, 15, &a); cxListInsert(right, 15, &b); - ASSERT_EQ(left->size, right->size); + ASSERT_EQ(cxListSize(left), cxListSize(right)); EXPECT_LT(cxListCompare(left, right), 0); EXPECT_GT(cxListCompare(right, left), 0); *(int *) cxListAt(left, 15) = 10; @@ -972,7 +966,7 @@ auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, 47)); EXPECT_FALSE(cxListIsStoringPointers(list)); cxListStorePointers(list); - EXPECT_EQ(list->itemsize, sizeof(void *)); + EXPECT_EQ(list->item_size, sizeof(void *)); EXPECT_NE(list->cl, nullptr); EXPECT_NE(list->climpl, nullptr); EXPECT_TRUE(cxListIsStoringPointers(list)); @@ -985,10 +979,11 @@ TEST_F(LinkedList, cxLinkedListCreate) { CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); ASSERT_NE(list, nullptr); - EXPECT_EQ(list->itemsize, sizeof(int)); - EXPECT_EQ(list->capacity, (size_t) -1); - EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE); - EXPECT_EQ(list->size, 0); + EXPECT_EQ(list->item_size, sizeof(int)); + EXPECT_EQ(list->simple_destructor, nullptr); + EXPECT_EQ(list->advanced_destructor, nullptr); + EXPECT_EQ(list->destructor_data, nullptr); + EXPECT_EQ(cxListSize(list), 0); EXPECT_EQ(list->allocator, &testingAllocator); EXPECT_EQ(list->cmpfunc, cx_cmp_int); EXPECT_FALSE(cxListIsStoringPointers(list)); @@ -997,30 +992,37 @@ TEST_F(LinkedList, cxLinkedListCreateSimple) { CxList *list = autofree(cxLinkedListCreateSimple(sizeof(int))); ASSERT_NE(list, nullptr); - EXPECT_EQ(list->itemsize, sizeof(int)); - EXPECT_EQ(list->capacity, (size_t) -1); + EXPECT_EQ(list->item_size, sizeof(int)); EXPECT_EQ(list->cmpfunc, nullptr); EXPECT_EQ(list->allocator, cxDefaultAllocator); + EXPECT_EQ(list->simple_destructor, nullptr); + EXPECT_EQ(list->advanced_destructor, nullptr); + EXPECT_EQ(list->destructor_data, nullptr); + EXPECT_EQ(cxListSize(list), 0); EXPECT_FALSE(cxListIsStoringPointers(list)); } TEST_F(LinkedList, cxLinkedListCreateSimpleForPointers) { CxList *list = autofree(cxLinkedListCreateSimple(CX_STORE_POINTERS)); ASSERT_NE(list, nullptr); - EXPECT_EQ(list->itemsize, sizeof(void *)); - EXPECT_EQ(list->capacity, (size_t) -1); + EXPECT_EQ(list->item_size, sizeof(void *)); EXPECT_EQ(list->cmpfunc, nullptr); EXPECT_EQ(list->allocator, cxDefaultAllocator); + EXPECT_EQ(list->simple_destructor, nullptr); + EXPECT_EQ(list->advanced_destructor, nullptr); + EXPECT_EQ(list->destructor_data, nullptr); + EXPECT_EQ(cxListSize(list), 0); EXPECT_TRUE(cxListIsStoringPointers(list)); } TEST_F(ArrayList, cxArrayListCreate) { CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); ASSERT_NE(list, nullptr); - EXPECT_EQ(list->itemsize, sizeof(int)); - EXPECT_EQ(list->capacity, 8); - EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE); - EXPECT_EQ(list->size, 0); + EXPECT_EQ(list->item_size, sizeof(int)); + EXPECT_EQ(list->simple_destructor, nullptr); + EXPECT_EQ(list->advanced_destructor, nullptr); + EXPECT_EQ(list->destructor_data, nullptr); + EXPECT_EQ(cxListSize(list), 0); EXPECT_EQ(list->allocator, &testingAllocator); EXPECT_EQ(list->cmpfunc, cx_cmp_int); EXPECT_FALSE(cxListIsStoringPointers(list)); @@ -1031,8 +1033,11 @@ ASSERT_NE(list, nullptr); EXPECT_EQ(list->cmpfunc, nullptr); EXPECT_EQ(list->allocator, cxDefaultAllocator); - EXPECT_EQ(list->itemsize, sizeof(int)); - EXPECT_EQ(list->capacity, 8); + EXPECT_EQ(list->item_size, sizeof(int)); + EXPECT_EQ(list->simple_destructor, nullptr); + EXPECT_EQ(list->advanced_destructor, nullptr); + EXPECT_EQ(list->destructor_data, nullptr); + EXPECT_EQ(cxListSize(list), 0); EXPECT_FALSE(cxListIsStoringPointers(list)); } @@ -1041,8 +1046,7 @@ ASSERT_NE(list, nullptr); EXPECT_EQ(list->cmpfunc, nullptr); EXPECT_EQ(list->allocator, cxDefaultAllocator); - EXPECT_EQ(list->itemsize, sizeof(void *)); - EXPECT_EQ(list->capacity, 8); + EXPECT_EQ(list->item_size, sizeof(void *)); EXPECT_TRUE(cxListIsStoringPointers(list)); } @@ -1313,7 +1317,6 @@ TEST_F(PointerLinkedList, DestroySimpleDestructor) { int item = 0; auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS); - list->content_destructor_type = CX_DESTRUCTOR_SIMPLE; list->simple_destructor = [](void *elem) { *(int *) elem = 42; }; cxListAdd(list, &item); cxListDestroy(list); @@ -1323,9 +1326,8 @@ TEST_F(PointerLinkedList, DestroyAdvancedDestructor) { void *item = cxMalloc(&testingAllocator, sizeof(int)); auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS); - list->content_destructor_type = CX_DESTRUCTOR_ADVANCED; - list->advanced_destructor.data = &testingAllocator; - list->advanced_destructor.func = (cx_destructor_func2) cxFree; + list->destructor_data = &testingAllocator; + list->advanced_destructor = (cx_destructor_func2) cxFree; cxListAdd(list, item); ASSERT_FALSE(testingAllocator.verify()); cxListDestroy(list);
--- a/tests/test_map.cpp Fri Apr 07 11:30:28 2023 +0200 +++ b/tests/test_map.cpp Sun Apr 09 19:03:58 2023 +0200 @@ -121,13 +121,13 @@ cx_for_n(i, hmap->bucket_count) { EXPECT_EQ(hmap->buckets[i], nullptr); } - EXPECT_EQ(map->itemsize, 1); + EXPECT_EQ(map->item_size, 1); EXPECT_EQ(map->size, 0); EXPECT_EQ(map->allocator, &allocator); EXPECT_FALSE(map->store_pointers); cxMapStorePointers(map); EXPECT_TRUE(map->store_pointers); - EXPECT_EQ(map->itemsize, sizeof(void *)); + EXPECT_EQ(map->item_size, sizeof(void *)); cxMapStoreObjects(map); EXPECT_FALSE(map->store_pointers); @@ -146,7 +146,7 @@ EXPECT_EQ(map->size, 0); EXPECT_EQ(map->allocator, &allocator); EXPECT_TRUE(map->store_pointers); - EXPECT_EQ(map->itemsize, sizeof(void *)); + EXPECT_EQ(map->item_size, sizeof(void *)); cxMapDestroy(map); EXPECT_TRUE(allocator.verify());