# HG changeset patch # User Olaf Wintermann # Date 1748527167 -7200 # Node ID 5ea41679e15deec2b514cd527679074c964c451b # Parent 6cfda23ae15461ed0ca2af87e53b73cb84463cb8 update ucx diff -r 6cfda23ae154 -r 5ea41679e15d ucx/allocator.c --- a/ucx/allocator.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/allocator.c Thu May 29 15:59:27 2025 +0200 @@ -29,6 +29,7 @@ #include "cx/allocator.h" #include +#include static void *cx_malloc_stdlib( cx_attr_unused void *d, @@ -60,18 +61,19 @@ free(mem); } -static cx_allocator_class cx_default_allocator_class = { +static cx_allocator_class cx_stdlib_allocator_class = { cx_malloc_stdlib, cx_realloc_stdlib, cx_calloc_stdlib, cx_free_stdlib }; -struct cx_allocator_s cx_default_allocator = { - &cx_default_allocator_class, +struct cx_allocator_s cx_stdlib_allocator = { + &cx_stdlib_allocator_class, NULL }; -const CxAllocator * const cxDefaultAllocator = &cx_default_allocator; +const CxAllocator * const cxStdlibAllocator = &cx_stdlib_allocator; +const CxAllocator * cxDefaultAllocator = cxStdlibAllocator; int cx_reallocate_( void **mem, @@ -115,6 +117,17 @@ return allocator->cl->malloc(allocator->data, n); } +void *cxZalloc( + const CxAllocator *allocator, + size_t n +) { + void *mem = allocator->cl->malloc(allocator->data, n); + if (mem != NULL) { + memset(mem, 0, n); + } + return mem; +} + void *cxRealloc( const CxAllocator *allocator, void *mem, diff -r 6cfda23ae154 -r 5ea41679e15d ucx/array_list.c --- a/ucx/array_list.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/array_list.c Thu May 29 15:59:27 2025 +0200 @@ -36,16 +36,17 @@ static void *cx_array_default_realloc( void *array, - size_t capacity, + cx_attr_unused size_t old_capacity, + size_t new_capacity, size_t elem_size, cx_attr_unused CxArrayReallocator *alloc ) { size_t n; - if (cx_szmul(capacity, elem_size, &n)) { + if (cx_szmul(new_capacity, elem_size, &n)) { errno = EOVERFLOW; return NULL; } - return realloc(array, n); + return cxReallocDefault(array, n); } CxArrayReallocator cx_array_default_reallocator_impl = { @@ -58,13 +59,14 @@ static void *cx_array_advanced_realloc( void *array, - size_t capacity, + size_t old_capacity, + size_t new_capacity, size_t elem_size, cx_attr_unused CxArrayReallocator *alloc ) { // check for overflow size_t n; - if (cx_szmul(capacity, elem_size, &n)) { + if (cx_szmul(new_capacity, elem_size, &n)) { errno = EOVERFLOW; return NULL; } @@ -77,7 +79,7 @@ if (array == alloc->ptr2) { newmem = cxMalloc(al, n); if (newmem != NULL && array != NULL) { - memcpy(newmem, array, n); + memcpy(newmem, array, old_capacity*elem_size); } } else { newmem = cxRealloc(al, array, n); @@ -180,7 +182,7 @@ // perform reallocation void *newmem = reallocator->realloc( - *array, newcap, elem_size, reallocator + *array, oldcap, newcap, elem_size, reallocator ); if (newmem == NULL) { return 1; // LCOV_EXCL_LINE @@ -286,7 +288,7 @@ // perform reallocation void *newmem = reallocator->realloc( - *target, newcap, elem_size, reallocator + *target, oldcap, newcap, elem_size, reallocator ); if (newmem == NULL) { return 1; @@ -366,13 +368,14 @@ // store some counts size_t old_size = *size; + size_t old_capacity = *capacity; size_t needed_capacity = old_size + elem_count; // if we need more than we have, try a reallocation - if (needed_capacity > *capacity) { + if (needed_capacity > old_capacity) { size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX); void *new_mem = reallocator->realloc( - *target, new_capacity, elem_size, reallocator + *target, old_capacity, new_capacity, elem_size, reallocator ); if (new_mem == NULL) { // give it up right away, there is no contract @@ -572,7 +575,7 @@ // decide if we can use the local buffer if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) { - tmp = malloc(elem_size); + tmp = cxMallocDefault(elem_size); // we don't want to enforce error handling if (tmp == NULL) abort(); } else { @@ -591,7 +594,7 @@ // free dynamic memory, if it was needed if (tmp != sbo_mem) { - free(tmp); + cxFreeDefault(tmp); } } @@ -638,50 +641,38 @@ // get a correctly typed pointer to the list cx_array_list *arl = (cx_array_list *) list; - // do we need to move some elements? - if (index < list->collection.size) { - const char *first_to_move = (const char *) arl->data; - first_to_move += index * list->collection.elem_size; - size_t elems_to_move = list->collection.size - index; - size_t start_of_moved = index + n; - - if (cx_array_copy( - &arl->data, - &list->collection.size, - &arl->capacity, - 0, - start_of_moved, - first_to_move, - list->collection.elem_size, - elems_to_move, - &arl->reallocator - )) { - // if moving existing elems is unsuccessful, abort + // guarantee enough capacity + if (arl->capacity < list->collection.size + n) { + size_t new_capacity = list->collection.size + n; + new_capacity = new_capacity - (new_capacity % 16) + 16; + if (cxReallocateArray( + list->collection.allocator, + &arl->data, new_capacity, + list->collection.elem_size) + ) { return 0; } + arl->capacity = new_capacity; } - // note that if we had to move the elements, the following operation - // is guaranteed to succeed, because we have the memory already allocated - // therefore, it is impossible to leave this function with an invalid array + // determine insert position + char *arl_data = arl->data; + char *insert_pos = arl_data + index * list->collection.elem_size; - // place the new elements - if (cx_array_copy( - &arl->data, - &list->collection.size, - &arl->capacity, - 0, - index, - array, - list->collection.elem_size, - n, - &arl->reallocator - )) { - // array list implementation is "all or nothing" - return 0; - } else { - return n; + // do we need to move some elements? + if (index < list->collection.size) { + size_t elems_to_move = list->collection.size - index; + char *target = insert_pos + n * list->collection.elem_size; + memmove(target, insert_pos, elems_to_move * list->collection.elem_size); } + + // place the new elements, if any + if (array != NULL) { + memcpy(insert_pos, array, n * list->collection.elem_size); + } + list->collection.size += n; + + return n; } static size_t cx_arl_insert_sorted( @@ -709,12 +700,16 @@ } } -static int cx_arl_insert_element( +static void *cx_arl_insert_element( struct cx_list_s *list, size_t index, const void *element ) { - return 1 != cx_arl_insert_array(list, index, element, 1); + if (cx_arl_insert_array(list, index, element, 1) == 1) { + return ((char*)((cx_array_list *) list)->data) + index * list->collection.elem_size; + } else { + return NULL; + } } static int cx_arl_insert_iter( @@ -724,26 +719,23 @@ ) { struct cx_list_s *list = iter->src_handle.m; if (iter->index < list->collection.size) { - int result = cx_arl_insert_element( - list, - iter->index + 1 - prepend, - elem - ); - if (result == 0) { - iter->elem_count++; - if (prepend != 0) { - iter->index++; - iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size; - } + if (cx_arl_insert_element(list, + iter->index + 1 - prepend, elem) == NULL) { + return 1; + } + iter->elem_count++; + if (prepend != 0) { + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size; } - return result; + return 0; } else { - int result = cx_arl_insert_element(list, list->collection.size, elem); - if (result == 0) { - iter->elem_count++; - iter->index = list->collection.size; + if (cx_arl_insert_element(list, list->collection.size, elem) == NULL) { + return 1; } - return result; + iter->elem_count++; + iter->index = list->collection.size; + return 0; } } diff -r 6cfda23ae154 -r 5ea41679e15d ucx/buffer.c --- a/ucx/buffer.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/buffer.c Thu May 29 15:59:27 2025 +0200 @@ -32,6 +32,24 @@ #include #include +#ifdef _WIN32 +#include +#include +static unsigned long system_page_size() { + static unsigned long ps = 0; + if (ps == 0) { + SYSTEM_INFO sysinfo; + GetSystemInfo(&sysinfo); + ps = sysinfo.dwPageSize; + } + return ps; +} +#define SYSTEM_PAGE_SIZE system_page_size() +#else +#include +#define SYSTEM_PAGE_SIZE sysconf(_SC_PAGESIZE) +#endif + static int buffer_copy_on_write(CxBuffer* buffer) { if (0 == (buffer->flags & CX_BUFFER_COPY_ON_WRITE)) return 0; void *newspace = cxMalloc(buffer->allocator, buffer->capacity); @@ -80,7 +98,7 @@ CxBuffer *buffer, CxBufferFlushConfig config ) { - buffer->flush = malloc(sizeof(CxBufferFlushConfig)); + buffer->flush = cxMallocDefault(sizeof(CxBufferFlushConfig)); if (buffer->flush == NULL) return -1; // LCOV_EXCL_LINE memcpy(buffer->flush, &config, sizeof(CxBufferFlushConfig)); return 0; @@ -90,7 +108,7 @@ if (buffer->flags & CX_BUFFER_FREE_CONTENTS) { cxFree(buffer->allocator, buffer->bytes); } - free(buffer->flush); + cxFreeDefault(buffer->flush); memset(buffer, 0, sizeof(CxBuffer)); } @@ -139,6 +157,7 @@ npos = 0; break; default: + errno = EINVAL; return -1; } @@ -146,11 +165,16 @@ npos += offset; if ((offset > 0 && npos < opos) || (offset < 0 && npos > opos)) { - errno = EOVERFLOW; + // to be compliant with fseek() specification + // we return EINVAL on underflow + errno = EINVAL; return -1; } if (npos > buffer->size) { + // not compliant with fseek() specification + // but this is the better behavior for CxBuffer + errno = EINVAL; return -1; } else { buffer->pos = npos; @@ -184,6 +208,28 @@ return 0; } + unsigned long pagesize = SYSTEM_PAGE_SIZE; + // if page size is larger than 64 KB - for some reason - truncate to 64 KB + if (pagesize > 65536) pagesize = 65536; + if (newcap < pagesize) { + // when smaller as one page, map to the next power of two + newcap--; + newcap |= newcap >> 1; + newcap |= newcap >> 2; + newcap |= newcap >> 4; + // last operation only needed for pages larger 4096 bytes + // but if/else would be more expensive than just doing this + newcap |= newcap >> 8; + newcap++; + } else { + // otherwise, map to a multiple of the page size + newcap -= newcap % pagesize; + newcap += pagesize; + // note: if newcap is already page aligned, + // this gives a full additional page (which is good) + } + + const int force_copy_flags = CX_BUFFER_COPY_ON_WRITE | CX_BUFFER_COPY_ON_EXTEND; if (buffer->flags & force_copy_flags) { void *newspace = cxMalloc(buffer->allocator, newcap); @@ -203,6 +249,28 @@ } } +void cxBufferShrink( + CxBuffer *buffer, + size_t reserve +) { + // Ensure buffer is in a reallocatable state + const int force_copy_flags = CX_BUFFER_COPY_ON_WRITE | CX_BUFFER_COPY_ON_EXTEND; + if (buffer->flags & force_copy_flags) { + // do nothing when we are not allowed to reallocate + return; + } + + // calculate new capacity + size_t newCapacity = buffer->size + reserve; + + // If new capacity is smaller than current capacity, resize the buffer + if (newCapacity < buffer->capacity) { + if (0 == cxReallocate(buffer->allocator, &buffer->bytes, newCapacity)) { + buffer->capacity = newCapacity; + } + } +} + static size_t cx_buffer_flush_helper( const CxBuffer *buffer, const unsigned char *src, @@ -399,10 +467,8 @@ } int cxBufferTerminate(CxBuffer *buffer) { - bool success = 0 == cxBufferPut(buffer, 0); - if (success) { - buffer->pos--; - buffer->size--; + if (0 == cxBufferPut(buffer, 0)) { + buffer->size = buffer->pos - 1; return 0; } else { return -1; diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/allocator.h --- a/ucx/cx/allocator.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/allocator.h Thu May 29 15:59:27 2025 +0200 @@ -98,10 +98,17 @@ typedef struct cx_allocator_s CxAllocator; /** - * A default allocator using standard library malloc() etc. + * A pre-defined allocator using standard library malloc() etc. */ cx_attr_export -extern const CxAllocator * const cxDefaultAllocator; +extern const CxAllocator * const cxStdlibAllocator; + +/** + * The default allocator that is used by UCX. + * Initialized with cxStdlibAllocator, but you may change it. + */ +cx_attr_export +extern const CxAllocator * cxDefaultAllocator; /** * Function pointer type for destructor functions. @@ -135,6 +142,8 @@ * Reallocate a previously allocated block and changes the pointer in-place, * if necessary. * + * @note This will use stdlib reallocate and @em not the cxDefaultAllocator. + * * @par Error handling * @c errno will be set by realloc() on failure. * @@ -158,6 +167,8 @@ * * The size is calculated by multiplying @p nemb and @p size. * + * @note This will use stdlib reallocate and @em not the cxDefaultAllocator. + * * @par Error handling * @c errno will be set by realloc() on failure or when the multiplication of * @p nmemb and @p size overflows. @@ -182,6 +193,8 @@ * Reallocate a previously allocated block and changes the pointer in-place, * if necessary. * + * @note This will use stdlib reallocate and @em not the cxDefaultAllocator. + * * @par Error handling * @c errno will be set by realloc() on failure. * @@ -199,6 +212,8 @@ * * The size is calculated by multiplying @p nemb and @p size. * + * @note This will use stdlib reallocate and @em not the cxDefaultAllocator. + * * @par Error handling * @c errno will be set by realloc() on failure or when the multiplication of * @p nmemb and @p size overflows. @@ -213,6 +228,14 @@ cx_reallocatearray_((void**)(mem), nmemb, size) /** + * Allocates memory and sets every byte to zero. + * + * @param n (@c size_t) the number of bytes + * @return (@c void*) a pointer to the allocated memory + */ +#define cx_zalloc(n) calloc(1, n) + +/** * Free a block allocated by this allocator. * * @note Freeing a block of a different allocator is undefined. @@ -414,6 +437,57 @@ size_t size ); +/** + * Allocate @p n bytes of memory and sets every byte to zero. + * + * @param allocator the allocator + * @param n the number of bytes + * @return a pointer to the allocated memory + */ +cx_attr_nodiscard +cx_attr_nonnull +cx_attr_malloc +cx_attr_dealloc_ucx +cx_attr_allocsize(2) +cx_attr_export +void *cxZalloc( + const CxAllocator *allocator, + size_t n +); + +/** + * Convenience macro that invokes cxMalloc() with the cxDefaultAllocator. + */ +#define cxMallocDefault(...) cxMalloc(cxDefaultAllocator, __VA_ARGS__) +/** + * Convenience macro that invokes cxZalloc() with the cxDefaultAllocator. + */ +#define cxZallocDefault(...) cxZalloc(cxDefaultAllocator, __VA_ARGS__) +/** + * Convenience macro that invokes cxCalloc() with the cxDefaultAllocator. + */ +#define cxCallocDefault(...) cxCalloc(cxDefaultAllocator, __VA_ARGS__) +/** + * Convenience macro that invokes cxRealloc() with the cxDefaultAllocator. + */ +#define cxReallocDefault(...) cxRealloc(cxDefaultAllocator, __VA_ARGS__) +/** + * Convenience macro that invokes cxReallocate() with the cxDefaultAllocator. + */ +#define cxReallocateDefault(...) cxReallocate(cxDefaultAllocator, __VA_ARGS__) +/** + * Convenience macro that invokes cxReallocateArray() with the cxDefaultAllocator. + */ +#define cxReallocateArrayDefault(...) cxReallocateArray(cxDefaultAllocator, __VA_ARGS__) +/** + * Convenience macro that invokes cxReallocArray() with the cxDefaultAllocator. + */ +#define cxReallocArrayDefault(...) cxReallocArray(cxDefaultAllocator, __VA_ARGS__) +/** + * Convenience macro that invokes cxFree() with the cxDefaultAllocator. + */ +#define cxFreeDefault(...) cxFree(cxDefaultAllocator, __VA_ARGS__) + #ifdef __cplusplus } // extern "C" #endif diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/array_list.h --- a/ucx/cx/array_list.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/array_list.h Thu May 29 15:59:27 2025 +0200 @@ -123,7 +123,8 @@ * @endcode * * - * The memory for the array is allocated with stdlib malloc(). + * The memory for the array is allocated with the cxDefaultAllocator. + * * @param array the name of the array * @param capacity the initial capacity * @see cx_array_initialize_a() @@ -133,7 +134,7 @@ #define cx_array_initialize(array, capacity) \ array##_capacity = capacity; \ array##_size = 0; \ - array = malloc(sizeof(array[0]) * capacity) + array = cxMallocDefault(sizeof(array[0]) * capacity) /** * Initializes an array with the given capacity using the specified allocator. @@ -149,7 +150,6 @@ * cxFree(al, myarray); // don't forget to free with same allocator * @endcode * - * The memory for the array is allocated with stdlib malloc(). * @param allocator (@c CxAllocator*) the allocator * @param array the name of the array * @param capacity the initial capacity @@ -178,17 +178,19 @@ * or to transport other additional data. * * @param array the array to reallocate - * @param capacity the new capacity (number of elements) + * @param old_capacity the old number of elements + * @param new_capacity the new number of elements * @param elem_size the size of each element * @param alloc a reference to this allocator * @return a pointer to the reallocated memory or @c NULL on failure */ cx_attr_nodiscard - cx_attr_nonnull_arg(4) - cx_attr_allocsize(2, 3) + cx_attr_nonnull_arg(5) + cx_attr_allocsize(3, 4) void *(*realloc)( void *array, - size_t capacity, + size_t old_capacity, + size_t new_capacity, size_t elem_size, struct cx_array_reallocator_s *alloc ); @@ -217,7 +219,7 @@ typedef struct cx_array_reallocator_s CxArrayReallocator; /** - * A default stdlib-based array reallocator. + * A default array reallocator that is based on the cxDefaultAllocator. */ cx_attr_export extern CxArrayReallocator *cx_array_default_reallocator; @@ -225,7 +227,7 @@ /** * Creates a new array reallocator. * - * When @p allocator is @c NULL, the stdlib default allocator will be used. + * When @p allocator is @c NULL, the cxDefaultAllocator will be used. * * When @p stackmem is not @c NULL, the reallocator is supposed to be used * @em only for the specific array that is initially located at @p stackmem. @@ -699,7 +701,7 @@ * to cx_cmp_ptr(), if none is given. * * @param allocator the allocator for allocating the list memory - * (if @c NULL, a default stdlib allocator will be used) + * (if @c NULL, the cxDefaultAllocator will be used) * @param comparator the comparator for the elements * (if @c NULL, and the list is not storing pointers, sort and find * functions will not work) @@ -727,7 +729,7 @@ * * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of * copies of the added elements and the compare function will be automatically set - * to cx_cmp_ptr(), if none is given. + * to cx_cmp_ptr(). * * @param elem_size (@c size_t) the size of each element in bytes * @param initial_capacity (@c size_t) the initial number of elements the array can store diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/buffer.h --- a/ucx/cx/buffer.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/buffer.h Thu May 29 15:59:27 2025 +0200 @@ -222,7 +222,7 @@ * @param capacity the capacity of the buffer * @param allocator the allocator this buffer shall use for automatic * memory management - * (if @c NULL, a default stdlib allocator will be used) + * (if @c NULL, the cxDefaultAllocator will be used) * @param flags buffer features (see cx_buffer_s.flags) * @return zero on success, non-zero if a required allocation failed */ @@ -305,7 +305,7 @@ * @param capacity the capacity of the buffer * @param allocator the allocator to use for allocating the structure and the automatic * memory management within the buffer - * (if @c NULL, a default stdlib allocator will be used) + * (if @c NULL, the cxDefaultAllocator will be used) * @param flags buffer features (see cx_buffer_s.flags) * @return a pointer to the buffer on success, @c NULL if a required allocation failed */ @@ -474,10 +474,14 @@ * * If the current capacity is not sufficient, the buffer will be extended. * + * The new capacity will be a power of two until the system's page size is reached. + * Then, the new capacity will be a multiple of the page size. + * * @param buffer the buffer * @param capacity the minimum required capacity for this buffer * @retval zero the capacity was already sufficient or successfully increased * @retval non-zero on allocation failure + * @see cxBufferShrink() */ cx_attr_nonnull cx_attr_export @@ -487,6 +491,29 @@ ); /** + * Shrinks the capacity of the buffer to fit its current size. + * + * If @p reserve is larger than zero, the buffer is shrunk to its size plus + * the number of reserved bytes. + * + * If the current capacity is not larger than the size plus the reserved bytes, + * nothing happens. + * + * If the #CX_BUFFER_COPY_ON_WRITE or #CX_BUFFER_COPY_ON_EXTEND flag is set, + * this function does nothing. + * + * @param buffer the buffer + * @param reserve the number of bytes that shall remain reserved + * @see cxBufferMinimumCapacity() + */ +cx_attr_nonnull +cx_attr_export +void cxBufferShrink( + CxBuffer *buffer, + size_t reserve +); + +/** * Writes data to a CxBuffer. * * If automatic flushing is not enabled, the data is simply written into the @@ -674,11 +701,10 @@ /** * Writes a terminating zero to a buffer at the current position. * - * On successful write, @em neither the position @em nor the size of the buffer is - * increased. + * If successful, sets the size to the current position and advances the position by one. * * The purpose of this function is to have the written data ready to be used as - * a C string. + * a C string with the buffer's size being the length of that string. * * @param buffer the buffer to write to * @return zero, if the terminator could be written, non-zero otherwise diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/common.h --- a/ucx/cx/common.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/common.h Thu May 29 15:59:27 2025 +0200 @@ -46,7 +46,7 @@ * Repositories:
* https://sourceforge.net/p/ucx/code * - or - - * https://develop.uap-core.de/hg/ucx + * https://uap-core.de/hg/ucx *

* *

LICENCE

@@ -150,7 +150,7 @@ */ #define cx_attr_malloc __attribute__((__malloc__)) -#ifndef __clang__ +#if !defined(__clang__) && __GNUC__ >= 11 /** * The pointer returned by the attributed function is supposed to be freed * by @p freefunc. @@ -240,20 +240,6 @@ */ #define cx_attr_access_w(...) cx_attr_access(__write_only__, __VA_ARGS__) -#if __STDC_VERSION__ >= 202300L - -/** - * Do not warn about unused variable. - */ -#define cx_attr_unused [[maybe_unused]] - -/** - * Warn about discarded return value. - */ -#define cx_attr_nodiscard [[nodiscard]] - -#else // no C23 - /** * Do not warn about unused variable. */ @@ -264,8 +250,6 @@ */ #define cx_attr_nodiscard __attribute__((__warn_unused_result__)) -#endif // __STDC_VERSION__ - // --------------------------------------------------------------------------- // MSVC specifics diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/hash_map.h --- a/ucx/cx/hash_map.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/hash_map.h Thu May 29 15:59:27 2025 +0200 @@ -77,7 +77,7 @@ * In other words, when the iterator is finished, @c index==size . * * @param allocator the allocator to use - * (if @c NULL, a default stdlib allocator will be used) + * (if @c NULL, the cxDefaultAllocator will be used) * @param itemsize the size of one element * @param buckets the initial number of buckets in this hash map * @return a pointer to the new hash map diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/linked_list.h --- a/ucx/cx/linked_list.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/linked_list.h Thu May 29 15:59:27 2025 +0200 @@ -51,7 +51,7 @@ * to cx_cmp_ptr(), if none is given. * * @param allocator the allocator for allocating the list nodes - * (if @c NULL, a default stdlib allocator will be used) + * (if @c NULL, the cxDefaultAllocator will be used) * @param comparator the comparator for the elements * (if @c NULL, and the list is not storing pointers, sort and find * functions will not work) @@ -77,7 +77,7 @@ * * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of * copies of the added elements and the compare function will be automatically set - * to cx_cmp_ptr(), if none is given. + * to cx_cmp_ptr(). * * @param elem_size (@c size_t) the size of each element in bytes * @return (@c CxList*) the created list @@ -393,7 +393,7 @@ * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance) * @li @p loc_next and @p begin (ancestor node is determined by list traversal, overall O(n) performance) * - * @remark The @c next and @c prev pointers of the removed node are not cleared by this function and may still be used + * @remark The @c next and @c prev pointers of the removed chain are not cleared by this function and may still be used * to traverse to a former adjacent node in the list, or within the chain. * * @param begin a pointer to the beginning node pointer (optional) diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/list.h --- a/ucx/cx/list.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/list.h Thu May 29 15:59:27 2025 +0200 @@ -80,8 +80,10 @@ /** * Member function for inserting a single element. + * The data pointer may be @c NULL in which case the function shall only allocate memory. + * Returns a pointer to the data of the inserted element. */ - int (*insert_element)( + void *(*insert_element)( struct cx_list_s *list, size_t index, const void *data @@ -203,6 +205,22 @@ }; /** + * Common type for all list implementations. + */ +typedef struct cx_list_s CxList; + +/** + * A shared instance of an empty list. + * + * Writing to that list is not allowed. + * + * You can use this is a placeholder for initializing CxList pointers + * for which you do not want to reserve memory right from the beginning. + */ +cx_attr_export +extern CxList *const cxEmptyList; + +/** * Default implementation of an array insert. * * This function uses the element insert function for each element of the array. @@ -336,11 +354,6 @@ ); /** - * Common type for all list implementations. - */ -typedef struct cx_list_s CxList; - -/** * Returns the number of elements currently stored in the list. * * @param list the list @@ -359,6 +372,7 @@ * @retval zero success * @retval non-zero memory allocation failure * @see cxListAddArray() + * @see cxListEmplace() */ cx_attr_nonnull static inline int cxListAdd( @@ -366,7 +380,7 @@ const void *elem ) { list->collection.sorted = false; - return list->cl->insert_element(list, list->collection.size, elem); + return list->cl->insert_element(list, list->collection.size, elem) == NULL; } /** @@ -407,6 +421,7 @@ * @retval non-zero memory allocation failure or the index is out of bounds * @see cxListInsertAfter() * @see cxListInsertBefore() + * @see cxListEmplaceAt() */ cx_attr_nonnull static inline int cxListInsert( @@ -415,7 +430,41 @@ const void *elem ) { list->collection.sorted = false; - return list->cl->insert_element(list, index, elem); + return list->cl->insert_element(list, index, elem) == NULL; +} + +/** + * Allocates memory for an element at the specified index and returns a pointer to that memory. + * + * @remark When the list is storing pointers, this will return a @c void**. + * + * @param list the list + * @param index the index where to emplace the element + * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds + * @see cxListEmplace() + * @see cxListInsert() + */ +cx_attr_nonnull +static inline void *cxListEmplaceAt(CxList *list, size_t index) { + list->collection.sorted = false; + return list->cl->insert_element(list, index, NULL); +} + + +/** + * Allocates memory for an element at the end of the list and returns a pointer to that memory. + * + * @remark When the list is storing pointers, this will return a @c void**. + * + * @param list the list + * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds + * @see cxListEmplaceAt() + * @see cxListAdd() + */ +cx_attr_nonnull +static inline void *cxListEmplace(CxList *list) { + list->collection.sorted = false; + return list->cl->insert_element(list, list->collection.size, NULL); } /** @@ -571,8 +620,9 @@ /** * Removes and returns the element at the specified index. * - * No destructor is called and instead the element is copied to the + * No destructor is called, and instead the element is copied to the * @p targetbuf which MUST be large enough to hold the removed element. + * If the list is storing pointers, only the pointer is copied to @p targetbuf. * * @param list the list * @param index the index of the element @@ -591,11 +641,93 @@ } /** + * Removes and returns the first element of the list. + * + * No destructor is called, and instead the element is copied to the + * @p targetbuf which MUST be large enough to hold the removed element. + * If the list is storing pointers, only the pointer is copied to @p targetbuf. + * + * @param list the list + * @param targetbuf a buffer where to copy the element + * @retval zero success + * @retval non-zero list is empty + * @see cxListPopFront() + * @see cxListRemoveAndGetLast() + */ +cx_attr_nonnull +cx_attr_access_w(2) +static inline int cxListRemoveAndGetFirst( + CxList *list, + void *targetbuf +) { + return list->cl->remove(list, 0, 1, targetbuf) == 0; +} + +/** + * Removes and returns the first element of the list. + * + * Alias for cxListRemoveAndGetFirst(). + * + * No destructor is called, and instead the element is copied to the + * @p targetbuf which MUST be large enough to hold the removed element. + * If the list is storing pointers, only the pointer is copied to @p targetbuf. + * + * @param list (@c CxList*) the list + * @param targetbuf (@c void*) a buffer where to copy the element + * @retval zero success + * @retval non-zero list is empty + * @see cxListRemoveAndGetFirst() + * @see cxListPop() + */ +#define cxListPopFront(list, targetbuf) cxListRemoveAndGetFirst((list), (targetbuf)) + + +/** + * Removes and returns the last element of the list. + * + * No destructor is called, and instead the element is copied to the + * @p targetbuf which MUST be large enough to hold the removed element. + * If the list is storing pointers, only the pointer is copied to @p targetbuf. + * + * @param list the list + * @param targetbuf a buffer where to copy the element + * @retval zero success + * @retval non-zero list is empty + */ +cx_attr_nonnull +cx_attr_access_w(2) +static inline int cxListRemoveAndGetLast( + CxList *list, + void *targetbuf +) { + // note: index may wrap - member function will catch that + return list->cl->remove(list, list->collection.size - 1, 1, targetbuf) == 0; +} + +/** + * Removes and returns the last element of the list. + * + * Alias for cxListRemoveAndGetLast(). + * + * No destructor is called, and instead the element is copied to the + * @p targetbuf which MUST be large enough to hold the removed element. + * If the list is storing pointers, only the pointer is copied to @p targetbuf. + * + * @param list (@c CxList*) the list + * @param targetbuf (@c void*) a buffer where to copy the element + * @retval zero success + * @retval non-zero list is empty + * @see cxListRemoveAndGetLast() + * @see cxListPopFront() + */ +#define cxListPop(list, targetbuf) cxListRemoveAndGetLast((list), (targetbuf)) + +/** * Removes multiple element starting at the specified index. * * If an element destructor function is specified, it is called for each * element. It is guaranteed that the destructor is called before removing - * the element, however, due to possible optimizations it is neither guaranteed + * the element. However, due to possible optimizations, it is neither guaranteed * that the destructors are invoked for all elements before starting to remove * them, nor that the element is removed immediately after the destructor call * before proceeding to the next element. @@ -615,10 +747,11 @@ } /** - * Removes and returns multiple element starting at the specified index. + * Removes and returns multiple elements starting at the specified index. * - * No destructor is called and instead the elements are copied to the + * No destructor is called, and instead the elements are copied to the * @p targetbuf which MUST be large enough to hold all removed elements. + * If the list is storing pointers, @p targetbuf is expected to be an array of pointers. * * @param list the list * @param index the index of the element @@ -654,15 +787,15 @@ /** * Swaps two items in the list. * - * Implementations should only allocate temporary memory for the swap, if + * Implementations should only allocate temporary memory for the swap if * it is necessary. * * @param list the list * @param i the index of the first element * @param j the index of the second element * @retval zero success - * @retval non-zero one of the indices is out of bounds - * or the swap needed extra memory but allocation failed + * @retval non-zero one of the indices is out of bounds, + * or the swap needed extra memory, but allocation failed */ cx_attr_nonnull static inline int cxListSwap( @@ -677,6 +810,8 @@ /** * Returns a pointer to the element at the specified index. * + * If the list is storing pointers, returns the pointer stored at the specified index. + * * @param list the list * @param index the index of the element * @return a pointer to the element or @c NULL if the index is out of bounds @@ -690,6 +825,49 @@ } /** + * Returns a pointer to the first element. + * + * If the list is storing pointers, returns the first pointer stored in the list. + * + * @param list the list + * @return a pointer to the first element or @c NULL if the list is empty + */ +cx_attr_nonnull +static inline void *cxListFirst(const CxList *list) { + return list->cl->at(list, 0); +} + +/** + * Returns a pointer to the last element. + * + * If the list is storing pointers, returns the last pointer stored in the list. + * + * @param list the list + * @return a pointer to the last element or @c NULL if the list is empty + */ +cx_attr_nonnull +static inline void *cxListLast(const CxList *list) { + return list->cl->at(list, list->collection.size - 1); +} + +/** + * Sets the element at the specified index in the list + * + * @param list the list to set the element in + * @param index the index to set the element at + * @param elem element to set + * @retval zero on success + * @retval non-zero when index is out of bounds + */ +cx_attr_nonnull +cx_attr_export +int cxListSet( + CxList *list, + size_t index, + const void *elem +); + +/** * Returns an iterator pointing to the item at the specified index. * * The returned iterator is position-aware. @@ -773,14 +951,14 @@ * * The returned iterator is position-aware. * - * If the list is empty, a past-the-end iterator will be returned. + * If the list is empty or @c NULL, a past-the-end iterator will be returned. * * @param list the list * @return a new iterator */ -cx_attr_nonnull cx_attr_nodiscard static inline CxIterator cxListIterator(const CxList *list) { + if (list == NULL) list = cxEmptyList; return list->cl->iterator(list, 0, false); } @@ -789,14 +967,14 @@ * * The returned iterator is position-aware. * - * If the list is empty, a past-the-end iterator will be returned. + * If the list is empty or @c NULL, a past-the-end iterator will be returned. * * @param list the list * @return a new iterator */ -cx_attr_nonnull cx_attr_nodiscard static inline CxIterator cxListMutIterator(CxList *list) { + if (list == NULL) list = cxEmptyList; return cxListMutIteratorAt(list, 0); } @@ -806,14 +984,14 @@ * * The returned iterator is position-aware. * - * If the list is empty, a past-the-end iterator will be returned. + * If the list is empty or @c NULL, a past-the-end iterator will be returned. * * @param list the list * @return a new iterator */ -cx_attr_nonnull cx_attr_nodiscard static inline CxIterator cxListBackwardsIterator(const CxList *list) { + if (list == NULL) list = cxEmptyList; return list->cl->iterator(list, list->collection.size - 1, true); } @@ -822,14 +1000,14 @@ * * The returned iterator is position-aware. * - * If the list is empty, a past-the-end iterator will be returned. + * If the list is empty or @c NULL, a past-the-end iterator will be returned. * * @param list the list * @return a new iterator */ -cx_attr_nonnull cx_attr_nodiscard static inline CxIterator cxListMutBackwardsIterator(CxList *list) { + if (list == NULL) list = cxEmptyList; return cxListMutBackwardsIteratorAt(list, list->collection.size - 1); } @@ -842,6 +1020,7 @@ * @param elem the element to find * @return the index of the element or the size of the list when the element is not found * @see cxListIndexValid() + * @see cxListContains() */ cx_attr_nonnull cx_attr_nodiscard @@ -853,6 +1032,26 @@ } /** + * Checks, if the list contains the specified element. + * + * The elements are compared with the list's comparator function. + * + * @param list the list + * @param elem the element to find + * @retval true if the element is contained + * @retval false if the element is not contained + * @see cxListFind() + */ +cx_attr_nonnull +cx_attr_nodiscard +static inline bool cxListContains( + const CxList* list, + const void* elem +) { + return list->cl->find_remove((CxList*)list, elem, false) < list->collection.size; +} + +/** * Checks if the specified index is within bounds. * * @param list the list @@ -894,6 +1093,7 @@ */ cx_attr_nonnull static inline void cxListSort(CxList *list) { + if (list->collection.sorted) return; list->cl->sort(list); list->collection.sorted = true; } @@ -942,17 +1142,6 @@ cx_attr_export void cxListFree(CxList *list); -/** - * A shared instance of an empty list. - * - * Writing to that list is not allowed. - * - * You can use this is a placeholder for initializing CxList pointers - * for which you do not want to reserve memory right from the beginning. - */ -cx_attr_export -extern CxList *const cxEmptyList; - #ifdef __cplusplus } // extern "C" diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/mempool.h --- a/ucx/cx/mempool.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/mempool.h Thu May 29 15:59:27 2025 +0200 @@ -43,31 +43,107 @@ extern "C" { #endif -/** Internal structure for pooled memory. */ -struct cx_mempool_memory_s; +/** A memory block in a simple memory pool. */ +struct cx_mempool_memory_s { + /** The destructor. */ + cx_destructor_func destructor; + /** The actual memory. */ + char c[]; +}; + +/** A memory block in an advanced memory pool. */ +struct cx_mempool_memory2_s { + /** The destructor. */ + cx_destructor_func2 destructor; + /** Data for the destructor. */ + void *data; + /** The actual memory. */ + char c[]; +}; + +/** Represents memory that is not allocated by, but registered with a pool. */ +struct cx_mempool_foreign_memory_s { + /** The foreign memory. */ + void* mem; + union { + /** Simple destructor. */ + cx_destructor_func destr; + /** Advanced destructor. */ + cx_destructor_func2 destr2; + }; + /** Data for the advanced destructor. */ + void *destr2_data; +}; + +/** Specifies how individual blocks are allocated. */ +enum cx_mempool_type { + /** + * Allows registration of cx_destructor_func for each memory block. + */ + CX_MEMPOOL_TYPE_SIMPLE, + /** + * Allows registration of cx_destructor_func2 for each memory block. + */ + CX_MEMPOOL_TYPE_ADVANCED, + /** + * No individual destructor registration allowed. + * + * In this mode, no additional memory per block is allocated. + */ + CX_MEMPOOL_TYPE_PURE, +}; /** * The basic structure of a memory pool. * Should be the first member of an actual memory pool implementation. */ struct cx_mempool_s { + /** The used allocator, initialized with the cxDefaultAllocator. */ + const CxAllocator * const base_allocator; + /** The provided allocator. */ const CxAllocator *allocator; - /** - * A destructor that shall be automatically registered for newly allocated memory. - * This destructor MUST NOT free the memory. - */ - cx_destructor_func auto_destr; - /** Array of pooled memory. */ - struct cx_mempool_memory_s **data; + void **data; /** Number of pooled memory items. */ size_t size; /** Memory pool capacity. */ size_t capacity; + + /** Array of registered memory. */ + struct cx_mempool_foreign_memory_s *registered; + + /** Number of registered memory items. */ + size_t registered_size; + + /** Capacity for registered memory. */ + size_t registered_capacity; + + /** + * A destructor that shall be called before deallocating a memory block. + * This destructor MUST NOT free the memory itself. + * + * It is guaranteed that this destructor is called after the individual + * destructor of the memory block and before @c destr2. + */ + cx_destructor_func destr; + + /** + * A destructor that shall be called before deallocating a memory block. + * This destructor MUST NOT free the memory itself. + * + * It is guaranteed that this destructor is called after the individual + * destructor of the memory block and @c destr. + */ + cx_destructor_func2 destr2; + + /** + * Additional data for the @c destr2. + */ + void *destr2_data; }; /** @@ -84,31 +160,76 @@ void cxMempoolFree(CxMempool *pool); /** - * Creates an array-based memory pool with a shared destructor function. + * Creates an array-based memory pool. * - * This destructor MUST NOT free the memory. + * The type determines how much additional memory is allocated per block + * to register a destructor function. * - * @param capacity the initial capacity of the pool - * @param destr optional destructor function to use for allocated memory + * @param capacity the initial capacity of the pool (an implementation default if zero) + * @param type the type of memory pool * @return the created memory pool or @c NULL if allocation failed */ cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxMempoolFree, 1) cx_attr_export -CxMempool *cxMempoolCreate(size_t capacity, cx_destructor_func destr); +CxMempool *cxMempoolCreate(size_t capacity, enum cx_mempool_type type); + +/** + * Creates a basic array-based memory pool. + * + * Convenience macro to create a memory pool of type #CX_MEMPOOL_TYPE_SIMPLE. + * + * @param capacity (@c size_t) the initial capacity of the pool + * @return (@c CxMempool*) the created memory pool or @c NULL if allocation failed + */ +#define cxMempoolCreateSimple(capacity) cxMempoolCreate(capacity, CX_MEMPOOL_TYPE_SIMPLE) + +/** + * Creates a basic array-based memory pool. + * + * Convenience macro to create a memory pool of type #CX_MEMPOOL_TYPE_ADVANCED. + * + * @param capacity (@c size_t) the initial capacity of the pool + * @return (@c CxMempool*) the created memory pool or @c NULL if allocation failed + */ +#define cxMempoolCreateAdvanced(capacity) cxMempoolCreate(capacity, CX_MEMPOOL_TYPE_ADVANCED) /** * Creates a basic array-based memory pool. * + * Convenience macro to create a memory pool of type #CX_MEMPOOL_TYPE_PURE. + * * @param capacity (@c size_t) the initial capacity of the pool * @return (@c CxMempool*) the created memory pool or @c NULL if allocation failed */ -#define cxMempoolCreateSimple(capacity) cxMempoolCreate(capacity, NULL) +#define cxMempoolCreatePure(capacity) cxMempoolCreate(capacity, CX_MEMPOOL_TYPE_PURE) + +/** + * Sets the global destructor for all memory blocks within the specified pool. + * + * @param pool the memory pool + * @param fnc the destructor that shall be applied to all memory blocks + */ +cx_attr_nonnull_arg(1) +cx_attr_export +void cxMempoolGlobalDestructor(CxMempool *pool, cx_destructor_func fnc); + +/** + * Sets the global destructor for all memory blocks within the specified pool. + * + * @param pool the memory pool + * @param fnc the destructor that shall be applied to all memory blocks + * @param data additional data for the destructor function + */ +cx_attr_nonnull_arg(1) +cx_attr_export +void cxMempoolGlobalDestructor2(CxMempool *pool, cx_destructor_func2 fnc, void *data); /** * Sets the destructor function for a specific allocated memory object. * + * If the type of memory pool is not #CX_MEMPOOL_TYPE_SIMPLE, the behavior is undefined. * If the memory is not managed by a UCX memory pool, the behavior is undefined. * The destructor MUST NOT free the memory. * @@ -123,10 +244,29 @@ ); /** + * Sets the destructor function for a specific allocated memory object. + * + * If the type of memory pool is not #CX_MEMPOOL_TYPE_ADVANCED, the behavior is undefined. + * If the memory is not managed by a UCX memory pool, the behavior is undefined. + * The destructor MUST NOT free the memory. + * + * @param memory the object allocated in the pool + * @param fnc the destructor function + * @param data additional data for the destructor function + */ +cx_attr_nonnull +cx_attr_export +void cxMempoolSetDestructor2( + void *memory, + cx_destructor_func2 fnc, + void *data +); + +/** * Removes the destructor function for a specific allocated memory object. * + * If the type of memory pool is not #CX_MEMPOOL_TYPE_SIMPLE, the behavior is undefined. * If the memory is not managed by a UCX memory pool, the behavior is undefined. - * The destructor MUST NOT free the memory. * * @param memory the object allocated in the pool */ @@ -135,12 +275,25 @@ void cxMempoolRemoveDestructor(void *memory); /** + * Removes the destructor function for a specific allocated memory object. + * + * If the type of memory pool is not #CX_MEMPOOL_TYPE_ADVANCED, the behavior is undefined. + * If the memory is not managed by a UCX memory pool, the behavior is undefined. + * + * @param memory the object allocated in the pool + */ +cx_attr_nonnull +cx_attr_export +void cxMempoolRemoveDestructor2(void *memory); + +/** * Registers foreign memory with this pool. * * The destructor, in contrast to memory allocated by the pool, MUST free the memory. + * This function can be used with any pool of any type, since destructors for registered memory + * are entirely independent of the pool's memory management. * - * A small portion of memory will be allocated to register the information in the pool. - * If that allocation fails, this function will return non-zero. + * The destructor for the registered memory will be called after all pooled items have been freed. * * @param pool the pool * @param memory the object to register (MUST NOT be already allocated in the pool) @@ -156,6 +309,79 @@ cx_destructor_func destr ); + +/** + * Registers foreign memory with this pool. + * + * The destructor, in contrast to memory allocated by the pool, MUST free the memory. + * This function can be used with any pool of any type, since destructors for registered memory + * are entirely independent of the pool's memory management. + * + * The destructor for the registered memory will be called after all pooled items have been freed. + * + * @attention The data pointer MUST NOT be @c NULL. + * If you wish to register a destructor without additional data, use cxMempoolRegister(). + * + * @param pool the pool + * @param memory the object to register (MUST NOT be already allocated in the pool) + * @param destr the destructor function + * @param data additional data for the destructor function + * @retval zero success + * @retval non-zero failure + */ +cx_attr_nonnull +cx_attr_export +int cxMempoolRegister2( + CxMempool *pool, + void *memory, + cx_destructor_func2 destr, + void *data +); + +/** + * Transfers all the memory managed by one pool to another. + * + * The allocator of the source pool will also be transferred and registered with the destination pool + * and stays valid, as long as the destination pool is not destroyed. + * + * The source pool will get a completely new allocator and can be reused or destroyed afterward. + * + * This function fails when the destination pool has a different type than the source pool. + * + * @param source the pool to move the memory from + * @param dest the pool where to transfer the memory to + * @retval zero success + * @retval non-zero allocation failure or incompatible pools + */ +cx_attr_nonnull +cx_attr_export +int cxMempoolTransfer( + CxMempool *source, + CxMempool *dest +); + +/** + * Transfers an object from one pool to another. + * + * This function fails when the destination pool has a different type than the source pool. + * + * @attention If the object maintains a reference to the pool's allocator, + * you must make sure to update that reference to the allocator of the destination pool. + * + * @param source the pool to move the memory from + * @param dest the pool where to transfer the memory to + * @param obj pointer to the object that shall be transferred + * @retval zero success + * @retval non-zero failure, or the object was not found in the source pool, or the pools are incompatible + */ +cx_attr_nonnull +cx_attr_export +int cxMempoolTransferObject( + CxMempool *source, + CxMempool *dest, + const void *obj +); + #ifdef __cplusplus } // extern "C" #endif diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/printf.h --- a/ucx/cx/printf.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/printf.h Thu May 29 15:59:27 2025 +0200 @@ -229,7 +229,7 @@ cx_attr_cstr_arg(4) cx_attr_export int cx_sprintf_a( - CxAllocator *alloc, + const CxAllocator *alloc, char **str, size_t *len, const char *fmt, @@ -274,7 +274,7 @@ cx_attr_access_rw(3) cx_attr_export int cx_vsprintf_a( - CxAllocator *alloc, + const CxAllocator *alloc, char **str, size_t *len, const char *fmt, @@ -333,7 +333,7 @@ cx_attr_access_rw(4) cx_attr_export int cx_sprintf_sa( - CxAllocator *alloc, + const CxAllocator *alloc, char *buf, size_t *len, char **str, @@ -388,7 +388,7 @@ cx_attr_cstr_arg(5) cx_attr_export int cx_vsprintf_sa( - CxAllocator *alloc, + const CxAllocator *alloc, char *buf, size_t *len, char **str, diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/properties.h --- a/ucx/cx/properties.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/properties.h Thu May 29 15:59:27 2025 +0200 @@ -551,10 +551,12 @@ /** * Creates a properties sink for an UCX map. * - * The values stored in the map will be pointers to strings allocated - * by #cx_strdup_a(). - * The default stdlib allocator will be used, unless you specify a custom - * allocator in the optional @c data of the sink. + * The values stored in the map will be pointers to freshly allocated, + * zero-terminated C strings (@c char*), which means the @p map should have been + * created with #CX_STORE_POINTERS. + * + * The cxDefaultAllocator will be used unless you specify a custom + * allocator in the optional @c data field of the returned sink. * * @param map the map that shall consume the k/v-pairs. * @return the sink diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/string.h --- a/ucx/cx/string.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/string.h Thu May 29 15:59:27 2025 +0200 @@ -39,6 +39,12 @@ #include "common.h" #include "allocator.h" +/** Expands a UCX string as printf arguments. */ +#define CX_SFMT(s) (int) (s).length, (s).ptr + +/** Format specifier for a UCX string */ +#define CX_PRIstr ".*s" + /** * The maximum length of the "needle" in cx_strstr() that can use SBO. */ @@ -151,7 +157,7 @@ * * @param literal the string literal */ -#define CX_STR(literal) (cxstring){literal, sizeof(literal) - 1} +#define CX_STR(literal) ((cxstring){literal, sizeof(literal) - 1}) #endif @@ -299,7 +305,7 @@ #endif /** - * Passes the pointer in this string to @c free(). + * Passes the pointer in this string to the cxDefaultAllocator's @c free() function. * * The pointer in the struct is set to @c NULL and the length is set to zero * which means that this function protects you against double-free. @@ -334,6 +340,46 @@ ); /** + * Copies a string. + * + * The memory in the @p dest structure is either allocated or re-allocated to fit the entire + * source string, including a zero-terminator. + * + * The string in @p dest is guaranteed to be zero-terminated, regardless of whether @p src is. + * + * @param alloc the allocator + * @param dest a pointer to the structure where to copy the contents to + * @param src the source string + * + * @retval zero success + * @retval non-zero if re-allocation failed + */ +cx_attr_nonnull_arg(1) +cx_attr_export +int cx_strcpy_a( + const CxAllocator *alloc, + cxmutstr *dest, + cxstring src +); + + +/** + * Copies a string. + * + * The memory in the @p dest structure is either allocated or re-allocated to fit the entire + * source string, including a zero-terminator. + * + * The string in @p dest is guaranteed to be zero-terminated, regardless of whether @p src is. + * + * @param dest (@c cxmutstr*) a pointer to the structure where to copy the contents to + * @param src (@c cxstring) the source string + * + * @retval zero success + * @retval non-zero if re-allocation failed + */ +#define cx_strcpy(dest, src) cx_strcpy_a(cxDefaultAllocator, dest, src) + +/** * Returns the accumulated length of all specified strings. * * If this sum overflows, errno is set to EOVERFLOW. @@ -408,7 +454,7 @@ /** * Concatenates strings and returns a new string. * - * The resulting string will be allocated by standard @c malloc(). + * The resulting string will be allocated by the cxDefaultAllocator. * So developers @em must pass the return value to cx_strfree() eventually. * * If memory allocation fails, the pointer in the returned string will @@ -428,7 +474,7 @@ /** * Concatenates strings. * - * The resulting string will be allocated by standard @c malloc(). + * The resulting string will be allocated by the cxDefaultAllocator. * So developers @em must pass the return value to cx_strfree() eventually. * * If @p str already contains a string, the memory will be reallocated and @@ -879,13 +925,13 @@ * @see cx_strfree_a() */ #define cx_strdup_a(allocator, string) \ - cx_strdup_a_((allocator), cx_strcast((string))) + cx_strdup_a_((allocator), cx_strcast(string)) /** * Creates a duplicate of the specified string. * - * The new string will contain a copy allocated by standard - * @c malloc(). So developers @em must pass the return value to cx_strfree(). + * The new string will contain a copy allocated by the cxDefaultAllocator. + * So developers @em must pass the return value to cx_strfree(). * * @note The returned string is guaranteed to be zero-terminated. * @@ -894,7 +940,7 @@ * @see cx_strdup_a() * @see cx_strfree() */ -#define cx_strdup(string) cx_strdup_a_(cxDefaultAllocator, string) +#define cx_strdup(string) cx_strdup_a(cxDefaultAllocator, string) /** * Omits leading and trailing spaces. @@ -1016,7 +1062,7 @@ * * Replaces at most @p replmax occurrences. * - * The returned string will be allocated by @c malloc() and is guaranteed + * The returned string will be allocated by the cxDefaultAllocator and is guaranteed * to be zero-terminated. * * If allocation fails, or the input string is empty, @@ -1052,7 +1098,7 @@ /** * Replaces a string with another string. * - * The returned string will be allocated by @c malloc() and is guaranteed + * The returned string will be allocated by the cxDefaultAllocator and is guaranteed * to be zero-terminated. * * If allocation fails, or the input string is empty, @@ -1091,7 +1137,7 @@ * @return (@c CxStrtokCtx) a new string tokenization context */ #define cx_strtok(str, delim, limit) \ - cx_strtok_(cx_strcast((str)), cx_strcast((delim)), (limit)) + cx_strtok_(cx_strcast(str), cx_strcast(delim), (limit)) /** * Returns the next token. diff -r 6cfda23ae154 -r 5ea41679e15d ucx/cx/tree.h --- a/ucx/cx/tree.h Thu May 29 15:59:17 2025 +0200 +++ b/ucx/cx/tree.h Thu May 29 15:59:27 2025 +0200 @@ -120,6 +120,7 @@ size_t stack_size; /** * The current depth in the tree. + * The node with which the iteration starts has depth 1. */ size_t depth; }; @@ -135,6 +136,7 @@ void *node; /** * The depth of the node. + * The first visited node has depth 1. */ size_t depth; /** @@ -211,7 +213,7 @@ */ cx_attr_nonnull static inline void cxTreeIteratorDispose(CxTreeIterator *iter) { - free(iter->stack); + cxFreeDefault(iter->stack); iter->stack = NULL; } @@ -224,7 +226,7 @@ struct cx_tree_visitor_queue_s *q = visitor->queue_next; while (q != NULL) { struct cx_tree_visitor_queue_s *next = q->next; - free(q); + cxFreeDefault(q); q = next; } } @@ -441,7 +443,7 @@ * Creates a depth-first iterator for a tree with the specified root node. * * @note A tree iterator needs to maintain a stack of visited nodes, which is - * allocated using stdlib malloc(). + * allocated using the cxDefaultAllocator. * When the iterator becomes invalid, this memory is automatically released. * However, if you wish to cancel the iteration before the iterator becomes * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release @@ -469,8 +471,8 @@ /** * Creates a breadth-first iterator for a tree with the specified root node. * - * @note A tree visitor needs to maintain a queue of to be visited nodes, which - * is allocated using stdlib malloc(). + * @note A tree visitor needs to maintain a queue of to-be visited nodes, which + * is allocated using the cxDefaultAllocator. * When the visitor becomes invalid, this memory is automatically released. * However, if you wish to cancel the iteration before the visitor becomes * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release @@ -956,7 +958,7 @@ * will free the nodes with the allocator's free() method. * * @param allocator the allocator that shall be used - * (if @c NULL, a default stdlib allocator will be used) + * (if @c NULL, the cxDefaultAllocator will be used) * @param create_func a function that creates new nodes * @param search_func a function that compares two nodes * @param search_data_func a function that compares a node with data @@ -1020,7 +1022,7 @@ * tree, you need to specify those functions afterwards. * * @param allocator the allocator that was used for nodes of the wrapped tree - * (if @c NULL, a default stdlib allocator is assumed) + * (if @c NULL, the cxDefaultAllocator is assumed) * @param root the root node of the tree that shall be wrapped * @param loc_parent offset in the node struct for the parent pointer * @param loc_children offset in the node struct for the children linked list @@ -1188,6 +1190,18 @@ size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); /** + * Determines the size of the entire tree. + * + * @param tree the tree + * @return the tree size, counting the root as one + */ +cx_attr_nonnull +cx_attr_nodiscard +static inline size_t cxTreeSize(CxTree *tree) { + return tree->size; +} + +/** * Determines the depth of the entire tree. * * @param tree the tree diff -r 6cfda23ae154 -r 5ea41679e15d ucx/json.c --- a/ucx/json.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/json.c Thu May 29 15:59:27 2025 +0200 @@ -500,7 +500,7 @@ if (all_printable && escape) { size_t capa = str.length + 32; - char *space = malloc(capa); + char *space = cxMallocDefault(capa); if (space == NULL) return cx_mutstrn(NULL, 0); cxBufferInit(&buf, space, capa, NULL, CX_BUFFER_AUTO_EXTEND); cxBufferWrite(str.ptr, 1, i, &buf); @@ -631,10 +631,10 @@ void cxJsonDestroy(CxJson *json) { cxBufferDestroy(&json->buffer); if (json->states != json->states_internal) { - free(json->states); + cxFreeDefault(json->states); } if (json->vbuf != json->vbuf_internal) { - free(json->vbuf); + cxFreeDefault(json->vbuf); } cxJsonValueFree(json->parsed); json->parsed = NULL; @@ -984,67 +984,67 @@ if (values[i] == NULL) break; cxJsonValueFree(values[i]); } - free(values); + cxFreeDefault(values); } // LCOV_EXCL_STOP int cxJsonArrAddNumbers(CxJsonValue* arr, const double* num, size_t count) { - CxJsonValue** values = calloc(count, sizeof(CxJsonValue*)); + CxJsonValue** values = cxCallocDefault(count, sizeof(CxJsonValue*)); if (values == NULL) return -1; for (size_t i = 0; i < count; i++) { values[i] = cxJsonCreateNumber(arr->allocator, num[i]); if (values[i] == NULL) { json_arr_free_temp(values, count); return -1; } } int ret = cxJsonArrAddValues(arr, values, count); - free(values); + cxFreeDefault(values); return ret; } int cxJsonArrAddIntegers(CxJsonValue* arr, const int64_t* num, size_t count) { - CxJsonValue** values = calloc(count, sizeof(CxJsonValue*)); + CxJsonValue** values = cxCallocDefault(count, sizeof(CxJsonValue*)); if (values == NULL) return -1; for (size_t i = 0; i < count; i++) { values[i] = cxJsonCreateInteger(arr->allocator, num[i]); if (values[i] == NULL) { json_arr_free_temp(values, count); return -1; } } int ret = cxJsonArrAddValues(arr, values, count); - free(values); + cxFreeDefault(values); return ret; } int cxJsonArrAddStrings(CxJsonValue* arr, const char* const* str, size_t count) { - CxJsonValue** values = calloc(count, sizeof(CxJsonValue*)); + CxJsonValue** values = cxCallocDefault(count, sizeof(CxJsonValue*)); if (values == NULL) return -1; for (size_t i = 0; i < count; i++) { values[i] = cxJsonCreateString(arr->allocator, str[i]); if (values[i] == NULL) { json_arr_free_temp(values, count); return -1; } } int ret = cxJsonArrAddValues(arr, values, count); - free(values); + cxFreeDefault(values); return ret; } int cxJsonArrAddCxStrings(CxJsonValue* arr, const cxstring* str, size_t count) { - CxJsonValue** values = calloc(count, sizeof(CxJsonValue*)); + CxJsonValue** values = cxCallocDefault(count, sizeof(CxJsonValue*)); if (values == NULL) return -1; for (size_t i = 0; i < count; i++) { values[i] = cxJsonCreateCxString(arr->allocator, str[i]); if (values[i] == NULL) { json_arr_free_temp(values, count); return -1; } } int ret = cxJsonArrAddValues(arr, values, count); - free(values); + cxFreeDefault(values); return ret; } int cxJsonArrAddLiterals(CxJsonValue* arr, const CxJsonLiteral* lit, size_t count) { - CxJsonValue** values = calloc(count, sizeof(CxJsonValue*)); + CxJsonValue** values = cxCallocDefault(count, sizeof(CxJsonValue*)); if (values == NULL) return -1; for (size_t i = 0; i < count; i++) { values[i] = cxJsonCreateLiteral(arr->allocator, lit[i]); if (values[i] == NULL) { json_arr_free_temp(values, count); return -1; } } int ret = cxJsonArrAddValues(arr, values, count); - free(values); + cxFreeDefault(values); return ret; } diff -r 6cfda23ae154 -r 5ea41679e15d ucx/linked_list.c --- a/ucx/linked_list.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/linked_list.c Thu May 29 15:59:27 2025 +0200 @@ -401,7 +401,7 @@ ) { void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? - malloc(sizeof(void *) * length) : sbo; + cxMallocDefault(sizeof(void *) * length) : sbo; if (sorted == NULL) abort(); void *rc, *lc; @@ -439,7 +439,7 @@ *begin = sorted[0]; *end = sorted[length - 1]; if (sorted != sbo) { - free(sorted); + cxFreeDefault(sorted); } } @@ -613,7 +613,9 @@ // initialize new new_node new_node->prev = new_node->next = NULL; - memcpy(new_node->payload, elem, list->collection.elem_size); + if (elem != NULL) { + memcpy(new_node->payload, elem, list->collection.elem_size); + } // insert cx_linked_list *ll = (cx_linked_list *) list; @@ -659,12 +661,26 @@ return n; } -static int cx_ll_insert_element( +static void *cx_ll_insert_element( struct cx_list_s *list, size_t index, const void *element ) { - return 1 != cx_ll_insert_array(list, index, element, 1); + // out-of-bounds check + if (index > list->collection.size) return NULL; + + // find position efficiently + cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); + + // perform first insert + if (cx_ll_insert_at(list, node, element)) return NULL; + + // return a pointer to the data of the inserted node + if (node == NULL) { + return ((cx_linked_list *) list)->begin->payload; + } else { + return node->next->payload; + } } static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; @@ -920,6 +936,8 @@ const void *elem, bool remove ) { + if (list->collection.size == 0) return 0; + size_t index; cx_linked_list *ll = ((cx_linked_list *) list); cx_linked_list_node *node = cx_linked_list_find( @@ -1054,12 +1072,12 @@ } return result; } else { - int result = cx_ll_insert_element(list, list->collection.size, elem); - if (result == 0) { - iter->elem_count++; - iter->index = list->collection.size; + if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) { + return 1; } - return result; + iter->elem_count++; + iter->index = list->collection.size; + return 0; } } diff -r 6cfda23ae154 -r 5ea41679e15d ucx/list.c --- a/ucx/list.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/list.c Thu May 29 15:59:27 2025 +0200 @@ -62,7 +62,7 @@ list->climpl->deallocate(list); } -static int cx_pl_insert_element( +static void *cx_pl_insert_element( struct cx_list_s *list, size_t index, const void *element @@ -282,7 +282,7 @@ const char *src = data; size_t i = 0; for (; i < n; i++) { - if (0 != invoke_list_func( + if (NULL == invoke_list_func( insert_element, list, index + i, src + (i * elem_size))) return i; } @@ -329,7 +329,7 @@ // insert the elements at location si if (ins == 1) { - if (0 != invoke_list_func( + if (NULL == invoke_list_func( insert_element, list, di, src)) return inserted; } else { size_t r = invoke_list_func(insert_array, list, di, src, ins); @@ -354,7 +354,7 @@ void cx_list_default_sort(struct cx_list_s *list) { size_t elem_size = list->collection.elem_size; size_t list_size = list->collection.size; - void *tmp = malloc(elem_size * list_size); + void *tmp = cxMallocDefault(elem_size * list_size); if (tmp == NULL) abort(); // copy elements from source array @@ -377,7 +377,7 @@ loc += elem_size; } - free(tmp); + cxFreeDefault(tmp); } int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) { @@ -387,7 +387,7 @@ size_t elem_size = list->collection.elem_size; - void *tmp = malloc(elem_size); + void *tmp = cxMallocDefault(elem_size); if (tmp == NULL) return 1; void *ip = invoke_list_func(at, list, i); @@ -397,7 +397,7 @@ memcpy(ip, jp, elem_size); memcpy(jp, tmp, elem_size); - free(tmp); + cxFreeDefault(tmp); return 0; } @@ -494,3 +494,24 @@ if (list == NULL) return; list->cl->deallocate(list); } + +int cxListSet( + CxList *list, + size_t index, + const void *elem +) { + if (index >= list->collection.size) { + return 1; + } + + if (list->collection.store_pointer) { + // For pointer collections, always use climpl + void **target = list->climpl->at(list, index); + *target = (void *)elem; + } else { + void *target = list->cl->at(list, index); + memcpy(target, elem, list->collection.elem_size); + } + + return 0; +} diff -r 6cfda23ae154 -r 5ea41679e15d ucx/mempool.c --- a/ucx/mempool.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/mempool.c Thu May 29 15:59:27 2025 +0200 @@ -31,44 +31,69 @@ #include #include -struct cx_mempool_memory_s { - /** The destructor. */ - cx_destructor_func destructor; - /** The actual memory. */ - char c[]; -}; +static int cx_mempool_ensure_capacity( + struct cx_mempool_s *pool, + size_t needed_capacity +) { + if (needed_capacity <= pool->capacity) return 0; + size_t newcap = pool->capacity >= 1000 ? + pool->capacity + 1000 : pool->capacity * 2; + size_t newmsize; + // LCOV_EXCL_START + if (pool->capacity > newcap + || cx_szmul(newcap, sizeof(void*), &newmsize)) { + errno = EOVERFLOW; + return 1; + } // LCOV_EXCL_STOP + void **newdata = cxRealloc(pool->base_allocator, pool->data, newmsize); + if (newdata == NULL) return 1; + pool->data = newdata; + pool->capacity = newcap; + return 0; +} -static void *cx_mempool_malloc( +static int cx_mempool_ensure_registered_capacity( + struct cx_mempool_s *pool, + size_t needed_capacity +) { + if (needed_capacity <= pool->registered_capacity) return 0; + // we do not expect so many registrations + size_t newcap = pool->registered_capacity + 8; + size_t newmsize; + // LCOV_EXCL_START + if (pool->registered_capacity > newcap || cx_szmul(newcap, + sizeof(struct cx_mempool_foreign_memory_s), &newmsize)) { + errno = EOVERFLOW; + return 1; + } // LCOV_EXCL_STOP + void *newdata = cxRealloc(pool->base_allocator, pool->registered, newmsize); + if (newdata == NULL) return 1; + pool->registered = newdata; + pool->registered_capacity = newcap; + return 0; +} + +static void *cx_mempool_malloc_simple( void *p, size_t n ) { struct cx_mempool_s *pool = p; - if (pool->size >= pool->capacity) { - size_t newcap = pool->capacity - (pool->capacity % 16) + 16; - size_t newmsize; - if (pool->capacity > newcap || cx_szmul(newcap, - sizeof(struct cx_mempool_memory_s*), &newmsize)) { - errno = EOVERFLOW; - return NULL; - } - struct cx_mempool_memory_s **newdata = realloc(pool->data, newmsize); - if (newdata == NULL) return NULL; - pool->data = newdata; - pool->capacity = newcap; + if (cx_mempool_ensure_capacity(pool, pool->size + 1)) { + return NULL; // LCOV_EXCL_LINE } - struct cx_mempool_memory_s *mem = malloc(sizeof(cx_destructor_func) + n); + struct cx_mempool_memory_s *mem = + cxMalloc(pool->base_allocator, sizeof(struct cx_mempool_memory_s) + n); if (mem == NULL) return NULL; - - mem->destructor = pool->auto_destr; + mem->destructor = NULL; pool->data[pool->size] = mem; pool->size++; return mem->c; } -static void *cx_mempool_calloc( +static void *cx_mempool_calloc_simple( void *p, size_t nelem, size_t elsize @@ -78,53 +103,165 @@ errno = EOVERFLOW; return NULL; } - void *ptr = cx_mempool_malloc(p, msz); + void *ptr = cx_mempool_malloc_simple(p, msz); if (ptr == NULL) return NULL; memset(ptr, 0, nelem * elsize); return ptr; } -static void *cx_mempool_realloc( +static void cx_mempool_free_simple( + void *p, + void *ptr +) { + if (!ptr) return; + struct cx_mempool_s *pool = p; + + struct cx_mempool_memory_s *mem = + (void*) ((char *) ptr - sizeof(struct cx_mempool_memory_s)); + + for (size_t i = 0; i < pool->size; i++) { + if (mem == pool->data[i]) { + if (mem->destructor) { + mem->destructor(mem->c); + } + if (pool->destr) { + pool->destr(mem->c); + } + if (pool->destr2) { + pool->destr2(pool->destr2_data, mem->c); + } + cxFree(pool->base_allocator, mem); + size_t last_index = pool->size - 1; + if (i != last_index) { + pool->data[i] = pool->data[last_index]; + pool->data[last_index] = NULL; + } + pool->size--; + return; + } + } + abort(); // LCOV_EXCL_LINE +} + +static void *cx_mempool_realloc_simple( void *p, void *ptr, size_t n ) { + if (ptr == NULL) { + return cx_mempool_malloc_simple(p, n); + } + if (n == 0) { + cx_mempool_free_simple(p, ptr); + return NULL; + } struct cx_mempool_s *pool = p; - struct cx_mempool_memory_s *mem, *newm; - mem = (struct cx_mempool_memory_s*)(((char *) ptr) - sizeof(cx_destructor_func)); - newm = realloc(mem, n + sizeof(cx_destructor_func)); + const unsigned overhead = sizeof(struct cx_mempool_memory_s); + struct cx_mempool_memory_s *mem = + (void *) (((char *) ptr) - overhead); + struct cx_mempool_memory_s *newm = + cxRealloc(pool->base_allocator, mem, n + overhead); if (newm == NULL) return NULL; if (mem != newm) { for (size_t i = 0; i < pool->size; i++) { if (pool->data[i] == mem) { pool->data[i] = newm; - return ((char*)newm) + sizeof(cx_destructor_func); + return ((char*)newm) + overhead; } } abort(); // LCOV_EXCL_LINE } else { - return ptr; + // unfortunately glibc() realloc seems to always move + return ptr; // LCOV_EXCL_LINE + } +} + +static void cx_mempool_free_all_simple(const struct cx_mempool_s *pool) { + const bool has_destr = pool->destr; + const bool has_destr2 = pool->destr2; + for (size_t i = 0; i < pool->size; i++) { + struct cx_mempool_memory_s *mem = pool->data[i]; + if (mem->destructor) { + mem->destructor(mem->c); + } + if (has_destr) { + pool->destr(mem->c); + } + if (has_destr2) { + pool->destr2(pool->destr2_data, mem->c); + } + cxFree(pool->base_allocator, mem); } } -static void cx_mempool_free( +static cx_allocator_class cx_mempool_simple_allocator_class = { + cx_mempool_malloc_simple, + cx_mempool_realloc_simple, + cx_mempool_calloc_simple, + cx_mempool_free_simple +}; + +static void *cx_mempool_malloc_advanced( + void *p, + size_t n +) { + struct cx_mempool_s *pool = p; + + if (cx_mempool_ensure_capacity(pool, pool->size + 1)) { + return NULL; // LCOV_EXCL_LINE + } + + struct cx_mempool_memory2_s *mem = + cxMalloc(pool->base_allocator, sizeof(struct cx_mempool_memory2_s) + n); + if (mem == NULL) return NULL; + mem->destructor = NULL; + mem->data = NULL; + pool->data[pool->size] = mem; + pool->size++; + + return mem->c; +} + +static void *cx_mempool_calloc_advanced( + void *p, + size_t nelem, + size_t elsize +) { + size_t msz; + if (cx_szmul(nelem, elsize, &msz)) { + errno = EOVERFLOW; + return NULL; + } + void *ptr = cx_mempool_malloc_advanced(p, msz); + if (ptr == NULL) return NULL; + memset(ptr, 0, nelem * elsize); + return ptr; +} + +static void cx_mempool_free_advanced( void *p, void *ptr ) { if (!ptr) return; struct cx_mempool_s *pool = p; - struct cx_mempool_memory_s *mem = (struct cx_mempool_memory_s *) - ((char *) ptr - sizeof(cx_destructor_func)); + struct cx_mempool_memory2_s *mem = + (void*) ((char *) ptr - sizeof(struct cx_mempool_memory2_s)); for (size_t i = 0; i < pool->size; i++) { if (mem == pool->data[i]) { if (mem->destructor) { - mem->destructor(mem->c); + mem->destructor(mem->data, mem->c); + } + if (pool->destr) { + pool->destr(mem->c); } - free(mem); + if (pool->destr2) { + pool->destr2(pool->destr2_data, mem->c); + } + cxFree(pool->base_allocator, mem); size_t last_index = pool->size - 1; if (i != last_index) { pool->data[i] = pool->data[last_index]; @@ -137,19 +274,207 @@ abort(); // LCOV_EXCL_LINE } +static void *cx_mempool_realloc_advanced( + void *p, + void *ptr, + size_t n +) { + if (ptr == NULL) { + return cx_mempool_malloc_advanced(p, n); + } + if (n == 0) { + cx_mempool_free_advanced(p, ptr); + return NULL; + } + struct cx_mempool_s *pool = p; + + const unsigned overhead = sizeof(struct cx_mempool_memory2_s); + struct cx_mempool_memory2_s *mem = + (void *) (((char *) ptr) - overhead); + struct cx_mempool_memory2_s *newm = + cxRealloc(pool->base_allocator, mem, n + overhead); + + if (newm == NULL) return NULL; + if (mem != newm) { + for (size_t i = 0; i < pool->size; i++) { + if (pool->data[i] == mem) { + pool->data[i] = newm; + return ((char*)newm) + overhead; + } + } + abort(); // LCOV_EXCL_LINE + } else { + // unfortunately glibc() realloc seems to always move + return ptr; // LCOV_EXCL_LINE + } +} + +static void cx_mempool_free_all_advanced(const struct cx_mempool_s *pool) { + const bool has_destr = pool->destr; + const bool has_destr2 = pool->destr2; + for (size_t i = 0; i < pool->size; i++) { + struct cx_mempool_memory2_s *mem = pool->data[i]; + if (mem->destructor) { + mem->destructor(mem->data, mem->c); + } + if (has_destr) { + pool->destr(mem->c); + } + if (has_destr2) { + pool->destr2(pool->destr2_data, mem->c); + } + cxFree(pool->base_allocator, mem); + } +} + +static cx_allocator_class cx_mempool_advanced_allocator_class = { + cx_mempool_malloc_advanced, + cx_mempool_realloc_advanced, + cx_mempool_calloc_advanced, + cx_mempool_free_advanced +}; + + +static void *cx_mempool_malloc_pure( + void *p, + size_t n +) { + struct cx_mempool_s *pool = p; + + if (cx_mempool_ensure_capacity(pool, pool->size + 1)) { + return NULL; // LCOV_EXCL_LINE + } + + void *mem = cxMalloc(pool->base_allocator, n); + if (mem == NULL) return NULL; + pool->data[pool->size] = mem; + pool->size++; + + return mem; +} + +static void *cx_mempool_calloc_pure( + void *p, + size_t nelem, + size_t elsize +) { + size_t msz; + if (cx_szmul(nelem, elsize, &msz)) { + errno = EOVERFLOW; + return NULL; + } + void *ptr = cx_mempool_malloc_pure(p, msz); + if (ptr == NULL) return NULL; + memset(ptr, 0, nelem * elsize); + return ptr; +} + +static void cx_mempool_free_pure( + void *p, + void *ptr +) { + if (!ptr) return; + struct cx_mempool_s *pool = p; + + for (size_t i = 0; i < pool->size; i++) { + if (ptr == pool->data[i]) { + if (pool->destr) { + pool->destr(ptr); + } + if (pool->destr2) { + pool->destr2(pool->destr2_data, ptr); + } + cxFree(pool->base_allocator, ptr); + size_t last_index = pool->size - 1; + if (i != last_index) { + pool->data[i] = pool->data[last_index]; + pool->data[last_index] = NULL; + } + pool->size--; + return; + } + } + abort(); // LCOV_EXCL_LINE +} + +static void *cx_mempool_realloc_pure( + void *p, + void *ptr, + size_t n +) { + if (ptr == NULL) { + return cx_mempool_malloc_pure(p, n); + } + if (n == 0) { + cx_mempool_free_pure(p, ptr); + return NULL; + } + struct cx_mempool_s *pool = p; + void *newm = cxRealloc(pool->base_allocator, ptr, n); + if (newm == NULL) return NULL; + if (ptr != newm) { + for (size_t i = 0; i < pool->size; i++) { + if (pool->data[i] == ptr) { + pool->data[i] = newm; + return newm; + } + } + abort(); // LCOV_EXCL_LINE + } else { + // unfortunately glibc() realloc seems to always move + return ptr; // LCOV_EXCL_LINE + } +} + +static void cx_mempool_free_all_pure(const struct cx_mempool_s *pool) { + const bool has_destr = pool->destr; + const bool has_destr2 = pool->destr2; + for (size_t i = 0; i < pool->size; i++) { + void *mem = pool->data[i]; + if (has_destr) { + pool->destr(mem); + } + if (has_destr2) { + pool->destr2(pool->destr2_data, mem); + } + cxFree(pool->base_allocator, mem); + } +} + +static cx_allocator_class cx_mempool_pure_allocator_class = { + cx_mempool_malloc_pure, + cx_mempool_realloc_pure, + cx_mempool_calloc_pure, + cx_mempool_free_pure +}; + +static void cx_mempool_free_foreign(const struct cx_mempool_s *pool) { + for (size_t i = 0; i < pool->registered_size; i++) { + struct cx_mempool_foreign_memory_s info = pool->registered[i]; + if (info.destr2_data == NULL) { + if (info.destr) { + info.destr(info.mem); + } + } else { + info.destr2(info.destr2_data, info.mem); + } + } +} + void cxMempoolFree(CxMempool *pool) { if (pool == NULL) return; - struct cx_mempool_memory_s *mem; - for (size_t i = 0; i < pool->size; i++) { - mem = pool->data[i]; - if (mem->destructor) { - mem->destructor(mem->c); - } - free(mem); + if (pool->allocator->cl == &cx_mempool_simple_allocator_class) { + cx_mempool_free_all_simple(pool); + } else if (pool->allocator->cl == &cx_mempool_advanced_allocator_class) { + cx_mempool_free_all_advanced(pool); + } else { + cx_mempool_free_all_pure(pool); } - free(pool->data); - free((void*) pool->allocator); - free(pool); + cx_mempool_free_foreign(pool); + cxFree(pool->base_allocator, pool->data); + cxFree(pool->base_allocator, pool->registered); + cxFree(pool->base_allocator, (void*) pool->allocator); + cxFree(pool->base_allocator, pool); } void cxMempoolSetDestructor( @@ -159,18 +484,26 @@ *(cx_destructor_func *) ((char *) ptr - sizeof(cx_destructor_func)) = func; } +void cxMempoolSetDestructor2( + void *ptr, + cx_destructor_func2 func, + void *data +) { + struct cx_mempool_memory2_s *info = + (void*)((char *) ptr - sizeof(struct cx_mempool_memory2_s)); + info->destructor = func; + info->data = data; +} + void cxMempoolRemoveDestructor(void *ptr) { *(cx_destructor_func *) ((char *) ptr - sizeof(cx_destructor_func)) = NULL; } -struct cx_mempool_foreign_mem_s { - cx_destructor_func destr; - void* mem; -}; - -static void cx_mempool_destr_foreign_mem(void* ptr) { - struct cx_mempool_foreign_mem_s *fm = ptr; - fm->destr(fm->mem); +void cxMempoolRemoveDestructor2(void *ptr) { + struct cx_mempool_memory2_s *info = + (void*)((char *) ptr - sizeof(struct cx_mempool_memory2_s)); + info->destructor = NULL; + info->data = NULL; } int cxMempoolRegister( @@ -178,60 +511,206 @@ void *memory, cx_destructor_func destr ) { - struct cx_mempool_foreign_mem_s *fm = cx_mempool_malloc( - pool, - sizeof(struct cx_mempool_foreign_mem_s) - ); - if (fm == NULL) return 1; + if (cx_mempool_ensure_registered_capacity(pool, pool->registered_size + 1)) { + return 1; // LCOV_EXCL_LINE + } + + pool->registered[pool->registered_size++] = + (struct cx_mempool_foreign_memory_s) { + .mem = memory, + .destr = destr, + .destr2_data = NULL + }; + + return 0; +} - fm->mem = memory; - fm->destr = destr; - *(cx_destructor_func *) ((char *) fm - sizeof(cx_destructor_func)) = cx_mempool_destr_foreign_mem; +int cxMempoolRegister2( + CxMempool *pool, + void *memory, + cx_destructor_func2 destr, + void *data +) { + if (cx_mempool_ensure_registered_capacity(pool, pool->registered_size + 1)) { + return 1; // LCOV_EXCL_LINE + } + + pool->registered[pool->registered_size++] = + (struct cx_mempool_foreign_memory_s) { + .mem = memory, + .destr2 = destr, + .destr2_data = data + }; return 0; } -static cx_allocator_class cx_mempool_allocator_class = { - cx_mempool_malloc, - cx_mempool_realloc, - cx_mempool_calloc, - cx_mempool_free -}; - CxMempool *cxMempoolCreate( size_t capacity, - cx_destructor_func destr + enum cx_mempool_type type ) { + if (capacity == 0) capacity = 16; size_t poolsize; - if (cx_szmul(capacity, sizeof(struct cx_mempool_memory_s*), &poolsize)) { + if (cx_szmul(capacity, sizeof(void*), &poolsize)) { + // LCOV_EXCL_START errno = EOVERFLOW; return NULL; + } // LCOV_EXCL_STOP + + CxAllocator *provided_allocator = cxMallocDefault(sizeof(CxAllocator)); + if (provided_allocator == NULL) { // LCOV_EXCL_START + return NULL; + } // LCOV_EXCL_STOP + + CxMempool *pool = cxCallocDefault(1, sizeof(CxMempool)); + if (pool == NULL) { // LCOV_EXCL_START + cxFreeDefault(provided_allocator); + return NULL; + } // LCOV_EXCL_STOP + + provided_allocator->data = pool; + *((const CxAllocator**)&pool->base_allocator) = cxDefaultAllocator; + pool->allocator = provided_allocator; + if (type == CX_MEMPOOL_TYPE_SIMPLE) { + provided_allocator->cl = &cx_mempool_simple_allocator_class; + } else if (type == CX_MEMPOOL_TYPE_ADVANCED) { + provided_allocator->cl = &cx_mempool_advanced_allocator_class; + } else { + provided_allocator->cl = &cx_mempool_pure_allocator_class; } - struct cx_mempool_s *pool = - malloc(sizeof(struct cx_mempool_s)); - if (pool == NULL) return NULL; - - CxAllocator *provided_allocator = malloc(sizeof(CxAllocator)); - if (provided_allocator == NULL) { // LCOV_EXCL_START - free(pool); - return NULL; - } // LCOV_EXCL_STOP - provided_allocator->cl = &cx_mempool_allocator_class; - provided_allocator->data = pool; - - pool->allocator = provided_allocator; - - pool->data = malloc(poolsize); + pool->data = cxMallocDefault(poolsize); if (pool->data == NULL) { // LCOV_EXCL_START - free(provided_allocator); - free(pool); + cxFreeDefault(provided_allocator); + cxFreeDefault(pool); return NULL; } // LCOV_EXCL_STOP pool->size = 0; pool->capacity = capacity; - pool->auto_destr = destr; return pool; } + +void cxMempoolGlobalDestructor(CxMempool *pool, cx_destructor_func fnc) { + pool->destr = fnc; +} + +void cxMempoolGlobalDestructor2(CxMempool *pool, cx_destructor_func2 fnc, void *data) { + pool->destr2 = fnc; + pool->destr2_data = data; +} + +static void cx_mempool_free_transferred_allocator(void *base_al, void *al) { + cxFree(base_al, al); +} + +int cxMempoolTransfer( + CxMempool *source, + CxMempool *dest +) { + // safety checks + if (source == dest) return 1; + if (source->allocator->cl != dest->allocator->cl) return 1; + if (source->base_allocator->cl != dest->base_allocator->cl) return 1; + + // ensure enough capacity in the destination pool + if (cx_mempool_ensure_capacity(dest, dest->size + source->size)) { + return 1; // LCOV_EXCL_LINE + } + if (cx_mempool_ensure_registered_capacity(dest, + dest->registered_size + source->registered_size)) { + return 1; // LCOV_EXCL_LINE + } + + // allocate a replacement allocator for the source pool + CxAllocator *new_source_allocator = + cxMalloc(source->base_allocator, sizeof(CxAllocator)); + if (new_source_allocator == NULL) { // LCOV_EXCL_START + return 1; + } // LCOV_EXCL_STOP + new_source_allocator->cl = source->allocator->cl; + new_source_allocator->data = source; + + // transfer all the data + memcpy(&dest->data[dest->size], source->data, sizeof(void*)*source->size); + dest->size += source->size; + + // transfer all registered memory + memcpy(&dest->registered[dest->registered_size], source->registered, + sizeof(struct cx_mempool_foreign_memory_s) * source->size); + dest->registered_size += source->registered_size; + + // register the old allocator with the new pool + // we have to remove const-ness for this, but that's okay here + // also register the base allocator, s.t. the pool knows how to free it + CxAllocator *transferred_allocator = (CxAllocator*) source->allocator; + transferred_allocator->data = dest; + cxMempoolRegister2(dest, transferred_allocator, + cx_mempool_free_transferred_allocator, (void*)source->base_allocator); + + // prepare the source pool for re-use + source->allocator = new_source_allocator; + memset(source->data, 0, source->size * sizeof(void*)); + memset(source->registered, 0, + source->registered_size * sizeof(struct cx_mempool_foreign_memory_s)); + source->size = 0; + source->registered_size = 0; + + return 0; +} + +int cxMempoolTransferObject( + CxMempool *source, + CxMempool *dest, + const void *obj +) { + // safety checks + if (source == dest) return 1; + if (source->allocator->cl != dest->allocator->cl) return 1; + if (source->base_allocator->cl != dest->base_allocator->cl) return 1; + + // search for the object + for (size_t i = 0; i < source->size; i++) { + struct cx_mempool_memory_s *mem = source->data[i]; + if (mem->c == obj) { + // first, make sure that the dest pool can take the object + if (cx_mempool_ensure_capacity(dest, dest->size + 1)) { + return 1; // LCOV_EXCL_LINE + } + // remove from the source pool + size_t last_index = source->size - 1; + if (i != last_index) { + source->data[i] = source->data[last_index]; + source->data[last_index] = NULL; + } + source->size--; + // add to the target pool + dest->data[dest->size++] = mem; + return 0; + } + } + // search in the registered objects + for (size_t i = 0; i < source->registered_size; i++) { + struct cx_mempool_foreign_memory_s *mem = &source->registered[i]; + if (mem->mem == obj) { + // first, make sure that the dest pool can take the object + if (cx_mempool_ensure_registered_capacity(dest, + dest->registered_size + 1)) { + return 1; // LCOV_EXCL_LINE + } + dest->registered[dest->registered_size++] = *mem; + // remove from the source pool + size_t last_index = source->registered_size - 1; + if (i != last_index) { + source->registered[i] = source->registered[last_index]; + memset(&source->registered[last_index], 0, + sizeof(struct cx_mempool_foreign_memory_s)); + } + source->registered_size--; + return 0; + } + } + // not found + return 1; +} diff -r 6cfda23ae154 -r 5ea41679e15d ucx/printf.c --- a/ucx/printf.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/printf.c Thu May 29 15:59:27 2025 +0200 @@ -68,7 +68,7 @@ return (int) wfc(buf, 1, ret, stream); } else { int len = ret + 1; - char *newbuf = malloc(len); + char *newbuf = cxMallocDefault(len); if (!newbuf) { // LCOV_EXCL_START va_end(ap2); return -1; @@ -79,7 +79,7 @@ if (ret > 0) { ret = (int) wfc(newbuf, 1, ret, stream); } - free(newbuf); + cxFreeDefault(newbuf); } return ret; } @@ -121,7 +121,7 @@ if (s.ptr) { ret = vsnprintf(s.ptr, len, fmt, ap2); if (ret < 0) { - free(s.ptr); + cxFree(a, s.ptr); s.ptr = NULL; } else { s.length = (size_t) ret; @@ -132,7 +132,13 @@ return s; } -int cx_sprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, ... ) { +int cx_sprintf_a( + const CxAllocator *alloc, + char **str, + size_t *len, + const char *fmt, + ... +) { va_list ap; va_start(ap, fmt); int ret = cx_vsprintf_a(alloc, str, len, fmt, ap); @@ -140,7 +146,13 @@ return ret; } -int cx_vsprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, va_list ap) { +int cx_vsprintf_a( + const CxAllocator *alloc, + char **str, + size_t *len, + const char *fmt, + va_list ap +) { va_list ap2; va_copy(ap2, ap); int ret = vsnprintf(*str, *len, fmt, ap); @@ -162,7 +174,14 @@ return ret; } -int cx_sprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, ... ) { +int cx_sprintf_sa( + const CxAllocator *alloc, + char *buf, + size_t *len, + char **str, + const char *fmt, + ... +) { va_list ap; va_start(ap, fmt); int ret = cx_vsprintf_sa(alloc, buf, len, str, fmt, ap); @@ -170,7 +189,14 @@ return ret; } -int cx_vsprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, va_list ap) { +int cx_vsprintf_sa( + const CxAllocator *alloc, + char *buf, + size_t *len, + char **str, + const char *fmt, + va_list ap +) { va_list ap2; va_copy(ap2, ap); int ret = vsnprintf(buf, *len, fmt, ap); diff -r 6cfda23ae154 -r 5ea41679e15d ucx/properties.c --- a/ucx/properties.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/properties.c Thu May 29 15:59:27 2025 +0200 @@ -287,7 +287,7 @@ cx_attr_unused CxProperties *prop, CxPropertiesSource *src ) { - src->data_ptr = malloc(src->data_size); + src->data_ptr = cxMallocDefault(src->data_size); if (src->data_ptr == NULL) return 1; return 0; } @@ -296,7 +296,7 @@ cx_attr_unused CxProperties *prop, CxPropertiesSource *src ) { - free(src->data_ptr); + cxFreeDefault(src->data_ptr); } CxPropertiesSource cxPropertiesStringSource(cxstring str) { diff -r 6cfda23ae154 -r 5ea41679e15d ucx/streams.c --- a/ucx/streams.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/streams.c Thu May 29 15:59:27 2025 +0200 @@ -27,6 +27,7 @@ */ #include "cx/streams.h" +#include "cx/allocator.h" #ifndef CX_STREAM_BCOPY_BUF_SIZE #define CX_STREAM_BCOPY_BUF_SIZE 8192 @@ -57,7 +58,7 @@ lbuf = buf; } else { if (bufsize == 0) bufsize = CX_STREAM_BCOPY_BUF_SIZE; - lbuf = malloc(bufsize); + lbuf = cxMallocDefault(bufsize); if (lbuf == NULL) return 0; } @@ -74,7 +75,7 @@ } if (lbuf != buf) { - free(lbuf); + cxFreeDefault(lbuf); } return ncp; diff -r 6cfda23ae154 -r 5ea41679e15d ucx/string.c --- a/ucx/string.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/string.c Thu May 29 15:59:27 2025 +0200 @@ -65,7 +65,7 @@ void cx_strfree(cxmutstr *str) { if (str == NULL) return; - free(str->ptr); + cxFreeDefault(str->ptr); str->ptr = NULL; str->length = 0; } @@ -80,6 +80,22 @@ str->length = 0; } +int cx_strcpy_a( + const CxAllocator *alloc, + cxmutstr *dest, + cxstring src +) { + if (cxReallocate(alloc, &dest->ptr, src.length + 1)) { + return 1; + } + + memcpy(dest->ptr, src.ptr, src.length); + dest->length = src.length; + dest->ptr[dest->length] = '\0'; + + return 0; +} + size_t cx_strlen( size_t count, ... @@ -106,27 +122,16 @@ ... ) { if (count == 0) return str; - - cxstring strings_stack[8]; - cxstring *strings; - if (count > 8) { - strings = calloc(count, sizeof(cxstring)); - if (strings == NULL) { - return (cxmutstr) {NULL, 0}; - } - } else { - strings = strings_stack; - } - va_list ap; va_start(ap, count); + va_list ap2; + va_copy(ap2, ap); - // get all args and overall length + // compute overall length bool overflow = false; size_t slen = str.length; for (size_t i = 0; i < count; i++) { - cxstring s = va_arg (ap, cxstring); - strings[i] = s; + cxstring s = va_arg(ap, cxstring); if (slen > SIZE_MAX - str.length) overflow = true; slen += s.length; } @@ -134,10 +139,8 @@ // abort in case of overflow if (overflow) { + va_end(ap2); errno = EOVERFLOW; - if (strings != strings_stack) { - free(strings); - } return (cxmutstr) { NULL, 0 }; } @@ -149,9 +152,7 @@ newstr = cxRealloc(alloc, str.ptr, slen + 1); } if (newstr == NULL) { - if (strings != strings_stack) { - free(strings); - } + va_end(ap2); return (cxmutstr) {NULL, 0}; } str.ptr = newstr; @@ -160,19 +161,15 @@ size_t pos = str.length; str.length = slen; for (size_t i = 0; i < count; i++) { - cxstring s = strings[i]; + cxstring s = va_arg(ap2, cxstring); memcpy(str.ptr + pos, s.ptr, s.length); pos += s.length; } + va_end(ap2); // terminate string str.ptr[str.length] = '\0'; - // free temporary array - if (strings != strings_stack) { - free(strings); - } - return str; } @@ -289,8 +286,9 @@ // check needle length and use appropriate prefix table // if the pattern exceeds static prefix table, allocate on the heap const bool useheap = needle.length >= CX_STRSTR_SBO_SIZE; - register size_t *ptable = useheap ? calloc(needle.length + 1, - sizeof(size_t)) : s_prefix_table; + register size_t *ptable = useheap + ? cxCallocDefault(needle.length + 1, sizeof(size_t)) + : s_prefix_table; // keep counter in registers register size_t i, j; @@ -328,7 +326,7 @@ // if prefix table was allocated on the heap, free it if (useheap) { - free(ptable); + cxFreeDefault(ptable); } return result; @@ -588,27 +586,6 @@ #endif } -#ifndef CX_STRREPLACE_INDEX_BUFFER_SIZE -#define CX_STRREPLACE_INDEX_BUFFER_SIZE 64 -#endif - -struct cx_strreplace_ibuf { - size_t *buf; - struct cx_strreplace_ibuf *next; - unsigned int len; -}; - -static void cx_strrepl_free_ibuf(struct cx_strreplace_ibuf *buf) { - // remember, the first data is on the stack! - buf = buf->next; - while (buf) { - struct cx_strreplace_ibuf *next = buf->next; - free(buf->buf); - free(buf); - buf = next; - } -} - cxmutstr cx_strreplacen_a( const CxAllocator *allocator, cxstring str, @@ -616,108 +593,60 @@ cxstring replacement, size_t replmax ) { + // special cases + if (search.length == 0 || search.length > str.length || replmax == 0) { + return cx_strdup_a(allocator, str); + } - if (search.length == 0 || search.length > str.length || replmax == 0) - return cx_strdup_a(allocator, str); + size_t in_len = str.length; + size_t search_len = search.length; + size_t repl_len = replacement.length; - // Compute expected buffer length - size_t ibufmax = str.length / search.length; - size_t ibuflen = replmax < ibufmax ? replmax : ibufmax; - if (ibuflen > CX_STRREPLACE_INDEX_BUFFER_SIZE) { - ibuflen = CX_STRREPLACE_INDEX_BUFFER_SIZE; + // first run, count the occurrences + // and remember where the first is + size_t occurrences = 1; + cxstring first = cx_strstr(str, search); + if (first.length == 0) { + // special case, no replacements + return cx_strdup_a(allocator, str); + } + cxstring tmp = cx_strsubs(first, search_len); + while (occurrences < replmax && + (tmp = cx_strstr(tmp, search)).length > 0) { + occurrences++; + tmp = cx_strsubs(tmp, search_len); } - // First index buffer can be on the stack - struct cx_strreplace_ibuf ibuf, *curbuf = &ibuf; - size_t ibuf_sbo[CX_STRREPLACE_INDEX_BUFFER_SIZE]; - ibuf.buf = ibuf_sbo; - ibuf.next = NULL; - ibuf.len = 0; + // calculate necessary memory + signed long long diff_len = (signed long long) repl_len - search_len; + size_t out_len = in_len + diff_len * occurrences; + cxmutstr out = { + cxMalloc(allocator, out_len + 1), + out_len + }; + if (out.ptr == NULL) return out; - // Search occurrences - cxstring searchstr = str; - size_t found = 0; - do { - cxstring match = cx_strstr(searchstr, search); - if (match.length > 0) { - // Allocate next buffer in chain, if required - if (curbuf->len == ibuflen) { - struct cx_strreplace_ibuf *nextbuf = - calloc(1, sizeof(struct cx_strreplace_ibuf)); - if (!nextbuf) { - cx_strrepl_free_ibuf(&ibuf); - return cx_mutstrn(NULL, 0); - } - nextbuf->buf = calloc(ibuflen, sizeof(size_t)); - if (!nextbuf->buf) { - free(nextbuf); - cx_strrepl_free_ibuf(&ibuf); - return cx_mutstrn(NULL, 0); - } - curbuf->next = nextbuf; - curbuf = nextbuf; - } - - // Record match index - found++; - size_t idx = match.ptr - str.ptr; - curbuf->buf[curbuf->len++] = idx; - searchstr.ptr = match.ptr + search.length; - searchstr.length = str.length - idx - search.length; - } else { - break; - } - } while (searchstr.length > 0 && found < replmax); - - // Allocate result string - cxmutstr result; - { - long long adjlen = (long long) replacement.length - (long long) search.length; - size_t rcount = 0; - curbuf = &ibuf; - do { - rcount += curbuf->len; - curbuf = curbuf->next; - } while (curbuf); - result.length = str.length + rcount * adjlen; - result.ptr = cxMalloc(allocator, result.length + 1); - if (!result.ptr) { - cx_strrepl_free_ibuf(&ibuf); - return cx_mutstrn(NULL, 0); - } + // second run: perform the replacements + // but start where we found the first occurrence + const char *inp = str.ptr; + tmp = first; + char *outp = out.ptr; + while (occurrences-- > 0 && (tmp = cx_strstr(tmp, search)).length > 0) { + size_t copylen = tmp.ptr - inp; + memcpy(outp, inp, copylen); + outp += copylen; + memcpy(outp, replacement.ptr, repl_len); + outp += repl_len; + inp += copylen + search_len; + tmp = cx_strsubs(tmp, search_len); } - // Build result string - curbuf = &ibuf; - size_t srcidx = 0; - char *destptr = result.ptr; - do { - for (size_t i = 0; i < curbuf->len; i++) { - // Copy source part up to next match - size_t idx = curbuf->buf[i]; - size_t srclen = idx - srcidx; - if (srclen > 0) { - memcpy(destptr, str.ptr + srcidx, srclen); - destptr += srclen; - srcidx += srclen; - } + // add the remaining string + size_t copylen = in_len - (inp - str.ptr); + memcpy(outp, inp, copylen); + out.ptr[out_len] = '\0'; - // Copy the replacement and skip the source pattern - srcidx += search.length; - memcpy(destptr, replacement.ptr, replacement.length); - destptr += replacement.length; - } - curbuf = curbuf->next; - } while (curbuf); - memcpy(destptr, str.ptr + srcidx, str.length - srcidx); - - // Result is guaranteed to be zero-terminated - result.ptr[result.length] = '\0'; - - // Free index buffer - cx_strrepl_free_ibuf(&ibuf); - - return result; + return out; } CxStrtokCtx cx_strtok_( diff -r 6cfda23ae154 -r 5ea41679e15d ucx/tree.c --- a/ucx/tree.c Thu May 29 15:59:17 2025 +0200 +++ b/ucx/tree.c Thu May 29 15:59:27 2025 +0200 @@ -226,14 +226,14 @@ int ret_elem = sfunc(elem, node); if (ret_elem == 0) { // if found, exit the search - *result = (void *) elem; + *result = elem; ret = 0; break; } else if (ret_elem > 0 && ret_elem < ret) { // new distance is better *result = elem; ret = ret_elem; - } else { + } else if (ret_elem < 0 || ret_elem > ret) { // not contained or distance is worse, skip entire subtree cxTreeIteratorContinue(iter); } @@ -305,12 +305,12 @@ if (children == NULL) { // search for the next node - void *next; + void *next = NULL; cx_tree_iter_search_next: - // check if there is a sibling + // check if there is a sibling, but only if we are not a (subtree-)root if (iter->exiting) { next = iter->node_next; - } else { + } else if (iter->depth > 1) { next = tree_next(iter->node); iter->node_next = next; } @@ -326,7 +326,7 @@ // invalidate the iterator and free the node stack iter->node = iter->node_next = NULL; iter->stack_capacity = iter->depth = 0; - free(iter->stack); + cxFreeDefault(iter->stack); iter->stack = NULL; } else { // the parent node can be obtained from the top of stack @@ -386,7 +386,7 @@ iter.node = root; if (root != NULL) { iter.stack_capacity = 16; - iter.stack = malloc(sizeof(void *) * 16); + iter.stack = cxMallocDefault(sizeof(void *) * 16); iter.stack[0] = root; iter.counter = 1; iter.depth = 1; @@ -416,7 +416,7 @@ node = tree_next(node); while (node != NULL) { struct cx_tree_visitor_queue_s *q; - q = malloc(sizeof(struct cx_tree_visitor_queue_s)); + q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s)); q->depth = iter->queue_last->depth; q->node = node; iter->queue_last->next = q; @@ -445,7 +445,7 @@ } if (children != NULL) { struct cx_tree_visitor_queue_s *q; - q = malloc(sizeof(struct cx_tree_visitor_queue_s)); + q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s)); q->depth = iter->depth + 1; q->node = children; if (iter->queue_last == NULL) { @@ -474,7 +474,7 @@ assert(iter->queue_last == q); iter->queue_last = NULL; } - free(q); + cxFreeDefault(q); } // increment the node counter