Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/linked_list.h	Sat Oct 09 11:12:48 2021 +0200
     1.2 +++ b/src/cx/linked_list.h	Sat Dec 04 17:38:23 2021 +0100
     1.3 @@ -97,17 +97,30 @@
     1.4  void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index);
     1.5  
     1.6  /**
     1.7 + * Finds the first node in a linked list.
     1.8 + *
     1.9 + * The function starts with the pointer denoted by \p node and traverses the list
    1.10 + * along a prev pointer whose location within the node struct is
    1.11 + * denoted by \p loc_prev.
    1.12 + *
    1.13 + * @param node a pointer to a node in the list
    1.14 + * @param loc_prev the location of the \c prev pointer
    1.15 + * @return a pointer to the first node or \c NULL if \p node is \c NULL
    1.16 + */
    1.17 +void *cx_linked_list_first(void *node, ptrdiff_t loc_prev);
    1.18 +
    1.19 +/**
    1.20   * Finds the last node in a linked list.
    1.21   *
    1.22 - * The function starts with the pointer denoted by \p begin and traverses the list
    1.23 + * The function starts with the pointer denoted by \p node and traverses the list
    1.24   * along a next pointer whose location within the node struct is
    1.25   * denoted by \p loc_next.
    1.26   *
    1.27 - * @param begin a pointer to the begin node
    1.28 + * @param node a pointer to a node in the list
    1.29   * @param loc_next the location of the \c next pointer
    1.30   * @return a pointer to the last node or \c NULL if \p begin is \c NULL
    1.31   */
    1.32 -void *cx_linked_list_last(void *begin, ptrdiff_t loc_next);
    1.33 +void *cx_linked_list_last(void *node, ptrdiff_t loc_next);
    1.34  
    1.35  /**
    1.36   * Finds the predecessor of a node in case it is not linked.
    1.37 @@ -123,6 +136,7 @@
    1.38  
    1.39  /**
    1.40   * Adds a new node to a linked list.
    1.41 + * The node must not be part of any list already.
    1.42   *
    1.43   * \remark One of the pointers \p begin and \p end may be \c NULL, but not both.
    1.44   *
    1.45 @@ -135,6 +149,20 @@
    1.46  void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
    1.47  
    1.48  /**
    1.49 + * Prepends a new node to a linked list.
    1.50 + * The node must not be part of any list already.
    1.51 + *
    1.52 + * \remark One of the pointers \p begin and \p end may be \c NULL, but not both.
    1.53 + *
    1.54 + * @param begin a pointer to the begin node pointer (if your list has one)
    1.55 + * @param end a pointer to the end node pointer (if your list has one)
    1.56 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
    1.57 + * @param loc_next the location of a \c next pointer within your node struct (required)
    1.58 + * @param new_node a pointer to the node that shall be prepended
    1.59 + */
    1.60 +void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
    1.61 +
    1.62 +/**
    1.63   * Removes a node from the linked list.
    1.64   *
    1.65   * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)

     2.1 --- a/src/linked_list.c	Sat Oct 09 11:12:48 2021 +0200
     2.2 +++ b/src/linked_list.c	Sat Dec 04 17:38:23 2021 +0100
     2.3 @@ -47,12 +47,16 @@
     2.4      return cur;
     2.5  }
     2.6  
     2.7 -void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {
     2.8 +void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
     2.9 +    return cx_linked_list_last(node, loc_prev);
    2.10 +}
    2.11 +
    2.12 +void *cx_linked_list_last(void *node, ptrdiff_t loc_next) {
    2.13      assert(loc_next >= 0);
    2.14 -    if (begin == NULL)
    2.15 +    if (node == NULL)
    2.16          return NULL;
    2.17  
    2.18 -    void *cur = begin;
    2.19 +    void *cur = node;
    2.20      void *last;
    2.21      do {
    2.22          last = cur;
    2.23 @@ -76,6 +80,7 @@
    2.24  
    2.25  void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
    2.26      assert(loc_next >= 0);
    2.27 +    assert(CX_LL_PTR(new_node, loc_next) == NULL);
    2.28      void *last;
    2.29      if (end == NULL) {
    2.30          assert(begin != NULL);
    2.31 @@ -84,8 +89,9 @@
    2.32          last = *end;
    2.33      }
    2.34      if (last == NULL) {
    2.35 -        assert(begin != NULL);
    2.36 -        *begin = new_node;
    2.37 +        if (begin != NULL) {
    2.38 +            *begin = new_node;
    2.39 +        }
    2.40      } else {
    2.41          // if there is a last node, update its next pointer
    2.42          CX_LL_PTR(last, loc_next) = new_node;
    2.43 @@ -93,15 +99,44 @@
    2.44  
    2.45      // if there is an end pointer, update it
    2.46      if (end != NULL) {
    2.47 -        *end = cx_linked_list_last(new_node, loc_next);
    2.48 +        *end = new_node;
    2.49      }
    2.50  
    2.51      // if the nodes use a prev pointer, update it
    2.52      if (loc_prev >= 0) {
    2.53 +        assert(CX_LL_PTR(new_node, loc_prev) == NULL);
    2.54          CX_LL_PTR(new_node, loc_prev) = last;
    2.55      }
    2.56  }
    2.57  
    2.58 +void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
    2.59 +    assert(loc_next >= 0);
    2.60 +    assert(CX_LL_PTR(new_node, loc_next) == NULL);
    2.61 +    void *first;
    2.62 +    if (begin == NULL) {
    2.63 +        assert(end != NULL);
    2.64 +        assert(loc_prev >= 0);
    2.65 +        first = cx_linked_list_first(*end, loc_prev);
    2.66 +    } else {
    2.67 +        first = *begin;
    2.68 +    }
    2.69 +    if (first == NULL) {
    2.70 +        if (end != NULL) {
    2.71 +            *end = new_node;
    2.72 +        }
    2.73 +    } else {
    2.74 +        CX_LL_PTR(new_node, loc_next) = first;
    2.75 +        if (loc_prev >= 0) {
    2.76 +            CX_LL_PTR(first, loc_prev) = new_node;
    2.77 +        }
    2.78 +    }
    2.79 +
    2.80 +    if (begin != NULL) {
    2.81 +        assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL);
    2.82 +        *begin = new_node;
    2.83 +    }
    2.84 +}
    2.85 +
    2.86  void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
    2.87      assert(loc_next >= 0);
    2.88      assert(loc_prev >= 0 || begin != NULL);

     3.1 --- a/test/test_list.c	Sat Oct 09 11:12:48 2021 +0200
     3.2 +++ b/test/test_list.c	Sat Dec 04 17:38:23 2021 +0100
     3.3 @@ -88,8 +88,8 @@
     3.4      cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
     3.5      CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
     3.6      CU_ASSERT_PTR_EQUAL(end, &nodes[0])
     3.7 -    CU_ASSERT_PTR_EQUAL(nodes[0].prev, NULL)
     3.8 -    CU_ASSERT_PTR_EQUAL(nodes[0].next, NULL)
     3.9 +    CU_ASSERT_PTR_NULL(nodes[0].prev)
    3.10 +    CU_ASSERT_PTR_NULL(nodes[0].next)
    3.11  
    3.12      cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
    3.13      CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    3.14 @@ -113,6 +113,23 @@
    3.15      CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
    3.16      CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
    3.17  
    3.18 +    // test with end only / prev, next
    3.19 +    memset(nodes, 0, 4 * sizeof(struct node));
    3.20 +    begin = NULL;
    3.21 +    end = NULL;
    3.22 +
    3.23 +    cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
    3.24 +    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    3.25 +    cx_linked_list_add(NULL, &end,  loc_prev, loc_next, &nodes[1]);
    3.26 +    CU_ASSERT_PTR_EQUAL(end, &nodes[1])
    3.27 +    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
    3.28 +    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
    3.29 +
    3.30 +    cx_linked_list_add(NULL, &end,  loc_prev, loc_next, &nodes[2]);
    3.31 +    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
    3.32 +    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
    3.33 +    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
    3.34 +
    3.35      // test with begin, end / next
    3.36      memset(nodes, 0, 4 * sizeof(struct node));
    3.37      begin = NULL;
    3.38 @@ -127,6 +144,104 @@
    3.39      CU_ASSERT_PTR_NULL(nodes[1].prev)
    3.40  }
    3.41  
    3.42 +void test_linked_list_prepend(void) {
    3.43 +    struct node {
    3.44 +        void *prev;
    3.45 +        void *next;
    3.46 +    };
    3.47 +
    3.48 +    struct node nodes[4];
    3.49 +
    3.50 +    // test with begin, end / prev, next
    3.51 +    memset(nodes, 0, 4 * sizeof(struct node));
    3.52 +    void *begin = NULL;
    3.53 +    void *end = NULL;
    3.54 +
    3.55 +    ptrdiff_t loc_prev = offsetof(struct node, prev);
    3.56 +    ptrdiff_t loc_next = offsetof(struct node, next);
    3.57 +
    3.58 +    cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
    3.59 +    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    3.60 +    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    3.61 +    CU_ASSERT_PTR_NULL(nodes[0].prev)
    3.62 +    CU_ASSERT_PTR_NULL(nodes[0].next)
    3.63 +
    3.64 +    cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
    3.65 +    CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
    3.66 +    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    3.67 +    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
    3.68 +    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
    3.69 +
    3.70 +    // test with begin only / prev, next
    3.71 +    memset(nodes, 0, 4 * sizeof(struct node));
    3.72 +    begin = NULL;
    3.73 +    end = NULL;
    3.74 +
    3.75 +    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
    3.76 +    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    3.77 +    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
    3.78 +    CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
    3.79 +    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
    3.80 +    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
    3.81 +
    3.82 +    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
    3.83 +    CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
    3.84 +    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
    3.85 +    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
    3.86 +
    3.87 +    // test with end only / prev, next
    3.88 +    memset(nodes, 0, 4 * sizeof(struct node));
    3.89 +    begin = NULL;
    3.90 +    end = NULL;
    3.91 +
    3.92 +    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
    3.93 +    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    3.94 +    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
    3.95 +    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    3.96 +    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
    3.97 +    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
    3.98 +
    3.99 +    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
   3.100 +    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.101 +    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
   3.102 +    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
   3.103 +
   3.104 +    // test with begin, end / next
   3.105 +    memset(nodes, 0, 4 * sizeof(struct node));
   3.106 +    begin = NULL;
   3.107 +    end = NULL;
   3.108 +
   3.109 +    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
   3.110 +    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.111 +    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.112 +    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
   3.113 +    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
   3.114 +    CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
   3.115 +    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.116 +    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
   3.117 +    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
   3.118 +    CU_ASSERT_PTR_NULL(nodes[1].prev)
   3.119 +    CU_ASSERT_PTR_NULL(nodes[0].prev)
   3.120 +}
   3.121 +
   3.122 +void test_linked_list_first(void) {
   3.123 +    CU_ASSERT_PTR_NULL(cx_linked_list_first(NULL, 0))
   3.124 +
   3.125 +    struct node {
   3.126 +        int data;
   3.127 +        void *prev;
   3.128 +    };
   3.129 +    ptrdiff_t loc = offsetof(struct node, prev);
   3.130 +
   3.131 +    struct node first = {1, NULL};
   3.132 +    struct node second = {2, &first};
   3.133 +    struct node third = {3, &second};
   3.134 +
   3.135 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&first, loc), &first)
   3.136 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&second, loc), &first)
   3.137 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&third, loc), &first)
   3.138 +}
   3.139 +
   3.140  void test_linked_list_last(void) {
   3.141      CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0))
   3.142  
   3.143 @@ -738,7 +853,9 @@
   3.144      suite = CU_add_suite("low level linked list", NULL, NULL);
   3.145  
   3.146      cu_add_test(suite, test_linked_list_at);
   3.147 +    cu_add_test(suite, test_linked_list_prepend);
   3.148      cu_add_test(suite, test_linked_list_add);
   3.149 +    cu_add_test(suite, test_linked_list_first);
   3.150      cu_add_test(suite, test_linked_list_last);
   3.151      cu_add_test(suite, test_linked_list_prev);
   3.152      cu_add_test(suite, test_linked_list_remove);