Annotation of embedaddon/bird2/lib/lists_test.c, revision 1.1.1.1
1.1 misho 1: /*
2: * BIRD Library -- 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: #include "lib/lists.h"
11:
12: #define MAX_NUM 1000
13:
14: static node nodes[MAX_NUM];
15: static list l;
16:
17: static void
18: show_list(void)
19: {
20: bt_debug("\n");
21: bt_debug("list.null is at %p and point to %p\n", &l.null, l.null);
22: bt_debug("list.head is at %p and point to %p\n", &l.head, l.head);
23: bt_debug("list.tail is at %p and point to %p\n", &l.tail, l.tail);
24:
25: int i;
26: for (i = 0; i < MAX_NUM; i++)
27: {
28: bt_debug("n[%3i] is at %p\n", i, &nodes[i]);
29: bt_debug(" prev is at %p and point to %p\n", &(nodes[i].prev), nodes[i].prev);
30: bt_debug(" next is at %p and point to %p\n", &(nodes[i].next), nodes[i].next);
31: }
32: }
33:
34: static int
35: is_filled_list_well_linked(void)
36: {
37: int i;
38: bt_assert(l.head == &nodes[0]);
39: bt_assert(l.tail == &nodes[MAX_NUM-1]);
40: bt_assert((void *) nodes[0].prev == (void *) &l.head);
41: bt_assert((void *) nodes[MAX_NUM-1].next == (void *) &l.null);
42:
43: for (i = 0; i < MAX_NUM; i++)
44: {
45: if (i < (MAX_NUM-1))
46: bt_assert(nodes[i].next == &nodes[i+1]);
47:
48: if (i > 0)
49: bt_assert(nodes[i].prev == &nodes[i-1]);
50: }
51:
52: return 1;
53: }
54:
55: static int
56: is_empty_list_well_unlinked(void)
57: {
58: int i;
59:
60: bt_assert(l.head == NODE &l.null);
61: bt_assert(l.tail == NODE &l.head);
62: bt_assert(EMPTY_LIST(l));
63:
64: for (i = 0; i < MAX_NUM; i++)
65: {
66: bt_assert(nodes[i].next == NULL);
67: bt_assert(nodes[i].prev == NULL);
68: }
69:
70: return 1;
71: }
72:
73: static void
74: init_list__(list *l, struct node nodes[])
75: {
76: init_list(l);
77:
78: int i;
79: for (i = 0; i < MAX_NUM; i++)
80: {
81: nodes[i].next = NULL;
82: nodes[i].prev = NULL;
83: }
84: }
85:
86: static void
87: init_list_(void)
88: {
89: init_list__(&l, (node *) nodes);
90: }
91:
92: static int
93: t_add_tail(void)
94: {
95: int i;
96:
97: init_list_();
98: for (i = 0; i < MAX_NUM; i++)
99: {
100: add_tail(&l, &nodes[i]);
101: bt_debug(".");
102: bt_assert(l.tail == &nodes[i]);
103: bt_assert(l.head == &nodes[0]);
104: bt_assert((void *) nodes[i].next == (void *) &l.null);
105: if (i > 0)
106: {
107: bt_assert(nodes[i-1].next == &nodes[i]);
108: bt_assert(nodes[i].prev == &nodes[i-1]);
109: }
110: }
111: show_list();
112: bt_assert(is_filled_list_well_linked());
113:
114: return 1;
115: }
116:
117: static int
118: t_add_head(void)
119: {
120: int i;
121:
122: init_list_();
123: for (i = MAX_NUM-1; i >= 0; i--)
124: {
125: add_head(&l, &nodes[i]);
126: bt_debug(".");
127: bt_assert(l.head == &nodes[i]);
128: bt_assert(l.tail == &nodes[MAX_NUM-1]);
129: if (i < MAX_NUM-1)
130: {
131: bt_assert(nodes[i+1].prev == &nodes[i]);
132: bt_assert(nodes[i].next == &nodes[i+1]);
133: }
134: }
135: show_list();
136: bt_assert(is_filled_list_well_linked());
137:
138: return 1;
139: }
140:
141: static void
142: insert_node_(node *n, node *after)
143: {
144: insert_node(n, after);
145: bt_debug(".");
146: }
147:
148: static int
149: t_insert_node(void)
150: {
151: int i;
152:
153: init_list_();
154:
155: // add first node
156: insert_node_(&nodes[0], NODE &l.head);
157:
158: // add odd nodes
159: for (i = 2; i < MAX_NUM; i+=2)
160: insert_node_(&nodes[i], &nodes[i-2]);
161:
162: // add even nodes
163: for (i = 1; i < MAX_NUM; i+=2)
164: insert_node_(&nodes[i], &nodes[i-1]);
165:
166: bt_debug("\n");
167: bt_assert(is_filled_list_well_linked());
168:
169: return 1;
170: }
171:
172: static void
173: fill_list2(list *l, node nodes[])
174: {
175: int i;
176: for (i = 0; i < MAX_NUM; i++)
177: add_tail(l, &nodes[i]);
178: }
179:
180: static void
181: fill_list(void)
182: {
183: fill_list2(&l, (node *) nodes);
184: }
185:
186: static int
187: t_remove_node(void)
188: {
189: int i;
190:
191: init_list_();
192:
193: /* Fill & Remove & Check */
194: fill_list();
195: for (i = 0; i < MAX_NUM; i++)
196: rem_node(&nodes[i]);
197: bt_assert(is_empty_list_well_unlinked());
198:
199: /* Fill & Remove the half of nodes & Check & Remove the rest nodes & Check */
200: fill_list();
201: for (i = 0; i < MAX_NUM; i+=2)
202: rem_node(&nodes[i]);
203:
204: int tail_node_index = (MAX_NUM % 2) ? MAX_NUM - 2 : MAX_NUM - 1;
205: bt_assert(l.head == &nodes[1]);
206: bt_assert(l.tail == &nodes[tail_node_index]);
207: bt_assert(nodes[tail_node_index].next == NODE &l.null);
208:
209: for (i = 1; i < MAX_NUM; i+=2)
210: {
211: if (i > 1)
212: bt_assert(nodes[i].prev == &nodes[i-2]);
213: if (i < tail_node_index)
214: bt_assert(nodes[i].next == &nodes[i+2]);
215: }
216:
217: for (i = 1; i < MAX_NUM; i+=2)
218: rem_node(&nodes[i]);
219: bt_assert(is_empty_list_well_unlinked());
220:
221: return 1;
222: }
223:
224: static int
225: t_replace_node(void)
226: {
227: node head, inside, tail;
228:
229: init_list_();
230: fill_list();
231:
232: replace_node(&nodes[0], &head);
233: bt_assert(l.head == &head);
234: bt_assert(head.prev == NODE &l.head);
235: bt_assert(head.next == &nodes[1]);
236: bt_assert(nodes[1].prev == &head);
237:
238: replace_node(&nodes[MAX_NUM/2], &inside);
239: bt_assert(nodes[MAX_NUM/2-1].next == &inside);
240: bt_assert(nodes[MAX_NUM/2+1].prev == &inside);
241: bt_assert(inside.prev == &nodes[MAX_NUM/2-1]);
242: bt_assert(inside.next == &nodes[MAX_NUM/2+1]);
243:
244: replace_node(&nodes[MAX_NUM-1], &tail);
245: bt_assert(l.tail == &tail);
246: bt_assert(tail.prev == &nodes[MAX_NUM-2]);
247: bt_assert(tail.next == NODE &l.null);
248: bt_assert(nodes[MAX_NUM-2].next == &tail);
249:
250: return 1;
251: }
252:
253: static int
254: t_add_tail_list(void)
255: {
256: node nodes2[MAX_NUM];
257: list l2;
258:
259: init_list__(&l, (node *) nodes);
260: fill_list2(&l, (node *) nodes);
261:
262: init_list__(&l2, (node *) nodes2);
263: fill_list2(&l2, (node *) nodes2);
264:
265: add_tail_list(&l, &l2);
266:
267: bt_assert(nodes[MAX_NUM-1].next == &nodes2[0]);
268: bt_assert(nodes2[0].prev == &nodes[MAX_NUM-1]);
269: bt_assert(l.tail == &nodes2[MAX_NUM-1]);
270:
271: return 1;
272: }
273:
274: int
275: main(int argc, char *argv[])
276: {
277: bt_init(argc, argv);
278:
279: bt_test_suite(t_add_tail, "Adding nodes to tail of list");
280: bt_test_suite(t_add_head, "Adding nodes to head of list");
281: bt_test_suite(t_insert_node, "Inserting nodes to list");
282: bt_test_suite(t_remove_node, "Removing nodes from list");
283: bt_test_suite(t_replace_node, "Replacing nodes in list");
284: bt_test_suite(t_add_tail_list, "At the tail of a list adding the another list");
285:
286: return bt_exit_value();
287: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to lists_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