Mercurial > hg > ucx / changeset

--- a/CHANGELOG	Tue Jan 07 00:12:46 2025 +0100
+++ b/CHANGELOG	Tue Jan 07 18:37:07 2025 +0100
@@ -37,6 +37,7 @@
  * removes CMake
  * removes GTest dependency
  * removes flags to disable SBO in tests
+ * removes CX_LINKED_LIST_SWAP_SBO_SIZE (it's not really an optimization for linked lists)
  * fixes cx_strcmp() and cx_strcasecmp() not being useful for lexicographic ordering
  * fixes cx_hash_key_cxstr() evaluating the argument twice
  * fixes wrong link from UCX 2 documentation to UCX 3 documentation

--- a/docs/src/install.md	Tue Jan 07 00:12:46 2025 +0100
+++ b/docs/src/install.md	Tue Jan 07 18:37:07 2025 +0100
@@ -26,8 +26,6 @@
 --------------------------------- --------------------------------------------------------------------- ----------
 CX_ARRAY_SWAP_SBO_SIZE            The maximum item size in an array list that uses SBO.                 128
 
-CX_LINKED_LIST_SWAP_SBO_SIZE      The maximum item size that uses SBO swap instead of relinking.        128
-
 CX_LINKED_LIST_SORT_SBO_SIZE      The maximum list size that uses SBO during sort.                      1024
 
 CX_PRINTF_SBO_SIZE                The maximum string length printf.h uses stack memory for.             512

--- a/src/cx/linked_list.h	Tue Jan 07 00:12:46 2025 +0100
+++ b/src/cx/linked_list.h	Tue Jan 07 18:37:07 2025 +0100
@@ -44,12 +44,6 @@
 #endif
 
 /**
- * The maximum item size that uses SBO swap instead of relinking.
- *
- */
-extern const unsigned cx_linked_list_swap_sbo_size;
-
-/**
  * Allocates a linked list for storing elements with @p elem_size bytes each.
  *
  * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of

--- a/src/linked_list.c	Tue Jan 07 00:12:46 2025 +0100
+++ b/src/linked_list.c	Tue Jan 07 18:37:07 2025 +0100
@@ -811,11 +811,6 @@
     list->collection.size = 0;
 }
 
-#ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
-#define CX_LINKED_LIST_SWAP_SBO_SIZE 128
-#endif
-const unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
-
 static int cx_ll_swap(
         struct cx_list_s *list,
         size_t i,
@@ -894,41 +889,33 @@
         }
     }
 
-    if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) {
-        cx_linked_list_node *prev = nleft->prev;
-        cx_linked_list_node *next = nright->next;
-        cx_linked_list_node *midstart = nleft->next;
-        cx_linked_list_node *midend = nright->prev;
+    cx_linked_list_node *prev = nleft->prev;
+    cx_linked_list_node *next = nright->next;
+    cx_linked_list_node *midstart = nleft->next;
+    cx_linked_list_node *midend = nright->prev;
 
-        if (prev == NULL) {
-            ll->begin = nright;
-        } else {
-            prev->next = nright;
-        }
-        nright->prev = prev;
-        if (midstart == nright) {
-            // special case: both nodes are adjacent
-            nright->next = nleft;
-            nleft->prev = nright;
-        } else {
-            // likely case: a chain is between the two nodes
-            nright->next = midstart;
-            midstart->prev = nright;
-            midend->next = nleft;
-            nleft->prev = midend;
-        }
-        nleft->next = next;
-        if (next == NULL) {
-            ll->end = nleft;
-        } else {
-            next->prev = nleft;
-        }
+    if (prev == NULL) {
+        ll->begin = nright;
+    } else {
+        prev->next = nright;
+    }
+    nright->prev = prev;
+    if (midstart == nright) {
+        // special case: both nodes are adjacent
+        nright->next = nleft;
+        nleft->prev = nright;
     } else {
-        // swap payloads to avoid relinking
-        char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
-        memcpy(buf, nleft->payload, list->collection.elem_size);
-        memcpy(nleft->payload, nright->payload, list->collection.elem_size);
-        memcpy(nright->payload, buf, list->collection.elem_size);
+        // likely case: a chain is between the two nodes
+        nright->next = midstart;
+        midstart->prev = nright;
+        midend->next = nleft;
+        nleft->prev = midend;
+    }
+    nleft->next = next;
+    if (next == NULL) {
+        ll->end = nleft;
+    } else {
+        next->prev = nleft;
     }
 
     return 0;

--- a/tests/test_list.c	Tue Jan 07 00:12:46 2025 +0100
+++ b/tests/test_list.c	Tue Jan 07 18:37:07 2025 +0100
@@ -1608,12 +1608,6 @@
     }
 })
 
-CX_TEST(test_list_ll_swap_no_sbo) {
-    set_up_combo
-        CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, 2*cx_linked_list_swap_sbo_size);
-        CX_TEST_CALL_SUBROUTINE(test_list_verify_swap, list, false);
-    tear_down_combo
-}
 CX_TEST(test_list_arl_swap_no_sbo) {
     set_up_combo
         CxList *list = cxArrayListCreate(alloc, cx_cmp_int, 2*cx_array_swap_sbo_size, 8);
@@ -2033,7 +2027,6 @@
     cx_test_register(suite, test_list_pll_at);
     cx_test_register(suite, test_list_ll_swap);
     cx_test_register(suite, test_list_pll_swap);
-    cx_test_register(suite, test_list_ll_swap_no_sbo);
     cx_test_register(suite, test_list_ll_find);
     cx_test_register(suite, test_list_pll_find);
     cx_test_register(suite, test_list_ll_sort);