Mercurial > hg > ucx / changeset

     1.1 --- a/src/CMakeLists.txt	Sun Nov 06 16:11:11 2022 +0100
     1.2 +++ b/src/CMakeLists.txt	Sat Nov 12 15:56:58 2022 +0100
     1.3 @@ -3,6 +3,7 @@
     1.4          allocator.c
     1.5          string.c
     1.6          list.c
     1.7 +        array_list.c
     1.8          linked_list.c
     1.9          tree.c
    1.10          buffer.c
    1.11 @@ -19,6 +20,7 @@
    1.12          cx/allocator.h
    1.13          cx/iterator.h
    1.14          cx/list.h
    1.15 +        cx/array_list.h
    1.16          cx/linked_list.h
    1.17          cx/tree.h
    1.18          cx/buffer.h

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/array_list.c	Sat Nov 12 15:56:58 2022 +0100
     2.3 @@ -0,0 +1,38 @@
     2.4 +/*
     2.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     2.6 + *
     2.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     2.8 + *
     2.9 + * Redistribution and use in source and binary forms, with or without
    2.10 + * modification, are permitted provided that the following conditions are met:
    2.11 + *
    2.12 + *   1. Redistributions of source code must retain the above copyright
    2.13 + *      notice, this list of conditions and the following disclaimer.
    2.14 + *
    2.15 + *   2. Redistributions in binary form must reproduce the above copyright
    2.16 + *      notice, this list of conditions and the following disclaimer in the
    2.17 + *      documentation and/or other materials provided with the distribution.
    2.18 + *
    2.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    2.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    2.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    2.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    2.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    2.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    2.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    2.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    2.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    2.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    2.29 + * POSSIBILITY OF SUCH DAMAGE.
    2.30 + */
    2.31 +
    2.32 +#include "cx/array_list.h"
    2.33 +
    2.34 +CxList *cxArrayListCreate(
    2.35 +        CxAllocator const *allocator,
    2.36 +        CxListComparator comparator,
    2.37 +        size_t item_size,
    2.38 +        size_t initial_capacity
    2.39 +) {
    2.40 +    return NULL;
    2.41 +}

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/cx/array_list.h	Sat Nov 12 15:56:58 2022 +0100
     3.3 @@ -0,0 +1,69 @@
     3.4 +/*
     3.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     3.6 + *
     3.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     3.8 + *
     3.9 + * Redistribution and use in source and binary forms, with or without
    3.10 + * modification, are permitted provided that the following conditions are met:
    3.11 + *
    3.12 + *   1. Redistributions of source code must retain the above copyright
    3.13 + *      notice, this list of conditions and the following disclaimer.
    3.14 + *
    3.15 + *   2. Redistributions in binary form must reproduce the above copyright
    3.16 + *      notice, this list of conditions and the following disclaimer in the
    3.17 + *      documentation and/or other materials provided with the distribution.
    3.18 + *
    3.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    3.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    3.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    3.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    3.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    3.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    3.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    3.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    3.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    3.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    3.29 + * POSSIBILITY OF SUCH DAMAGE.
    3.30 + */
    3.31 +/**
    3.32 + * \file array_list.h
    3.33 + * \brief Array list implementation.
    3.34 + * \details Also provides several low-level functions for custom array list implementations.
    3.35 + * \author Mike Becker
    3.36 + * \author Olaf Wintermann
    3.37 + * \version 3.0
    3.38 + * \copyright 2-Clause BSD License
    3.39 + */
    3.40 +
    3.41 +
    3.42 +#ifndef UCX_ARRAY_LIST_H
    3.43 +#define UCX_ARRAY_LIST_H
    3.44 +
    3.45 +#include "cx/list.h"
    3.46 +
    3.47 +#ifdef __cplusplus
    3.48 +extern "C" {
    3.49 +#endif
    3.50 +
    3.51 +/**
    3.52 + * Allocates an array list for storing elements with \p item_size bytes each.
    3.53 + *
    3.54 + * @param allocator the allocator for allocating the list memory
    3.55 + * @param comparator the comparator for the elements
    3.56 + * @param item_size the size of each element in bytes
    3.57 + * @param initial_capacity the initial number of elements the array can store
    3.58 + * @return the created list
    3.59 + */
    3.60 +CxList *cxArrayListCreate(
    3.61 +        CxAllocator const *allocator,
    3.62 +        CxListComparator comparator,
    3.63 +        size_t item_size,
    3.64 +        size_t initial_capacity
    3.65 +) __attribute__((__nonnull__));
    3.66 +
    3.67 +
    3.68 +#ifdef __cplusplus
    3.69 +} /* extern "C" */
    3.70 +#endif
    3.71 +
    3.72 +#endif /* UCX_ARRAY_LIST_H */

     4.1 --- a/test/test_list.cpp	Sun Nov 06 16:11:11 2022 +0100
     4.2 +++ b/test/test_list.cpp	Sat Nov 12 15:56:58 2022 +0100
     4.3 @@ -27,6 +27,7 @@
     4.4   */
     4.5  
     4.6  #include "cx/linked_list.h"
     4.7 +#include "cx/array_list.h"
     4.8  #include "cx/utils.h"
     4.9  #include "cx/compare.h"
    4.10  #include "util_allocator.h"
    4.11 @@ -563,11 +564,12 @@
    4.12      int_test_data<testdata_len> testdata;
    4.13  
    4.14      auto autofree(CxList *list) const -> CxList * {
    4.15 -        lists.insert(list);
    4.16 +        if (list != nullptr) lists.insert(list);
    4.17          return list;
    4.18      }
    4.19  
    4.20      auto linkedListFromTestData() const -> CxList * {
    4.21 +        // TODO: replace with cxListAddArray
    4.22          return autofree(
    4.23                  cxLinkedListFromArray(
    4.24                          &testingAllocator,
    4.25 @@ -585,17 +587,23 @@
    4.26          return list;
    4.27      }
    4.28  
    4.29 +    auto arrayListFromTestData() const -> CxList * {
    4.30 +        auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), testdata_len));
    4.31 +        // TODO: replace with cxListAddArray
    4.32 +        cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);
    4.33 +        return list;
    4.34 +    }
    4.35 +
    4.36      void verifyCreate(CxList *list) const {
    4.37          EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE);
    4.38          EXPECT_EQ(list->size, 0);
    4.39 -        EXPECT_EQ(list->capacity, (size_t) -1);
    4.40          EXPECT_EQ(list->allocator, &testingAllocator);
    4.41          EXPECT_EQ(list->cmpfunc, cx_cmp_int);
    4.42      }
    4.43  
    4.44      void verifyAdd(
    4.45              CxList *list,
    4.46 -            bool write_through
    4.47 +            bool as_pointer
    4.48      ) {
    4.49          auto len = testdata_len;
    4.50          cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0);
    4.51 @@ -603,7 +611,7 @@
    4.52          EXPECT_GE(list->capacity, list->size);
    4.53          cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
    4.54          cx_for_n (i, len) ++testdata.data[i];
    4.55 -        if (write_through) {
    4.56 +        if (as_pointer) {
    4.57              cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
    4.58          } else {
    4.59              cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1);
    4.60 @@ -769,15 +777,22 @@
    4.61  class PointerLinkedList : public HighLevelTest {
    4.62  };
    4.63  
    4.64 +class ArrayList : public HighLevelTest {
    4.65 +};
    4.66 +
    4.67  TEST_F(LinkedList, cxLinkedListCreate) {
    4.68      CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
    4.69 +    ASSERT_NE(list, nullptr);
    4.70      EXPECT_EQ(list->itemsize, sizeof(int));
    4.71 +    EXPECT_EQ(list->capacity, (size_t) -1);
    4.72      verifyCreate(list);
    4.73  }
    4.74  
    4.75  TEST_F(PointerLinkedList, cxPointerLinkedListCreate) {
    4.76      CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int));
    4.77 +    ASSERT_NE(list, nullptr);
    4.78      EXPECT_EQ(list->itemsize, sizeof(void *));
    4.79 +    EXPECT_EQ(list->capacity, (size_t) -1);
    4.80      verifyCreate(list);
    4.81  }
    4.82  
    4.83 @@ -786,9 +801,21 @@
    4.84      cx_for_n (i, testdata_len) cxListAdd(expected, &testdata.data[i]);
    4.85      CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cx_cmp_int, sizeof(int),
    4.86                                                    testdata_len, testdata.data.data()));
    4.87 +    ASSERT_NE(list, nullptr);
    4.88 +    EXPECT_EQ(list->itemsize, sizeof(int));
    4.89 +    EXPECT_EQ(list->capacity, (size_t) -1);
    4.90 +    EXPECT_EQ(list->size, testdata_len);
    4.91      EXPECT_EQ(cxListCompare(list, expected), 0);
    4.92  }
    4.93  
    4.94 +TEST_F(ArrayList, cxArrayListCreate) {
    4.95 +    CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));
    4.96 +    ASSERT_NE(list, nullptr);
    4.97 +    EXPECT_EQ(list->itemsize, sizeof(int));
    4.98 +    EXPECT_EQ(list->capacity, 8);
    4.99 +    verifyCreate(list);
   4.100 +}
   4.101 +
   4.102  TEST_F(LinkedList, cxListAdd) {
   4.103      CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
   4.104      verifyAdd(list, false);
   4.105 @@ -799,6 +826,12 @@
   4.106      verifyAdd(list, true);
   4.107  }
   4.108  
   4.109 +TEST_F(ArrayList, cxListAdd) {
   4.110 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.111 +    CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));
   4.112 +    verifyAdd(list, false);
   4.113 +}
   4.114 +
   4.115  TEST_F(LinkedList, cxListInsert) {
   4.116      verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
   4.117  }
   4.118 @@ -807,6 +840,11 @@
   4.119      verifyInsert(autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int)));
   4.120  }
   4.121  
   4.122 +TEST_F(ArrayList, cxListInsert) {
   4.123 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.124 +    verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2)));
   4.125 +}
   4.126 +
   4.127  TEST_F(LinkedList, cxListRemove) {
   4.128      verifyRemove(linkedListFromTestData());
   4.129  }
   4.130 @@ -815,6 +853,11 @@
   4.131      verifyRemove(pointerLinkedListFromTestData());
   4.132  }
   4.133  
   4.134 +TEST_F(ArrayList, cxListRemove) {
   4.135 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.136 +    verifyRemove(arrayListFromTestData());
   4.137 +}
   4.138 +
   4.139  TEST_F(LinkedList, cxListAt) {
   4.140      verifyAt(linkedListFromTestData());
   4.141  }
   4.142 @@ -823,6 +866,11 @@
   4.143      verifyAt(pointerLinkedListFromTestData());
   4.144  }
   4.145  
   4.146 +TEST_F(ArrayList, cxListAt) {
   4.147 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.148 +    verifyAt(arrayListFromTestData());
   4.149 +}
   4.150 +
   4.151  TEST_F(LinkedList, cxListFind) {
   4.152      verifyFind(linkedListFromTestData());
   4.153  }
   4.154 @@ -831,6 +879,11 @@
   4.155      verifyFind(pointerLinkedListFromTestData());
   4.156  }
   4.157  
   4.158 +TEST_F(ArrayList, cxListFind) {
   4.159 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.160 +    verifyFind(arrayListFromTestData());
   4.161 +}
   4.162 +
   4.163  TEST_F(LinkedList, cxListSort) {
   4.164      verifySort(linkedListFromTestData());
   4.165  }
   4.166 @@ -839,6 +892,11 @@
   4.167      verifySort(pointerLinkedListFromTestData());
   4.168  }
   4.169  
   4.170 +TEST_F(ArrayList, cxListSort) {
   4.171 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.172 +    verifySort(arrayListFromTestData());
   4.173 +}
   4.174 +
   4.175  TEST_F(LinkedList, Iterator) {
   4.176      verifyIterator(linkedListFromTestData());
   4.177  }
   4.178 @@ -847,6 +905,11 @@
   4.179      verifyIterator(pointerLinkedListFromTestData());
   4.180  }
   4.181  
   4.182 +TEST_F(ArrayList, Iterator) {
   4.183 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.184 +    verifyIterator(arrayListFromTestData());
   4.185 +}
   4.186 +
   4.187  TEST_F(LinkedList, InsertViaIterator) {
   4.188      int fivenums[] = {0, 1, 2, 3, 4, 5};
   4.189      CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cx_cmp_int, sizeof(int), 5, fivenums));
   4.190 @@ -860,6 +923,15 @@
   4.191      verifyInsertViaIterator(list);
   4.192  }
   4.193  
   4.194 +TEST_F(ArrayList, InsertViaIterator) {
   4.195 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.196 +    int fivenums[] = {0, 1, 2, 3, 4, 5};
   4.197 +    CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4));
   4.198 +    // TODO: replace with cxListAddArray
   4.199 +    cx_for_n (i, 5) cxListAdd(list, &fivenums[i]);
   4.200 +    verifyInsertViaIterator(list);
   4.201 +}
   4.202 +
   4.203  TEST_F(LinkedList, cxListReverse) {
   4.204      verifyReverse(linkedListFromTestData());
   4.205  }
   4.206 @@ -868,6 +940,11 @@
   4.207      verifyReverse(pointerLinkedListFromTestData());
   4.208  }
   4.209  
   4.210 +TEST_F(ArrayList, cxListReverse) {
   4.211 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.212 +    verifyReverse(arrayListFromTestData());
   4.213 +}
   4.214 +
   4.215  TEST_F(LinkedList, cxListCompare) {
   4.216      auto left = linkedListFromTestData();
   4.217      auto right = linkedListFromTestData();
   4.218 @@ -880,6 +957,13 @@
   4.219      verifyCompare(left, right);
   4.220  }
   4.221  
   4.222 +TEST_F(LinkedList, cxListCompareWithArrayList) {
   4.223 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.224 +    auto left = linkedListFromTestData();
   4.225 +    auto right = arrayListFromTestData();
   4.226 +    verifyCompare(left, right);
   4.227 +}
   4.228 +
   4.229  TEST_F(PointerLinkedList, cxListCompare) {
   4.230      auto left = pointerLinkedListFromTestData();
   4.231      auto right = pointerLinkedListFromTestData();
   4.232 @@ -892,6 +976,34 @@
   4.233      verifyCompare(left, right);
   4.234  }
   4.235  
   4.236 +TEST_F(PointerLinkedList, cxListCompareWithArrayList) {
   4.237 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.238 +    auto left = pointerLinkedListFromTestData();
   4.239 +    auto right = arrayListFromTestData();
   4.240 +    verifyCompare(left, right);
   4.241 +}
   4.242 +
   4.243 +TEST_F(ArrayList, cxListCompare) {
   4.244 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.245 +    auto left = arrayListFromTestData();
   4.246 +    auto right = arrayListFromTestData();
   4.247 +    verifyCompare(left, right);
   4.248 +}
   4.249 +
   4.250 +TEST_F(ArrayList, cxListCompareWithPtrList) {
   4.251 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.252 +    auto left = arrayListFromTestData();
   4.253 +    auto right = pointerLinkedListFromTestData();
   4.254 +    verifyCompare(left, right);
   4.255 +}
   4.256 +
   4.257 +TEST_F(ArrayList, cxListCompareWithNormalList) {
   4.258 +    ASSERT_EQ(1,0); // TODO: remove when implemented
   4.259 +    auto left = arrayListFromTestData();
   4.260 +    auto right = linkedListFromTestData();
   4.261 +    verifyCompare(left, right);
   4.262 +}
   4.263 +
   4.264  TEST_F(PointerLinkedList, NoDestructor) {
   4.265      void *item = cxMalloc(&testingAllocator, sizeof(int));
   4.266      auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_int);