Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.68 KB)

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
}