Mercurial > hg > ucx / changeset

     1.1 --- a/src/linked_list.c	Tue Sep 28 18:09:25 2021 +0200
     1.2 +++ b/src/linked_list.c	Tue Sep 28 18:22:00 2021 +0200
     1.3 @@ -36,7 +36,7 @@
     1.4  
     1.5  void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
     1.6      size_t i = start_index;
     1.7 -    void* cur = start;
     1.8 +    void *cur = start;
     1.9      while (i != index && cur != NULL) {
    1.10          cur = *CX_LL_PTR(cur, loc_advance);
    1.11          i < index ? i++ : i--;
    1.12 @@ -93,45 +93,42 @@
    1.13  
    1.14  /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
    1.15  
    1.16 -struct cx_linked_list_node {
    1.17 +typedef struct {
    1.18      void *prev;
    1.19      void *next;
    1.20      char payload[];
    1.21 -};
    1.22 +} cx_linked_list_node;
    1.23  
    1.24 -#define CX_LL_LOC_PREV offsetof(struct cx_linked_list_node, prev)
    1.25 -#define CX_LL_LOC_NEXT offsetof(struct cx_linked_list_node, next)
    1.26 +#define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
    1.27 +#define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
    1.28  
    1.29  typedef struct {
    1.30      cx_list_s base;
    1.31 -    void *begin;
    1.32 -    void *end;
    1.33 -    ptrdiff_t loc_prev;
    1.34 -    ptrdiff_t loc_next;
    1.35 +    cx_linked_list_node *begin;
    1.36 +    cx_linked_list_node *end;
    1.37  } cx_linked_list;
    1.38  
    1.39  static int cx_ll_add(cx_list_s *list, void *elem) {
    1.40      cx_linked_list *ll = (cx_linked_list *) list;
    1.41  
    1.42 -    struct cx_linked_list_node *node = cxMalloc(list->allocator,
    1.43 -                                                sizeof(struct cx_linked_list_node) + list->itemsize);
    1.44 +    cx_linked_list_node *node = cxMalloc(list->allocator,
    1.45 +                                         sizeof(cx_linked_list_node) + list->itemsize);
    1.46      if (node == NULL)
    1.47          return 1;
    1.48  
    1.49 -    node->next = node->prev = NULL;
    1.50      memcpy(node->payload, elem, list->itemsize);
    1.51 +    node->next = NULL;
    1.52  
    1.53 -    int ret = cx_linked_list_add(
    1.54 -            &ll->begin, &ll->end,
    1.55 -            CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
    1.56 -            node
    1.57 -    );
    1.58 -    if (ret == 0) {
    1.59 -        list->size++;
    1.60 -        return 0;
    1.61 +    if (ll->begin == NULL) {
    1.62 +        ll->begin = ll->end = node;
    1.63      } else {
    1.64 -        return ret;
    1.65 +        // per contract of this linked list we know that end must be non-null
    1.66 +        ll->end->next = node;
    1.67 +        ll->end = node;
    1.68      }
    1.69 +    list->size++;
    1.70 +
    1.71 +    return 0;
    1.72  }
    1.73  
    1.74  static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
    1.75 @@ -151,7 +148,7 @@
    1.76  
    1.77  static void *cx_ll_at(cx_list_s *list, size_t index) {
    1.78      cx_linked_list *ll = (cx_linked_list *) list;
    1.79 -    struct cx_linked_list_node *node;
    1.80 +    cx_linked_list_node *node;
    1.81      if (index >= list->size) {
    1.82          node = NULL;
    1.83      } else if (index > list->size / 2) {
    1.84 @@ -167,9 +164,9 @@
    1.85      cx_linked_list *ll = (cx_linked_list *) list;
    1.86  
    1.87      size_t index;
    1.88 -    struct cx_linked_list_node* node = ll->begin;
    1.89 -    for (index = 0 ; index < list->size ; index++) {
    1.90 -        void* current = node->payload;
    1.91 +    cx_linked_list_node *node = ll->begin;
    1.92 +    for (index = 0; index < list->size; index++) {
    1.93 +        void *current = node->payload;
    1.94          if (cmp(current, elem) == 0) {
    1.95              return index;
    1.96          }
    1.97 @@ -180,7 +177,7 @@
    1.98  
    1.99  static void *cx_ll_last(cx_list_s *list) {
   1.100      cx_linked_list *ll = (cx_linked_list *) list;
   1.101 -    struct cx_linked_list_node *last = cx_linked_list_last(NULL, &ll->end, CX_LL_LOC_NEXT);
   1.102 +    cx_linked_list_node *last = cx_linked_list_last(NULL, (void **) &ll->end, CX_LL_LOC_NEXT);
   1.103      return &last->payload;
   1.104  }
   1.105  
   1.106 @@ -194,7 +191,7 @@
   1.107  };
   1.108  
   1.109  CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
   1.110 -    cx_linked_list* list = cxMalloc(allocator, sizeof(cx_linked_list));
   1.111 +    cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
   1.112      if (list == NULL)
   1.113          return NULL;
   1.114  
   1.115 @@ -207,18 +204,16 @@
   1.116  
   1.117      list->begin = NULL;
   1.118      list->end = NULL;
   1.119 -    list->loc_prev = CX_LL_LOC_PREV;
   1.120 -    list->loc_next = CX_LL_LOC_NEXT;
   1.121  
   1.122      return (CxList) list;
   1.123  }
   1.124  
   1.125  void cxLinkedListDestroy(CxList list) {
   1.126 -    cx_linked_list* ll = (cx_linked_list*) list;
   1.127 +    cx_linked_list *ll = (cx_linked_list *) list;
   1.128  
   1.129 -    struct cx_linked_list_node* node = ll->begin;
   1.130 +    cx_linked_list_node *node = ll->begin;
   1.131      while (node) {
   1.132 -        void* next = node->next;
   1.133 +        void *next = node->next;
   1.134          cxFree(list->allocator, node);
   1.135          node = next;
   1.136      }
   1.137 @@ -234,13 +229,13 @@
   1.138          ll->end = NULL;
   1.139          return 0;
   1.140      } else {
   1.141 -        void *cur = ll->begin;
   1.142 -        void *last;
   1.143 +        cx_linked_list_node *cur = ll->begin;
   1.144 +        cx_linked_list_node *last;
   1.145          size_t size = 0;
   1.146          do {
   1.147              last = cur;
   1.148              size++;
   1.149 -        } while ((cur = *CX_LL_PTR(cur, ll->loc_next)) != NULL);
   1.150 +        } while ((cur = cur->next) != NULL);
   1.151          ll->end = last;
   1.152          ll->base.size = size;
   1.153          return size;

     2.1 --- a/test/test_list.c	Tue Sep 28 18:09:25 2021 +0200
     2.2 +++ b/test/test_list.c	Tue Sep 28 18:22:00 2021 +0200
     2.3 @@ -51,15 +51,11 @@
     2.4          cx_list_s base;
     2.5          void *begin;
     2.6          void *end;
     2.7 -        ptrdiff_t ploc;
     2.8 -        ptrdiff_t nloc;
     2.9      };
    2.10  
    2.11      struct ll_check *actual = (struct ll_check *) list;
    2.12      CU_ASSERT_PTR_NULL(actual->begin)
    2.13      CU_ASSERT_PTR_NULL(actual->end)
    2.14 -    CU_ASSERT_EQUAL(0, actual->ploc)
    2.15 -    CU_ASSERT_EQUAL(sizeof(void *), actual->nloc)
    2.16  
    2.17      cxLinkedListDestroy(list);
    2.18