Mercurial > hg > ucx / changeset

--- a/src/CMakeLists.txt	Tue Oct 05 16:33:11 2021 +0200
+++ b/src/CMakeLists.txt	Wed Oct 06 14:10:19 2021 +0200
@@ -1,6 +1,5 @@
 set(sources
         allocator.c
-        list.c
         linked_list.c
         tree.c
 )

--- a/src/cx/list.h	Tue Oct 05 16:33:11 2021 +0200
+++ b/src/cx/list.h	Wed Oct 06 14:10:19 2021 +0200
@@ -87,6 +87,11 @@
      * Member function for retrieving the last element.
      */
     void *(*last)(cx_list_s *list);
+
+    /**
+     * Member function for sorting the list in place.
+     */
+    void (*sort)(cx_list_s *list);
 } cx_list_class;
 
 /**
@@ -136,7 +141,9 @@
  * @param elem a pointer to the element to add
  * @return zero on success, non-zero on memory allocation failure
  */
-int cxListAdd(CxList list, void *elem);
+static inline int cxListAdd(CxList list, void *elem) {
+    return list->cl->add(list, elem);
+}
 
 /**
  * Inserts an item at the specified index.
@@ -154,7 +161,9 @@
  * @return zero on success, non-zero on memory allocation failure
  * or when the index is out of bounds
  */
-int cxListInsert(CxList list, size_t index, void *elem);
+static inline int cxListInsert(CxList list, size_t index, void *elem) {
+    return list->cl->insert(list, index, elem);
+}
 
 /**
  * Removes the element at the specified index.
@@ -162,7 +171,9 @@
  * @param index the index of the element
  * @return zero on success, non-zero if the index is out of bounds
  */
-int cxListRemove(CxList list, size_t index);
+static inline int cxListRemove(CxList list, size_t index) {
+    return list->cl->remove(list, index);
+}
 
 /**
  * Returns a pointer to the element at the specified index.
@@ -171,7 +182,9 @@
  * @param index the index of the element
  * @return a pointer to the element or \c NULL if the index is out of bounds
  */
-void *cxListAt(CxList list, size_t index);
+static inline void *cxListAt(CxList list, size_t index) {
+    return list->cl->at(list, index);
+}
 
 /**
  * Returns the index of the first element that equals \p elem.
@@ -182,7 +195,9 @@
  * @param elem the element to find
  * @return the index of the element or \c (size+1) if the element is not found
  */
-size_t cxListFind(CxList list, void *elem);
+static inline size_t cxListFind(CxList list, void *elem) {
+    return list->cl->find(list, elem);
+}
 
 /**
  * Returns a pointer to the last element of the list.
@@ -194,7 +209,20 @@
  * @param list the list
  * @return a pointer to the last element or \c NULL if the list is empty
  */
-void *cxListLast(CxList list);
+static inline void *cxListLast(CxList list) {
+    return list->cl->last(list);
+}
+
+/**
+ * Sorts the list in place.
+ *
+ * \remark The underlying sort algorithm is implementation defined.
+ *
+ * @param list the list
+ */
+static inline void cxListSort(CxList list) {
+    list->cl->sort(list);
+}
 
 #ifdef __cplusplus
 } /* extern "C" */

--- a/src/linked_list.c	Tue Oct 05 16:33:11 2021 +0200
+++ b/src/linked_list.c	Wed Oct 06 14:10:19 2021 +0200
@@ -212,6 +212,7 @@
 
 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
+#define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
 
 typedef struct {
     cx_list_s base;
@@ -380,13 +381,28 @@
     return last == NULL ? NULL : *(void **) last->payload;
 }
 
+static void cx_ll_sort(cx_list_s *list) {
+    cx_linked_list *ll = (cx_linked_list *) list;
+    cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
+                        CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                        0, list->cmpfunc);
+}
+
+static void cx_pll_sort(cx_list_s *list) {
+    cx_linked_list *ll = (cx_linked_list *) list;
+    cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
+                        CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                        1, list->cmpfunc);
+}
+
 static cx_list_class cx_linked_list_class = {
         cx_ll_add,
         cx_ll_insert,
         cx_ll_remove,
         cx_ll_at,
         cx_ll_find,
-        cx_ll_last
+        cx_ll_last,
+        cx_ll_sort
 };
 
 static cx_list_class cx_pointer_linked_list_class = {
@@ -395,7 +411,8 @@
         cx_ll_remove,
         cx_pll_at,
         cx_pll_find,
-        cx_pll_last
+        cx_pll_last,
+        cx_pll_sort
 };
 
 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {

--- a/src/list.c	Tue Oct 05 16:33:11 2021 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,53 +0,0 @@
-/*
- * 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/list.h"
-
-int cxListAdd(CxList list, void *elem) {
-    return list->cl->add(list, elem);
-}
-
-int cxListInsert(CxList list, size_t index, void *elem) {
-    return list->cl->insert(list, index, elem);
-}
-
-int cxListRemove(CxList list, size_t index) {
-    return list->cl->remove(list, index);
-}
-
-void *cxListAt(CxList list, size_t index) {
-    return list->cl->at(list, index);
-}
-
-size_t cxListFind(CxList list, void *elem) {
-    return list->cl->find(list, elem);
-}
-
-void *cxListLast(CxList list) {
-    return list->cl->last(list);
-}

--- a/test/test_list.c	Tue Oct 05 16:33:11 2021 +0200
+++ b/test/test_list.c	Wed Oct 06 14:10:19 2021 +0200
@@ -393,6 +393,42 @@
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
 }
 
+void test_hl_linked_list_sort(void) {
+    int expected[] = {
+            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
+            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
+            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
+            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
+            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
+            4785, 4791, 4801, 4859, 4903, 4973
+    };
+    int scrambled[] = {
+            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
+            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
+            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
+            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
+            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
+            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
+    };
+
+    cxTestingAllocatorReset();
+
+    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
+
+    for (int i = 0 ; i < 100 ; i++) {
+        cxListAdd(list, &scrambled[i]);
+    }
+
+    cxListSort(list);
+
+    for (int i = 0 ; i < 100 ; i++) {
+        CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
+    }
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
 void test_hl_ptr_linked_list_create(void) {
     cxTestingAllocatorReset();
 
@@ -558,6 +594,42 @@
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
 }
 
+void test_hl_ptr_linked_list_sort(void) {
+    int expected[] = {
+            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
+            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
+            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
+            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
+            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
+            4785, 4791, 4801, 4859, 4903, 4973
+    };
+    int scrambled[] = {
+            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
+            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
+            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
+            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
+            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
+            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
+    };
+
+    cxTestingAllocatorReset();
+
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
+
+    for (int i = 0 ; i < 100 ; i++) {
+        cxListAdd(list, &scrambled[i]);
+    }
+
+    cxListSort(list);
+
+    for (int i = 0 ; i < 100 ; i++) {
+        CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
+    }
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
 int main() {
     CU_pSuite suite = NULL;
 
@@ -581,6 +653,7 @@
     cu_add_test(suite, test_hl_linked_list_insert);
     cu_add_test(suite, test_hl_linked_list_remove);
     cu_add_test(suite, test_hl_linked_list_find);
+    cu_add_test(suite, test_hl_linked_list_sort);
 
     suite = CU_add_suite("high level pointer linked list", NULL, NULL);
 
@@ -590,6 +663,7 @@
     cu_add_test(suite, test_hl_ptr_linked_list_insert);
     cu_add_test(suite, test_hl_ptr_linked_list_remove);
     cu_add_test(suite, test_hl_ptr_linked_list_find);
+    cu_add_test(suite, test_hl_ptr_linked_list_sort);
 
     CU_basic_set_mode(UCX_CU_BRM);