Annotation of embedaddon/bird2/lib/slist_test.c, revision 1.1.1.1
1.1 misho 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:
106: return 1;
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:
130: return 1;
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:
161: return 1;
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:
214: return 1;
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:
235: return 1;
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:
293: return 1;
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:
347: return 1;
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:
366: return 1;
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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to slist_test.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib