This source file includes following definitions.
- create_subtree_with_contents
- gl_tree_nx_create
- rotate_left
- rotate_right
- rebalance_after_add
- rebalance_after_remove
- 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
26
27 static gl_list_node_t
28 create_subtree_with_contents (unsigned int bh,
29 size_t count, const void **contents)
30 {
31 size_t half1 = (count - 1) / 2;
32 size_t half2 = count / 2;
33
34 gl_list_node_t node =
35 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
36 if (node == NULL)
37 return NULL;
38
39 if (half1 > 0)
40 {
41
42
43 node->left =
44 create_subtree_with_contents (bh - 1, half1, contents);
45 if (node->left == NULL)
46 goto fail1;
47 node->left->parent = node;
48 }
49 else
50 node->left = NULL;
51
52 node->value = contents[half1];
53
54 if (half2 > 0)
55 {
56
57
58 node->right =
59 create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
60 if (node->right == NULL)
61 goto fail2;
62 node->right->parent = node;
63 }
64 else
65 node->right = NULL;
66
67 node->color = (bh == 0 ? RED : BLACK);
68
69 node->branch_size = count;
70
71 return node;
72
73 fail2:
74 if (node->left != NULL)
75 free_subtree (node->left);
76 fail1:
77 free (node);
78 return NULL;
79 }
80
81 static gl_list_t
82 gl_tree_nx_create (gl_list_implementation_t implementation,
83 gl_listelement_equals_fn equals_fn,
84 gl_listelement_hashcode_fn hashcode_fn,
85 gl_listelement_dispose_fn dispose_fn,
86 bool allow_duplicates,
87 size_t count, const void **contents)
88 {
89 struct gl_list_impl *list =
90 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
91
92 if (list == NULL)
93 return NULL;
94
95 list->base.vtable = implementation;
96 list->base.equals_fn = equals_fn;
97 list->base.hashcode_fn = hashcode_fn;
98 list->base.dispose_fn = dispose_fn;
99 list->base.allow_duplicates = allow_duplicates;
100 #if WITH_HASHTABLE
101 {
102 size_t estimate = xsum (count, count / 2);
103 if (estimate < 10)
104 estimate = 10;
105 list->table_size = next_prime (estimate);
106 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
107 goto fail1;
108 list->table =
109 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
110 if (list->table == NULL)
111 goto fail1;
112 }
113 #endif
114 if (count > 0)
115 {
116
117
118
119 unsigned int bh;
120 {
121 size_t n;
122 for (n = count + 1, bh = 0; n > 1; n = n >> 1)
123 bh++;
124 }
125
126 list->root = create_subtree_with_contents (bh, count, contents);
127 if (list->root == NULL)
128 goto fail2;
129 list->root->parent = NULL;
130
131 #if WITH_HASHTABLE
132
133
134 if (add_nodes_to_buckets (list) < 0)
135 goto fail3;
136 #endif
137 }
138 else
139 list->root = NULL;
140
141 return list;
142
143 #if WITH_HASHTABLE
144 fail3:
145 free_subtree (list->root);
146 #endif
147 fail2:
148 #if WITH_HASHTABLE
149 free (list->table);
150 fail1:
151 #endif
152 free (list);
153 return NULL;
154 }
155
156
157
158
159
160
161
162
163
164
165
166 static gl_list_node_t
167 rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
168 {
169 gl_list_node_t a_node = b_node->left;
170 gl_list_node_t c_node = d_node->left;
171 gl_list_node_t e_node = d_node->right;
172
173 b_node->right = c_node;
174 d_node->left = b_node;
175
176 d_node->parent = b_node->parent;
177 b_node->parent = d_node;
178 if (c_node != NULL)
179 c_node->parent = b_node;
180
181 b_node->branch_size =
182 (a_node != NULL ? a_node->branch_size : 0)
183 + 1 + (c_node != NULL ? c_node->branch_size : 0);
184 d_node->branch_size =
185 b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
186
187 return d_node;
188 }
189
190
191
192
193
194
195
196
197
198
199
200 static gl_list_node_t
201 rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
202 {
203 gl_list_node_t a_node = b_node->left;
204 gl_list_node_t c_node = b_node->right;
205 gl_list_node_t e_node = d_node->right;
206
207 d_node->left = c_node;
208 b_node->right = d_node;
209
210 b_node->parent = d_node->parent;
211 d_node->parent = b_node;
212 if (c_node != NULL)
213 c_node->parent = d_node;
214
215 d_node->branch_size =
216 (c_node != NULL ? c_node->branch_size : 0)
217 + 1 + (e_node != NULL ? e_node->branch_size : 0);
218 b_node->branch_size =
219 (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
220
221 return b_node;
222 }
223
224
225
226
227 static void
228 rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
229 {
230 for (;;)
231 {
232
233
234
235 gl_list_node_t grandparent;
236 gl_list_node_t uncle;
237
238 if (parent->color == BLACK)
239 {
240
241 node->color = RED;
242 return;
243 }
244
245 grandparent = parent->parent;
246
247
248
249 if (grandparent->left == parent)
250 uncle = grandparent->right;
251 else if (grandparent->right == parent)
252 uncle = grandparent->left;
253 else
254 abort ();
255
256 if (uncle != NULL && uncle->color == RED)
257 {
258
259
260
261 node->color = RED;
262 parent->color = uncle->color = BLACK;
263 node = grandparent;
264 }
265 else
266 {
267
268
269
270
271 gl_list_node_t *grandparentp;
272
273 if (grandparent->parent == NULL)
274 grandparentp = &list->root;
275 else if (grandparent->parent->left == grandparent)
276 grandparentp = &grandparent->parent->left;
277 else if (grandparent->parent->right == grandparent)
278 grandparentp = &grandparent->parent->right;
279 else
280 abort ();
281
282 if (grandparent->left == parent)
283 {
284 if (parent->right == node)
285 {
286
287 grandparent->left = rotate_left (parent, node);
288 node = parent;
289 parent = grandparent->left;
290 }
291
292
293
294
295
296
297
298
299
300
301
302
303 *grandparentp = rotate_right (parent, grandparent);
304 parent->color = BLACK;
305 node->color = grandparent->color = RED;
306 }
307 else
308 {
309 if (parent->left == node)
310 {
311
312 grandparent->right = rotate_right (node, parent);
313 node = parent;
314 parent = grandparent->right;
315 }
316
317
318
319
320
321
322
323
324
325
326
327
328 *grandparentp = rotate_left (grandparent, parent);
329 parent->color = BLACK;
330 node->color = grandparent->color = RED;
331 }
332 return;
333 }
334
335
336 parent = node->parent;
337
338 if (parent == NULL)
339 {
340
341
342 node->color = BLACK;
343 return;
344 }
345 }
346 }
347
348
349
350
351
352 static void
353 rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
354 {
355 for (;;)
356 {
357
358
359
360
361 gl_list_node_t *parentp;
362
363 if (parent->parent == NULL)
364 parentp = &list->root;
365 else if (parent->parent->left == parent)
366 parentp = &parent->parent->left;
367 else if (parent->parent->right == parent)
368 parentp = &parent->parent->right;
369 else
370 abort ();
371
372 if (parent->left == child)
373 {
374 gl_list_node_t sibling = parent->right;
375
376
377
378
379
380
381
382
383
384 if (sibling->color == RED)
385 {
386
387
388
389
390
391
392
393
394
395
396
397
398 *parentp = rotate_left (parent, sibling);
399 parent->color = RED;
400 sibling->color = BLACK;
401
402
403
404 parentp = &sibling->left;
405 sibling = parent->right;
406 }
407
408
409
410
411
412
413
414 if (sibling->right != NULL && sibling->right->color == RED)
415 {
416
417
418
419
420
421
422
423
424
425
426 *parentp = rotate_left (parent, sibling);
427 sibling->color = parent->color;
428 parent->color = BLACK;
429 sibling->right->color = BLACK;
430 return;
431 }
432 else if (sibling->left != NULL && sibling->left->color == RED)
433 {
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449 parent->right = rotate_right (sibling->left, sibling);
450
451 sibling->color = RED;
452 sibling = parent->right;
453 sibling->color = BLACK;
454
455
456 *parentp = rotate_left (parent, sibling);
457 sibling->color = parent->color;
458 parent->color = BLACK;
459 sibling->right->color = BLACK;
460 return;
461 }
462 else
463 {
464 if (parent->color == BLACK)
465 {
466
467
468
469
470
471
472
473
474 sibling->color = RED;
475
476 child = parent;
477 }
478 else
479 {
480
481
482
483
484
485
486
487
488 parent->color = BLACK;
489 sibling->color = RED;
490 return;
491 }
492 }
493 }
494 else if (parent->right == child)
495 {
496 gl_list_node_t sibling = parent->left;
497
498
499
500
501
502
503
504
505
506 if (sibling->color == RED)
507 {
508
509
510
511
512
513
514
515
516
517
518
519
520 *parentp = rotate_right (sibling, parent);
521 parent->color = RED;
522 sibling->color = BLACK;
523
524
525
526 parentp = &sibling->right;
527 sibling = parent->left;
528 }
529
530
531
532
533
534
535
536 if (sibling->left != NULL && sibling->left->color == RED)
537 {
538
539
540
541
542
543
544
545
546
547
548 *parentp = rotate_right (sibling, parent);
549 sibling->color = parent->color;
550 parent->color = BLACK;
551 sibling->left->color = BLACK;
552 return;
553 }
554 else if (sibling->right != NULL && sibling->right->color == RED)
555 {
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571 parent->left = rotate_left (sibling, sibling->right);
572
573 sibling->color = RED;
574 sibling = parent->left;
575 sibling->color = BLACK;
576
577
578 *parentp = rotate_right (sibling, parent);
579 sibling->color = parent->color;
580 parent->color = BLACK;
581 sibling->left->color = BLACK;
582 return;
583 }
584 else
585 {
586 if (parent->color == BLACK)
587 {
588
589
590
591
592
593
594
595
596 sibling->color = RED;
597
598 child = parent;
599 }
600 else
601 {
602
603
604
605
606
607
608
609
610 parent->color = BLACK;
611 sibling->color = RED;
612 return;
613 }
614 }
615 }
616 else
617 abort ();
618
619
620 parent = child->parent;
621
622 #if 0
623 if (child != NULL && child->color == RED)
624 {
625 child->color = BLACK;
626 return;
627 }
628 #endif
629
630 if (parent == NULL)
631 return;
632 }
633 }
634
635 static void
636 gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
637 {
638 gl_list_node_t parent = node->parent;
639
640 if (node->left == NULL)
641 {
642
643 gl_list_node_t child = node->right;
644
645 if (child != NULL)
646 {
647 child->parent = parent;
648
649
650 child->color = BLACK;
651 }
652 if (parent == NULL)
653 list->root = child;
654 else
655 {
656 if (parent->left == node)
657 parent->left = child;
658 else
659 parent->right = child;
660
661
662 {
663 gl_list_node_t p;
664
665 for (p = parent; p != NULL; p = p->parent)
666 p->branch_size--;
667 }
668
669 if (child == NULL && node->color == BLACK)
670 rebalance_after_remove (list, child, parent);
671 }
672 }
673 else if (node->right == NULL)
674 {
675
676
677
678 gl_list_node_t child = node->left;
679
680 child->parent = parent;
681
682
683 child->color = BLACK;
684 if (parent == NULL)
685 list->root = child;
686 else
687 {
688 if (parent->left == node)
689 parent->left = child;
690 else
691 parent->right = child;
692
693
694 {
695 gl_list_node_t p;
696
697 for (p = parent; p != NULL; p = p->parent)
698 p->branch_size--;
699 }
700 }
701 }
702 else
703 {
704
705 gl_list_node_t subst;
706 gl_list_node_t subst_parent;
707 gl_list_node_t child;
708 color_t removed_color;
709
710 for (subst = node->left; subst->right != NULL; )
711 subst = subst->right;
712
713 subst_parent = subst->parent;
714
715 child = subst->left;
716
717 removed_color = subst->color;
718
719
720
721
722
723
724
725
726
727
728
729
730 if (subst_parent != node)
731 {
732 if (child != NULL)
733 child->parent = subst_parent;
734 subst_parent->right = child;
735 }
736
737
738 {
739 gl_list_node_t p;
740
741 for (p = subst_parent; p != NULL; p = p->parent)
742 p->branch_size--;
743 }
744
745
746
747
748 if (subst_parent != node)
749 {
750 subst->left = node->left;
751 subst->left->parent = subst;
752 }
753 subst->right = node->right;
754 subst->right->parent = subst;
755 subst->color = node->color;
756 subst->branch_size = node->branch_size;
757 subst->parent = parent;
758 if (parent == NULL)
759 list->root = subst;
760 else if (parent->left == node)
761 parent->left = subst;
762 else
763 parent->right = subst;
764
765 if (removed_color == BLACK)
766 {
767 if (child != NULL && child->color == RED)
768
769 child->color = BLACK;
770 else
771
772
773
774 rebalance_after_remove (list, child,
775 subst_parent != node ? subst_parent : subst);
776 }
777 }
778 }
779
780 static gl_list_node_t
781 gl_tree_nx_add_first (gl_list_t list, const void *elt)
782 {
783
784 gl_list_node_t new_node =
785 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
786
787 if (new_node == NULL)
788 return NULL;
789
790 new_node->left = NULL;
791 new_node->right = NULL;
792 new_node->branch_size = 1;
793 new_node->value = elt;
794 #if WITH_HASHTABLE
795 new_node->h.hashcode =
796 (list->base.hashcode_fn != NULL
797 ? list->base.hashcode_fn (new_node->value)
798 : (size_t)(uintptr_t) new_node->value);
799 #endif
800
801
802 if (list->root == NULL)
803 {
804 new_node->color = BLACK;
805 list->root = new_node;
806 new_node->parent = NULL;
807 }
808 else
809 {
810 gl_list_node_t node;
811
812 for (node = list->root; node->left != NULL; )
813 node = node->left;
814
815 node->left = new_node;
816 new_node->parent = node;
817
818
819 {
820 gl_list_node_t p;
821
822 for (p = node; p != NULL; p = p->parent)
823 p->branch_size++;
824 }
825
826
827 rebalance_after_add (list, new_node, node);
828 }
829
830 #if WITH_HASHTABLE
831
832
833
834 if (add_to_bucket (list, new_node) < 0)
835 {
836 gl_tree_remove_node_from_tree (list, new_node);
837 free (new_node);
838 return NULL;
839 }
840 hash_resize_after_add (list);
841 #endif
842
843 return new_node;
844 }
845
846 static gl_list_node_t
847 gl_tree_nx_add_last (gl_list_t list, const void *elt)
848 {
849
850 gl_list_node_t new_node =
851 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
852
853 if (new_node == NULL)
854 return NULL;
855
856 new_node->left = NULL;
857 new_node->right = NULL;
858 new_node->branch_size = 1;
859 new_node->value = elt;
860 #if WITH_HASHTABLE
861 new_node->h.hashcode =
862 (list->base.hashcode_fn != NULL
863 ? list->base.hashcode_fn (new_node->value)
864 : (size_t)(uintptr_t) new_node->value);
865 #endif
866
867
868 if (list->root == NULL)
869 {
870 new_node->color = BLACK;
871 list->root = new_node;
872 new_node->parent = NULL;
873 }
874 else
875 {
876 gl_list_node_t node;
877
878 for (node = list->root; node->right != NULL; )
879 node = node->right;
880
881 node->right = new_node;
882 new_node->parent = node;
883
884
885 {
886 gl_list_node_t p;
887
888 for (p = node; p != NULL; p = p->parent)
889 p->branch_size++;
890 }
891
892
893 rebalance_after_add (list, new_node, node);
894 }
895
896 #if WITH_HASHTABLE
897
898
899
900 if (add_to_bucket (list, new_node) < 0)
901 {
902 gl_tree_remove_node_from_tree (list, new_node);
903 free (new_node);
904 return NULL;
905 }
906 hash_resize_after_add (list);
907 #endif
908
909 return new_node;
910 }
911
912 static gl_list_node_t
913 gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
914 {
915
916 gl_list_node_t new_node =
917 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
918
919 if (new_node == NULL)
920 return NULL;
921
922 new_node->left = NULL;
923 new_node->right = NULL;
924 new_node->branch_size = 1;
925 new_node->value = elt;
926 #if WITH_HASHTABLE
927 new_node->h.hashcode =
928 (list->base.hashcode_fn != NULL
929 ? list->base.hashcode_fn (new_node->value)
930 : (size_t)(uintptr_t) new_node->value);
931 #endif
932
933
934 if (node->left == NULL)
935 node->left = new_node;
936 else
937 {
938 for (node = node->left; node->right != NULL; )
939 node = node->right;
940 node->right = new_node;
941 }
942 new_node->parent = node;
943
944
945 {
946 gl_list_node_t p;
947
948 for (p = node; p != NULL; p = p->parent)
949 p->branch_size++;
950 }
951
952
953 rebalance_after_add (list, new_node, node);
954
955 #if WITH_HASHTABLE
956
957
958
959 if (add_to_bucket (list, new_node) < 0)
960 {
961 gl_tree_remove_node_from_tree (list, new_node);
962 free (new_node);
963 return NULL;
964 }
965 hash_resize_after_add (list);
966 #endif
967
968 return new_node;
969 }
970
971 static gl_list_node_t
972 gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
973 {
974
975 gl_list_node_t new_node =
976 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
977
978 if (new_node == NULL)
979 return NULL;
980
981 new_node->left = NULL;
982 new_node->right = NULL;
983 new_node->branch_size = 1;
984 new_node->value = elt;
985 #if WITH_HASHTABLE
986 new_node->h.hashcode =
987 (list->base.hashcode_fn != NULL
988 ? list->base.hashcode_fn (new_node->value)
989 : (size_t)(uintptr_t) new_node->value);
990 #endif
991
992
993 if (node->right == NULL)
994 node->right = new_node;
995 else
996 {
997 for (node = node->right; node->left != NULL; )
998 node = node->left;
999 node->left = new_node;
1000 }
1001 new_node->parent = node;
1002
1003
1004 {
1005 gl_list_node_t p;
1006
1007 for (p = node; p != NULL; p = p->parent)
1008 p->branch_size++;
1009 }
1010
1011
1012 rebalance_after_add (list, new_node, node);
1013
1014 #if WITH_HASHTABLE
1015
1016
1017
1018 if (add_to_bucket (list, new_node) < 0)
1019 {
1020 gl_tree_remove_node_from_tree (list, new_node);
1021 free (new_node);
1022 return NULL;
1023 }
1024 hash_resize_after_add (list);
1025 #endif
1026
1027 return new_node;
1028 }