Mercurial > hg > ucx / changeset

     1.1 --- a/src/CMakeLists.txt	Tue Feb 15 19:07:14 2022 +0100
     1.2 +++ b/src/CMakeLists.txt	Tue Feb 15 19:41:48 2022 +0100
     1.3 @@ -1,6 +1,7 @@
     1.4  set(sources
     1.5          utils.c
     1.6          allocator.c
     1.7 +        list.c
     1.8          linked_list.c
     1.9          tree.c
    1.10          buffer.c

     2.1 --- a/src/cx/allocator.h	Tue Feb 15 19:07:14 2022 +0100
     2.2 +++ b/src/cx/allocator.h	Tue Feb 15 19:41:48 2022 +0100
     2.3 @@ -46,23 +46,37 @@
     2.4      /**
     2.5       * The allocator's malloc() implementation.
     2.6       */
     2.7 -    void *(*malloc)(void *data, size_t n);
     2.8 +    void *(*malloc)(
     2.9 +            void *data,
    2.10 +            size_t n
    2.11 +    );
    2.12  
    2.13      /**
    2.14       * The allocator's realloc() implementation.
    2.15       */
    2.16 -    void *(*realloc)(void *data, void *mem, size_t n)
    2.17 +    void *(*realloc)(
    2.18 +            void *data,
    2.19 +            void *mem,
    2.20 +            size_t n
    2.21 +    )
    2.22      __attribute__((__warn_unused_result__));
    2.23  
    2.24      /**
    2.25       * The allocator's calloc() implementation.
    2.26       */
    2.27 -    void *(*calloc)(void *data, size_t nelem, size_t n);
    2.28 +    void *(*calloc)(
    2.29 +            void *data,
    2.30 +            size_t nelem,
    2.31 +            size_t n
    2.32 +    );
    2.33  
    2.34      /**
    2.35       * The allocator's free() implementation.
    2.36       */
    2.37 -    void (*free)(void *data, void *mem)
    2.38 +    void (*free)(
    2.39 +            void *data,
    2.40 +            void *mem
    2.41 +    )
    2.42      __attribute__((__nonnull__));
    2.43  } cx_allocator_class;
    2.44  
    2.45 @@ -91,6 +105,18 @@
    2.46  extern CxAllocator *cxDefaultAllocator;
    2.47  
    2.48  /**
    2.49 + * Function pointer type for destructor functions.
    2.50 + *
    2.51 + * A destructor function deallocates possible contents and MAY free the memory
    2.52 + * pointed to by \p memory.
    2.53 + *
    2.54 + * @param memory a pointer to the object to destruct
    2.55 + * @return \p memory if it has NOT been free'd by this destructor, otherwise \c NULL
    2.56 +  */
    2.57 +typedef void *(*cx_destructor_func)(void *memory)
    2.58 +        __attribute__((__nonnull__, __warn_unused_result__));
    2.59 +
    2.60 +/**
    2.61   * Allocate \p n bytes of memory.
    2.62   *
    2.63   * @param allocator the allocator

     3.1 --- a/src/cx/common.h	Tue Feb 15 19:07:14 2022 +0100
     3.2 +++ b/src/cx/common.h	Tue Feb 15 19:41:48 2022 +0100
     3.3 @@ -114,6 +114,9 @@
     3.4  #endif /* _WIN32 */
     3.5  
     3.6  #ifndef __GNUC__
     3.7 +/**
     3.8 + * Removes GNU C attributes where they are not supported.
     3.9 + */
    3.10  #define __attribute__(x)
    3.11  #endif
    3.12  

     4.1 --- a/src/cx/linked_list.h	Tue Feb 15 19:07:14 2022 +0100
     4.2 +++ b/src/cx/linked_list.h	Tue Feb 15 19:41:48 2022 +0100
     4.3 @@ -94,15 +94,6 @@
     4.4  ) __attribute__((__nonnull__));
     4.5  
     4.6  /**
     4.7 - * Deallocates the memory of the entire list.
     4.8 - *
     4.9 - * \attention If this is a pointer list, the memory the pointers are referring to is \em not freed.
    4.10 - *
    4.11 - * @param list the list
    4.12 - */
    4.13 -void cxLinkedListDestroy(CxList *list) __attribute__((__nonnull__));
    4.14 -
    4.15 -/**
    4.16   * Finds the node at a certain index.
    4.17   *
    4.18   * This function can be used to start at an arbitrary position within the list.

     5.1 --- a/src/cx/list.h	Tue Feb 15 19:07:14 2022 +0100
     5.2 +++ b/src/cx/list.h	Tue Feb 15 19:41:48 2022 +0100
     5.3 @@ -71,6 +71,14 @@
     5.4       */
     5.5      CxAllocator *allocator;
     5.6      /**
     5.7 +     * A mandatory destructor for the list structure.
     5.8 +     */
     5.9 +    cx_destructor_func list_destructor;
    5.10 +    /**
    5.11 +     * An optional destructor for the list contents.
    5.12 +     */
    5.13 +    cx_destructor_func content_destructor;
    5.14 +    /**
    5.15       * The comparator function for the elements.
    5.16       */
    5.17      CxListComparator cmpfunc;
    5.18 @@ -86,6 +94,16 @@
    5.19       * The capacity of the list (maximum number of elements).
    5.20       */
    5.21      size_t capacity;
    5.22 +    /**
    5.23 +     * Flag indicating whether cxListDestroy() shall free the list structure,
    5.24 +     * even if cx_list_s.list_destructor did not do that.
    5.25 +     */
    5.26 +    bool autofree;
    5.27 +    /**
    5.28 +     * Flag indicating whether cxListDestroy() shall free each list element,
    5.29 +     * even if cx_list_s.content_destructor did not do that.
    5.30 +     */
    5.31 +    bool autofree_contents;
    5.32  };
    5.33  
    5.34  /**
    5.35 @@ -364,6 +382,21 @@
    5.36      return list->cl->compare(list, other);
    5.37  }
    5.38  
    5.39 +/**
    5.40 + * Calls the list's destructor function for every element.
    5.41 + * If CxList.autofree_content is \c true, the elements are automatically free'd
    5.42 + * unless the content destructor function did not already do that.
    5.43 + * Similarly, if CxList.autofree is \c true, the list structure is free'd, unless
    5.44 + * the list destructor function did not already do that.
    5.45 + *
    5.46 + * This function itself is a destructor function for the CxList.
    5.47 + *
    5.48 + * @param list the list which contents shall be destroyed
    5.49 + * @return \p list if the list structure has been free'd during the process
    5.50 + */
    5.51 +__attribute__((__nonnull__))
    5.52 +CxList *cxListDestroy(CxList *list);
    5.53 +
    5.54  #ifdef __cplusplus
    5.55  } /* extern "C" */
    5.56  #endif

     6.1 --- a/src/linked_list.c	Tue Feb 15 19:07:14 2022 +0100
     6.2 +++ b/src/linked_list.c	Tue Feb 15 19:41:48 2022 +0100
     6.3 @@ -757,24 +757,35 @@
     6.4          cx_pll_iterator,
     6.5  };
     6.6  
     6.7 +static CxList *cx_ll_default_destructor(CxList *list) {
     6.8 +    cx_linked_list *ll = (cx_linked_list *) list;
     6.9 +
    6.10 +    cx_linked_list_node *node = ll->begin;
    6.11 +    while (node) {
    6.12 +        void *next = node->next;
    6.13 +        cxFree(list->allocator, node);
    6.14 +        node = next;
    6.15 +    }
    6.16 +
    6.17 +    cxFree(list->allocator, list);
    6.18 +    return NULL;
    6.19 +}
    6.20 +
    6.21  CxList *cxLinkedListCreate(
    6.22          CxAllocator *allocator,
    6.23          CxListComparator comparator,
    6.24          size_t item_size
    6.25  ) {
    6.26 -    cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
    6.27 +    cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
    6.28      if (list == NULL)
    6.29          return NULL;
    6.30  
    6.31      list->base.cl = &cx_linked_list_class;
    6.32      list->base.allocator = allocator;
    6.33 +    list->base.list_destructor = (cx_destructor_func) cx_ll_default_destructor;
    6.34      list->base.cmpfunc = comparator;
    6.35      list->base.itemsize = item_size;
    6.36      list->base.capacity = SIZE_MAX;
    6.37 -    list->base.size = 0;
    6.38 -
    6.39 -    list->begin = NULL;
    6.40 -    list->end = NULL;
    6.41  
    6.42      return (CxList *) list;
    6.43  }
    6.44 @@ -783,19 +794,16 @@
    6.45          CxAllocator *allocator,
    6.46          CxListComparator comparator
    6.47  ) {
    6.48 -    cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
    6.49 +    cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
    6.50      if (list == NULL)
    6.51          return NULL;
    6.52  
    6.53      list->base.cl = &cx_pointer_linked_list_class;
    6.54      list->base.allocator = allocator;
    6.55 +    list->base.list_destructor = (cx_destructor_func) cx_ll_default_destructor;
    6.56      list->base.cmpfunc = comparator;
    6.57      list->base.itemsize = sizeof(void *);
    6.58      list->base.capacity = SIZE_MAX;
    6.59 -    list->base.size = 0;
    6.60 -
    6.61 -    list->begin = NULL;
    6.62 -    list->end = NULL;
    6.63  
    6.64      return (CxList *) list;
    6.65  }
    6.66 @@ -811,22 +819,8 @@
    6.67      if (list == NULL) return NULL;
    6.68      for (size_t i = 0; i < num_items; i++) {
    6.69          if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) {
    6.70 -            cxLinkedListDestroy(list);
    6.71 -            return NULL;
    6.72 +            return cx_ll_default_destructor(list);
    6.73          }
    6.74      }
    6.75      return list;
    6.76  }
    6.77 -
    6.78 -void cxLinkedListDestroy(CxList *list) {
    6.79 -    cx_linked_list *ll = (cx_linked_list *) list;
    6.80 -
    6.81 -    cx_linked_list_node *node = ll->begin;
    6.82 -    while (node) {
    6.83 -        void *next = node->next;
    6.84 -        cxFree(list->allocator, node);
    6.85 -        node = next;
    6.86 -    }
    6.87 -
    6.88 -    cxFree(list->allocator, list);
    6.89 -}

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/src/list.c	Tue Feb 15 19:41:48 2022 +0100
     7.3 @@ -0,0 +1,59 @@
     7.4 +/*
     7.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     7.6 + *
     7.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     7.8 + *
     7.9 + * Redistribution and use in source and binary forms, with or without
    7.10 + * modification, are permitted provided that the following conditions are met:
    7.11 + *
    7.12 + *   1. Redistributions of source code must retain the above copyright
    7.13 + *      notice, this list of conditions and the following disclaimer.
    7.14 + *
    7.15 + *   2. Redistributions in binary form must reproduce the above copyright
    7.16 + *      notice, this list of conditions and the following disclaimer in the
    7.17 + *      documentation and/or other materials provided with the distribution.
    7.18 + *
    7.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    7.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    7.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    7.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    7.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    7.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    7.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    7.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    7.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    7.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    7.29 + * POSSIBILITY OF SUCH DAMAGE.
    7.30 + */
    7.31 +
    7.32 +#include "cx/list.h"
    7.33 +
    7.34 +CxList *cxListDestroy(CxList *list) {
    7.35 +    if (list->content_destructor == NULL) {
    7.36 +        if (list->autofree_contents) {
    7.37 +            CxIterator iter = cxListBegin(list);
    7.38 +            cx_foreach(void*, elem, iter) {
    7.39 +                cxFree(list->allocator, elem);
    7.40 +            }
    7.41 +        }
    7.42 +    } else {
    7.43 +        // avoid checking this condition every loop iteration
    7.44 +        if (list->autofree_contents) {
    7.45 +            CxIterator iter = cxListBegin(list);
    7.46 +            cx_foreach(void*, elem, iter) {
    7.47 +                cxFree(list->allocator, list->content_destructor(elem));
    7.48 +            }
    7.49 +        } else {
    7.50 +            CxIterator iter = cxListBegin(list);
    7.51 +            cx_foreach(void*, elem, iter) {
    7.52 +                elem = list->content_destructor(elem);
    7.53 +            }
    7.54 +        }
    7.55 +    }
    7.56 +    if (list->autofree) {
    7.57 +        cxFree(list->allocator, list->list_destructor(list));
    7.58 +        return NULL;
    7.59 +    } else {
    7.60 +        return list->list_destructor(list);
    7.61 +    }
    7.62 +}

     8.1 --- a/test/test_list.c	Tue Feb 15 19:07:14 2022 +0100
     8.2 +++ b/test/test_list.c	Tue Feb 15 19:41:48 2022 +0100
     8.3 @@ -568,7 +568,7 @@
     8.4      CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
     8.5      CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
     8.6  
     8.7 -    cxLinkedListDestroy(list);
     8.8 +    cxListDestroy(list);
     8.9      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.10  }
    8.11  
    8.12 @@ -583,7 +583,7 @@
    8.13      CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
    8.14      CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
    8.15  
    8.16 -    cxLinkedListDestroy(list);
    8.17 +    cxListDestroy(list);
    8.18      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.19  }
    8.20  
    8.21 @@ -599,8 +599,8 @@
    8.22  
    8.23      CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
    8.24  
    8.25 -    cxLinkedListDestroy(list);
    8.26 -    cxLinkedListDestroy(expected);
    8.27 +    cxListDestroy(list);
    8.28 +    cxListDestroy(expected);
    8.29      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.30  }
    8.31  
    8.32 @@ -624,8 +624,8 @@
    8.33      CxList *expected = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 3, exp);
    8.34      CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
    8.35  
    8.36 -    cxLinkedListDestroy(list);
    8.37 -    cxLinkedListDestroy(expected);
    8.38 +    cxListDestroy(list);
    8.39 +    cxListDestroy(expected);
    8.40      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.41  }
    8.42  
    8.43 @@ -655,7 +655,7 @@
    8.44      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
    8.45      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
    8.46  
    8.47 -    cxLinkedListDestroy(list);
    8.48 +    cxListDestroy(list);
    8.49      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.50  }
    8.51  
    8.52 @@ -686,8 +686,8 @@
    8.53      CxList *expected = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 4, exp);
    8.54      CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
    8.55  
    8.56 -    cxLinkedListDestroy(list);
    8.57 -    cxLinkedListDestroy(expected);
    8.58 +    cxListDestroy(list);
    8.59 +    cxListDestroy(expected);
    8.60      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.61  }
    8.62  
    8.63 @@ -716,7 +716,7 @@
    8.64      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
    8.65      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
    8.66  
    8.67 -    cxLinkedListDestroy(list);
    8.68 +    cxListDestroy(list);
    8.69      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.70  }
    8.71  
    8.72 @@ -756,7 +756,7 @@
    8.73  
    8.74      CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
    8.75  
    8.76 -    cxLinkedListDestroy(list);
    8.77 +    cxListDestroy(list);
    8.78      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.79  }
    8.80  
    8.81 @@ -800,7 +800,7 @@
    8.82  
    8.83      CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
    8.84  
    8.85 -    cxLinkedListDestroy(list);
    8.86 +    cxListDestroy(list);
    8.87      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.88  }
    8.89  
    8.90 @@ -816,7 +816,7 @@
    8.91      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
    8.92      CU_ASSERT_PTR_NULL(cxListAt(list, 3))
    8.93  
    8.94 -    cxLinkedListDestroy(list);
    8.95 +    cxListDestroy(list);
    8.96      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    8.97  }
    8.98  
    8.99 @@ -835,7 +835,7 @@
   8.100      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
   8.101      CU_ASSERT_PTR_NULL(cxListAt(list, 3))
   8.102  
   8.103 -    cxLinkedListDestroy(list);
   8.104 +    cxListDestroy(list);
   8.105      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   8.106  }
   8.107  
   8.108 @@ -861,7 +861,7 @@
   8.109      criteria = -5;
   8.110      CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
   8.111  
   8.112 -    cxLinkedListDestroy(list);
   8.113 +    cxListDestroy(list);
   8.114      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   8.115  }
   8.116  
   8.117 @@ -891,7 +891,7 @@
   8.118      b = -5;
   8.119      CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
   8.120  
   8.121 -    cxLinkedListDestroy(list);
   8.122 +    cxListDestroy(list);
   8.123      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   8.124  }
   8.125  
   8.126 @@ -921,8 +921,8 @@
   8.127      cxListSort(list);
   8.128      CU_ASSERT_TRUE(0 == cxListCompare(list, exp))
   8.129  
   8.130 -    cxLinkedListDestroy(list);
   8.131 -    cxLinkedListDestroy(exp);
   8.132 +    cxListDestroy(list);
   8.133 +    cxListDestroy(exp);
   8.134      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   8.135  }
   8.136  
   8.137 @@ -958,7 +958,7 @@
   8.138          CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
   8.139      }
   8.140  
   8.141 -    cxLinkedListDestroy(list);
   8.142 +    cxListDestroy(list);
   8.143      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   8.144  }
   8.145  
   8.146 @@ -978,7 +978,7 @@
   8.147      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 4)
   8.148      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 6)
   8.149      CU_ASSERT_EQUAL(*(int *) cxListAt(list, 4), 8)
   8.150 -    cxLinkedListDestroy(list);
   8.151 +    cxListDestroy(list);
   8.152      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   8.153  }
   8.154  
   8.155 @@ -1041,8 +1041,8 @@
   8.156                                               cmp_int, sizeof(int), 10, expdata);
   8.157  
   8.158      CU_ASSERT_EQUAL(0, cxListCompare(list, expected))
   8.159 -    cxLinkedListDestroy(list);
   8.160 -    cxLinkedListDestroy(expected);
   8.161 +    cxListDestroy(list);
   8.162 +    cxListDestroy(expected);
   8.163      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   8.164  }
   8.165  
   8.166 @@ -1083,7 +1083,7 @@
   8.167          CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expdata[i])
   8.168      }
   8.169  
   8.170 -    cxLinkedListDestroy(list);
   8.171 +    cxListDestroy(list);
   8.172      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   8.173  }
   8.174