Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / slist_test.c @ 6b3f1a54

History | View | Annotate | Download (7.31 KB)

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
}