diff -r eef025d82a34 -r 0d998f19d130 test/test_list.c --- a/test/test_list.c Thu Dec 23 15:20:50 2021 +0100 +++ b/test/test_list.c Mon Dec 27 14:44:08 2021 +0100 @@ -35,6 +35,40 @@ return left == right ? 0 : (left < right ? -1 : 1); } +void test_linked_list_link_unlink(void) { + struct node { + void *next; + void *prev; + }; + const ptrdiff_t loc_prev = offsetof(struct node, prev); + const ptrdiff_t loc_next = offsetof(struct node, next); + + struct node a = {NULL, NULL}, b = {NULL, NULL}; + + cx_linked_list_link(&a, &b, loc_prev, loc_next); + CU_ASSERT_PTR_NULL(a.prev) + CU_ASSERT_PTR_EQUAL(a.next, &b) + CU_ASSERT_PTR_EQUAL(b.prev, &a) + CU_ASSERT_PTR_NULL(b.next) + + cx_linked_list_unlink(&a, &b, loc_prev, loc_next); + CU_ASSERT_PTR_NULL(a.prev) + CU_ASSERT_PTR_NULL(a.next) + CU_ASSERT_PTR_NULL(b.prev) + CU_ASSERT_PTR_NULL(b.next) + + struct node c = {NULL, NULL}; + cx_linked_list_link(&b, &c, loc_prev, loc_next); + cx_linked_list_link(&a, &b, loc_prev, loc_next); + cx_linked_list_unlink(&b, &c, loc_prev, loc_next); + CU_ASSERT_PTR_NULL(a.prev) + CU_ASSERT_PTR_EQUAL(a.next, &b) + CU_ASSERT_PTR_EQUAL(b.prev, &a) + CU_ASSERT_PTR_NULL(b.next) + CU_ASSERT_PTR_NULL(c.prev) + CU_ASSERT_PTR_NULL(c.next) +} + void test_linked_list_at(void) { struct node { void *next; @@ -224,6 +258,125 @@ CU_ASSERT_PTR_NULL(nodes[0].prev) } +void test_linked_list_insert(void) { + struct node { + void *prev; + void *next; + }; + ptrdiff_t loc_prev = offsetof(struct node, prev); + ptrdiff_t loc_next = offsetof(struct node, next); + + struct node nodes[4]; + void *begin, *end; + + // insert mid list + memset(nodes, 0, 4 * sizeof(struct node)); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); + CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) + CU_ASSERT_PTR_EQUAL(end, &nodes[2]) + CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3]) + CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[3]) + CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1]) + CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[2]) + + // insert end + memset(nodes, 0, 4 * sizeof(struct node)); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); + CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) + CU_ASSERT_PTR_EQUAL(end, &nodes[3]) + CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3]) + CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2]) + CU_ASSERT_PTR_NULL(nodes[3].next) + + // insert begin + memset(nodes, 0, 4 * sizeof(struct node)); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]); + CU_ASSERT_PTR_EQUAL(begin, &nodes[3]) + CU_ASSERT_PTR_EQUAL(end, &nodes[2]) + CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[3]) + CU_ASSERT_PTR_NULL(nodes[3].prev) + CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0]) +} + +void test_linked_list_insert_chain(void) { + struct node { + void *prev; + void *next; + }; + ptrdiff_t loc_prev = offsetof(struct node, prev); + ptrdiff_t loc_next = offsetof(struct node, next); + + struct node nodes[5]; + void *begin, *end; + + // insert mid list + memset(nodes, 0, 5 * sizeof(struct node)); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); + + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL); + CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) + CU_ASSERT_PTR_EQUAL(end, &nodes[2]) + CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3]) + CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[4]) + CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1]) + CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[2]) + + // insert end + memset(nodes, 0, 5 * sizeof(struct node)); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); + + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL); + CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) + CU_ASSERT_PTR_EQUAL(end, &nodes[4]) + CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3]) + CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2]) + CU_ASSERT_PTR_NULL(nodes[4].next) + + // insert begin + memset(nodes, 0, 5 * sizeof(struct node)); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); + + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL); + CU_ASSERT_PTR_EQUAL(begin, &nodes[3]) + CU_ASSERT_PTR_EQUAL(end, &nodes[2]) + CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[4]) + CU_ASSERT_PTR_NULL(nodes[3].prev) + CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0]) +} + void test_linked_list_first(void) { struct node { int data; @@ -873,9 +1026,12 @@ suite = CU_add_suite("low level linked list", NULL, NULL); + cu_add_test(suite, test_linked_list_link_unlink); cu_add_test(suite, test_linked_list_at); cu_add_test(suite, test_linked_list_prepend); cu_add_test(suite, test_linked_list_add); + cu_add_test(suite, test_linked_list_insert); + cu_add_test(suite, test_linked_list_insert_chain); cu_add_test(suite, test_linked_list_first); cu_add_test(suite, test_linked_list_last); cu_add_test(suite, test_linked_list_prev);