This source file includes following definitions.
- create_subtree_with_contents
- gl_tree_nx_create
- rebalance
- gl_tree_remove_node_from_tree
- gl_tree_nx_add_first
- gl_tree_nx_add_last
- gl_tree_nx_add_before
- gl_tree_nx_add_after
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 static gl_list_node_t
26 create_subtree_with_contents (size_t count, const void **contents)
27 {
28 size_t half1 = (count - 1) / 2;
29 size_t half2 = count / 2;
30
31 gl_list_node_t node =
32 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
33 if (node == NULL)
34 return NULL;
35
36 if (half1 > 0)
37 {
38 node->left = create_subtree_with_contents (half1, contents);
39 if (node->left == NULL)
40 goto fail1;
41 node->left->parent = node;
42 }
43 else
44 node->left = NULL;
45
46 node->value = contents[half1];
47
48 if (half2 > 0)
49 {
50 node->right = create_subtree_with_contents (half2, contents + half1 + 1);
51 if (node->right == NULL)
52 goto fail2;
53 node->right->parent = node;
54 }
55 else
56 node->right = NULL;
57
58
59
60
61
62 node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0);
63
64 node->branch_size = count;
65
66 return node;
67
68 fail2:
69 if (node->left != NULL)
70 free_subtree (node->left);
71 fail1:
72 free (node);
73 return NULL;
74 }
75
76 static gl_list_t
77 gl_tree_nx_create (gl_list_implementation_t implementation,
78 gl_listelement_equals_fn equals_fn,
79 gl_listelement_hashcode_fn hashcode_fn,
80 gl_listelement_dispose_fn dispose_fn,
81 bool allow_duplicates,
82 size_t count, const void **contents)
83 {
84 struct gl_list_impl *list =
85 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
86
87 if (list == NULL)
88 return NULL;
89
90 list->base.vtable = implementation;
91 list->base.equals_fn = equals_fn;
92 list->base.hashcode_fn = hashcode_fn;
93 list->base.dispose_fn = dispose_fn;
94 list->base.allow_duplicates = allow_duplicates;
95 #if WITH_HASHTABLE
96 {
97 size_t estimate = xsum (count, count / 2);
98 if (estimate < 10)
99 estimate = 10;
100 list->table_size = next_prime (estimate);
101 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
102 goto fail1;
103 list->table =
104 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
105 if (list->table == NULL)
106 goto fail1;
107 }
108 #endif
109 if (count > 0)
110 {
111 list->root = create_subtree_with_contents (count, contents);
112 if (list->root == NULL)
113 goto fail2;
114 list->root->parent = NULL;
115
116 #if WITH_HASHTABLE
117
118
119 if (add_nodes_to_buckets (list) < 0)
120 goto fail3;
121 #endif
122 }
123 else
124 list->root = NULL;
125
126 return list;
127
128 #if WITH_HASHTABLE
129 fail3:
130 free_subtree (list->root);
131 #endif
132 fail2:
133 #if WITH_HASHTABLE
134 free (list->table);
135 fail1:
136 #endif
137 free (list);
138 return NULL;
139 }
140
141
142
143
144
145 static void
146 rebalance (gl_list_t list,
147 gl_list_node_t node, int height_diff, gl_list_node_t parent)
148 {
149 for (;;)
150 {
151 gl_list_node_t child;
152 int previous_balance;
153 int balance_diff;
154 gl_list_node_t nodeleft;
155 gl_list_node_t noderight;
156
157 child = node;
158 node = parent;
159
160 previous_balance = node->balance;
161
162
163
164
165
166 if (node->left != NULL || node->right != NULL)
167 balance_diff = (child == node->right ? height_diff : -height_diff);
168 else
169
170
171
172 balance_diff = - previous_balance;
173
174 node->balance += balance_diff;
175 if (balance_diff == previous_balance)
176 {
177
178 gl_list_node_t *nodep;
179
180 if (node->parent == NULL)
181
182 nodep = &list->root;
183 else if (node->parent->left == node)
184 nodep = &node->parent->left;
185 else if (node->parent->right == node)
186 nodep = &node->parent->right;
187 else
188 abort ();
189
190 nodeleft = node->left;
191 noderight = node->right;
192
193 if (balance_diff < 0)
194 {
195
196
197
198
199
200
201
202 gl_list_node_t nodeleftleft = nodeleft->left;
203 gl_list_node_t nodeleftright = nodeleft->right;
204 if (nodeleft->balance <= 0)
205 {
206
207
208
209
210
211
212
213 node->left = nodeleftright;
214 nodeleft->right = node;
215
216 nodeleft->parent = node->parent;
217 node->parent = nodeleft;
218 if (nodeleftright != NULL)
219 nodeleftright->parent = node;
220
221 nodeleft->balance += 1;
222 node->balance = - nodeleft->balance;
223
224 node->branch_size =
225 (nodeleftright != NULL ? nodeleftright->branch_size : 0)
226 + 1 + (noderight != NULL ? noderight->branch_size : 0);
227 nodeleft->branch_size =
228 nodeleftleft->branch_size + 1 + node->branch_size;
229
230 *nodep = nodeleft;
231 height_diff = (height_diff < 0
232 ?
233
234
235 nodeleft->balance - 1
236 :
237
238
239 nodeleft->balance);
240 }
241 else
242 {
243
244
245
246
247
248
249
250
251
252
253 gl_list_node_t L = nodeleft->right = nodeleftright->left;
254 gl_list_node_t R = node->left = nodeleftright->right;
255 nodeleftright->left = nodeleft;
256 nodeleftright->right = node;
257
258 nodeleftright->parent = node->parent;
259 if (L != NULL)
260 L->parent = nodeleft;
261 if (R != NULL)
262 R->parent = node;
263 nodeleft->parent = nodeleftright;
264 node->parent = nodeleftright;
265
266 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
267 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
268 nodeleftright->balance = 0;
269
270 nodeleft->branch_size =
271 (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
272 + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
273 node->branch_size =
274 (node->left != NULL ? node->left->branch_size : 0)
275 + 1 + (node->right != NULL ? node->right->branch_size : 0);
276 nodeleftright->branch_size =
277 nodeleft->branch_size + 1 + node->branch_size;
278
279 *nodep = nodeleftright;
280 height_diff = (height_diff < 0
281 ?
282
283
284 -1
285 :
286
287
288 0);
289 }
290 }
291 else
292 {
293
294
295
296
297
298
299
300 gl_list_node_t noderightleft = noderight->left;
301 gl_list_node_t noderightright = noderight->right;
302 if (noderight->balance >= 0)
303 {
304
305
306
307
308
309
310
311 node->right = noderightleft;
312 noderight->left = node;
313
314 noderight->parent = node->parent;
315 node->parent = noderight;
316 if (noderightleft != NULL)
317 noderightleft->parent = node;
318
319 noderight->balance -= 1;
320 node->balance = - noderight->balance;
321
322 node->branch_size =
323 (nodeleft != NULL ? nodeleft->branch_size : 0)
324 + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
325 noderight->branch_size =
326 node->branch_size + 1 + noderightright->branch_size;
327
328 *nodep = noderight;
329 height_diff = (height_diff < 0
330 ?
331
332
333 - noderight->balance - 1
334 :
335
336
337 - noderight->balance);
338 }
339 else
340 {
341
342
343
344
345
346
347
348
349
350
351 gl_list_node_t L = node->right = noderightleft->left;
352 gl_list_node_t R = noderight->left = noderightleft->right;
353 noderightleft->left = node;
354 noderightleft->right = noderight;
355
356 noderightleft->parent = node->parent;
357 if (L != NULL)
358 L->parent = node;
359 if (R != NULL)
360 R->parent = noderight;
361 node->parent = noderightleft;
362 noderight->parent = noderightleft;
363
364 node->balance = (noderightleft->balance > 0 ? -1 : 0);
365 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
366 noderightleft->balance = 0;
367
368 node->branch_size =
369 (node->left != NULL ? node->left->branch_size : 0)
370 + 1 + (node->right != NULL ? node->right->branch_size : 0);
371 noderight->branch_size =
372 (noderight->left != NULL ? noderight->left->branch_size : 0)
373 + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
374 noderightleft->branch_size =
375 node->branch_size + 1 + noderight->branch_size;
376
377 *nodep = noderightleft;
378 height_diff = (height_diff < 0
379 ?
380
381
382 -1
383 :
384
385
386 0);
387 }
388 }
389 node = *nodep;
390 }
391 else
392 {
393
394
395 if (height_diff < 0)
396 height_diff = (previous_balance == 0 ? 0 : -1);
397 else
398 height_diff = (node->balance == 0 ? 0 : 1);
399 }
400
401 if (height_diff == 0)
402 break;
403
404 parent = node->parent;
405 if (parent == NULL)
406 break;
407 }
408 }
409
410 static void
411 gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
412 {
413 gl_list_node_t parent = node->parent;
414
415 if (node->left == NULL)
416 {
417
418 gl_list_node_t child = node->right;
419
420 if (child != NULL)
421 child->parent = parent;
422 if (parent == NULL)
423 list->root = child;
424 else
425 {
426 if (parent->left == node)
427 parent->left = child;
428 else
429 parent->right = child;
430
431
432 {
433 gl_list_node_t p;
434
435 for (p = parent; p != NULL; p = p->parent)
436 p->branch_size--;
437 }
438
439 rebalance (list, child, -1, parent);
440 }
441 }
442 else if (node->right == NULL)
443 {
444
445
446
447 gl_list_node_t child = node->left;
448
449 child->parent = parent;
450 if (parent == NULL)
451 list->root = child;
452 else
453 {
454 if (parent->left == node)
455 parent->left = child;
456 else
457 parent->right = child;
458
459
460 {
461 gl_list_node_t p;
462
463 for (p = parent; p != NULL; p = p->parent)
464 p->branch_size--;
465 }
466
467 rebalance (list, child, -1, parent);
468 }
469 }
470 else
471 {
472
473 gl_list_node_t subst;
474 gl_list_node_t subst_parent;
475 gl_list_node_t child;
476
477 for (subst = node->left; subst->right != NULL; )
478 subst = subst->right;
479
480 subst_parent = subst->parent;
481
482 child = subst->left;
483
484
485
486
487
488
489
490
491
492
493
494
495 if (subst_parent != node)
496 {
497 if (child != NULL)
498 child->parent = subst_parent;
499 subst_parent->right = child;
500 }
501
502
503 {
504 gl_list_node_t p;
505
506 for (p = subst_parent; p != NULL; p = p->parent)
507 p->branch_size--;
508 }
509
510
511
512
513 if (subst_parent != node)
514 {
515 subst->left = node->left;
516 subst->left->parent = subst;
517 }
518 subst->right = node->right;
519 subst->right->parent = subst;
520 subst->balance = node->balance;
521 subst->branch_size = node->branch_size;
522 subst->parent = parent;
523 if (parent == NULL)
524 list->root = subst;
525 else if (parent->left == node)
526 parent->left = subst;
527 else
528 parent->right = subst;
529
530
531
532
533 rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
534 }
535 }
536
537 static gl_list_node_t
538 gl_tree_nx_add_first (gl_list_t list, const void *elt)
539 {
540
541 gl_list_node_t new_node =
542 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
543
544 if (new_node == NULL)
545 return NULL;
546
547 new_node->left = NULL;
548 new_node->right = NULL;
549 new_node->balance = 0;
550 new_node->branch_size = 1;
551 new_node->value = elt;
552 #if WITH_HASHTABLE
553 new_node->h.hashcode =
554 (list->base.hashcode_fn != NULL
555 ? list->base.hashcode_fn (new_node->value)
556 : (size_t)(uintptr_t) new_node->value);
557 #endif
558
559
560 if (list->root == NULL)
561 {
562 list->root = new_node;
563 new_node->parent = NULL;
564 }
565 else
566 {
567 gl_list_node_t node;
568
569 for (node = list->root; node->left != NULL; )
570 node = node->left;
571
572 node->left = new_node;
573 new_node->parent = node;
574 node->balance--;
575
576
577 {
578 gl_list_node_t p;
579
580 for (p = node; p != NULL; p = p->parent)
581 p->branch_size++;
582 }
583
584
585 if (node->right == NULL && node->parent != NULL)
586 rebalance (list, node, 1, node->parent);
587 }
588
589 #if WITH_HASHTABLE
590
591
592
593 if (add_to_bucket (list, new_node) < 0)
594 {
595 gl_tree_remove_node_from_tree (list, new_node);
596 free (new_node);
597 return NULL;
598 }
599 hash_resize_after_add (list);
600 #endif
601
602 return new_node;
603 }
604
605 static gl_list_node_t
606 gl_tree_nx_add_last (gl_list_t list, const void *elt)
607 {
608
609 gl_list_node_t new_node =
610 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
611
612 if (new_node == NULL)
613 return NULL;
614
615 new_node->left = NULL;
616 new_node->right = NULL;
617 new_node->balance = 0;
618 new_node->branch_size = 1;
619 new_node->value = elt;
620 #if WITH_HASHTABLE
621 new_node->h.hashcode =
622 (list->base.hashcode_fn != NULL
623 ? list->base.hashcode_fn (new_node->value)
624 : (size_t)(uintptr_t) new_node->value);
625 #endif
626
627
628 if (list->root == NULL)
629 {
630 list->root = new_node;
631 new_node->parent = NULL;
632 }
633 else
634 {
635 gl_list_node_t node;
636
637 for (node = list->root; node->right != NULL; )
638 node = node->right;
639
640 node->right = new_node;
641 new_node->parent = node;
642 node->balance++;
643
644
645 {
646 gl_list_node_t p;
647
648 for (p = node; p != NULL; p = p->parent)
649 p->branch_size++;
650 }
651
652
653 if (node->left == NULL && node->parent != NULL)
654 rebalance (list, node, 1, node->parent);
655 }
656
657 #if WITH_HASHTABLE
658
659
660
661 if (add_to_bucket (list, new_node) < 0)
662 {
663 gl_tree_remove_node_from_tree (list, new_node);
664 free (new_node);
665 return NULL;
666 }
667 hash_resize_after_add (list);
668 #endif
669
670 return new_node;
671 }
672
673 static gl_list_node_t
674 gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
675 {
676
677 gl_list_node_t new_node;
678 bool height_inc;
679
680 new_node =
681 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
682 if (new_node == NULL)
683 return NULL;
684
685 new_node->left = NULL;
686 new_node->right = NULL;
687 new_node->balance = 0;
688 new_node->branch_size = 1;
689 new_node->value = elt;
690 #if WITH_HASHTABLE
691 new_node->h.hashcode =
692 (list->base.hashcode_fn != NULL
693 ? list->base.hashcode_fn (new_node->value)
694 : (size_t)(uintptr_t) new_node->value);
695 #endif
696
697
698 if (node->left == NULL)
699 {
700 node->left = new_node;
701 node->balance--;
702 height_inc = (node->right == NULL);
703 }
704 else
705 {
706 for (node = node->left; node->right != NULL; )
707 node = node->right;
708 node->right = new_node;
709 node->balance++;
710 height_inc = (node->left == NULL);
711 }
712 new_node->parent = node;
713
714
715 {
716 gl_list_node_t p;
717
718 for (p = node; p != NULL; p = p->parent)
719 p->branch_size++;
720 }
721
722
723 if (height_inc && node->parent != NULL)
724 rebalance (list, node, 1, node->parent);
725
726 #if WITH_HASHTABLE
727
728
729
730 if (add_to_bucket (list, new_node) < 0)
731 {
732 gl_tree_remove_node_from_tree (list, new_node);
733 free (new_node);
734 return NULL;
735 }
736 hash_resize_after_add (list);
737 #endif
738
739 return new_node;
740 }
741
742 static gl_list_node_t
743 gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
744 {
745
746 gl_list_node_t new_node;
747 bool height_inc;
748
749 new_node =
750 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
751 if (new_node == NULL)
752 return NULL;
753
754 new_node->left = NULL;
755 new_node->right = NULL;
756 new_node->balance = 0;
757 new_node->branch_size = 1;
758 new_node->value = elt;
759 #if WITH_HASHTABLE
760 new_node->h.hashcode =
761 (list->base.hashcode_fn != NULL
762 ? list->base.hashcode_fn (new_node->value)
763 : (size_t)(uintptr_t) new_node->value);
764 #endif
765
766
767 if (node->right == NULL)
768 {
769 node->right = new_node;
770 node->balance++;
771 height_inc = (node->left == NULL);
772 }
773 else
774 {
775 for (node = node->right; node->left != NULL; )
776 node = node->left;
777 node->left = new_node;
778 node->balance--;
779 height_inc = (node->right == NULL);
780 }
781 new_node->parent = node;
782
783
784 {
785 gl_list_node_t p;
786
787 for (p = node; p != NULL; p = p->parent)
788 p->branch_size++;
789 }
790
791
792 if (height_inc && node->parent != NULL)
793 rebalance (list, node, 1, node->parent);
794
795 #if WITH_HASHTABLE
796
797
798
799 if (add_to_bucket (list, new_node) < 0)
800 {
801 gl_tree_remove_node_from_tree (list, new_node);
802 free (new_node);
803 return NULL;
804 }
805 hash_resize_after_add (list);
806 #endif
807
808 return new_node;
809 }