This source file includes following definitions.
- rebalance
- gl_tree_nx_add_first
- gl_tree_add_node_before
- gl_tree_nx_add_before
- gl_tree_add_node_after
- gl_tree_nx_add_after
- gl_tree_remove_node_no_free
- gl_tree_remove_node
- check_invariants
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 struct NODE_IMPL
31 {
32 struct NODE_IMPL *left;
33 struct NODE_IMPL *right;
34
35
36
37
38 struct NODE_IMPL *parent;
39 int balance;
40
41 NODE_PAYLOAD_FIELDS
42 };
43 typedef struct NODE_IMPL * NODE_T;
44
45
46 struct CONTAINER_IMPL
47 {
48 struct CONTAINER_IMPL_BASE base;
49 struct NODE_IMPL *root;
50 size_t count;
51 };
52
53
54
55
56
57
58 #define MAXHEIGHT 83
59
60
61
62
63
64 static void
65 rebalance (CONTAINER_T container,
66 NODE_T node, int height_diff, NODE_T parent)
67 {
68 for (;;)
69 {
70 NODE_T child;
71 int previous_balance;
72 int balance_diff;
73 NODE_T nodeleft;
74 NODE_T noderight;
75
76 child = node;
77 node = parent;
78
79 previous_balance = node->balance;
80
81
82
83
84
85 if (node->left != NULL || node->right != NULL)
86 balance_diff = (child == node->right ? height_diff : -height_diff);
87 else
88
89
90
91 balance_diff = - previous_balance;
92
93 node->balance += balance_diff;
94 if (balance_diff == previous_balance)
95 {
96
97 NODE_T *nodep;
98
99 if (node->parent == NULL)
100
101 nodep = &container->root;
102 else if (node->parent->left == node)
103 nodep = &node->parent->left;
104 else if (node->parent->right == node)
105 nodep = &node->parent->right;
106 else
107 abort ();
108
109 nodeleft = node->left;
110 noderight = node->right;
111
112 if (balance_diff < 0)
113 {
114
115
116
117
118
119
120
121 NODE_T nodeleftright = nodeleft->right;
122 if (nodeleft->balance <= 0)
123 {
124
125
126
127
128
129
130
131 node->left = nodeleftright;
132 nodeleft->right = node;
133
134 nodeleft->parent = node->parent;
135 node->parent = nodeleft;
136 if (nodeleftright != NULL)
137 nodeleftright->parent = node;
138
139 nodeleft->balance += 1;
140 node->balance = - nodeleft->balance;
141
142 *nodep = nodeleft;
143 height_diff = (height_diff < 0
144 ?
145
146
147 nodeleft->balance - 1
148 :
149
150
151 nodeleft->balance);
152 }
153 else
154 {
155
156
157
158
159
160
161
162
163
164
165 NODE_T L = nodeleft->right = nodeleftright->left;
166 NODE_T R = node->left = nodeleftright->right;
167 nodeleftright->left = nodeleft;
168 nodeleftright->right = node;
169
170 nodeleftright->parent = node->parent;
171 if (L != NULL)
172 L->parent = nodeleft;
173 if (R != NULL)
174 R->parent = node;
175 nodeleft->parent = nodeleftright;
176 node->parent = nodeleftright;
177
178 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
179 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
180 nodeleftright->balance = 0;
181
182 *nodep = nodeleftright;
183 height_diff = (height_diff < 0
184 ?
185
186
187 -1
188 :
189
190
191 0);
192 }
193 }
194 else
195 {
196
197
198
199
200
201
202
203 NODE_T noderightleft = noderight->left;
204 if (noderight->balance >= 0)
205 {
206
207
208
209
210
211
212
213 node->right = noderightleft;
214 noderight->left = node;
215
216 noderight->parent = node->parent;
217 node->parent = noderight;
218 if (noderightleft != NULL)
219 noderightleft->parent = node;
220
221 noderight->balance -= 1;
222 node->balance = - noderight->balance;
223
224 *nodep = noderight;
225 height_diff = (height_diff < 0
226 ?
227
228
229 - noderight->balance - 1
230 :
231
232
233 - noderight->balance);
234 }
235 else
236 {
237
238
239
240
241
242
243
244
245
246
247 NODE_T L = node->right = noderightleft->left;
248 NODE_T R = noderight->left = noderightleft->right;
249 noderightleft->left = node;
250 noderightleft->right = noderight;
251
252 noderightleft->parent = node->parent;
253 if (L != NULL)
254 L->parent = node;
255 if (R != NULL)
256 R->parent = noderight;
257 node->parent = noderightleft;
258 noderight->parent = noderightleft;
259
260 node->balance = (noderightleft->balance > 0 ? -1 : 0);
261 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
262 noderightleft->balance = 0;
263
264 *nodep = noderightleft;
265 height_diff = (height_diff < 0
266 ?
267
268
269 -1
270 :
271
272
273 0);
274 }
275 }
276 node = *nodep;
277 }
278 else
279 {
280
281
282 if (height_diff < 0)
283 height_diff = (previous_balance == 0 ? 0 : -1);
284 else
285 height_diff = (node->balance == 0 ? 0 : 1);
286 }
287
288 if (height_diff == 0)
289 break;
290
291 parent = node->parent;
292 if (parent == NULL)
293 break;
294 }
295 }
296
297 static NODE_T
298 gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS)
299 {
300
301 NODE_T new_node =
302 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
303
304 if (new_node == NULL)
305 return NULL;
306
307 new_node->left = NULL;
308 new_node->right = NULL;
309 new_node->balance = 0;
310 NODE_PAYLOAD_ASSIGN(new_node)
311
312
313 if (container->root == NULL)
314 {
315 container->root = new_node;
316 new_node->parent = NULL;
317 }
318 else
319 {
320 NODE_T node;
321
322 for (node = container->root; node->left != NULL; )
323 node = node->left;
324
325 node->left = new_node;
326 new_node->parent = node;
327 node->balance--;
328
329
330 if (node->right == NULL && node->parent != NULL)
331 rebalance (container, node, 1, node->parent);
332 }
333
334 container->count++;
335 return new_node;
336 }
337
338
339 static void
340 gl_tree_add_node_before (CONTAINER_T container, NODE_T node, NODE_T new_node)
341 {
342 bool height_inc;
343
344 new_node->left = NULL;
345 new_node->right = NULL;
346 new_node->balance = 0;
347
348
349 if (node->left == NULL)
350 {
351 node->left = new_node;
352 node->balance--;
353 height_inc = (node->right == NULL);
354 }
355 else
356 {
357 for (node = node->left; node->right != NULL; )
358 node = node->right;
359 node->right = new_node;
360 node->balance++;
361 height_inc = (node->left == NULL);
362 }
363 new_node->parent = node;
364
365
366 if (height_inc && node->parent != NULL)
367 rebalance (container, node, 1, node->parent);
368
369 container->count++;
370 }
371
372 static NODE_T
373 gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
374 {
375
376 NODE_T new_node =
377 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
378
379 if (new_node == NULL)
380 return NULL;
381
382 NODE_PAYLOAD_ASSIGN(new_node)
383
384 gl_tree_add_node_before (container, node, new_node);
385 return new_node;
386 }
387
388
389 static void
390 gl_tree_add_node_after (CONTAINER_T container, NODE_T node, NODE_T new_node)
391 {
392 bool height_inc;
393
394 new_node->left = NULL;
395 new_node->right = NULL;
396 new_node->balance = 0;
397
398
399 if (node->right == NULL)
400 {
401 node->right = new_node;
402 node->balance++;
403 height_inc = (node->left == NULL);
404 }
405 else
406 {
407 for (node = node->right; node->left != NULL; )
408 node = node->left;
409 node->left = new_node;
410 node->balance--;
411 height_inc = (node->right == NULL);
412 }
413 new_node->parent = node;
414
415
416 if (height_inc && node->parent != NULL)
417 rebalance (container, node, 1, node->parent);
418
419 container->count++;
420 }
421
422 static NODE_T
423 gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
424 {
425
426 NODE_T new_node =
427 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
428
429 if (new_node == NULL)
430 return NULL;
431
432 NODE_PAYLOAD_ASSIGN(new_node)
433
434 gl_tree_add_node_after (container, node, new_node);
435 return new_node;
436 }
437
438 static void
439 gl_tree_remove_node_no_free (CONTAINER_T container, NODE_T node)
440 {
441 NODE_T parent = node->parent;
442
443 if (node->left == NULL)
444 {
445
446 NODE_T child = node->right;
447
448 if (child != NULL)
449 child->parent = parent;
450 if (parent == NULL)
451 container->root = child;
452 else
453 {
454 if (parent->left == node)
455 parent->left = child;
456 else
457 parent->right = child;
458
459 rebalance (container, child, -1, parent);
460 }
461 }
462 else if (node->right == NULL)
463 {
464
465
466
467 NODE_T child = node->left;
468
469 child->parent = parent;
470 if (parent == NULL)
471 container->root = child;
472 else
473 {
474 if (parent->left == node)
475 parent->left = child;
476 else
477 parent->right = child;
478
479 rebalance (container, child, -1, parent);
480 }
481 }
482 else
483 {
484
485 NODE_T subst;
486 NODE_T subst_parent;
487 NODE_T child;
488
489 for (subst = node->left; subst->right != NULL; )
490 subst = subst->right;
491
492 subst_parent = subst->parent;
493
494 child = subst->left;
495
496
497
498
499
500
501
502
503
504
505
506
507 if (subst_parent != node)
508 {
509 if (child != NULL)
510 child->parent = subst_parent;
511 subst_parent->right = child;
512 }
513
514
515
516
517 if (subst_parent != node)
518 {
519 subst->left = node->left;
520 subst->left->parent = subst;
521 }
522 subst->right = node->right;
523 subst->right->parent = subst;
524 subst->balance = node->balance;
525 subst->parent = parent;
526 if (parent == NULL)
527 container->root = subst;
528 else if (parent->left == node)
529 parent->left = subst;
530 else
531 parent->right = subst;
532
533
534
535
536 rebalance (container, child, -1, subst_parent != node ? subst_parent : subst);
537 }
538
539 container->count--;
540 }
541
542 static bool
543 gl_tree_remove_node (CONTAINER_T container, NODE_T node)
544 {
545 gl_tree_remove_node_no_free (container, node);
546 NODE_PAYLOAD_DISPOSE (container, node)
547 free (node);
548 return true;
549 }
550
551
552 static unsigned int
553 check_invariants (NODE_T node, NODE_T parent, size_t *counterp)
554 {
555 unsigned int left_height =
556 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
557 unsigned int right_height =
558 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
559 int balance = (int)right_height - (int)left_height;
560
561 if (!(node->parent == parent))
562 abort ();
563 if (!(balance >= -1 && balance <= 1))
564 abort ();
565 if (!(node->balance == balance))
566 abort ();
567
568 (*counterp)++;
569
570 return 1 + (left_height > right_height ? left_height : right_height);
571 }