]>
git.ipfire.org Git - thirdparty/bird.git/blob - lib/slist_test.c
2 * BIRD Library -- Safe Linked Lists Tests
4 * (c) 2015 CZ.NIC z.s.p.o.
6 * Can be freely distributed and used under the terms of the GNU GPL.
9 #include "test/birdtest.h"
11 #include "lib/slists.h"
15 static snode nodes
[MAX_NUM
];
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
);
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
);
34 is_filled_list_well_linked(void)
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
);
42 for (i
= 0; i
< MAX_NUM
; i
++)
45 bt_assert(nodes
[i
].next
== &nodes
[i
+1]);
48 bt_assert(nodes
[i
].prev
== &nodes
[i
-1]);
55 is_empty_list_well_unlinked(void)
57 bt_assert(lst
.head
== SNODE
&lst
.null
);
58 bt_assert(lst
.tail
== SNODE
&lst
.head
);
60 bt_assert(EMPTY_SLIST(lst
));
66 init_list__(slist
*l
, struct snode nodes
[])
71 for (i
= 0; i
< MAX_NUM
; i
++)
81 init_list__(&lst
, nodes
);
90 for (i
= 0; i
< MAX_NUM
; i
++)
92 s_add_tail(&lst
, &nodes
[i
]);
94 bt_assert(lst
.tail
== &nodes
[i
]);
95 bt_assert(lst
.head
== &nodes
[0]);
96 bt_assert((void *) nodes
[i
].next
== (void *) &lst
.null
);
99 bt_assert(nodes
[i
-1].next
== &nodes
[i
]);
100 bt_assert(nodes
[i
].prev
== &nodes
[i
-1]);
104 bt_assert(is_filled_list_well_linked());
115 for (i
= MAX_NUM
-1; i
>= 0; i
--)
117 s_add_head(&lst
, &nodes
[i
]);
119 bt_assert(lst
.head
== &nodes
[i
]);
120 bt_assert(lst
.tail
== &nodes
[MAX_NUM
-1]);
123 bt_assert(nodes
[i
+1].prev
== &nodes
[i
]);
124 bt_assert(nodes
[i
].next
== &nodes
[i
+1]);
128 bt_assert(is_filled_list_well_linked());
134 insert_node_(snode
*n
, snode
*after
)
136 s_insert_node(n
, after
);
148 insert_node_(&nodes
[0], SNODE
&lst
.head
);
151 for (i
= 2; i
< MAX_NUM
; i
+=2)
152 insert_node_(&nodes
[i
], &nodes
[i
-2]);
155 for (i
= 1; i
< MAX_NUM
; i
+=2)
156 insert_node_(&nodes
[i
], &nodes
[i
-1]);
159 bt_assert(is_filled_list_well_linked());
165 fill_list2(slist
*l
, snode nodes
[])
168 for (i
= 0; i
< MAX_NUM
; i
++)
169 s_add_tail(l
, &nodes
[i
]);
175 fill_list2(&lst
, SNODE nodes
);
186 /* Fill & Remove & Check */
188 for (i
= 0; i
< MAX_NUM
; i
++)
189 s_rem_node(&nodes
[i
]);
190 bt_assert(is_empty_list_well_unlinked());
192 /* Fill & Remove the half of nodes & Check & Remove the rest nodes & Check */
194 for (i
= 0; i
< MAX_NUM
; i
+=2)
195 s_rem_node(&nodes
[i
]);
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
);
202 for (i
= 1; i
< MAX_NUM
; i
+=2)
205 bt_assert(nodes
[i
].prev
== &nodes
[i
-2]);
206 if (i
< tail_node_index
)
207 bt_assert(nodes
[i
].next
== &nodes
[i
+2]);
210 for (i
= 1; i
< MAX_NUM
; i
+=2)
211 s_rem_node(&nodes
[i
]);
212 bt_assert(is_empty_list_well_unlinked());
218 t_add_tail_list(void)
220 snode nodes2
[MAX_NUM
];
223 init_list__(&lst
, SNODE
&nodes
);
224 fill_list2(&lst
, SNODE
&nodes
);
226 init_list__(&l2
, SNODE
&nodes2
);
227 fill_list2(&l2
, SNODE
&nodes2
);
229 s_add_tail_list(&lst
, &l2
);
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]);
239 dump(const char *str
, slist
*a
)
243 bt_debug("%s \n", str
);
244 for (x
= SHEAD(*a
); x
; x
= x
->next
)
249 for (i
= x
->readers
; i
; i
= i
->next
)
254 bt_debug(" [%p:%p]", i
, i
->node
);
262 t_iterator_walk(void)
276 WALK_SLIST(node
, lst
)
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
++)
287 bt_assert(nodes
[k
].readers
== NULL
);
305 x
= xmalloc(sizeof(*x
));
307 x
= xmalloc(sizeof(*x
));
309 x
= xmalloc(sizeof(*x
));
318 bt_debug("Got %p\n", x
);
334 s_rem_node(a
.head
->next
);
335 dump("6 (deletion)", &a
);
337 s_put(&i
, s_get(&i
)->next
);
338 dump("6 (relink)", &a
);
340 x
= xmalloc(sizeof(*x
));
342 dump("7 (second list)", &b
);
344 s_add_tail_list(&b
, &a
);
345 dump("8 (after merge)", &b
);
351 t_safe_del_walk(void)
358 snode
*node
, *node_next
;
359 WALK_SLIST_DELSAFE(node
,node_next
, lst
)
361 bt_debug("Will remove node %p \n", node
);
362 s_rem_node(SNODE node
);
364 bt_assert(is_empty_list_well_unlinked());
370 main(int argc
, char *argv
[])
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");
383 return bt_exit_value();