# HG changeset patch # User Olaf Wintermann # Date 1668943149 -3600 # Node ID 1260fad21be7f4cecbc0b2e03aa3c49fe245a183 # Parent 713ec3da79ecbe8a65948ea56dbc35a35ebf3f26 update ucx diff -r 713ec3da79ec -r 1260fad21be7 src/server/test/main.c --- a/src/server/test/main.c Sun Nov 20 11:39:46 2022 +0100 +++ b/src/server/test/main.c Sun Nov 20 12:19:09 2022 +0100 @@ -79,7 +79,6 @@ ucx_test_register(suite, test_util_uri_escape_kanji); // object tests - /* ucx_test_register(suite, test_expr_parse_expr_value); ucx_test_register(suite, test_expr_parse_expr_neg_value); ucx_test_register(suite, test_expr_parse_expr_value_str); @@ -91,8 +90,7 @@ ucx_test_register(suite, test_expr_parse_expr_compare2value_expr); ucx_test_register(suite, test_expr_parse_expr_compare2expr_value); ucx_test_register(suite, test_expr_parse_expr_bracket); - */ - //ucx_test_register(suite, test_expr_parse_expr_func_arg0); + ucx_test_register(suite, test_expr_parse_expr_func_arg0); ucx_test_register(suite, test_expr_parse_expr_func_arg1); ucx_test_register(suite, test_expr_parse_expr_func_arg3); ucx_test_register(suite, test_expr_parse_expr_func_expr1); diff -r 713ec3da79ec -r 1260fad21be7 src/ucx/Makefile --- a/src/ucx/Makefile Sun Nov 20 11:39:46 2022 +0100 +++ b/src/ucx/Makefile Sun Nov 20 12:19:09 2022 +0100 @@ -37,6 +37,7 @@ SRC += hash_key.c SRC += hash_map.c SRC += linked_list.c +SRC += array_list.c SRC += list.c SRC += string.c SRC += tree.c diff -r 713ec3da79ec -r 1260fad21be7 src/ucx/array_list.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ucx/array_list.c Sun Nov 20 12:19:09 2022 +0100 @@ -0,0 +1,342 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/array_list.h" +#include +#include +#include + +/* LOW LEVEL ARRAY LIST FUNCTIONS */ + +enum cx_array_copy_result cx_array_copy( + void **target, + size_t *size, + size_t *capacity, + size_t index, + void const *src, + size_t elem_size, + size_t elem_count, + struct cx_array_reallocator_s *reallocator +) { + /* assert pointers */ + assert(target != NULL); + assert(size != NULL); + assert(src != NULL); + + /* determine capacity */ + size_t cap = capacity == NULL ? *size : *capacity; + + /* check if resize is required */ + size_t newsize = index + elem_count; + bool needrealloc = newsize > cap; + + /* reallocate if possible */ + if (needrealloc) { + /* a reallocator and a capacity variable must be available */ + if (reallocator == NULL || capacity == NULL) { + return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; + } + + /* check, if we need to repair the src pointer */ + uintptr_t targetaddr = (uintptr_t) *target; + uintptr_t srcaddr = (uintptr_t) src; + bool repairsrc = targetaddr <= srcaddr + && srcaddr < targetaddr + cap * elem_size; + + /* increase capacity linearly */ + cap += 16; + + /* perform reallocation */ + void *newmem = reallocator->realloc( + *target, cap, elem_size, reallocator + ); + if (newmem == NULL) { + return CX_ARRAY_COPY_REALLOC_FAILED; + } + + /* repair src pointer, if necessary */ + if (repairsrc) { + src = ((char *) newmem) + (srcaddr - targetaddr); + } + + /* store new pointer and capacity */ + *target = newmem; + *capacity = cap; + } + + /* determine target pointer */ + char *start = *target; + start += index * elem_size; + + /* copy elements and set new size */ + memmove(start, src, elem_count * elem_size); + *size = newsize; + + /* return successfully */ + return CX_ARRAY_COPY_SUCCESS; +} + +/* HIGH LEVEL ARRAY LIST FUNCTIONS */ + +typedef struct { + struct cx_list_s base; + void *data; + struct cx_array_reallocator_s reallocator; +} cx_array_list; + +static void *cx_arl_realloc( + void *array, + size_t capacity, + size_t elem_size, + struct cx_array_reallocator_s *alloc +) { + /* retrieve the pointer to the list allocator */ + CxAllocator const *al = alloc->ptr1; + + /* use the list allocator to reallocate the memory */ + return cxRealloc(al, array, capacity * elem_size); +} + +static void cx_arl_destructor(struct cx_list_s *list) { + cx_array_list *arl = (cx_array_list *) list; + cxFree(list->allocator, arl->data); +} + +static int cx_arl_add( + struct cx_list_s *list, + void const *elem +) { + cx_array_list *arl = (cx_array_list *) list; + return cx_array_copy( + &arl->data, + &list->size, + &list->capacity, + list->size, + elem, + list->itemsize, + 1, + &arl->reallocator + ); +} + +static int cx_arl_insert( + struct cx_list_s *list, + size_t index, + void const *elem +) { + if (index > list->size) { + return 1; + } else if (index == list->size) { + return cx_arl_add(list, elem); + } else { + cx_array_list *arl = (cx_array_list *) list; + + /* move elements starting at index to the right */ + if (cx_array_copy( + &arl->data, + &list->size, + &list->capacity, + index + 1, + ((char *) arl->data) + index * list->itemsize, + list->itemsize, + list->size - index, + &arl->reallocator + )) { + return 1; + } + + /* place the element */ + memcpy(((char *) arl->data) + index * list->itemsize, + elem, list->itemsize); + + return 0; + } +} + +static int cx_arl_insert_iter( + struct cx_iterator_s *iter, + void const *elem, + int prepend +) { + return 1; +} + +static int cx_arl_remove( + struct cx_list_s *list, + size_t index +) { + /* out-of-bounds check */ + if (index >= list->size) { + return 1; + } + + cx_array_list *arl = (cx_array_list *) list; + + /* just move the elements starting at index to the left */ + int result = cx_array_copy( + &arl->data, + &list->size, + &list->capacity, + index, + ((char *) arl->data) + (index + 1) * list->itemsize, + list->itemsize, + list->size - index, + &arl->reallocator + ); + if (result == 0) { + /* decrease the size */ + list->size--; + } + return result; +} + +static void *cx_arl_at( + struct cx_list_s const *list, + size_t index +) { + if (index < list->size) { + cx_array_list const *arl = (cx_array_list const *) list; + char *space = arl->data; + return space + index * list->itemsize; + } else { + return NULL; + } +} + +static size_t cx_arl_find( + struct cx_list_s const *list, + void const *elem +) { + char *cur = ((cx_array_list const *) list)->data; + + for (size_t i = 0; i < list->size; i++) { + if (0 == list->cmpfunc(elem, cur)) { + return i; + } + cur += list->itemsize; + } + + return list->size; +} + +static void cx_arl_sort(struct cx_list_s *list) { + qsort(((cx_array_list *) list)->data, + list->size, + list->itemsize, + list->cmpfunc + ); +} + +static int cx_arl_compare( + struct cx_list_s const *list, + struct cx_list_s const *other +) { + +} + +static void cx_arl_reverse(struct cx_list_s *list) { + +} + +static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) { + struct cx_list_s const *list = iter->src_handle; + return iter->index < list->size; +} + +static void *cx_arl_iter_current(struct cx_iterator_s const *iter) { + return iter->elem_handle; +} + +static void cx_arl_iter_next(struct cx_iterator_s *iter) { + if (iter->remove) { + iter->remove = false; + cx_arl_remove(iter->src_handle, iter->index); + } else { + iter->index++; + iter->elem_handle = cx_arl_at(iter->src_handle, iter->index); + } +} + +static struct cx_iterator_s cx_arl_iterator( + struct cx_list_s *list, + size_t index +) { + struct cx_iterator_s iter; + + iter.index = index; + iter.src_handle = list; + iter.elem_handle = cx_arl_at(list, index); + iter.valid = cx_arl_iter_valid; + iter.current = cx_arl_iter_current; + iter.next = cx_arl_iter_next; + iter.remove = false; + + return iter; +} + +static cx_list_class cx_array_list_class = { + cx_arl_destructor, + cx_arl_add, + cx_arl_insert, + cx_arl_insert_iter, + cx_arl_remove, + cx_arl_at, + cx_arl_find, + cx_arl_sort, + cx_arl_compare, + cx_arl_reverse, + cx_arl_iterator, +}; + +CxList *cxArrayListCreate( + CxAllocator const *allocator, + CxListComparator comparator, + size_t item_size, + size_t initial_capacity +) { + cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); + if (list == NULL) return NULL; + + list->data = cxCalloc(allocator, initial_capacity, item_size); + if (list->data == NULL) { + cxFree(allocator, list); + return NULL; + } + + list->base.cl = &cx_array_list_class; + list->base.allocator = allocator; + list->base.cmpfunc = comparator; + list->base.itemsize = item_size; + list->base.capacity = initial_capacity; + + /* configure the reallocator */ + list->reallocator.realloc = cx_arl_realloc; + list->reallocator.ptr1 = (void *) allocator; + + return (CxList *) list; +} diff -r 713ec3da79ec -r 1260fad21be7 src/ucx/cx/array_list.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ucx/cx/array_list.h Sun Nov 20 12:19:09 2022 +0100 @@ -0,0 +1,156 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +/** + * \file array_list.h + * \brief Array list implementation. + * \details Also provides several low-level functions for custom array list implementations. + * \author Mike Becker + * \author Olaf Wintermann + * \version 3.0 + * \copyright 2-Clause BSD License + */ + + +#ifndef UCX_ARRAY_LIST_H +#define UCX_ARRAY_LIST_H + +#include "list.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * Defines a reallocation mechanism for arrays. + */ +struct cx_array_reallocator_s { + /** + * Re-allocates space for the given array. + * + * Implementations are not required to free the original array. + * This allows re-allocation of static memory by allocating heap memory + * and copying the array contents. The information in \p data can keep + * track of the state of the memory or other additional allocator info. + * + * @param array the array to reallocate + * @param capacity the new capacity (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 + */ + void *(*realloc)( + void *array, + size_t capacity, + size_t elem_size, + struct cx_array_reallocator_s *alloc + ); + + /** + * Custom data pointer. + */ + void *ptr1; + /** + * Custom data pointer. + */ + void *ptr2; + /** + * Custom data integer. + */ + size_t int1; + /** + * Custom data integer. + */ + size_t int2; +}; + +/** + * Return codes for cx_array_copy(). + */ +enum cx_array_copy_result { + CX_ARRAY_COPY_SUCCESS, + CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED, + CX_ARRAY_COPY_REALLOC_FAILED, +}; + +/** + * Copies elements from one array to another. + * + * The elements are copied to the \p target array at the specified \p index, + * overwriting possible elements. The index must be in range of the current + * array \p size. If the number of elements added would extend the array's size, + * and \p capacity is not \c NULL, the remaining capacity is used. + * + * If the capacity is insufficient to hold the new data, a reallocation + * attempt is made, unless the allocator is set to \c NULL, in which case + * this function ultimately returns a failure. + * + * @param target the target array + * @param size a pointer to the size of the target array + * @param capacity a pointer to the target array's capacity - + * \c NULL if only the size shall be used to bound the array + * @param index the index where the copied elements shall be placed + * @param src the source array + * @param elem_size the size of one element + * @param elem_count the number of elements to copy + * @param reallocator the array re-allocator to use, or \c NULL + * if re-allocation shall not happen + * @return zero on success, non-zero error code on failure + */ +enum cx_array_copy_result cx_array_copy( + void **target, + size_t *size, + size_t *capacity, + size_t index, + void const *src, + size_t elem_size, + size_t elem_count, + struct cx_array_reallocator_s *reallocator +) __attribute__((__nonnull__(1, 2, 5))); + +/** + * Allocates an array list for storing elements with \p item_size bytes each. + * + * @param allocator the allocator for allocating the list memory + * @param comparator the comparator for the elements + * @param item_size the size of each element in bytes + * @param initial_capacity the initial number of elements the array can store + * @return the created list + */ +CxList *cxArrayListCreate( + CxAllocator const *allocator, + CxListComparator comparator, + size_t item_size, + size_t initial_capacity +) __attribute__((__nonnull__)); + + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* UCX_ARRAY_LIST_H */