# HG changeset patch # User Olaf Wintermann # Date 1684679698 -7200 # Node ID 4d7a2238c5acd0b0e19d6990c9b7b7d289ad5123 # Parent bbadf84cfc2da475ae077fe94e86c8d9600d55d1 update ucx diff -r bbadf84cfc2d -r 4d7a2238c5ac dav/Makefile --- a/dav/Makefile Sun May 21 11:52:06 2023 +0200 +++ b/dav/Makefile Sun May 21 16:34:58 2023 +0200 @@ -81,9 +81,9 @@ $(LD) -o $(XATTRTOOL_BIN) $(XATTR_OBJ) $(LDFLAGS) ../build/tool/%$(OBJ_EXT): %.c - $(CC) $(CFLAGS) $(DAV_CFLAGS) -I../ -I../ucx -c -o $@ $< + $(CC) -I../ucx -I../ $(CFLAGS) $(DAV_CFLAGS) -c -o $@ $< cppcheck: $(DAV_SRC) $(SYNC_SRC) - $(CPPCHECK) $(CPPCHECK_CONFIG) $(CPPCHECK_FLAGS) -I../ucx -I../ $+ 2>> ../$(CPPCHECK_LOG) + $(CPPCHECK) $(CPPCHECK_CONFIG) -I../ucx $(CPPCHECK_FLAGS) $+ 2>> ../$(CPPCHECK_LOG) diff -r bbadf84cfc2d -r 4d7a2238c5ac dav/sync.c --- a/dav/sync.c Sun May 21 11:52:06 2023 +0200 +++ b/dav/sync.c Sun May 21 16:34:58 2023 +0200 @@ -36,8 +36,10 @@ #include #include #include +#include #include #include +#include #include #include #include @@ -115,45 +117,12 @@ - -static bool nulliter_valid(void const *d) { - return false; -} - -static void * nulliter_current(void const *d) { - return NULL; -} - -void * nulliter_current_impl(void const *d) { - return NULL; -} - -void nulliter_next(void *d) { - // noop -} - -bool nulliter_flag_removal(void *d) { - return false; -} - - -static CxIterator nullIterator(void) { - CxIterator iter; - memset(&iter, 0, sizeof(CxIterator)); - iter.base.valid = nulliter_valid; - iter.base.current = nulliter_current; - iter.base.current_impl = nulliter_current_impl; - iter.base.next = nulliter_next; - iter.base.flag_removal = nulliter_flag_removal; - return iter; -} - static CxIterator mapIteratorValues(CxMap *map) { - return map ? cxMapIteratorValues(map) : nullIterator(); + return cxMapIteratorValues(map ? map : cxEmptyMap); } static CxIterator listIterator(CxList *list) { - return list ? cxListIterator(list) : nullIterator(); + return cxListIterator(list ? list : cxEmptyList); } typedef void*(*clonefunc)(void *elm, void *userdata); diff -r bbadf84cfc2d -r 4d7a2238c5ac libidav/Makefile --- a/libidav/Makefile Sun May 21 11:52:06 2023 +0200 +++ b/libidav/Makefile Sun May 21 16:34:58 2023 +0200 @@ -50,8 +50,8 @@ $(AR) $(ARFLAGS) $(AOFLAGS)$@ $(OBJ) ../build/libidav/%$(OBJ_EXT): %.c - $(CC) $(CFLAGS) $(DAV_CFLAGS) -I.. -I../ucx -c -o $@ $< + $(CC) -I../ucx $(CFLAGS) $(DAV_CFLAGS) -c -o $@ $< cppcheck: $(SRC) - $(CPPCHECK) $(CPPCHECK_CONFIG) $(CPPCHECK_FLAGS) -I../ucx $+ 2>> ../$(CPPCHECK_LOG) + $(CPPCHECK) $(CPPCHECK_CONFIG) -I../ucx $(CPPCHECK_FLAGS) $+ 2>> ../$(CPPCHECK_LOG) diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/Makefile --- a/ucx/Makefile Sun May 21 11:52:06 2023 +0200 +++ b/ucx/Makefile Sun May 21 16:34:58 2023 +0200 @@ -39,6 +39,7 @@ SRC += hash_map.c SRC += linked_list.c SRC += list.c +SRC += map.c SRC += printf.c SRC += string.c SRC += utils.c diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/array_list.c --- a/ucx/array_list.c Sun May 21 11:52:06 2023 +0200 +++ b/ucx/array_list.c Sun May 21 16:34:58 2023 +0200 @@ -169,7 +169,24 @@ static void cx_arl_destructor(struct cx_list_s *list) { cx_array_list *arl = (cx_array_list *) list; + + char *ptr = arl->data; + + if (list->simple_destructor) { + for (size_t i = 0; i < list->size; i++) { + cx_invoke_simple_destructor(list, ptr); + ptr += list->item_size; + } + } + if (list->advanced_destructor) { + for (size_t i = 0; i < list->size; i++) { + cx_invoke_advanced_destructor(list, ptr); + ptr += list->item_size; + } + } + cxFree(list->allocator, arl->data); + cxFree(list->allocator, list); } static size_t cx_arl_insert_array( diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/cx/iterator.h --- a/ucx/cx/iterator.h Sun May 21 11:52:06 2023 +0200 +++ b/ucx/cx/iterator.h Sun May 21 16:34:58 2023 +0200 @@ -51,6 +51,8 @@ /** * Returns a pointer to the current element. + * + * When valid returns false, the behavior of this function is undefined. */ __attribute__ ((__nonnull__)) void *(*current)(void const *); @@ -63,12 +65,16 @@ /** * Advances the iterator. + * + * When valid returns false, the behavior of this function is undefined. */ __attribute__ ((__nonnull__)) void (*next)(void *); /** * Flag current element for removal, if possible. + * + * When valid returns false, the behavior of this function is undefined. */ __attribute__ ((__nonnull__)) bool (*flag_removal)(void *); diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/cx/list.h --- a/ucx/cx/list.h Sun May 21 11:52:06 2023 +0200 +++ b/ucx/cx/list.h Sun May 21 16:34:58 2023 +0200 @@ -70,6 +70,9 @@ struct cx_list_class_s { /** * Destructor function. + * + * Implementations SHALL invoke the content destructor functions if provided + * and SHALL deallocate the list memory, if an allocator is provided. */ void (*destructor)(struct cx_list_s *list); @@ -632,6 +635,14 @@ __attribute__((__nonnull__)) void cxListDestroy(CxList *list); +/** + * A shared instance of an empty list. + * + * Writing to that list is undefined. + */ +extern CxList * const cxEmptyList; + + #ifdef __cplusplus } // extern "C" #endif diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/cx/map.h --- a/ucx/cx/map.h Sun May 21 11:52:06 2023 +0200 +++ b/ucx/cx/map.h Sun May 21 16:34:58 2023 +0200 @@ -63,6 +63,24 @@ }; /** + * The type of iterator for a map. + */ +enum cx_map_iterator_type { + /** + * Iterates over key/value pairs. + */ + CX_MAP_ITERATOR_PAIRS, + /** + * Iterates over keys only. + */ + CX_MAP_ITERATOR_KEYS, + /** + * Iterates over values only. + */ + CX_MAP_ITERATOR_VALUES +}; + +/** * The class definition for arbitrary maps. */ struct cx_map_class_s { @@ -108,40 +126,10 @@ ); /** - * Iterator over the key/value pairs. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator)(CxMap const *map); - - /** - * Iterator over the keys. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator_keys)(CxMap const *map); - - /** - * Iterator over the values. + * Creates an iterator for this map. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator_values)(CxMap const *map); - - /** - * Mutating iterator over the key/value pairs. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxMutIterator (*mut_iterator)(CxMap *map); - - /** - * Mutating iterator over the keys. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxMutIterator (*mut_iterator_keys)(CxMap *map); - - /** - * Mutating iterator over the values. - */ - __attribute__((__nonnull__, __warn_unused_result__)) - CxMutIterator (*mut_iterator_values)(CxMap *map); + CxIterator (*iterator)(CxMap const *map, enum cx_map_iterator_type type); }; /** @@ -158,6 +146,8 @@ void *value; }; +extern CxMap *const cxEmptyMap; + /** * Advises the map to store copies of the objects (default mode of operation). * @@ -225,8 +215,8 @@ * @return an iterator for the currently stored values */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIteratorValues(CxMap *map) { - return map->cl->iterator_values(map); +static inline CxIterator cxMapIteratorValues(CxMap const *map) { + return map->cl->iterator(map, CX_MAP_ITERATOR_VALUES); } /** @@ -241,8 +231,8 @@ * @return an iterator for the currently stored keys */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIteratorKeys(CxMap *map) { - return map->cl->iterator_keys(map); +static inline CxIterator cxMapIteratorKeys(CxMap const *map) { + return map->cl->iterator(map, CX_MAP_ITERATOR_KEYS); } /** @@ -259,8 +249,8 @@ * @see cxMapIteratorValues() */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIterator(CxMap *map) { - return map->cl->iterator(map); +static inline CxIterator cxMapIterator(CxMap const *map) { + return map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS); } @@ -274,9 +264,7 @@ * @return an iterator for the currently stored values */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) { - return map->cl->mut_iterator_values(map); -} +CxMutIterator cxMapMutIteratorValues(CxMap *map); /** * Creates a mutating iterator over the keys of a map. @@ -290,9 +278,7 @@ * @return an iterator for the currently stored keys */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) { - return map->cl->mut_iterator_keys(map); -} +CxMutIterator cxMapMutIteratorKeys(CxMap *map); /** * Creates a mutating iterator for a map. @@ -308,9 +294,7 @@ * @see cxMapMutIteratorValues() */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxMapMutIterator(CxMap *map) { - return map->cl->mut_iterator(map); -} +CxMutIterator cxMapMutIterator(CxMap *map); #ifdef __cplusplus } // end the extern "C" block here, because we want to start overloading diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/hash_map.c --- a/ucx/hash_map.c Sun May 21 11:52:06 2023 +0200 +++ b/ucx/hash_map.c Sun May 21 16:34:58 2023 +0200 @@ -26,10 +26,12 @@ * POSSIBILITY OF SUCH DAMAGE. */ -#include #include "cx/hash_map.h" #include "cx/utils.h" +#include +#include + struct cx_hash_map_element_s { /** A pointer to the next element in the current bucket. */ struct cx_hash_map_element_s *next; @@ -334,13 +336,30 @@ } } -static CxIterator cx_hash_map_iterator(CxMap const *map) { +static CxIterator cx_hash_map_iterator( + CxMap const *map, + enum cx_map_iterator_type type +) { CxIterator iter; iter.src_handle = map; iter.base.valid = cx_hash_map_iter_valid; iter.base.next = cx_hash_map_iter_next; - iter.base.current = cx_hash_map_iter_current_entry; + + switch (type) { + case CX_MAP_ITERATOR_PAIRS: + iter.base.current = cx_hash_map_iter_current_entry; + break; + case CX_MAP_ITERATOR_KEYS: + iter.base.current = cx_hash_map_iter_current_key; + break; + case CX_MAP_ITERATOR_VALUES: + iter.base.current = cx_hash_map_iter_current_value; + break; + default: + assert(false); + } + iter.base.flag_removal = cx_hash_map_iter_flag_rm; iter.base.remove = false; iter.base.mutating = false; @@ -370,40 +389,6 @@ return iter; } -static CxIterator cx_hash_map_iterator_keys(CxMap const *map) { - CxIterator iter = cx_hash_map_iterator(map); - iter.base.current = cx_hash_map_iter_current_key; - return iter; -} - -static CxIterator cx_hash_map_iterator_values(CxMap const *map) { - CxIterator iter = cx_hash_map_iterator(map); - iter.base.current = cx_hash_map_iter_current_value; - return iter; -} - -static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) { - CxIterator it = cx_hash_map_iterator(map); - it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; -} - -static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) { - CxMutIterator iter = cx_hash_map_mut_iterator(map); - iter.base.current = cx_hash_map_iter_current_key; - return iter; -} - -static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) { - CxMutIterator iter = cx_hash_map_mut_iterator(map); - iter.base.current = cx_hash_map_iter_current_value; - return iter; -} - static cx_map_class cx_hash_map_class = { cx_hash_map_destructor, cx_hash_map_clear, @@ -411,11 +396,6 @@ cx_hash_map_get, cx_hash_map_remove, cx_hash_map_iterator, - cx_hash_map_iterator_keys, - cx_hash_map_iterator_values, - cx_hash_map_mut_iterator, - cx_hash_map_mut_iterator_keys, - cx_hash_map_mut_iterator_values, }; CxMap *cxHashMapCreate( diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/linked_list.c --- a/ucx/linked_list.c Sun May 21 11:52:06 2023 +0200 +++ b/ucx/linked_list.c Sun May 21 16:34:58 2023 +0200 @@ -283,7 +283,7 @@ #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 #endif -static void *cx_linked_list_sort_merge( +static void cx_linked_list_sort_merge( ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, @@ -291,7 +291,9 @@ void *ls, void *le, void *re, - cx_compare_func cmp_func + cx_compare_func cmp_func, + void **begin, + void **end ) { void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? @@ -330,11 +332,11 @@ } ll_next(sorted[length - 1]) = NULL; - void *ret = sorted[0]; + *begin = sorted[0]; + *end = sorted[length-1]; if (sorted != sbo) { free(sorted); } - return ret; } void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function @@ -380,8 +382,10 @@ re = ll_next(rc); // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them - void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, - ln + rn, ls, le, re, cmp_func); + void *sorted_begin, *sorted_end; + cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, + ln + rn, ls, le, re, cmp_func, + &sorted_begin, &sorted_end); // Something left? Sort it! size_t remainder_length = cx_linked_list_size(re, loc_next); @@ -390,14 +394,13 @@ cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); // merge sorted list with (also sorted) remainder - *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, - ln + rn + remainder_length, - sorted, remainder, NULL, cmp_func); - } else { - // no remainder - we've got our sorted list - *begin = sorted; + cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, + ln + rn + remainder_length, + sorted_begin, remainder, NULL, cmp_func, + &sorted_begin, &sorted_end); } - if (end) *end = cx_linked_list_last(sorted, loc_next); + *begin = sorted_begin; + if (end) *end = sorted_end; } } @@ -873,11 +876,13 @@ cx_linked_list_node *node = ll->begin; while (node) { + cx_invoke_destructor(list, node->payload); void *next = node->next; cxFree(list->allocator, node); node = next; } - // do not free the list pointer, this is just a destructor! + + cxFree(list->allocator, list); } static cx_list_class cx_linked_list_class = { diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/list.c --- a/ucx/list.c Sun May 21 11:52:06 2023 +0200 +++ b/ucx/list.c Sun May 21 16:34:58 2023 +0200 @@ -195,34 +195,102 @@ // +// + +static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) { + // this is a noop, but MUST be implemented +} + +static void *cx_emptyl_at( + __attribute__((__unused__)) struct cx_list_s const *list, + __attribute__((__unused__)) size_t index +) { + return NULL; +} + +static ssize_t cx_emptyl_find( + __attribute__((__unused__)) struct cx_list_s const *list, + __attribute__((__unused__)) void const *elem +) { + return -1; +} + +static int cx_emptyl_compare( + __attribute__((__unused__)) struct cx_list_s const *list, + struct cx_list_s const *other +) { + if (other->size == 0) return 0; + return -1; +} + +static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) { + return false; +} + +static CxIterator cx_emptyl_iterator( + struct cx_list_s const *list, + size_t index, + __attribute__((__unused__)) bool backwards +) { + CxIterator iter = {0}; + iter.src_handle = list; + iter.index = index; + iter.base.valid = cx_emptyl_iter_valid; + return iter; +} + +static cx_list_class cx_empty_list_class = { + cx_emptyl_noop, + NULL, + NULL, + NULL, + NULL, + cx_emptyl_noop, + NULL, + cx_emptyl_at, + cx_emptyl_find, + cx_emptyl_noop, + cx_emptyl_compare, + cx_emptyl_noop, + cx_emptyl_iterator, +}; + +CxList cx_empty_list = { + NULL, + NULL, + 0, + 0, + NULL, + NULL, + NULL, + false, + &cx_empty_list_class, + NULL +}; + +CxList *const cxEmptyList = &cx_empty_list; + +// + void cxListDestroy(CxList *list) { - if (list->simple_destructor) { - CxIterator iter = cxListIterator(list); - cx_foreach(void*, elem, iter) { - // already correctly resolved pointer - immediately invoke dtor - list->simple_destructor(elem); - } - } - if (list->advanced_destructor) { - CxIterator iter = cxListIterator(list); - cx_foreach(void*, elem, iter) { - // already correctly resolved pointer - immediately invoke dtor - list->advanced_destructor(list->destructor_data, elem); - } - } - list->cl->destructor(list); - cxFree(list->allocator, list); } int cxListCompare( CxList const *list, CxList const *other ) { - if ((list->store_pointer ^ other->store_pointer) || - ((list->climpl == NULL) ^ (other->climpl != NULL)) || + if ( + // if one is storing pointers but the other is not + (list->store_pointer ^ other->store_pointer) || + + // if one class is wrapped but the other is not + ((list->climpl == NULL) ^ (other->climpl == NULL)) || + + // if the resolved compare functions are not the same ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) != - (other->climpl != NULL ? other->climpl->compare : other->cl->compare))) { + (other->climpl != NULL ? other->climpl->compare : other->cl->compare)) + ) { // lists are definitely different - cannot use internal compare function if (list->size == other->size) { CxIterator left = cxListIterator(list); diff -r bbadf84cfc2d -r 4d7a2238c5ac ucx/map.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/map.c Sun May 21 16:34:58 2023 +0200 @@ -0,0 +1,112 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/map.h" +#include + +// + +static void cx_empty_map_noop(__attribute__((__unused__)) CxMap *map) { + // this is a noop, but MUST be implemented +} + +static void *cx_empty_map_get( + __attribute__((__unused__)) CxMap const *map, + __attribute__((__unused__)) CxHashKey key +) { + return NULL; +} + +static bool cx_empty_map_iter_valid(__attribute__((__unused__)) void const *iter) { + return false; +} + +static CxIterator cx_empty_map_iterator( + struct cx_map_s const *map, + __attribute__((__unused__)) enum cx_map_iterator_type type +) { + CxIterator iter = {0}; + iter.src_handle = map; + iter.base.valid = cx_empty_map_iter_valid; + return iter; +} + +static struct cx_map_class_s cx_empty_map_class = { + cx_empty_map_noop, + cx_empty_map_noop, + NULL, + cx_empty_map_get, + NULL, + cx_empty_map_iterator +}; + +CxMap cx_empty_map = { + NULL, + NULL, + 0, + 0, + NULL, + NULL, + NULL, + false, + &cx_empty_map_class +}; + +CxMap *const cxEmptyMap = &cx_empty_map; + +// + +CxMutIterator cxMapMutIteratorValues(CxMap *map) { + CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_VALUES); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} + +CxMutIterator cxMapMutIteratorKeys(CxMap *map) { + CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_KEYS); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} + +CxMutIterator cxMapMutIterator(CxMap *map) { + CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +}