Mercurial > hg > ucx / changeset

     1.1 --- a/src/array_list.c	Sun Nov 20 16:28:03 2022 +0100
     1.2 +++ b/src/array_list.c	Sun Nov 20 16:58:51 2022 +0100
     1.3 @@ -101,6 +101,45 @@
     1.4      return CX_ARRAY_COPY_SUCCESS;
     1.5  }
     1.6  
     1.7 +#define CX_ARRAY_SWAP_SBO_SIZE 512
     1.8 +
     1.9 +void cx_array_swap(
    1.10 +        void *arr,
    1.11 +        size_t elem_size,
    1.12 +        size_t idx1,
    1.13 +        size_t idx2
    1.14 +) {
    1.15 +    /* short circuit */
    1.16 +    if (idx1 == idx2) return;
    1.17 +
    1.18 +    char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
    1.19 +    void *tmp;
    1.20 +
    1.21 +    /* decide if we can use the local buffer */
    1.22 +    if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
    1.23 +        tmp = malloc(elem_size);
    1.24 +        /* we don't want to enforce error handling */
    1.25 +        if (tmp == NULL) abort();
    1.26 +    } else {
    1.27 +        tmp = sbo_mem;
    1.28 +    }
    1.29 +
    1.30 +    /* calculate memory locations */
    1.31 +    char *left = arr, *right = arr;
    1.32 +    left += idx1 * elem_size;
    1.33 +    right += idx2 * elem_size;
    1.34 +
    1.35 +    /* three-way swap */
    1.36 +    memcpy(tmp, left, elem_size);
    1.37 +    memcpy(left, right, elem_size);
    1.38 +    memcpy(right, tmp, elem_size);
    1.39 +
    1.40 +    /* free dynamic memory, if it was needed */
    1.41 +    if (tmp != sbo_mem) {
    1.42 +        free(tmp);
    1.43 +    }
    1.44 +}
    1.45 +
    1.46  /* HIGH LEVEL ARRAY LIST FUNCTIONS */
    1.47  
    1.48  typedef struct {
    1.49 @@ -290,7 +329,12 @@
    1.50  }
    1.51  
    1.52  static void cx_arl_reverse(struct cx_list_s *list) {
    1.53 -
    1.54 +    if (list->size < 2) return;
    1.55 +    void *data = ((cx_array_list const *) list)->data;
    1.56 +    size_t half = list->size / 2;
    1.57 +    for (size_t i = 0; i < half; i++) {
    1.58 +        cx_array_swap(data, list->itemsize, i, list->size - 1 - i);
    1.59 +    }
    1.60  }
    1.61  
    1.62  static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) {

     2.1 --- a/src/cx/array_list.h	Sun Nov 20 16:28:03 2022 +0100
     2.2 +++ b/src/cx/array_list.h	Sun Nov 20 16:58:51 2022 +0100
     2.3 @@ -132,6 +132,22 @@
     2.4          struct cx_array_reallocator_s *reallocator
     2.5  ) __attribute__((__nonnull__(1, 2, 5)));
     2.6  
     2.7 +
     2.8 +/**
     2.9 + * Swaps two array elements.
    2.10 + *
    2.11 + * @param arr the array
    2.12 + * @param elem_size the element size
    2.13 + * @param idx1 index of first element
    2.14 + * @param idx2 index of second element
    2.15 + */
    2.16 +void cx_array_swap(
    2.17 +        void *arr,
    2.18 +        size_t elem_size,
    2.19 +        size_t idx1,
    2.20 +        size_t idx2
    2.21 +) __attribute__((__nonnull__));
    2.22 +
    2.23  /**
    2.24   * Allocates an array list for storing elements with \p item_size bytes each.
    2.25   *

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