diff options
| -rw-r--r-- | lib/Makefile | 2 | ||||
| -rw-r--r-- | lib/tlists.h | 28 | ||||
| -rw-r--r-- | lib/tlists_test.c | 314 |
3 files changed, 342 insertions, 2 deletions
diff --git a/lib/Makefile b/lib/Makefile index f4ade9a6..6ed778cc 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -2,6 +2,6 @@ src := a-path.c a-set.c bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c obj := $(src-o-files) $(all-daemon) -tests_src := a-set_test.c a-path_test.c bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c type_test.c +tests_src := a-set_test.c a-path_test.c bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c tlists_test.c type_test.c tests_targets := $(tests_targets) $(tests-target-files) tests_objs := $(tests_objs) $(src-o-files) diff --git a/lib/tlists.h b/lib/tlists.h index ea21b141..d7f1cf03 100644 --- a/lib/tlists.h +++ b/lib/tlists.h @@ -89,7 +89,7 @@ static inline struct TLIST_NAME(node) * TLIST_NAME(node_get)(TLIST_TYPE *node) { return &(node->TLIST_ITEM); } #endif -#ifdef TLIST_WANT_ADD_HEAD +#if defined(TLIST_WANT_ADD_HEAD) || defined(TLIST_WANT_ADD_AFTER) static inline void TLIST_NAME(add_head)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node) { ASSERT_DIE(!TLIST_NAME(enlisted)(node)); @@ -136,6 +136,32 @@ static inline void TLIST_NAME(update_node)(TLIST_LIST_STRUCT *list, TLIST_TYPE * } #endif +#ifdef TLIST_WANT_ADD_AFTER +static inline void TLIST_NAME(add_after)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node, TLIST_TYPE *after) +{ + ASSERT_DIE(!TLIST_NAME(enlisted)(node)); + + /* Adding to beginning */ + if (!(node->TLIST_ITEM.prev = after)) + return TLIST_NAME(add_head)(list, node); + + /* OK, Adding after a real node */ + node->TLIST_ITEM.list = list; + + /* There is another node after the anchor */ + if (node->TLIST_ITEM.next = after->TLIST_ITEM.next) + /* Link back */ + node->TLIST_ITEM.next->TLIST_ITEM.prev = node; + else + /* Or we are adding the last node */ + list->last = node; + + /* Link forward from "after" */ + after->TLIST_ITEM.next = node; +} +#endif + + static inline void TLIST_NAME(rem_node)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node) { ASSERT_DIE(TLIST_NAME(enlisted)(node) == list); diff --git a/lib/tlists_test.c b/lib/tlists_test.c new file mode 100644 index 00000000..8ba080a6 --- /dev/null +++ b/lib/tlists_test.c @@ -0,0 +1,314 @@ +/* + * BIRD Library -- Linked Lists Tests + * + * (c) 2015 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "lib/tlists.h" + +#define TLIST_PREFIX tp +#define TLIST_TYPE struct test_node +#define TLIST_ITEM n +#define TLIST_WANT_ADD_HEAD +#define TLIST_WANT_ADD_TAIL +#define TLIST_WANT_ADD_AFTER +#define TLIST_WANT_UPDATE_NODE + +struct test_node { + TLIST_DEFAULT_NODE; +}; + +#include "lib/tlists.h" + +#define MAX_NUM 1000 + +static struct test_node nodes[MAX_NUM]; +static TLIST_LIST(tp) l; + +static void +show_list(void) +{ + bt_debug("\n"); + bt_debug("list.first points to %p\n", l.first); + bt_debug("list.last points to %p\n", l.last); + + int i; + for (i = 0; i < MAX_NUM; i++) + { + bt_debug("n[%3i] is at %p\n", i, &nodes[i]); + bt_debug(" prev is at %p and point to %p\n", &(nodes[i].n.prev), nodes[i].n.prev); + bt_debug(" next is at %p and point to %p\n", &(nodes[i].n.next), nodes[i].n.next); + } +} + +static int +is_filled_list_well_linked(void) +{ + int i; + bt_assert(l.first == &nodes[0]); + bt_assert(l.last == &nodes[MAX_NUM-1]); + bt_assert(!nodes[0].n.prev); + bt_assert(!nodes[MAX_NUM-1].n.next); + + for (i = 0; i < MAX_NUM; i++) + { + bt_assert(nodes[i].n.list == &l); + + if (i < (MAX_NUM-1)) + bt_assert(nodes[i].n.next == &nodes[i+1]); + + if (i > 0) + bt_assert(nodes[i].n.prev == &nodes[i-1]); + } + + return 1; +} + +static int +is_empty_list_well_unlinked(void) +{ + int i; + + bt_assert(!l.first); + bt_assert(!l.last); + bt_assert(EMPTY_TLIST(tp, &l)); + + for (i = 0; i < MAX_NUM; i++) + { + bt_assert(nodes[i].n.next == NULL); + bt_assert(nodes[i].n.prev == NULL); + bt_assert(nodes[i].n.list == NULL); + } + + return 1; +} + +static void +init_list__(TLIST_LIST(tp) *l, struct test_node nodes[]) +{ + *l = (TLIST_LIST(tp)) {}; + + int i; + for (i = 0; i < MAX_NUM; i++) + { + nodes[i].n.next = NULL; + nodes[i].n.prev = NULL; + nodes[i].n.list = NULL; + } +} + +static void +init_list_(void) +{ + init_list__(&l, nodes); +} + +static int +t_add_tail(void) +{ + int i; + + init_list_(); + for (i = 0; i < MAX_NUM; i++) + { + tp_add_tail(&l, &nodes[i]); + bt_debug("."); + bt_assert(l.last == &nodes[i]); + bt_assert(l.first == &nodes[0]); + + bt_assert(nodes[i].n.list == &l); + bt_assert(!nodes[i].n.next); + + if (i > 0) + { + bt_assert(nodes[i-1].n.next == &nodes[i]); + bt_assert(nodes[i].n.prev == &nodes[i-1]); + } + } + show_list(); + bt_assert(is_filled_list_well_linked()); + + return 1; +} + +static int +t_add_head(void) +{ + int i; + + init_list_(); + for (i = MAX_NUM-1; i >= 0; i--) + { + tp_add_head(&l, &nodes[i]); + bt_debug("."); + bt_assert(l.first == &nodes[i]); + bt_assert(l.last == &nodes[MAX_NUM-1]); + if (i < MAX_NUM-1) + { + bt_assert(nodes[i+1].n.prev == &nodes[i]); + bt_assert(nodes[i].n.next == &nodes[i+1]); + } + } + show_list(); + bt_assert(is_filled_list_well_linked()); + + return 1; +} + +static void +insert_node_(TLIST_LIST(tp) *l, struct test_node *n, struct test_node *after) +{ + tp_add_after(l, n, after); + bt_debug("."); +} + +static int +t_insert_node(void) +{ + int i; + + init_list_(); + + // add first node + insert_node_(&l, &nodes[0], NULL); + + // add odd nodes + for (i = 2; i < MAX_NUM; i+=2) + insert_node_(&l, &nodes[i], &nodes[i-2]); + + // add even nodes + for (i = 1; i < MAX_NUM; i+=2) + insert_node_(&l, &nodes[i], &nodes[i-1]); + + bt_debug("\n"); + bt_assert(is_filled_list_well_linked()); + + return 1; +} + +static void +fill_list2(TLIST_LIST(tp) *l, struct test_node nodes[]) +{ + int i; + for (i = 0; i < MAX_NUM; i++) + tp_add_tail(l, &nodes[i]); +} + +static void +fill_list(void) +{ + fill_list2(&l, nodes); +} + +static int +t_remove_node(void) +{ + int i; + + init_list_(); + + /* Fill & Remove & Check */ + fill_list(); + for (i = 0; i < MAX_NUM; i++) + tp_rem_node(&l, &nodes[i]); + bt_assert(is_empty_list_well_unlinked()); + + /* Fill & Remove the half of nodes & Check & Remove the rest nodes & Check */ + fill_list(); + for (i = 0; i < MAX_NUM; i+=2) + tp_rem_node(&l, &nodes[i]); + + int tail_node_index = (MAX_NUM % 2) ? MAX_NUM - 2 : MAX_NUM - 1; + bt_assert(l.first == &nodes[1]); + bt_assert(l.last == &nodes[tail_node_index]); + bt_assert(!nodes[tail_node_index].n.next); + + for (i = 1; i < MAX_NUM; i+=2) + { + if (i > 1) + bt_assert(nodes[i].n.prev == &nodes[i-2]); + if (i < tail_node_index) + bt_assert(nodes[i].n.next == &nodes[i+2]); + } + + for (i = 1; i < MAX_NUM; i+=2) + tp_rem_node(&l, &nodes[i]); + bt_assert(is_empty_list_well_unlinked()); + + return 1; +} + +static int +t_update_node(void) +{ + struct test_node head, inside, tail; + + init_list_(); + fill_list(); + + head = nodes[0]; + tp_update_node(&l, &head); + bt_assert(l.first == &head); + bt_assert(head.n.prev == NULL); + bt_assert(head.n.next == &nodes[1]); + bt_assert(nodes[1].n.prev == &head); + + inside = nodes[MAX_NUM/2]; + tp_update_node(&l, &inside); + bt_assert(nodes[MAX_NUM/2-1].n.next == &inside); + bt_assert(nodes[MAX_NUM/2+1].n.prev == &inside); + bt_assert(inside.n.prev == &nodes[MAX_NUM/2-1]); + bt_assert(inside.n.next == &nodes[MAX_NUM/2+1]); + + tail = nodes[MAX_NUM-1]; + tp_update_node(&l, &tail); + bt_assert(l.last == &tail); + bt_assert(tail.n.prev == &nodes[MAX_NUM-2]); + bt_assert(tail.n.next == NULL); + bt_assert(nodes[MAX_NUM-2].n.next == &tail); + + return 1; +} + +#if 0 +static int +t_add_tail_list(void) +{ + node nodes2[MAX_NUM]; + list l2; + + init_list__(&l, (node *) nodes); + fill_list2(&l, (node *) nodes); + + init_list__(&l2, (node *) nodes2); + fill_list2(&l2, (node *) nodes2); + + add_tail_list(&l, &l2); + + bt_assert(nodes[MAX_NUM-1].next == &nodes2[0]); + bt_assert(nodes2[0].prev == &nodes[MAX_NUM-1]); + bt_assert(l.tail == &nodes2[MAX_NUM-1]); + + return 1; +} +#endif + +int +main(int argc, char *argv[]) +{ + bt_init(argc, argv); + + bt_test_suite(t_add_tail, "Adding nodes to tail of list"); + bt_test_suite(t_add_head, "Adding nodes to head of list"); + bt_test_suite(t_insert_node, "Inserting nodes to list"); + bt_test_suite(t_remove_node, "Removing nodes from list"); + bt_test_suite(t_update_node, "Updating nodes in list"); +#if 0 + bt_test_suite(t_add_tail_list, "At the tail of a list adding the another list"); +#endif + + return bt_exit_value(); +} |