Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/linked_list.h	Mon Sep 27 17:49:23 2021 +0200
     1.2 +++ b/src/cx/linked_list.h	Mon Sep 27 18:33:30 2021 +0200
     1.3 @@ -36,6 +36,25 @@
     1.4  extern "C" {
     1.5  #endif
     1.6  
     1.7 +/**
     1.8 + * Finds the node at a certain index.
     1.9 + *
    1.10 + * This function can be used to start at an arbitrary position within the list.
    1.11 + * If the search index is large than the start index, \p loc_advance must denote
    1.12 + * the location of some sort of \c next pointer (i.e. a pointer to the next node).
    1.13 + * But it is also possible that the search index is smaller than the start index
    1.14 + * (e.g. in cases where traversing a list backwards is faster) in which case
    1.15 + * \p loc_advance must denote the location of some sort of \c prev pointer
    1.16 + * (i.e. a pointer to the previous node).
    1.17 + *
    1.18 + * @param start a pointer to the start node
    1.19 + * @param start_index the start index
    1.20 + * @param loc_advance the location of the pointer to advance
    1.21 + * @param index the search index
    1.22 + * @return the node found at the specified index
    1.23 + */
    1.24 +void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index);
    1.25 +
    1.26  void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next);
    1.27  
    1.28  int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);

     2.1 --- a/src/cx/list.h	Mon Sep 27 17:49:23 2021 +0200
     2.2 +++ b/src/cx/list.h	Mon Sep 27 18:33:30 2021 +0200
     2.3 @@ -45,7 +45,7 @@
     2.4  
     2.5      int (*insert)(cx_list_s *list, size_t index, void *elem);
     2.6  
     2.7 -    void *(*remove)(cx_list_s *list, size_t index);
     2.8 +    int (*remove)(cx_list_s *list, size_t index);
     2.9  
    2.10      size_t (*find)(cx_list_s *list, void *elem);
    2.11  
    2.12 @@ -67,7 +67,7 @@
    2.13  
    2.14  int cxListInsert(CxList list, size_t index, void *elem);
    2.15  
    2.16 -void *cxListRemove(CxList list, size_t index);
    2.17 +int cxListRemove(CxList list, size_t index);
    2.18  
    2.19  size_t cxListFind(CxList list, void *elem);
    2.20  

     3.1 --- a/src/linked_list.c	Mon Sep 27 17:49:23 2021 +0200
     3.2 +++ b/src/linked_list.c	Mon Sep 27 18:33:30 2021 +0200
     3.3 @@ -34,6 +34,16 @@
     3.4  
     3.5  #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
     3.6  
     3.7 +void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
     3.8 +    size_t i = start_index;
     3.9 +    void* cur = start;
    3.10 +    while (i != index && cur != NULL) {
    3.11 +        cur = *CX_LL_PTR(cur, loc_advance);
    3.12 +        i < index ? i++ : i--;
    3.13 +    }
    3.14 +    return cur;
    3.15 +}
    3.16 +
    3.17  void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next) {
    3.18      if (end != NULL) {
    3.19          return *end;
    3.20 @@ -97,7 +107,7 @@
    3.21      ptrdiff_t loc_next;
    3.22  } cx_linked_list;
    3.23  
    3.24 -int cx_ll_add(cx_list_s *list, void *elem) {
    3.25 +static int cx_ll_add(cx_list_s *list, void *elem) {
    3.26      cx_linked_list *ll = (cx_linked_list *) list;
    3.27  
    3.28      struct cx_linked_list_node *node = cxMalloc(list->allocator,
    3.29 @@ -122,19 +132,22 @@
    3.30      }
    3.31  }
    3.32  
    3.33 -int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
    3.34 +static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
    3.35      cx_linked_list *ll = (cx_linked_list *) list;
    3.36      // TODO: implement using low level API
    3.37      return 1;
    3.38  }
    3.39  
    3.40 -void *cx_ll_remove(cx_list_s *list, size_t index) {
    3.41 +static int cx_ll_remove(cx_list_s *list, size_t index) {
    3.42 +    if (index >= list->size) {
    3.43 +        return 1;
    3.44 +    }
    3.45      cx_linked_list *ll = (cx_linked_list *) list;
    3.46      // TODO: implement using low level API
    3.47 -    return NULL;
    3.48 +    return 0;
    3.49  }
    3.50  
    3.51 -size_t cx_ll_find(cx_list_s *list, void *elem) {
    3.52 +static size_t cx_ll_find(cx_list_s *list, void *elem) {
    3.53      CxListComparator cmp = list->cmpfunc;
    3.54      cx_linked_list *ll = (cx_linked_list *) list;
    3.55  
    3.56 @@ -150,7 +163,7 @@
    3.57      return index;
    3.58  }
    3.59  
    3.60 -void *cx_ll_last(cx_list_s *list) {
    3.61 +static void *cx_ll_last(cx_list_s *list) {
    3.62      cx_linked_list *linkedList = (cx_linked_list *) list;
    3.63      struct cx_linked_list_node *last = cx_linked_list_last(
    3.64              NULL, &linkedList->end, offsetof(struct cx_linked_list_node, next));

     4.1 --- a/src/list.c	Mon Sep 27 17:49:23 2021 +0200
     4.2 +++ b/src/list.c	Mon Sep 27 18:33:30 2021 +0200
     4.3 @@ -36,7 +36,7 @@
     4.4      return list->cl->insert(list, index, elem);
     4.5  }
     4.6  
     4.7 -void *cxListRemove(CxList list, size_t index) {
     4.8 +int cxListRemove(CxList list, size_t index) {
     4.9      return list->cl->remove(list, index);
    4.10  }
    4.11  

     5.1 --- a/test/test_list.c	Mon Sep 27 17:49:23 2021 +0200
     5.2 +++ b/test/test_list.c	Mon Sep 27 18:33:30 2021 +0200
     5.3 @@ -35,7 +35,7 @@
     5.4      return left == right ? 0 : (left < right ? -1 : 1);
     5.5  }
     5.6  
     5.7 -void test_linked_list_create() {
     5.8 +void test_linked_list_create(void) {
     5.9      cxTestingAllocatorReset();
    5.10  
    5.11      CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
    5.12 @@ -66,6 +66,40 @@
    5.13      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    5.14  }
    5.15  
    5.16 +void test_linked_list_at(void) {
    5.17 +    struct node {
    5.18 +        void *next;
    5.19 +        void *prev;
    5.20 +    };
    5.21 +    const ptrdiff_t loc_prev = offsetof(struct node, prev);
    5.22 +    const ptrdiff_t loc_next = offsetof(struct node, next);
    5.23 +
    5.24 +    struct node a, b, c, d;
    5.25 +    a.prev = NULL;
    5.26 +    a.next = &b;
    5.27 +    b.prev = &a;
    5.28 +    b.next = &c;
    5.29 +    c.prev = &b;
    5.30 +    c.next = &d;
    5.31 +    d.prev = &c;
    5.32 +    d.next = NULL;
    5.33 +
    5.34 +    CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&a, 0, loc_next, 0));
    5.35 +    CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&a, 0, loc_next, 1));
    5.36 +    CU_ASSERT_PTR_EQUAL(&c, cx_linked_list_at(&a, 0, loc_next, 2));
    5.37 +    CU_ASSERT_PTR_EQUAL(&d, cx_linked_list_at(&a, 0, loc_next, 3));
    5.38 +    CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4));
    5.39 +
    5.40 +    CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&b, 1, loc_prev, 0));
    5.41 +    CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&b, 1, loc_next, 1));
    5.42 +    CU_ASSERT_PTR_EQUAL(&c, cx_linked_list_at(&b, 1, loc_next, 2));
    5.43 +    CU_ASSERT_PTR_EQUAL(&d, cx_linked_list_at(&b, 1, loc_next, 3));
    5.44 +    CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4));
    5.45 +
    5.46 +    CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&d, 3, loc_prev, 0));
    5.47 +    CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&d, 3, loc_prev, 1));
    5.48 +}
    5.49 +
    5.50  int main() {
    5.51      CU_pSuite suite = NULL;
    5.52  
    5.53 @@ -80,7 +114,8 @@
    5.54      }
    5.55  
    5.56      if (
    5.57 -            !CU_add_test(suite, "create and destroy linked list", test_linked_list_create)
    5.58 +            !CU_add_test(suite, "linked list: create and destroy", test_linked_list_create) ||
    5.59 +            !CU_add_test(suite, "linked list: get node at index", test_linked_list_at)
    5.60              ) {
    5.61          CU_cleanup_registry();
    5.62          return CU_get_error();