Mercurial > hg > ucx / changeset

--- a/src/array_list.c	Sun Nov 20 16:28:03 2022 +0100
+++ b/src/array_list.c	Sun Nov 20 16:58:51 2022 +0100
@@ -101,6 +101,45 @@
     return CX_ARRAY_COPY_SUCCESS;
 }
 
+#define CX_ARRAY_SWAP_SBO_SIZE 512
+
+void cx_array_swap(
+        void *arr,
+        size_t elem_size,
+        size_t idx1,
+        size_t idx2
+) {
+    /* short circuit */
+    if (idx1 == idx2) return;
+
+    char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
+    void *tmp;
+
+    /* decide if we can use the local buffer */
+    if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
+        tmp = malloc(elem_size);
+        /* we don't want to enforce error handling */
+        if (tmp == NULL) abort();
+    } else {
+        tmp = sbo_mem;
+    }
+
+    /* calculate memory locations */
+    char *left = arr, *right = arr;
+    left += idx1 * elem_size;
+    right += idx2 * elem_size;
+
+    /* three-way swap */
+    memcpy(tmp, left, elem_size);
+    memcpy(left, right, elem_size);
+    memcpy(right, tmp, elem_size);
+
+    /* free dynamic memory, if it was needed */
+    if (tmp != sbo_mem) {
+        free(tmp);
+    }
+}
+
 /* HIGH LEVEL ARRAY LIST FUNCTIONS */
 
 typedef struct {
@@ -290,7 +329,12 @@
 }
 
 static void cx_arl_reverse(struct cx_list_s *list) {
-
+    if (list->size < 2) return;
+    void *data = ((cx_array_list const *) list)->data;
+    size_t half = list->size / 2;
+    for (size_t i = 0; i < half; i++) {
+        cx_array_swap(data, list->itemsize, i, list->size - 1 - i);
+    }
 }
 
 static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) {

--- a/src/cx/array_list.h	Sun Nov 20 16:28:03 2022 +0100
+++ b/src/cx/array_list.h	Sun Nov 20 16:58:51 2022 +0100
@@ -132,6 +132,22 @@
         struct cx_array_reallocator_s *reallocator
 ) __attribute__((__nonnull__(1, 2, 5)));
 
+
+/**
+ * Swaps two array elements.
+ *
+ * @param arr the array
+ * @param elem_size the element size
+ * @param idx1 index of first element
+ * @param idx2 index of second element
+ */
+void cx_array_swap(
+        void *arr,
+        size_t elem_size,
+        size_t idx1,
+        size_t idx2
+) __attribute__((__nonnull__));
+
 /**
  * Allocates an array list for storing elements with \p item_size bytes each.
  *

--- a/test/test_list.cpp	Sun Nov 20 16:28:03 2022 +0100
+++ b/test/test_list.cpp	Sun Nov 20 16:58:51 2022 +0100
@@ -933,7 +933,6 @@
 }
 
 TEST_F(ArrayList, cxListReverse) {
-    ASSERT_EQ(1,0); // TODO: remove when implemented
     verifyReverse(arrayListFromTestData());
 }