Mercurial > hg > ucx / file comparison

comparison: test/test_list.c

test/test_list.c

changeset 486
d7ca126eab7f
parent 482
0d998f19d130
child 487
4bd19279778c
equal deleted inserted replaced
485:6a86ad3d8c03 486:d7ca126eab7f
28 28
29 #include "cx/linked_list.h" 29 #include "cx/linked_list.h"
30 #include "test_config.h" 30 #include "test_config.h"
31 #include "util_allocator.h" 31 #include "util_allocator.h"
32 32
33 int cmp_int(int const *l, int const *r) { 33 int cmp_int(
34 int const *l,
35 int const *r
36 ) {
34 int left = *l, right = *r; 37 int left = *l, right = *r;
35 return left == right ? 0 : (left < right ? -1 : 1); 38 return left == right ? 0 : (left < right ? -1 : 1);
36 } 39 }
37 40
41 struct node {
42 struct node *next;
43 struct node *prev;
44 int data;
45 };
46
47 #define nd(name) name = {0}
48
49 const ptrdiff_t loc_prev = offsetof(struct node, prev);
50 const ptrdiff_t loc_next = offsetof(struct node, next);
51 const ptrdiff_t loc_data = offsetof(struct node, data);
52
53 struct node *create_test_data(
54 size_t n,
55 const int data[]
56 ) {
57 if (n == 0) return NULL;
58 struct node *begin = calloc(1, sizeof(struct node));
59 struct node *prev = begin;
60 if (data) begin->data = data[0];
61 for (size_t i = 1; i < n; i++) {
62 struct node *node = calloc(1, sizeof(struct node));
63 if (data) node->data = data[i];
64 cx_linked_list_link(prev, node, loc_prev, loc_next);
65 prev = node;
66 }
67 return begin;
68 }
69
70 void destroy_test_data(struct node *begin) {
71 struct node *node = begin;
72 while (node) {
73 struct node *next = node->next;
74 free(node);
75 node = next;
76 }
77 }
78
38 void test_linked_list_link_unlink(void) { 79 void test_linked_list_link_unlink(void) {
39 struct node { 80
40 void *next; 81 struct node nd(a), nd(b), nd(c);
41 void *prev;
42 };
43 const ptrdiff_t loc_prev = offsetof(struct node, prev);
44 const ptrdiff_t loc_next = offsetof(struct node, next);
45
46 struct node a = {NULL, NULL}, b = {NULL, NULL};
47 82
48 cx_linked_list_link(&a, &b, loc_prev, loc_next); 83 cx_linked_list_link(&a, &b, loc_prev, loc_next);
49 CU_ASSERT_PTR_NULL(a.prev) 84 CU_ASSERT_PTR_NULL(a.prev)
50 CU_ASSERT_PTR_EQUAL(a.next, &b) 85 CU_ASSERT_PTR_EQUAL(a.next, &b)
51 CU_ASSERT_PTR_EQUAL(b.prev, &a) 86 CU_ASSERT_PTR_EQUAL(b.prev, &a)
55 CU_ASSERT_PTR_NULL(a.prev) 90 CU_ASSERT_PTR_NULL(a.prev)
56 CU_ASSERT_PTR_NULL(a.next) 91 CU_ASSERT_PTR_NULL(a.next)
57 CU_ASSERT_PTR_NULL(b.prev) 92 CU_ASSERT_PTR_NULL(b.prev)
58 CU_ASSERT_PTR_NULL(b.next) 93 CU_ASSERT_PTR_NULL(b.next)
59 94
60 struct node c = {NULL, NULL};
61 cx_linked_list_link(&b, &c, loc_prev, loc_next); 95 cx_linked_list_link(&b, &c, loc_prev, loc_next);
62 cx_linked_list_link(&a, &b, loc_prev, loc_next); 96 cx_linked_list_link(&a, &b, loc_prev, loc_next);
63 cx_linked_list_unlink(&b, &c, loc_prev, loc_next); 97 cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
64 CU_ASSERT_PTR_NULL(a.prev) 98 CU_ASSERT_PTR_NULL(a.prev)
65 CU_ASSERT_PTR_EQUAL(a.next, &b) 99 CU_ASSERT_PTR_EQUAL(a.next, &b)
68 CU_ASSERT_PTR_NULL(c.prev) 102 CU_ASSERT_PTR_NULL(c.prev)
69 CU_ASSERT_PTR_NULL(c.next) 103 CU_ASSERT_PTR_NULL(c.next)
70 } 104 }
71 105
72 void test_linked_list_at(void) { 106 void test_linked_list_at(void) {
73 struct node { 107 struct node nd(a), nd(b), nd(c), nd(d);
74 void *next; 108 cx_linked_list_link(&a, &b, loc_prev, loc_next);
75 void *prev; 109 cx_linked_list_link(&b, &c, loc_prev, loc_next);
76 }; 110 cx_linked_list_link(&c, &d, loc_prev, loc_next);
77 const ptrdiff_t loc_prev = offsetof(struct node, prev);
78 const ptrdiff_t loc_next = offsetof(struct node, next);
79
80 struct node a, b, c, d;
81 a.prev = NULL;
82 a.next = &b;
83 b.prev = &a;
84 b.next = &c;
85 c.prev = &b;
86 c.next = &d;
87 d.prev = &c;
88 d.next = NULL;
89 111
90 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a) 112 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a)
91 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b) 113 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b)
92 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c) 114 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c)
93 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d) 115 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d)
101 123
102 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a) 124 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a)
103 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b) 125 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b)
104 } 126 }
105 127
128 void test_linked_list_compare(void) {
129 int a[] = {2, 4, 6, 8};
130 int b[] = {2, 4, 6};
131 int c[] = {2, 4, 6, 9};
132
133 void *la = create_test_data(4, a);
134 void *lb = create_test_data(3, b);
135 void *lc = create_test_data(4, c);
136
137 CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data,
138 0, (CxListComparator) cmp_int)
139 )
140 CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data,
141 0, (CxListComparator) cmp_int)
142 )
143 CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data,
144 0, (CxListComparator) cmp_int)
145 )
146 CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data,
147 0, (CxListComparator) cmp_int)
148 )
149 CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data,
150 0, (CxListComparator) cmp_int)
151 )
152
153 destroy_test_data(la);
154 destroy_test_data(lb);
155 destroy_test_data(lc);
156 }
157
106 void test_linked_list_add(void) { 158 void test_linked_list_add(void) {
107 struct node {
108 void *prev;
109 void *next;
110 };
111
112 struct node nodes[4]; 159 struct node nodes[4];
160 void *begin, *end;
113 161
114 // test with begin, end / prev, next 162 // test with begin, end / prev, next
115 memset(nodes, 0, 4 * sizeof(struct node)); 163 memset(nodes, 0, 4 * sizeof(struct node));
116 void *begin = NULL; 164 begin = end = NULL;
117 void *end = NULL;
118
119 ptrdiff_t loc_prev = offsetof(struct node, prev);
120 ptrdiff_t loc_next = offsetof(struct node, next);
121 165
122 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); 166 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
123 CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) 167 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
124 CU_ASSERT_PTR_EQUAL(end, &nodes[0]) 168 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
125 CU_ASSERT_PTR_NULL(nodes[0].prev) 169 CU_ASSERT_PTR_NULL(nodes[0].prev)
131 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) 175 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
132 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0]) 176 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
133 177
134 // test with begin only / prev, next 178 // test with begin only / prev, next
135 memset(nodes, 0, 4 * sizeof(struct node)); 179 memset(nodes, 0, 4 * sizeof(struct node));
136 begin = NULL; 180 begin = end = NULL;
137 end = NULL;
138 181
139 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); 182 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
140 CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) 183 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
141 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); 184 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
142 CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) 185 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
147 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2]) 190 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
148 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1]) 191 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
149 192
150 // test with end only / prev, next 193 // test with end only / prev, next
151 memset(nodes, 0, 4 * sizeof(struct node)); 194 memset(nodes, 0, 4 * sizeof(struct node));
152 begin = NULL; 195 begin = end = NULL;
153 end = NULL;
154 196
155 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); 197 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
156 CU_ASSERT_PTR_EQUAL(end, &nodes[0]) 198 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
157 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); 199 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
158 CU_ASSERT_PTR_EQUAL(end, &nodes[1]) 200 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
164 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2]) 206 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
165 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1]) 207 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
166 208
167 // test with begin, end / next 209 // test with begin, end / next
168 memset(nodes, 0, 4 * sizeof(struct node)); 210 memset(nodes, 0, 4 * sizeof(struct node));
169 begin = NULL; 211 begin = end = NULL;
170 end = NULL;
171 212
172 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); 213 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
173 CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) 214 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
174 CU_ASSERT_PTR_EQUAL(end, &nodes[0]) 215 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
175 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); 216 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
177 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) 218 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
178 CU_ASSERT_PTR_NULL(nodes[1].prev) 219 CU_ASSERT_PTR_NULL(nodes[1].prev)
179 } 220 }
180 221
181 void test_linked_list_prepend(void) { 222 void test_linked_list_prepend(void) {
182 struct node {
183 void *prev;
184 void *next;
185 };
186
187 struct node nodes[4]; 223 struct node nodes[4];
224 void *begin, *end;
188 225
189 // test with begin, end / prev, next 226 // test with begin, end / prev, next
190 memset(nodes, 0, 4 * sizeof(struct node)); 227 memset(nodes, 0, 4 * sizeof(struct node));
191 void *begin = NULL; 228 begin = end = NULL;
192 void *end = NULL;
193
194 ptrdiff_t loc_prev = offsetof(struct node, prev);
195 ptrdiff_t loc_next = offsetof(struct node, next);
196 229
197 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); 230 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
198 CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) 231 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
199 CU_ASSERT_PTR_EQUAL(end, &nodes[0]) 232 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
200 CU_ASSERT_PTR_NULL(nodes[0].prev) 233 CU_ASSERT_PTR_NULL(nodes[0].prev)
206 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) 239 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
207 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1]) 240 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
208 241
209 // test with begin only / prev, next 242 // test with begin only / prev, next
210 memset(nodes, 0, 4 * sizeof(struct node)); 243 memset(nodes, 0, 4 * sizeof(struct node));
211 begin = NULL; 244 begin = end = NULL;
212 end = NULL;
213 245
214 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); 246 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
215 CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) 247 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
216 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); 248 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
217 CU_ASSERT_PTR_EQUAL(begin, &nodes[1]) 249 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
223 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1]) 255 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
224 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2]) 256 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
225 257
226 // test with end only / prev, next 258 // test with end only / prev, next
227 memset(nodes, 0, 4 * sizeof(struct node)); 259 memset(nodes, 0, 4 * sizeof(struct node));
228 begin = NULL; 260 begin = end = NULL;
229 end = NULL;
230 261
231 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); 262 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
232 CU_ASSERT_PTR_EQUAL(end, &nodes[0]) 263 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
233 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); 264 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
234 CU_ASSERT_PTR_EQUAL(end, &nodes[0]) 265 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
240 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1]) 271 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
241 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2]) 272 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
242 273
243 // test with begin, end / next 274 // test with begin, end / next
244 memset(nodes, 0, 4 * sizeof(struct node)); 275 memset(nodes, 0, 4 * sizeof(struct node));
245 begin = NULL; 276 begin = end = NULL;
246 end = NULL;
247 277
248 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); 278 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
249 CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) 279 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
250 CU_ASSERT_PTR_EQUAL(end, &nodes[0]) 280 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
251 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); 281 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
257 CU_ASSERT_PTR_NULL(nodes[1].prev) 287 CU_ASSERT_PTR_NULL(nodes[1].prev)
258 CU_ASSERT_PTR_NULL(nodes[0].prev) 288 CU_ASSERT_PTR_NULL(nodes[0].prev)
259 } 289 }
260 290
261 void test_linked_list_insert(void) { 291 void test_linked_list_insert(void) {
262 struct node {
263 void *prev;
264 void *next;
265 };
266 ptrdiff_t loc_prev = offsetof(struct node, prev);
267 ptrdiff_t loc_next = offsetof(struct node, next);
268
269 struct node nodes[4]; 292 struct node nodes[4];
270 void *begin, *end; 293 void *begin, *end;
271 294
272 // insert mid list 295 // insert mid list
273 memset(nodes, 0, 4 * sizeof(struct node)); 296 memset(nodes, 0, 4 * sizeof(struct node));
315 CU_ASSERT_PTR_NULL(nodes[3].prev) 338 CU_ASSERT_PTR_NULL(nodes[3].prev)
316 CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0]) 339 CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0])
317 } 340 }
318 341
319 void test_linked_list_insert_chain(void) { 342 void test_linked_list_insert_chain(void) {
320 struct node {
321 void *prev;
322 void *next;
323 };
324 ptrdiff_t loc_prev = offsetof(struct node, prev);
325 ptrdiff_t loc_next = offsetof(struct node, next);
326
327 struct node nodes[5]; 343 struct node nodes[5];
328 void *begin, *end; 344 void *begin, *end;
329 345
330 // insert mid list 346 // insert mid list
331 memset(nodes, 0, 5 * sizeof(struct node)); 347 memset(nodes, 0, 5 * sizeof(struct node));
376 CU_ASSERT_PTR_NULL(nodes[3].prev) 392 CU_ASSERT_PTR_NULL(nodes[3].prev)
377 CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0]) 393 CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0])
378 } 394 }
379 395
380 void test_linked_list_first(void) { 396 void test_linked_list_first(void) {
381 struct node { 397 struct node *begin = create_test_data(3, NULL);
382 int data; 398 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin)
383 void *prev; 399 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin)
384 }; 400 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin)
385 ptrdiff_t loc = offsetof(struct node, prev); 401 destroy_test_data(begin);
386
387 struct node first = {1, NULL};
388 struct node second = {2, &first};
389 struct node third = {3, &second};
390
391 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&first, loc), &first)
392 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&second, loc), &first)
393 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&third, loc), &first)
394 } 402 }
395 403
396 void test_linked_list_last(void) { 404 void test_linked_list_last(void) {
397 struct node { 405 struct node *begin = create_test_data(3, NULL);
398 int data; 406 struct node *end = begin->next->next;
399 void *next; 407 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end)
400 }; 408 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end)
401 ptrdiff_t loc = offsetof(struct node, next); 409 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end)
402 410 destroy_test_data(begin);
403 struct node third = {3, NULL};
404 struct node second = {2, &third};
405 struct node first = {1, &second};
406
407 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&first, loc), &third)
408 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&second, loc), &third)
409 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
410 } 411 }
411 412
412 void test_linked_list_prev(void) { 413 void test_linked_list_prev(void) {
413 struct node { 414 struct node *begin = create_test_data(3, NULL);
414 void *next; 415 CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin))
415 }; 416 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin)
416 ptrdiff_t loc = offsetof(struct node, next); 417 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next)
417 418 destroy_test_data(begin);
418 struct node third = {NULL};
419 struct node second = {&third};
420 struct node first = {&second};
421
422 CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first))
423 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first)
424 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second)
425 } 419 }
426 420
427 void test_linked_list_remove(void) { 421 void test_linked_list_remove(void) {
428 struct node { 422 void *begin, *end;
429 void *next; 423
430 }; 424 int data[] = {2, 4, 6};
431 struct dnode { 425 begin = create_test_data(3, data);
432 void *next; 426 struct node *first = begin;
433 void *prev; 427 struct node *second = first->next;
434 }; 428 struct node *third = second->next;
435 ptrdiff_t loc = offsetof(struct node, next); 429 end = third;
436 ptrdiff_t ploc = offsetof(struct dnode, prev); 430
437 431 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
438 void *begin; 432 CU_ASSERT_PTR_EQUAL(begin, first)
439 void *end; 433 CU_ASSERT_PTR_EQUAL(end, third)
440 434 CU_ASSERT_PTR_NULL(first->prev)
441 // single linked list 435 CU_ASSERT_PTR_EQUAL(first->next, third)
442 struct node third = {NULL}; 436 CU_ASSERT_PTR_EQUAL(third->prev, first)
443 struct node second = {&third}; 437 CU_ASSERT_PTR_NULL(third->next)
444 struct node first = {&second}; 438
445 begin = &first; 439 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
446 440 CU_ASSERT_PTR_EQUAL(begin, first)
447 cx_linked_list_remove(&begin, NULL, -1, loc, &second); 441 CU_ASSERT_PTR_EQUAL(end, first)
448 CU_ASSERT_PTR_EQUAL(begin, &first) 442 CU_ASSERT_PTR_NULL(first->prev)
449 CU_ASSERT_PTR_EQUAL(first.next, &third) 443 CU_ASSERT_PTR_NULL(first->next)
450 CU_ASSERT_PTR_NULL(third.next) 444
451 445 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
452 cx_linked_list_remove(&begin, NULL, -1, loc, &first);
453 CU_ASSERT_PTR_EQUAL(begin, &third)
454 CU_ASSERT_PTR_NULL(third.next)
455
456 cx_linked_list_remove(&begin, NULL, -1, loc, &third);
457 CU_ASSERT_PTR_NULL(begin)
458
459 // doubly linked list
460 struct dnode dthird = {NULL , NULL};
461 struct dnode dsecond = {&dthird, NULL};
462 struct dnode dfirst = {&dsecond, NULL};
463 dthird.prev = &dsecond;
464 dsecond.prev = &dfirst;
465 begin = &dfirst;
466 end = &dthird;
467
468 cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
469 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
470 CU_ASSERT_PTR_EQUAL(end, &dthird)
471 CU_ASSERT_PTR_NULL(dfirst.prev)
472 CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
473 CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
474 CU_ASSERT_PTR_NULL(dthird.next)
475
476 cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
477 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
478 CU_ASSERT_PTR_EQUAL(end, &dfirst)
479 CU_ASSERT_PTR_NULL(dfirst.prev)
480 CU_ASSERT_PTR_NULL(dfirst.next)
481
482 cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
483 CU_ASSERT_PTR_NULL(begin) 446 CU_ASSERT_PTR_NULL(begin)
484 CU_ASSERT_PTR_NULL(end) 447 CU_ASSERT_PTR_NULL(end)
448
449 free(first);
450 free(second);
451 free(third);
485 } 452 }
486 453
487 void test_linked_list_size(void) { 454 void test_linked_list_size(void) {
488 struct node { 455 struct node *list;
489 void *next; 456
490 }; 457 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0)
491 ptrdiff_t loc = offsetof(struct node, next); 458
492 459 list = create_test_data(5, NULL);
493 struct node first = {NULL}; 460 CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5)
494 struct node second = {NULL}; 461 destroy_test_data(list);
495 struct node third = {NULL}; 462
496 463 list = create_test_data(13, NULL);
497 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0) 464 CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13)
498 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1) 465 destroy_test_data(list);
499 first.next = &second;
500 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
501 second.next = &third;
502 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
503 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
504 } 466 }
505 467
506 void test_linked_list_sort(void) { 468 void test_linked_list_sort(void) {
507 struct node {
508 void *prev;
509 void *next;
510 int data;
511 };
512
513 int expected[] = { 469 int expected[] = {
514 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880, 470 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
515 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894, 471 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
516 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797, 472 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
517 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677, 473 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
525 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424, 481 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
526 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973, 482 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
527 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681 483 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
528 }; 484 };
529 485
530 struct node *nodes = calloc(100, sizeof(struct node)); 486 void *begin = create_test_data(100, scrambled);
531 for (int i = 0; i < 100; i++) { 487 void *end = cx_linked_list_last(begin, loc_next);
532 nodes[i].prev = i == 0 ? NULL : &nodes[i - 1]; 488
533 nodes[i].next = i == 99 ? NULL : &nodes[i + 1]; 489 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
534 nodes[i].data = scrambled[i];
535 }
536
537 struct node *begin = &nodes[0];
538 struct node *end = &nodes[99];
539
540 cx_linked_list_sort((void **) &begin, (void **) &end,
541 offsetof(struct node, prev),
542 offsetof(struct node, next),
543 offsetof(struct node, data),
544 0, (CxListComparator) cmp_int); 490 0, (CxListComparator) cmp_int);
545 491
546 CU_ASSERT_PTR_NULL(begin->prev)
547 CU_ASSERT_EQUAL(begin->data, expected[0])
548 struct node *check = begin; 492 struct node *check = begin;
549 struct node *check_last = NULL; 493 struct node *check_last = NULL;
494 CU_ASSERT_PTR_NULL(check->prev)
495 CU_ASSERT_EQUAL(check->data, expected[0])
550 for (int i = 0; i < 100; i++) { 496 for (int i = 0; i < 100; i++) {
551 CU_ASSERT_EQUAL(check->data, expected[i]) 497 CU_ASSERT_EQUAL(check->data, expected[i])
552 CU_ASSERT_PTR_EQUAL(check->prev, check_last) 498 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
553 if (i < 99) { 499 if (i < 99) {
554 CU_ASSERT_PTR_NOT_NULL(check->next) 500 CU_ASSERT_PTR_NOT_NULL(check->next)
555 } 501 }
556 check_last = check; 502 check_last = check;
557 check = check->next; 503 check = check->next;
558 } 504 }
559 CU_ASSERT_PTR_NULL(check) 505 CU_ASSERT_PTR_NULL(check)
560 CU_ASSERT_EQUAL(end->data, expected[99]) 506 CU_ASSERT_PTR_EQUAL(end, check_last)
507
508 destroy_test_data(begin);
561 } 509 }
562 510
563 void test_linked_list_reverse(void) { 511 void test_linked_list_reverse(void) {
564 struct node { 512 void *begin, *end;
565 void *next; 513
566 }; 514 int data[] = {2, 4, 6, 8};
567 struct dnode { 515 int reversed[] = {8, 6, 4, 2};
568 void *next; 516
569 void *prev; 517 void *list = create_test_data(4, data);
570 }; 518 void *expected = create_test_data(4, reversed);
571 ptrdiff_t loc = offsetof(struct node, next); 519
572 ptrdiff_t ploc = offsetof(struct dnode, prev); 520 begin = list;
573 521 end = cx_linked_list_last(list, loc_next);
574 void *begin; 522
575 void *end; 523 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
576 524 CU_ASSERT_PTR_EQUAL(end, list)
577 // single linked list 525 CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev))
578 struct node third = {NULL}; 526 CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data,
579 struct node second = {&third}; 527 0, (CxListComparator) cmp_int))
580 struct node first = {&second}; 528
581 begin = &first; 529 destroy_test_data(begin);
582 530 destroy_test_data(expected);
583 cx_linked_list_reverse(&begin, NULL, -1, loc);
584 CU_ASSERT_PTR_EQUAL(begin, &third)
585 CU_ASSERT_PTR_EQUAL(third.next, &second)
586 CU_ASSERT_PTR_EQUAL(second.next, &first)
587 CU_ASSERT_PTR_NULL(first.next)
588
589 // doubly linked list
590 struct dnode dthird = {NULL , NULL};
591 struct dnode dsecond = {&dthird, NULL};
592 struct dnode dfirst = {&dsecond, NULL};
593 dthird.prev = &dsecond;
594 dsecond.prev = &dfirst;
595 begin = &dfirst;
596 end = &dthird;
597
598 cx_linked_list_reverse(&begin, &end, ploc, loc);
599 CU_ASSERT_PTR_EQUAL(begin, &dthird)
600 CU_ASSERT_PTR_EQUAL(end, &dfirst)
601 CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond)
602 CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst)
603 CU_ASSERT_PTR_NULL(dfirst.next)
604 CU_ASSERT_PTR_NULL(dthird.prev)
605 CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird)
606 CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond)
607 } 531 }
608 532
609 void test_hl_linked_list_create(void) { 533 void test_hl_linked_list_create(void) {
610 cxTestingAllocatorReset(); 534 cxTestingAllocatorReset();
611 535
1026 950
1027 suite = CU_add_suite("low level linked list", NULL, NULL); 951 suite = CU_add_suite("low level linked list", NULL, NULL);
1028 952
1029 cu_add_test(suite, test_linked_list_link_unlink); 953 cu_add_test(suite, test_linked_list_link_unlink);
1030 cu_add_test(suite, test_linked_list_at); 954 cu_add_test(suite, test_linked_list_at);
955 cu_add_test(suite, test_linked_list_compare);
1031 cu_add_test(suite, test_linked_list_prepend); 956 cu_add_test(suite, test_linked_list_prepend);
1032 cu_add_test(suite, test_linked_list_add); 957 cu_add_test(suite, test_linked_list_add);
1033 cu_add_test(suite, test_linked_list_insert); 958 cu_add_test(suite, test_linked_list_insert);
1034 cu_add_test(suite, test_linked_list_insert_chain); 959 cu_add_test(suite, test_linked_list_insert_chain);
1035 cu_add_test(suite, test_linked_list_first); 960 cu_add_test(suite, test_linked_list_first);

Mercurial Repository: ucx

mercurial