[thirdparty/bird.git] / lib / slist_test.c

/*
 *	BIRD Library -- Safe 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/slists.h"

#define MAX_NUM 1000

static snode nodes[MAX_NUM];
static slist lst;

static void
show_list(void)
{
  bt_debug("\n");
  bt_debug("list.null is at %p and point to %p \n", &lst.null, lst.null);
  bt_debug("list.head is at %p and point to %p \n", &lst.head, lst.head);
  bt_debug("list.tail is at %p and point to %p \n", &lst.tail, lst.tail);
  bt_debug("list.tail_readers is at %p and point to %p \n", &lst.tail_readers, lst.tail_readers);

  int i;
  for (i = 0; i < MAX_NUM; i++)
    bt_debug("n[%3i] is at %p, .prev (%p) points to %p, .next (%p) points to %p, .readers (%p) points to %p \n",
	     i, &nodes[i], &(nodes[i].prev), nodes[i].prev, &(nodes[i].next), nodes[i].next, &(nodes[i].readers), nodes[i].readers);
}

static int
is_filled_list_well_linked(void)
{
  int i;
  bt_assert(lst.head == &nodes[0]);
  bt_assert(lst.tail == &nodes[MAX_NUM-1]);
  bt_assert((void *) nodes[0].prev == (void *) &lst.head);
  bt_assert((void *) nodes[MAX_NUM-1].next == (void *) &lst.null);

  for (i = 0; i < MAX_NUM; i++)
  {
    if (i < (MAX_NUM-1))
      bt_assert(nodes[i].next == &nodes[i+1]);

    if (i > 0)
      bt_assert(nodes[i].prev == &nodes[i-1]);
  }

  return 1;
}

static int
is_empty_list_well_unlinked(void)
{
  bt_assert(lst.head == SNODE &lst.null);
  bt_assert(lst.tail == SNODE &lst.head);

  bt_assert(EMPTY_SLIST(lst));

  return 1;
}

static void
init_list__(slist *l, struct snode nodes[])
{
  s_init_list(l);

  int i;
  for (i = 0; i < MAX_NUM; i++)
  {
    nodes[i].next = NULL;
    nodes[i].prev = NULL;
  }
}

static void
init_list_(void)
{
  init_list__(&lst, nodes);
}

static int
t_add_tail(void)
{
  int i;

  init_list_();
  for (i = 0; i < MAX_NUM; i++)
  {
    s_add_tail(&lst, &nodes[i]);
    bt_debug(".");
    bt_assert(lst.tail == &nodes[i]);
    bt_assert(lst.head == &nodes[0]);
    bt_assert((void *) nodes[i].next == (void *) &lst.null);
    if (i > 0)
    {
      bt_assert(nodes[i-1].next == &nodes[i]);
      bt_assert(nodes[i].prev == &nodes[i-1]);
    }
  }

  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--)
  {
    s_add_head(&lst, &nodes[i]);
    bt_debug(".");
    bt_assert(lst.head == &nodes[i]);
    bt_assert(lst.tail == &nodes[MAX_NUM-1]);
    if (i < MAX_NUM-1)
    {
      bt_assert(nodes[i+1].prev == &nodes[i]);
      bt_assert(nodes[i].next == &nodes[i+1]);
    }
  }

  bt_assert(is_filled_list_well_linked());

  return 1;
}

static void
insert_node_(snode *n, snode *after)
{
  s_insert_node(n, after);
  bt_debug(".");
}

static int
t_insert_node(void)
{
  int i;

  init_list_();

  // add first node
  insert_node_(&nodes[0], SNODE &lst.head);

  // add odd nodes
  for (i = 2; i < MAX_NUM; i+=2)
    insert_node_(&nodes[i], &nodes[i-2]);

  // add even nodes
  for (i = 1; i < MAX_NUM; i+=2)
    insert_node_(&nodes[i], &nodes[i-1]);

  bt_debug("\n");
  bt_assert(is_filled_list_well_linked());

  return 1;
}

static void
fill_list2(slist *l, snode nodes[])
{
  int i;
  for (i = 0; i < MAX_NUM; i++)
    s_add_tail(l, &nodes[i]);
}

static void
fill_list(void)
{
  fill_list2(&lst, SNODE nodes);
}


static int
t_remove_node(void)
{
  int i;

  init_list_();

  /* Fill & Remove & Check */
  fill_list();
  for (i = 0; i < MAX_NUM; i++)
    s_rem_node(&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)
    s_rem_node(&nodes[i]);

  int tail_node_index = (MAX_NUM % 2) ? MAX_NUM - 2 : MAX_NUM - 1;
  bt_assert(lst.head == &nodes[1]);
  bt_assert(lst.tail == &nodes[tail_node_index]);
  bt_assert(nodes[tail_node_index].next == SNODE &lst.null);

  for (i = 1; i < MAX_NUM; i+=2)
  {
    if (i > 1)
      bt_assert(nodes[i].prev == &nodes[i-2]);
    if (i < tail_node_index)
      bt_assert(nodes[i].next == &nodes[i+2]);
  }

  for (i = 1; i < MAX_NUM; i+=2)
    s_rem_node(&nodes[i]);
  bt_assert(is_empty_list_well_unlinked());

  return 1;
}

static int
t_add_tail_list(void)
{
  snode nodes2[MAX_NUM];
  slist l2;

  init_list__(&lst, SNODE &nodes);
  fill_list2(&lst, SNODE &nodes);

  init_list__(&l2, SNODE &nodes2);
  fill_list2(&l2, SNODE &nodes2);

  s_add_tail_list(&lst, &l2);

  bt_assert(nodes[MAX_NUM-1].next == &nodes2[0]);
  bt_assert(nodes2[0].prev == &nodes[MAX_NUM-1]);
  bt_assert(lst.tail == &nodes2[MAX_NUM-1]);

  return 1;
}

void
dump(const char *str, slist *a)
{
  snode *x;

  bt_debug("%s \n", str);
  for (x = SHEAD(*a); x; x = x->next)
  {
    siterator *i, *j;
    bt_debug("%p", x);
    j = (siterator *) x;
    for (i = x->readers; i; i = i->next)
    {
      if (i->prev != j)
	bt_debug(" ???");
      j = i;
      bt_debug(" [%p:%p]", i, i->node);
    }
    bt_debug("\n");
  }
  bt_debug("---\n");
}

static int
t_iterator_walk(void)
{
  snode *node;
  siterator iter;

  init_list_();
  fill_list();

  int k;
  int i = 0;

  show_list();

  s_init(&iter, &lst);
  WALK_SLIST(node, lst)
  {
    s_get(&iter);
    s_put(&iter, node);
    bt_debug("node->readers: %p, iter: %p, nodes[%d].readers: %p, node: %p, nodes[i]: %p, node->next: %p \n",
	     node->readers, &iter, i, nodes[i].readers, node, &(nodes[i]), node->next);
    bt_assert(node->readers == &iter);
    bt_assert(node->readers == nodes[i].readers);
    bt_assert(node == &(nodes[i]));
    for (k = 0; k < MAX_NUM; k++)
      if (k != i)
	bt_assert(nodes[k].readers == NULL);

    dump("",&lst);
    i++;
  }

  return 1;
}

static int
t_original(void)
{
  slist a, b;
  snode *x, *y;
  siterator i, j;

  s_init_list(&a);
  s_init_list(&b);
  x = xmalloc(sizeof(*x));
  s_add_tail(&a, x);
  x = xmalloc(sizeof(*x));
  s_add_tail(&a, x);
  x = xmalloc(sizeof(*x));
  s_add_tail(&a, x);
  dump("1", &a);

  s_init(&i, &a);
  s_init(&j, &a);
  dump("2", &a);

  x = s_get(&i);
  bt_debug("Got %p\n", x);
  dump("3", &a);

  s_put(&i, x->next);
  dump("4", &a);

  y = s_get(&j);
  while (y)
  {
    s_put(&j, y);
    dump("5*", &a);
    y = s_get(&j)->next;
  }

  dump("5 done", &a);

  s_rem_node(a.head->next);
  dump("6 (deletion)", &a);

  s_put(&i, s_get(&i)->next);
  dump("6 (relink)", &a);

  x = xmalloc(sizeof(*x));
  s_add_tail(&b, x);
  dump("7 (second list)", &b);

  s_add_tail_list(&b, &a);
  dump("8 (after merge)", &b);

  return 1;
}

static int
t_safe_del_walk(void)
{
  init_list_();
  fill_list();

  show_list();

  snode *node, *node_next;
  WALK_SLIST_DELSAFE(node,node_next, lst)
  {
    bt_debug("Will remove node %p \n", node);
    s_rem_node(SNODE node);
  }
  bt_assert(is_empty_list_well_unlinked());

  return 1;
}

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_add_tail_list,	"At the tail of a list adding the another list");
  bt_test_suite(t_iterator_walk,	"Iterator walk");
  bt_test_suite(t_safe_del_walk,	"WALK_SLIST_DELSAFE and s_rem_node all nodes");
  bt_test_suite(t_original, 		"The original BIRD test suit for SLIST");

  return bt_exit_value();
}
Commit	Line	Data
9b0a0ba9 OZ	1	/*
	2	* BIRD Library -- Safe Linked Lists Tests
	3	*
	4	* (c) 2015 CZ.NIC z.s.p.o.
	5	*
	6	* Can be freely distributed and used under the terms of the GNU GPL.
	7	*/
	8
	9	#include "test/birdtest.h"
	10
	11	#include "lib/slists.h"
	12
	13	#define MAX_NUM 1000
	14
	15	static snode nodes[MAX_NUM];
	16	static slist lst;
	17
	18	static void
	19	show_list(void)
	20	{
	21	bt_debug("\n");
	22	bt_debug("list.null is at %p and point to %p \n", &lst.null, lst.null);
	23	bt_debug("list.head is at %p and point to %p \n", &lst.head, lst.head);
	24	bt_debug("list.tail is at %p and point to %p \n", &lst.tail, lst.tail);
	25	bt_debug("list.tail_readers is at %p and point to %p \n", &lst.tail_readers, lst.tail_readers);
	26
	27	int i;
	28	for (i = 0; i < MAX_NUM; i++)
	29	bt_debug("n[%3i] is at %p, .prev (%p) points to %p, .next (%p) points to %p, .readers (%p) points to %p \n",
	30	i, &nodes[i], &(nodes[i].prev), nodes[i].prev, &(nodes[i].next), nodes[i].next, &(nodes[i].readers), nodes[i].readers);
	31	}
	32
	33	static int
	34	is_filled_list_well_linked(void)
	35	{
	36	int i;
	37	bt_assert(lst.head == &nodes[0]);
	38	bt_assert(lst.tail == &nodes[MAX_NUM-1]);
	39	bt_assert((void ) nodes[0].prev == (void ) &lst.head);
	40	bt_assert((void ) nodes[MAX_NUM-1].next == (void ) &lst.null);
	41
	42	for (i = 0; i < MAX_NUM; i++)
	43	{
	44	if (i < (MAX_NUM-1))
	45	bt_assert(nodes[i].next == &nodes[i+1]);
	46
	47	if (i > 0)
	48	bt_assert(nodes[i].prev == &nodes[i-1]);
	49	}
	50
	51	return 1;
	52	}
	53
	54	static int
	55	is_empty_list_well_unlinked(void)
	56	{
	57	bt_assert(lst.head == SNODE &lst.null);
	58	bt_assert(lst.tail == SNODE &lst.head);
	59
	60	bt_assert(EMPTY_SLIST(lst));
	61
	62	return 1;
	63	}
	64
65	static void
66	init_list__(slist *l, struct snode nodes[])
67	{
68	s_init_list(l);
69
70	int i;
71	for (i = 0; i < MAX_NUM; i++)
72	{
73	nodes[i].next = NULL;
74	nodes[i].prev = NULL;
75	}
76	}
77
78	static void
79	init_list_(void)
80	{
81	init_list__(&lst, nodes);
82	}
83
84	static int
85	t_add_tail(void)
86	{
87	int i;
88
89	init_list_();
90	for (i = 0; i < MAX_NUM; i++)
91	{
92	s_add_tail(&lst, &nodes[i]);
93	bt_debug(".");
94	bt_assert(lst.tail == &nodes[i]);
95	bt_assert(lst.head == &nodes[0]);
96	bt_assert((void ) nodes[i].next == (void ) &lst.null);
97	if (i > 0)
98	{
99	bt_assert(nodes[i-1].next == &nodes[i]);
100	bt_assert(nodes[i].prev == &nodes[i-1]);
101	}
102	}
103
104	bt_assert(is_filled_list_well_linked());
105
5e3cd0e5	106	return 1;
9b0a0ba9 OZ	107	}
	108
	109	static int
	110	t_add_head(void)
	111	{
	112	int i;
	113
	114	init_list_();
	115	for (i = MAX_NUM-1; i >= 0; i--)
	116	{
	117	s_add_head(&lst, &nodes[i]);
	118	bt_debug(".");
	119	bt_assert(lst.head == &nodes[i]);
	120	bt_assert(lst.tail == &nodes[MAX_NUM-1]);
	121	if (i < MAX_NUM-1)
	122	{
	123	bt_assert(nodes[i+1].prev == &nodes[i]);
	124	bt_assert(nodes[i].next == &nodes[i+1]);
	125	}
	126	}
	127
	128	bt_assert(is_filled_list_well_linked());
	129
5e3cd0e5	130	return 1;
9b0a0ba9 OZ	131	}
	132
	133	static void
	134	insert_node_(snode n, snode after)
	135	{
	136	s_insert_node(n, after);
	137	bt_debug(".");
	138	}
	139
	140	static int
	141	t_insert_node(void)
	142	{
	143	int i;
	144
	145	init_list_();
	146
	147	// add first node
	148	insert_node_(&nodes[0], SNODE &lst.head);
	149
	150	// add odd nodes
	151	for (i = 2; i < MAX_NUM; i+=2)
	152	insert_node_(&nodes[i], &nodes[i-2]);
	153
	154	// add even nodes
	155	for (i = 1; i < MAX_NUM; i+=2)
	156	insert_node_(&nodes[i], &nodes[i-1]);
	157
	158	bt_debug("\n");
	159	bt_assert(is_filled_list_well_linked());
	160
5e3cd0e5	161	return 1;
9b0a0ba9 OZ	162	}
	163
	164	static void
	165	fill_list2(slist *l, snode nodes[])
	166	{
	167	int i;
	168	for (i = 0; i < MAX_NUM; i++)
	169	s_add_tail(l, &nodes[i]);
	170	}
	171
	172	static void
	173	fill_list(void)
	174	{
	175	fill_list2(&lst, SNODE nodes);
	176	}
	177
	178
	179	static int
	180	t_remove_node(void)
	181	{
	182	int i;
	183
	184	init_list_();
	185
	186	/* Fill & Remove & Check */
	187	fill_list();
	188	for (i = 0; i < MAX_NUM; i++)
	189	s_rem_node(&nodes[i]);
	190	bt_assert(is_empty_list_well_unlinked());
	191
	192	/* Fill & Remove the half of nodes & Check & Remove the rest nodes & Check */
	193	fill_list();
	194	for (i = 0; i < MAX_NUM; i+=2)
	195	s_rem_node(&nodes[i]);
	196
	197	int tail_node_index = (MAX_NUM % 2) ? MAX_NUM - 2 : MAX_NUM - 1;
	198	bt_assert(lst.head == &nodes[1]);
	199	bt_assert(lst.tail == &nodes[tail_node_index]);
	200	bt_assert(nodes[tail_node_index].next == SNODE &lst.null);
	201
	202	for (i = 1; i < MAX_NUM; i+=2)
	203	{
	204	if (i > 1)
	205	bt_assert(nodes[i].prev == &nodes[i-2]);
	206	if (i < tail_node_index)
	207	bt_assert(nodes[i].next == &nodes[i+2]);
	208	}
	209
	210	for (i = 1; i < MAX_NUM; i+=2)
	211	s_rem_node(&nodes[i]);
	212	bt_assert(is_empty_list_well_unlinked());
	213
5e3cd0e5	214	return 1;
9b0a0ba9 OZ	215	}
	216
	217	static int
	218	t_add_tail_list(void)
	219	{
	220	snode nodes2[MAX_NUM];
	221	slist l2;
	222
	223	init_list__(&lst, SNODE &nodes);
	224	fill_list2(&lst, SNODE &nodes);
	225
	226	init_list__(&l2, SNODE &nodes2);
	227	fill_list2(&l2, SNODE &nodes2);
	228
	229	s_add_tail_list(&lst, &l2);
	230
	231	bt_assert(nodes[MAX_NUM-1].next == &nodes2[0]);
	232	bt_assert(nodes2[0].prev == &nodes[MAX_NUM-1]);
	233	bt_assert(lst.tail == &nodes2[MAX_NUM-1]);
	234
5e3cd0e5	235	return 1;
9b0a0ba9 OZ	236	}
	237
	238	void
	239	dump(const char str, slist a)
	240	{
	241	snode *x;
	242
	243	bt_debug("%s \n", str);
	244	for (x = SHEAD(*a); x; x = x->next)
	245	{
	246	siterator i, j;
	247	bt_debug("%p", x);
	248	j = (siterator *) x;
	249	for (i = x->readers; i; i = i->next)
	250	{
	251	if (i->prev != j)
	252	bt_debug(" ???");
	253	j = i;
	254	bt_debug(" [%p:%p]", i, i->node);
	255	}
	256	bt_debug("\n");
	257	}
	258	bt_debug("---\n");
	259	}
	260
	261	static int
	262	t_iterator_walk(void)
	263	{
	264	snode *node;
	265	siterator iter;
	266
	267	init_list_();
	268	fill_list();
	269
	270	int k;
	271	int i = 0;
	272
	273	show_list();
	274
	275	s_init(&iter, &lst);
	276	WALK_SLIST(node, lst)
	277	{
	278	s_get(&iter);
	279	s_put(&iter, node);
	280	bt_debug("node->readers: %p, iter: %p, nodes[%d].readers: %p, node: %p, nodes[i]: %p, node->next: %p \n",
	281	node->readers, &iter, i, nodes[i].readers, node, &(nodes[i]), node->next);
	282	bt_assert(node->readers == &iter);
	283	bt_assert(node->readers == nodes[i].readers);
	284	bt_assert(node == &(nodes[i]));
	285	for (k = 0; k < MAX_NUM; k++)
	286	if (k != i)
	287	bt_assert(nodes[k].readers == NULL);
	288
	289	dump("",&lst);
	290	i++;
	291	}
	292
5e3cd0e5	293	return 1;
9b0a0ba9 OZ	294	}
	295
	296	static int
	297	t_original(void)
	298	{
	299	slist a, b;
	300	snode x, y;
	301	siterator i, j;
	302
	303	s_init_list(&a);
	304	s_init_list(&b);
	305	x = xmalloc(sizeof(*x));
	306	s_add_tail(&a, x);
	307	x = xmalloc(sizeof(*x));
	308	s_add_tail(&a, x);
	309	x = xmalloc(sizeof(*x));
	310	s_add_tail(&a, x);
	311	dump("1", &a);
	312
	313	s_init(&i, &a);
	314	s_init(&j, &a);
	315	dump("2", &a);
	316
	317	x = s_get(&i);
	318	bt_debug("Got %p\n", x);
	319	dump("3", &a);
	320
	321	s_put(&i, x->next);
	322	dump("4", &a);
	323
	324	y = s_get(&j);
	325	while (y)
	326	{
	327	s_put(&j, y);
	328	dump("5*", &a);
	329	y = s_get(&j)->next;
	330	}
	331
	332	dump("5 done", &a);
	333
	334	s_rem_node(a.head->next);
	335	dump("6 (deletion)", &a);
	336
	337	s_put(&i, s_get(&i)->next);
	338	dump("6 (relink)", &a);
	339
	340	x = xmalloc(sizeof(*x));
	341	s_add_tail(&b, x);
	342	dump("7 (second list)", &b);
	343
	344	s_add_tail_list(&b, &a);
	345	dump("8 (after merge)", &b);
	346
5e3cd0e5	347	return 1;
9b0a0ba9 OZ	348	}
	349
	350	static int
	351	t_safe_del_walk(void)
	352	{
	353	init_list_();
	354	fill_list();
	355
	356	show_list();
	357
	358	snode node, node_next;
	359	WALK_SLIST_DELSAFE(node,node_next, lst)
	360	{
	361	bt_debug("Will remove node %p \n", node);
	362	s_rem_node(SNODE node);
	363	}
	364	bt_assert(is_empty_list_well_unlinked());
	365
5e3cd0e5	366	return 1;
9b0a0ba9 OZ	367	}
	368
	369	int
	370	main(int argc, char *argv[])
	371	{
	372	bt_init(argc, argv);
	373
	374	bt_test_suite(t_add_tail, "Adding nodes to tail of list");
	375	bt_test_suite(t_add_head, "Adding nodes to head of list");
	376	bt_test_suite(t_insert_node, "Inserting nodes to list");
	377	bt_test_suite(t_remove_node, "Removing nodes from list");
	378	bt_test_suite(t_add_tail_list, "At the tail of a list adding the another list");
	379	bt_test_suite(t_iterator_walk, "Iterator walk");
	380	bt_test_suite(t_safe_del_walk, "WALK_SLIST_DELSAFE and s_rem_node all nodes");
	381	bt_test_suite(t_original, "The original BIRD test suit for SLIST");
	382
	383	return bt_exit_value();
	384	}