Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/linked_list.h	Tue Oct 05 13:04:20 2021 +0200
     1.2 +++ b/src/cx/linked_list.h	Tue Oct 05 16:33:11 2021 +0200
     1.3 @@ -122,6 +122,46 @@
     1.4   */
     1.5  void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
     1.6  
     1.7 +/**
     1.8 + * Determines the size of a linked list starting with \p node.
     1.9 + * @param node the first node
    1.10 + * @param loc_next the location of the \c next pointer within the node struct
    1.11 + * @return the size of the list or zero if \p node is \c NULL
    1.12 + */
    1.13 +size_t cx_linked_list_size(void *node, ptrdiff_t loc_next);
    1.14 +
    1.15 +/**
    1.16 + * Sorts a linked list based on a comparison function.
    1.17 + *
    1.18 + * This function can work with linked lists of the following structures:
    1.19 + * \code
    1.20 + * typedef struct node node;
    1.21 + * struct node {
    1.22 + *   node* prev;
    1.23 + *   node* next;
    1.24 + *   my_payload data; // in this case set follow_ptr = 0
    1.25 + * }
    1.26 + *
    1.27 + * typedef struct ptr_node ptr_node;
    1.28 + * struct ptr_node {
    1.29 + *   ptr_node* prev;
    1.30 + *   ptr_node* next;
    1.31 + *   my_payload* data; // in this case set follow_ptr = 1
    1.32 + * }
    1.33 + * \endcode
    1.34 + *
    1.35 + * @param begin a pointer to the begin node pointer (required)
    1.36 + * @param end a pointer to the end node pointer (optional)
    1.37 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
    1.38 + * @param loc_next the location of a \c next pointer within your node struct (required)
    1.39 + * @param loc_data the location of the \c data pointer within your node struct
    1.40 + * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
    1.41 + * If \c true, the data at \p loc_data is dereferenced, assuming to be a pointer, and then passed to \p cmp_func.
    1.42 + * @param cmp_func the compare function defining the sort order
    1.43 + */
    1.44 +void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
    1.45 +                         ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func);
    1.46 +
    1.47  #ifdef __cplusplus
    1.48  } /* extern "C" */
    1.49  #endif

     2.1 --- a/src/linked_list.c	Tue Oct 05 13:04:20 2021 +0200
     2.2 +++ b/src/linked_list.c	Tue Oct 05 16:33:11 2021 +0200
     2.3 @@ -33,13 +33,13 @@
     2.4  
     2.5  /* LOW LEVEL LINKED LIST FUNCTIONS */
     2.6  
     2.7 -#define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
     2.8 +#define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
     2.9  
    2.10  void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
    2.11      size_t i = start_index;
    2.12      void *cur = start;
    2.13      while (i != index && cur != NULL) {
    2.14 -        cur = *CX_LL_PTR(cur, loc_advance);
    2.15 +        cur = CX_LL_PTR(cur, loc_advance);
    2.16          i < index ? i++ : i--;
    2.17      }
    2.18      return cur;
    2.19 @@ -53,7 +53,7 @@
    2.20      void *last;
    2.21      do {
    2.22          last = cur;
    2.23 -    } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);
    2.24 +    } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
    2.25  
    2.26      return last;
    2.27  }
    2.28 @@ -71,8 +71,7 @@
    2.29          *begin = new_node;
    2.30      } else {
    2.31          // if there is a last node, update its next pointer
    2.32 -        void **next = CX_LL_PTR(last, loc_next);
    2.33 -        *next = new_node;
    2.34 +        CX_LL_PTR(last, loc_next) = new_node;
    2.35      }
    2.36  
    2.37      // if there is an end pointer, update it
    2.38 @@ -82,11 +81,126 @@
    2.39  
    2.40      // if the nodes use a prev pointer, update it
    2.41      if (loc_prev >= 0) {
    2.42 -        void **prev = CX_LL_PTR(new_node, loc_prev);
    2.43 -        *prev = last;
    2.44 +        CX_LL_PTR(new_node, loc_prev) = last;
    2.45      }
    2.46  }
    2.47  
    2.48 +size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
    2.49 +    size_t size = 0;
    2.50 +    while (node != NULL) {
    2.51 +        node = CX_LL_PTR(node, loc_next);
    2.52 +        size++;
    2.53 +    }
    2.54 +    return size;
    2.55 +}
    2.56 +
    2.57 +#define ll_prev(node) CX_LL_PTR(node, loc_prev)
    2.58 +#define ll_next(node) CX_LL_PTR(node, loc_next)
    2.59 +#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
    2.60 +
    2.61 +static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
    2.62 +                                       ptrdiff_t loc_data, int follow_ptr,
    2.63 +                                       size_t length, void *ls, void *le, void *re,
    2.64 +                                       CxListComparator cmp_func) {
    2.65 +    const size_t sbo_len = 1024;
    2.66 +    void *sbo[sbo_len];
    2.67 +    void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
    2.68 +    void *rc, *lc;
    2.69 +
    2.70 +    lc = ls;
    2.71 +    rc = le;
    2.72 +    size_t n = 0;
    2.73 +    while (lc && lc != le && rc != re) {
    2.74 +        if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
    2.75 +            sorted[n] = lc;
    2.76 +            lc = ll_next(lc);
    2.77 +        } else {
    2.78 +            sorted[n] = rc;
    2.79 +            rc = ll_next(rc);
    2.80 +        }
    2.81 +        n++;
    2.82 +    }
    2.83 +    while (lc && lc != le) {
    2.84 +        sorted[n] = lc;
    2.85 +        lc = ll_next(lc);
    2.86 +        n++;
    2.87 +    }
    2.88 +    while (rc && rc != re) {
    2.89 +        sorted[n] = rc;
    2.90 +        rc = ll_next(rc);
    2.91 +        n++;
    2.92 +    }
    2.93 +
    2.94 +    // Update pointer
    2.95 +    if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
    2.96 +    for (size_t i = 0; i < length - 1; i++) {
    2.97 +        ll_next(sorted[i]) = sorted[i + 1];
    2.98 +        if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
    2.99 +    }
   2.100 +    ll_next(sorted[length - 1]) = NULL;
   2.101 +
   2.102 +    void *ret = sorted[0];
   2.103 +    if (sorted != sbo) {
   2.104 +        free(sorted);
   2.105 +    }
   2.106 +    return ret;
   2.107 +}
   2.108 +
   2.109 +void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
   2.110 +                         ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
   2.111 +    assert(begin != NULL);
   2.112 +
   2.113 +    void *lc, *ls, *le, *re;
   2.114 +
   2.115 +    // set start node
   2.116 +    ls = *begin;
   2.117 +
   2.118 +    // check how many elements are already sorted
   2.119 +    lc = ls;
   2.120 +    size_t ln = 1;
   2.121 +    while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
   2.122 +        lc = ll_next(lc);
   2.123 +        ln++;
   2.124 +    }
   2.125 +    le = ll_next(lc);
   2.126 +
   2.127 +    // if first unsorted node is NULL, the list is already completely sorted
   2.128 +    if (le != NULL) {
   2.129 +        void *rc;
   2.130 +        size_t rn = 1;
   2.131 +        rc = le;
   2.132 +        // skip already sorted elements
   2.133 +        while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
   2.134 +            rc = ll_next(rc);
   2.135 +            rn++;
   2.136 +        }
   2.137 +        re = ll_next(rc);
   2.138 +
   2.139 +        // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
   2.140 +        void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
   2.141 +                                                 ln + rn, ls, le, re, cmp_func);
   2.142 +
   2.143 +        // Something left? Sort it!
   2.144 +        size_t remainder_length = cx_linked_list_size(re, loc_next);
   2.145 +        if (remainder_length > 0) {
   2.146 +            void *remainder = re;
   2.147 +            cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
   2.148 +
   2.149 +            // merge sorted list with (also sorted) remainder
   2.150 +            *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
   2.151 +                                               ln + rn + remainder_length,
   2.152 +                                               sorted, remainder, NULL, cmp_func);
   2.153 +        } else {
   2.154 +            // no remainder - we've got our sorted list
   2.155 +            *begin = sorted;
   2.156 +        }
   2.157 +        if (end) *end = cx_linked_list_last(sorted, loc_next);
   2.158 +    }
   2.159 +}
   2.160 +
   2.161 +#undef ll_next
   2.162 +#undef ll_data
   2.163 +
   2.164  /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
   2.165  
   2.166  typedef struct cx_linked_list_node cx_linked_list_node;
   2.167 @@ -109,7 +223,7 @@
   2.168      if (index >= list->base.size) {
   2.169          return NULL;
   2.170      } else if (index > list->base.size / 2) {
   2.171 -        return cx_linked_list_at(list->end, list->base.size-1, CX_LL_LOC_PREV, index);
   2.172 +        return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
   2.173      } else {
   2.174          return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
   2.175      }
   2.176 @@ -144,7 +258,7 @@
   2.177              node->next = NULL;
   2.178              ll->end = node;
   2.179          }
   2.180 -        // check if this shall be the new start node
   2.181 +            // check if this shall be the new start node
   2.182          else if (index == 0) {
   2.183              ll->begin->prev = node;
   2.184              node->next = ll->begin;
   2.185 @@ -219,7 +333,7 @@
   2.186  static void *cx_pll_at(cx_list_s *list, size_t index) {
   2.187      cx_linked_list *ll = (cx_linked_list *) list;
   2.188      cx_linked_list_node *node = cx_ll_node_at(ll, index);
   2.189 -    return node == NULL ? NULL : *(void**)node->payload;
   2.190 +    return node == NULL ? NULL : *(void **) node->payload;
   2.191  }
   2.192  
   2.193  static size_t cx_ll_find(cx_list_s *list, void *elem) {
   2.194 @@ -245,7 +359,7 @@
   2.195      size_t index;
   2.196      cx_linked_list_node *node = ll->begin;
   2.197      for (index = 0; index < list->size; index++) {
   2.198 -        void *current = *(void**)node->payload;
   2.199 +        void *current = *(void **) node->payload;
   2.200          if (cmp(current, elem) == 0) {
   2.201              return index;
   2.202          }
   2.203 @@ -263,7 +377,7 @@
   2.204  static void *cx_pll_last(cx_list_s *list) {
   2.205      cx_linked_list *ll = (cx_linked_list *) list;
   2.206      cx_linked_list_node *last = ll->end;
   2.207 -    return last == NULL ? NULL : *(void**)last->payload;
   2.208 +    return last == NULL ? NULL : *(void **) last->payload;
   2.209  }
   2.210  
   2.211  static cx_list_class cx_linked_list_class = {
   2.212 @@ -310,7 +424,7 @@
   2.213      list->base.cl = &cx_pointer_linked_list_class;
   2.214      list->base.allocator = allocator;
   2.215      list->base.cmpfunc = comparator;
   2.216 -    list->base.itemsize = sizeof(void*);
   2.217 +    list->base.itemsize = sizeof(void *);
   2.218      list->base.capacity = SIZE_MAX;
   2.219      list->base.size = 0;
   2.220  

     3.1 --- a/test/test_list.c	Tue Oct 05 13:04:20 2021 +0200
     3.2 +++ b/test/test_list.c	Tue Oct 05 16:33:11 2021 +0200
     3.3 @@ -146,6 +146,82 @@
     3.4      CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
     3.5  }
     3.6  
     3.7 +void test_linked_list_size(void) {
     3.8 +    struct node {
     3.9 +        void *next;
    3.10 +    };
    3.11 +    ptrdiff_t loc = offsetof(struct node, next);
    3.12 +
    3.13 +    struct node first = {NULL};
    3.14 +    struct node second = {NULL};
    3.15 +    struct node third = {NULL};
    3.16 +
    3.17 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0)
    3.18 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1)
    3.19 +    first.next = &second;
    3.20 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
    3.21 +    second.next = &third;
    3.22 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
    3.23 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
    3.24 +}
    3.25 +
    3.26 +void test_linked_list_sort(void) {
    3.27 +    struct node {
    3.28 +        void *prev;
    3.29 +        void *next;
    3.30 +        int data;
    3.31 +    };
    3.32 +
    3.33 +    int expected[] = {
    3.34 +            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
    3.35 +            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
    3.36 +            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
    3.37 +            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
    3.38 +            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
    3.39 +            4785, 4791, 4801, 4859, 4903, 4973
    3.40 +    };
    3.41 +    int scrambled[] = {
    3.42 +            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
    3.43 +            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
    3.44 +            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
    3.45 +            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
    3.46 +            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
    3.47 +            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
    3.48 +    };
    3.49 +
    3.50 +    struct node *nodes = calloc(100, sizeof(struct node));
    3.51 +    for (int i = 0; i < 100; i++) {
    3.52 +        nodes[i].prev = i == 0 ? NULL : &nodes[i - 1];
    3.53 +        nodes[i].next = i == 99 ? NULL : &nodes[i + 1];
    3.54 +        nodes[i].data = scrambled[i];
    3.55 +    }
    3.56 +
    3.57 +    struct node *begin = &nodes[0];
    3.58 +    struct node *end = &nodes[99];
    3.59 +
    3.60 +    cx_linked_list_sort((void **) &begin, (void **) &end,
    3.61 +                        offsetof(struct node, prev),
    3.62 +                        offsetof(struct node, next),
    3.63 +                        offsetof(struct node, data),
    3.64 +                        0, (CxListComparator) cmp_int);
    3.65 +
    3.66 +    CU_ASSERT_PTR_NULL(begin->prev)
    3.67 +    CU_ASSERT_EQUAL(begin->data, expected[0])
    3.68 +    struct node *check = begin;
    3.69 +    struct node *check_last = NULL;
    3.70 +    for (int i = 0 ; i < 100 ; i++) {
    3.71 +        CU_ASSERT_EQUAL(check->data, expected[i])
    3.72 +        CU_ASSERT_PTR_EQUAL(check->prev, check_last)
    3.73 +        if (i < 99) {
    3.74 +            CU_ASSERT_PTR_NOT_NULL(check->next)
    3.75 +        }
    3.76 +        check_last = check;
    3.77 +        check = check->next;
    3.78 +    }
    3.79 +    CU_ASSERT_PTR_NULL(check)
    3.80 +    CU_ASSERT_EQUAL(end->data, expected[99])
    3.81 +}
    3.82 +
    3.83  
    3.84  void test_hl_linked_list_create(void) {
    3.85      cxTestingAllocatorReset();
    3.86 @@ -494,6 +570,8 @@
    3.87      cu_add_test(suite, test_linked_list_at);
    3.88      cu_add_test(suite, test_linked_list_add);
    3.89      cu_add_test(suite, test_linked_list_last);
    3.90 +    cu_add_test(suite, test_linked_list_size);
    3.91 +    cu_add_test(suite, test_linked_list_sort);
    3.92  
    3.93      suite = CU_add_suite("high level linked list", NULL, NULL);
    3.94