Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/linked_list.h	Tue Oct 05 12:25:23 2021 +0200
     1.2 +++ b/src/cx/linked_list.h	Tue Oct 05 13:03:45 2021 +0200
     1.3 @@ -45,8 +45,36 @@
     1.4  extern "C" {
     1.5  #endif
     1.6  
     1.7 +/**
     1.8 + * Allocates a linked list for storing elements with \p item_size bytes each.
     1.9 + *
    1.10 + * Elements added to the list are copied.
    1.11 + *
    1.12 + * @param allocator the allocator for allocating the list nodes
    1.13 + * @param comparator the comparator for the elements
    1.14 + * @param item_size the size of each element in bytes
    1.15 + * @return the created list
    1.16 + */
    1.17  CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size);
    1.18  
    1.19 +/**
    1.20 + * Allocates a linked list for storing pointers.
    1.21 + *
    1.22 + * If you want to store the elements directly in this list, use cxLinkedListCreate().
    1.23 + *
    1.24 + * @param allocator the allocator for allocating the list nodes
    1.25 + * @param comparator the comparator for the elements
    1.26 + * @return the created list
    1.27 + */
    1.28 +CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator);
    1.29 +
    1.30 +/**
    1.31 + * Deallocates the memory of the entire list.
    1.32 + *
    1.33 + * \attention If this is a pointer list, the memory the pointers are referring to is \em not freed.
    1.34 + *
    1.35 + * @param list the list
    1.36 + */
    1.37  void cxLinkedListDestroy(CxList list);
    1.38  
    1.39  size_t cxLinkedListRecalculateSize(CxList list);

     2.1 --- a/src/linked_list.c	Tue Oct 05 12:25:23 2021 +0200
     2.2 +++ b/src/linked_list.c	Tue Oct 05 13:03:45 2021 +0200
     2.3 @@ -172,6 +172,14 @@
     2.4      return cx_ll_insert(list, list->size, elem);
     2.5  }
     2.6  
     2.7 +static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
     2.8 +    return cx_ll_insert(list, index, &elem);
     2.9 +}
    2.10 +
    2.11 +static int cx_pll_add(cx_list_s *list, void *elem) {
    2.12 +    return cx_ll_insert(list, list->size, &elem);
    2.13 +}
    2.14 +
    2.15  static int cx_ll_remove(cx_list_s *list, size_t index) {
    2.16      cx_linked_list *ll = (cx_linked_list *) list;
    2.17      cx_linked_list_node *node = cx_ll_node_at(ll, index);
    2.18 @@ -205,7 +213,13 @@
    2.19  static void *cx_ll_at(cx_list_s *list, size_t index) {
    2.20      cx_linked_list *ll = (cx_linked_list *) list;
    2.21      cx_linked_list_node *node = cx_ll_node_at(ll, index);
    2.22 -    return node == NULL ? NULL : &node->payload;
    2.23 +    return node == NULL ? NULL : node->payload;
    2.24 +}
    2.25 +
    2.26 +static void *cx_pll_at(cx_list_s *list, size_t index) {
    2.27 +    cx_linked_list *ll = (cx_linked_list *) list;
    2.28 +    cx_linked_list_node *node = cx_ll_node_at(ll, index);
    2.29 +    return node == NULL ? NULL : *(void**)node->payload;
    2.30  }
    2.31  
    2.32  static size_t cx_ll_find(cx_list_s *list, void *elem) {
    2.33 @@ -224,10 +238,32 @@
    2.34      return index;
    2.35  }
    2.36  
    2.37 +static size_t cx_pll_find(cx_list_s *list, void *elem) {
    2.38 +    CxListComparator cmp = list->cmpfunc;
    2.39 +    cx_linked_list *ll = (cx_linked_list *) list;
    2.40 +
    2.41 +    size_t index;
    2.42 +    cx_linked_list_node *node = ll->begin;
    2.43 +    for (index = 0; index < list->size; index++) {
    2.44 +        void *current = *(void**)node->payload;
    2.45 +        if (cmp(current, elem) == 0) {
    2.46 +            return index;
    2.47 +        }
    2.48 +        node = node->next;
    2.49 +    }
    2.50 +    return index;
    2.51 +}
    2.52 +
    2.53  static void *cx_ll_last(cx_list_s *list) {
    2.54      cx_linked_list *ll = (cx_linked_list *) list;
    2.55      cx_linked_list_node *last = ll->end;
    2.56 -    return last == NULL ? NULL : &last->payload;
    2.57 +    return last == NULL ? NULL : last->payload;
    2.58 +}
    2.59 +
    2.60 +static void *cx_pll_last(cx_list_s *list) {
    2.61 +    cx_linked_list *ll = (cx_linked_list *) list;
    2.62 +    cx_linked_list_node *last = ll->end;
    2.63 +    return last == NULL ? NULL : *(void**)last->payload;
    2.64  }
    2.65  
    2.66  static cx_list_class cx_linked_list_class = {
    2.67 @@ -239,6 +275,15 @@
    2.68          cx_ll_last
    2.69  };
    2.70  
    2.71 +static cx_list_class cx_pointer_linked_list_class = {
    2.72 +        cx_pll_add,
    2.73 +        cx_pll_insert,
    2.74 +        cx_ll_remove,
    2.75 +        cx_pll_at,
    2.76 +        cx_pll_find,
    2.77 +        cx_pll_last
    2.78 +};
    2.79 +
    2.80  CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
    2.81      cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
    2.82      if (list == NULL)
    2.83 @@ -257,6 +302,24 @@
    2.84      return (CxList) list;
    2.85  }
    2.86  
    2.87 +CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
    2.88 +    cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
    2.89 +    if (list == NULL)
    2.90 +        return NULL;
    2.91 +
    2.92 +    list->base.cl = &cx_pointer_linked_list_class;
    2.93 +    list->base.allocator = allocator;
    2.94 +    list->base.cmpfunc = comparator;
    2.95 +    list->base.itemsize = sizeof(void*);
    2.96 +    list->base.capacity = SIZE_MAX;
    2.97 +    list->base.size = 0;
    2.98 +
    2.99 +    list->begin = NULL;
   2.100 +    list->end = NULL;
   2.101 +
   2.102 +    return (CxList) list;
   2.103 +}
   2.104 +
   2.105  void cxLinkedListDestroy(CxList list) {
   2.106      cx_linked_list *ll = (cx_linked_list *) list;
   2.107  

     3.1 --- a/test/test_list.c	Tue Oct 05 12:25:23 2021 +0200
     3.2 +++ b/test/test_list.c	Tue Oct 05 13:03:45 2021 +0200
     3.3 @@ -158,19 +158,7 @@
     3.4      CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
     3.5      CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
     3.6  
     3.7 -    // assume this structure for a linked list
     3.8 -    struct ll_check {
     3.9 -        cx_list_s base;
    3.10 -        void *begin;
    3.11 -        void *end;
    3.12 -    };
    3.13 -
    3.14 -    struct ll_check *actual = (struct ll_check *) list;
    3.15 -    CU_ASSERT_PTR_NULL(actual->begin)
    3.16 -    CU_ASSERT_PTR_NULL(actual->end)
    3.17 -
    3.18      cxLinkedListDestroy(list);
    3.19 -
    3.20      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    3.21  }
    3.22  
    3.23 @@ -190,9 +178,9 @@
    3.24      CU_ASSERT_EQUAL(list->size, 3)
    3.25      CU_ASSERT_TRUE(list->capacity >= list->size)
    3.26  
    3.27 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5)
    3.28 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47)
    3.29 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13)
    3.30 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
    3.31 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
    3.32 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
    3.33  
    3.34      cxLinkedListDestroy(list);
    3.35      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    3.36 @@ -208,11 +196,11 @@
    3.37  
    3.38      data = 5;
    3.39      CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
    3.40 -    CU_ASSERT_EQUAL(*(int*)cxListLast(list), 5)
    3.41 +    CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
    3.42  
    3.43      data = 47;
    3.44      CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
    3.45 -    CU_ASSERT_EQUAL(*(int*)cxListLast(list), 47)
    3.46 +    CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
    3.47  
    3.48      cxLinkedListDestroy(list);
    3.49      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    3.50 @@ -241,10 +229,10 @@
    3.51      CU_ASSERT_EQUAL(list->size, 4)
    3.52      CU_ASSERT_TRUE(list->capacity >= list->size)
    3.53  
    3.54 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47)
    3.55 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 13)
    3.56 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 5)
    3.57 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 3), 42)
    3.58 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
    3.59 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
    3.60 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
    3.61 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
    3.62  
    3.63      cxLinkedListDestroy(list);
    3.64      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    3.65 @@ -273,20 +261,20 @@
    3.66      CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
    3.67      CU_ASSERT_EQUAL(list->size, 3)
    3.68      CU_ASSERT_TRUE(list->capacity >= list->size)
    3.69 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5)
    3.70 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47)
    3.71 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13)
    3.72 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
    3.73 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
    3.74 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
    3.75  
    3.76      CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
    3.77      CU_ASSERT_EQUAL(list->size, 2)
    3.78      CU_ASSERT_TRUE(list->capacity >= list->size)
    3.79 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47)
    3.80 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 13)
    3.81 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
    3.82 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
    3.83  
    3.84      CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
    3.85      CU_ASSERT_EQUAL(list->size, 1)
    3.86      CU_ASSERT_TRUE(list->capacity >= list->size)
    3.87 -    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47)
    3.88 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
    3.89  
    3.90      CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
    3.91      CU_ASSERT_EQUAL(list->size, 0)
    3.92 @@ -329,6 +317,171 @@
    3.93      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    3.94  }
    3.95  
    3.96 +void test_hl_ptr_linked_list_create(void) {
    3.97 +    cxTestingAllocatorReset();
    3.98 +
    3.99 +    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
   3.100 +
   3.101 +    CU_ASSERT_EQUAL(list->size, 0)
   3.102 +    CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
   3.103 +    CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
   3.104 +    CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
   3.105 +    CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
   3.106 +
   3.107 +    cxLinkedListDestroy(list);
   3.108 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   3.109 +}
   3.110 +
   3.111 +void test_hl_ptr_linked_list_add(void) {
   3.112 +    cxTestingAllocatorReset();
   3.113 +
   3.114 +    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
   3.115 +
   3.116 +    int a = 5, b = 47, c = 13;
   3.117 +
   3.118 +    CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
   3.119 +    CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
   3.120 +    CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
   3.121 +
   3.122 +    CU_ASSERT_EQUAL(list->size, 3)
   3.123 +    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.124 +
   3.125 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
   3.126 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
   3.127 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
   3.128 +
   3.129 +    a = 9;
   3.130 +    b = 10;
   3.131 +    c = 11;
   3.132 +
   3.133 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
   3.134 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
   3.135 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
   3.136 +
   3.137 +    cxLinkedListDestroy(list);
   3.138 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   3.139 +}
   3.140 +
   3.141 +void test_hl_ptr_linked_list_last(void) {
   3.142 +    cxTestingAllocatorReset();
   3.143 +
   3.144 +    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
   3.145 +    CU_ASSERT_PTR_NULL(cxListLast(list))
   3.146 +
   3.147 +    int a = 5, b = 47;
   3.148 +
   3.149 +    CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
   3.150 +    CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
   3.151 +    CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
   3.152 +    CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
   3.153 +
   3.154 +    cxLinkedListDestroy(list);
   3.155 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   3.156 +}
   3.157 +
   3.158 +void test_hl_ptr_linked_list_insert(void) {
   3.159 +    cxTestingAllocatorReset();
   3.160 +
   3.161 +    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
   3.162 +
   3.163 +    int a = 5, b = 47, c = 13, d = 42;
   3.164 +
   3.165 +    CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
   3.166 +    CU_ASSERT_EQUAL(list->size, 0)
   3.167 +    CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
   3.168 +    CU_ASSERT_EQUAL(list->size, 1)
   3.169 +    CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
   3.170 +    CU_ASSERT_EQUAL(list->size, 2)
   3.171 +    CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
   3.172 +    CU_ASSERT_EQUAL(list->size, 3)
   3.173 +    CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
   3.174 +
   3.175 +    CU_ASSERT_EQUAL(list->size, 4)
   3.176 +    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.177 +
   3.178 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
   3.179 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
   3.180 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
   3.181 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
   3.182 +
   3.183 +    cxLinkedListDestroy(list);
   3.184 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   3.185 +}
   3.186 +
   3.187 +void test_hl_ptr_linked_list_remove(void) {
   3.188 +    cxTestingAllocatorReset();
   3.189 +
   3.190 +    int a = 5, b = 47, c = 42, d = 13;
   3.191 +    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
   3.192 +
   3.193 +    cxListAdd(list, &a);
   3.194 +    cxListAdd(list, &b);
   3.195 +    cxListAdd(list, &c);
   3.196 +    cxListAdd(list, &d);
   3.197 +
   3.198 +    CU_ASSERT_EQUAL(list->size, 4)
   3.199 +    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.200 +
   3.201 +    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
   3.202 +
   3.203 +    CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
   3.204 +    CU_ASSERT_EQUAL(list->size, 3)
   3.205 +    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.206 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
   3.207 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
   3.208 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
   3.209 +
   3.210 +    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
   3.211 +    CU_ASSERT_EQUAL(list->size, 2)
   3.212 +    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.213 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
   3.214 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
   3.215 +
   3.216 +    CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
   3.217 +    CU_ASSERT_EQUAL(list->size, 1)
   3.218 +    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.219 +    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
   3.220 +
   3.221 +    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
   3.222 +    CU_ASSERT_EQUAL(list->size, 0)
   3.223 +    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.224 +
   3.225 +    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
   3.226 +
   3.227 +    cxLinkedListDestroy(list);
   3.228 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   3.229 +}
   3.230 +
   3.231 +void test_hl_ptr_linked_list_find(void) {
   3.232 +    cxTestingAllocatorReset();
   3.233 +
   3.234 +    int a = 5, b = 47, c = 13, criteria;
   3.235 +    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
   3.236 +
   3.237 +    cxListAdd(list, &a);
   3.238 +    cxListAdd(list, &b);
   3.239 +    cxListAdd(list, &c);
   3.240 +
   3.241 +    CU_ASSERT_EQUAL(list->size, 3)
   3.242 +    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.243 +
   3.244 +    criteria = 5;
   3.245 +    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
   3.246 +    criteria = 47;
   3.247 +    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
   3.248 +    criteria = 13;
   3.249 +    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
   3.250 +    criteria = 9000;
   3.251 +    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
   3.252 +    criteria = -5;
   3.253 +    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
   3.254 +    b = -5;
   3.255 +    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
   3.256 +
   3.257 +    cxLinkedListDestroy(list);
   3.258 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   3.259 +}
   3.260 +
   3.261  int main() {
   3.262      CU_pSuite suite = NULL;
   3.263  
   3.264 @@ -351,6 +504,15 @@
   3.265      cu_add_test(suite, test_hl_linked_list_remove);
   3.266      cu_add_test(suite, test_hl_linked_list_find);
   3.267  
   3.268 +    suite = CU_add_suite("high level pointer linked list", NULL, NULL);
   3.269 +
   3.270 +    cu_add_test(suite, test_hl_ptr_linked_list_create);
   3.271 +    cu_add_test(suite, test_hl_ptr_linked_list_add);
   3.272 +    cu_add_test(suite, test_hl_ptr_linked_list_last);
   3.273 +    cu_add_test(suite, test_hl_ptr_linked_list_insert);
   3.274 +    cu_add_test(suite, test_hl_ptr_linked_list_remove);
   3.275 +    cu_add_test(suite, test_hl_ptr_linked_list_find);
   3.276 +
   3.277      CU_basic_set_mode(UCX_CU_BRM);
   3.278  
   3.279      int exitcode;