Mercurial > hg > ucx / changeset

--- a/src/CMakeLists.txt	Sun Nov 06 16:11:11 2022 +0100
+++ b/src/CMakeLists.txt	Sat Nov 12 15:56:58 2022 +0100
@@ -3,6 +3,7 @@
         allocator.c
         string.c
         list.c
+        array_list.c
         linked_list.c
         tree.c
         buffer.c
@@ -19,6 +20,7 @@
         cx/allocator.h
         cx/iterator.h
         cx/list.h
+        cx/array_list.h
         cx/linked_list.h
         cx/tree.h
         cx/buffer.h

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/array_list.c	Sat Nov 12 15:56:58 2022 +0100
@@ -0,0 +1,38 @@
+/*
+ * 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"
+
+CxList *cxArrayListCreate(
+        CxAllocator const *allocator,
+        CxListComparator comparator,
+        size_t item_size,
+        size_t initial_capacity
+) {
+    return NULL;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/cx/array_list.h	Sat Nov 12 15:56:58 2022 +0100
@@ -0,0 +1,69 @@
+/*
+ * 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 "cx/list.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * 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 */

--- a/test/test_list.cpp	Sun Nov 06 16:11:11 2022 +0100
+++ b/test/test_list.cpp	Sat Nov 12 15:56:58 2022 +0100
@@ -27,6 +27,7 @@
  */
 
 #include "cx/linked_list.h"
+#include "cx/array_list.h"
 #include "cx/utils.h"
 #include "cx/compare.h"
 #include "util_allocator.h"
@@ -563,11 +564,12 @@
     int_test_data<testdata_len> testdata;
 
     auto autofree(CxList *list) const -> CxList * {
-        lists.insert(list);
+        if (list != nullptr) lists.insert(list);
         return list;
     }
 
     auto linkedListFromTestData() const -> CxList * {
+        // TODO: replace with cxListAddArray
         return autofree(
                 cxLinkedListFromArray(
                         &testingAllocator,
@@ -585,17 +587,23 @@
         return list;
     }
 
+    auto arrayListFromTestData() const -> CxList * {
+        auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), testdata_len));
+        // TODO: replace with cxListAddArray
+        cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);
+        return list;
+    }
+
     void verifyCreate(CxList *list) const {
         EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE);
         EXPECT_EQ(list->size, 0);
-        EXPECT_EQ(list->capacity, (size_t) -1);
         EXPECT_EQ(list->allocator, &testingAllocator);
         EXPECT_EQ(list->cmpfunc, cx_cmp_int);
     }
 
     void verifyAdd(
             CxList *list,
-            bool write_through
+            bool as_pointer
     ) {
         auto len = testdata_len;
         cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0);
@@ -603,7 +611,7 @@
         EXPECT_GE(list->capacity, list->size);
         cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
         cx_for_n (i, len) ++testdata.data[i];
-        if (write_through) {
+        if (as_pointer) {
             cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
         } else {
             cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1);
@@ -769,15 +777,22 @@
 class PointerLinkedList : public HighLevelTest {
 };
 
+class ArrayList : public HighLevelTest {
+};
+
 TEST_F(LinkedList, cxLinkedListCreate) {
     CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
+    ASSERT_NE(list, nullptr);
     EXPECT_EQ(list->itemsize, sizeof(int));
+    EXPECT_EQ(list->capacity, (size_t) -1);
     verifyCreate(list);
 }
 
 TEST_F(PointerLinkedList, cxPointerLinkedListCreate) {
     CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int));
+    ASSERT_NE(list, nullptr);
     EXPECT_EQ(list->itemsize, sizeof(void *));
+    EXPECT_EQ(list->capacity, (size_t) -1);
     verifyCreate(list);
 }
 
@@ -786,9 +801,21 @@
     cx_for_n (i, testdata_len) cxListAdd(expected, &testdata.data[i]);
     CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cx_cmp_int, sizeof(int),
                                                   testdata_len, testdata.data.data()));
+    ASSERT_NE(list, nullptr);
+    EXPECT_EQ(list->itemsize, sizeof(int));
+    EXPECT_EQ(list->capacity, (size_t) -1);
+    EXPECT_EQ(list->size, testdata_len);
     EXPECT_EQ(cxListCompare(list, expected), 0);
 }
 
+TEST_F(ArrayList, cxArrayListCreate) {
+    CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));
+    ASSERT_NE(list, nullptr);
+    EXPECT_EQ(list->itemsize, sizeof(int));
+    EXPECT_EQ(list->capacity, 8);
+    verifyCreate(list);
+}
+
 TEST_F(LinkedList, cxListAdd) {
     CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
     verifyAdd(list, false);
@@ -799,6 +826,12 @@
     verifyAdd(list, true);
 }
 
+TEST_F(ArrayList, cxListAdd) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));
+    verifyAdd(list, false);
+}
+
 TEST_F(LinkedList, cxListInsert) {
     verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
 }
@@ -807,6 +840,11 @@
     verifyInsert(autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int)));
 }
 
+TEST_F(ArrayList, cxListInsert) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2)));
+}
+
 TEST_F(LinkedList, cxListRemove) {
     verifyRemove(linkedListFromTestData());
 }
@@ -815,6 +853,11 @@
     verifyRemove(pointerLinkedListFromTestData());
 }
 
+TEST_F(ArrayList, cxListRemove) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    verifyRemove(arrayListFromTestData());
+}
+
 TEST_F(LinkedList, cxListAt) {
     verifyAt(linkedListFromTestData());
 }
@@ -823,6 +866,11 @@
     verifyAt(pointerLinkedListFromTestData());
 }
 
+TEST_F(ArrayList, cxListAt) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    verifyAt(arrayListFromTestData());
+}
+
 TEST_F(LinkedList, cxListFind) {
     verifyFind(linkedListFromTestData());
 }
@@ -831,6 +879,11 @@
     verifyFind(pointerLinkedListFromTestData());
 }
 
+TEST_F(ArrayList, cxListFind) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    verifyFind(arrayListFromTestData());
+}
+
 TEST_F(LinkedList, cxListSort) {
     verifySort(linkedListFromTestData());
 }
@@ -839,6 +892,11 @@
     verifySort(pointerLinkedListFromTestData());
 }
 
+TEST_F(ArrayList, cxListSort) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    verifySort(arrayListFromTestData());
+}
+
 TEST_F(LinkedList, Iterator) {
     verifyIterator(linkedListFromTestData());
 }
@@ -847,6 +905,11 @@
     verifyIterator(pointerLinkedListFromTestData());
 }
 
+TEST_F(ArrayList, Iterator) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    verifyIterator(arrayListFromTestData());
+}
+
 TEST_F(LinkedList, InsertViaIterator) {
     int fivenums[] = {0, 1, 2, 3, 4, 5};
     CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cx_cmp_int, sizeof(int), 5, fivenums));
@@ -860,6 +923,15 @@
     verifyInsertViaIterator(list);
 }
 
+TEST_F(ArrayList, InsertViaIterator) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    int fivenums[] = {0, 1, 2, 3, 4, 5};
+    CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4));
+    // TODO: replace with cxListAddArray
+    cx_for_n (i, 5) cxListAdd(list, &fivenums[i]);
+    verifyInsertViaIterator(list);
+}
+
 TEST_F(LinkedList, cxListReverse) {
     verifyReverse(linkedListFromTestData());
 }
@@ -868,6 +940,11 @@
     verifyReverse(pointerLinkedListFromTestData());
 }
 
+TEST_F(ArrayList, cxListReverse) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    verifyReverse(arrayListFromTestData());
+}
+
 TEST_F(LinkedList, cxListCompare) {
     auto left = linkedListFromTestData();
     auto right = linkedListFromTestData();
@@ -880,6 +957,13 @@
     verifyCompare(left, right);
 }
 
+TEST_F(LinkedList, cxListCompareWithArrayList) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    auto left = linkedListFromTestData();
+    auto right = arrayListFromTestData();
+    verifyCompare(left, right);
+}
+
 TEST_F(PointerLinkedList, cxListCompare) {
     auto left = pointerLinkedListFromTestData();
     auto right = pointerLinkedListFromTestData();
@@ -892,6 +976,34 @@
     verifyCompare(left, right);
 }
 
+TEST_F(PointerLinkedList, cxListCompareWithArrayList) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    auto left = pointerLinkedListFromTestData();
+    auto right = arrayListFromTestData();
+    verifyCompare(left, right);
+}
+
+TEST_F(ArrayList, cxListCompare) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    auto left = arrayListFromTestData();
+    auto right = arrayListFromTestData();
+    verifyCompare(left, right);
+}
+
+TEST_F(ArrayList, cxListCompareWithPtrList) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    auto left = arrayListFromTestData();
+    auto right = pointerLinkedListFromTestData();
+    verifyCompare(left, right);
+}
+
+TEST_F(ArrayList, cxListCompareWithNormalList) {
+    ASSERT_EQ(1,0); // TODO: remove when implemented
+    auto left = arrayListFromTestData();
+    auto right = linkedListFromTestData();
+    verifyCompare(left, right);
+}
+
 TEST_F(PointerLinkedList, NoDestructor) {
     void *item = cxMalloc(&testingAllocator, sizeof(int));
     auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_int);