This source file includes following definitions.
- hb_tree_new
- hb_dict_new
- hb_tree_destroy
- hb_tree_empty
- hb_tree_search
- hb_tree_insert
- hb_tree_probe
- hb_tree_remove
- hb_tree_min
- hb_tree_max
- hb_tree_walk
- hb_tree_count
- hb_tree_height
- hb_tree_mheight
- hb_tree_pathlen
- node_new
- node_min
- node_max
- node_next
- node_prev
- node_height
- node_mheight
- node_pathlen
- rot_left
- rot_right
- hb_itor_new
- hb_dict_itor_new
- hb_itor_destroy
- hb_itor_valid
- hb_itor_invalidate
- hb_itor_next
- hb_itor_prev
- hb_itor_nextn
- hb_itor_prevn
- hb_itor_first
- hb_itor_last
- hb_itor_search
- hb_itor_key
- hb_itor_data
- hb_itor_cdata
- hb_itor_set_data
1
2
3
4
5
6
7
8
9
10
11
12 #include <stdlib.h>
13
14 #include "hb_tree.h"
15 #include "dict_private.h"
16
17 typedef signed char balance_t;
18
19 typedef struct hb_node hb_node;
20
21 struct hb_node {
22 void *key;
23 void *dat;
24 hb_node *parent;
25 hb_node *llink;
26 hb_node *rlink;
27 balance_t bal;
28 };
29
30 struct hb_tree {
31 hb_node *root;
32 unsigned count;
33 dict_cmp_func key_cmp;
34 dict_del_func key_del;
35 dict_del_func dat_del;
36 };
37
38 struct hb_itor {
39 hb_tree *tree;
40 hb_node *node;
41 };
42
43 static int rot_left __P((hb_tree *tree, hb_node *node));
44 static int rot_right __P((hb_tree *tree, hb_node *node));
45 static unsigned node_height __P((const hb_node *node));
46 static unsigned node_mheight __P((const hb_node *node));
47 static unsigned node_pathlen __P((const hb_node *node, unsigned level));
48 static hb_node *node_new __P((void *key, void *dat));
49 static hb_node *node_min __P((hb_node *node));
50 static hb_node *node_max __P((hb_node *node));
51 static hb_node *node_next __P((hb_node *node));
52 static hb_node *node_prev __P((hb_node *node));
53
54 hb_tree *
55 hb_tree_new(dict_cmp_func key_cmp, dict_del_func key_del,
56 dict_del_func dat_del)
57 {
58 hb_tree *tree;
59
60 if ((tree = (hb_tree*)MALLOC(sizeof(*tree))) == NULL)
61 return NULL;
62
63 tree->root = NULL;
64 tree->count = 0;
65 tree->key_cmp = key_cmp ? key_cmp : dict_ptr_cmp;
66 tree->key_del = key_del;
67 tree->dat_del = dat_del;
68
69 return tree;
70 }
71
72 dict *
73 hb_dict_new(dict_cmp_func key_cmp, dict_del_func key_del,
74 dict_del_func dat_del)
75 {
76 dict *dct;
77 hb_tree *tree;
78
79 if ((dct = (dict*)MALLOC(sizeof(*dct))) == NULL)
80 return NULL;
81
82 if ((tree = hb_tree_new(key_cmp, key_del, dat_del)) == NULL) {
83 FREE(dct);
84 return NULL;
85 }
86
87 dct->_object = tree;
88 dct->_inew = (inew_func)hb_dict_itor_new;
89 dct->_destroy = (destroy_func)hb_tree_destroy;
90 dct->_insert = (insert_func)hb_tree_insert;
91 dct->_probe = (probe_func)hb_tree_probe;
92 dct->_search = (search_func)hb_tree_search;
93 dct->_remove = (remove_func)hb_tree_remove;
94 dct->_empty = (empty_func)hb_tree_empty;
95 dct->_walk = (walk_func)hb_tree_walk;
96 dct->_count = (count_func)hb_tree_count;
97
98 return dct;
99 }
100
101 void
102 hb_tree_destroy(hb_tree *tree, int del)
103 {
104 ASSERT(tree != NULL);
105
106 if (tree->root)
107 hb_tree_empty(tree, del);
108
109 FREE(tree);
110 }
111
112 void
113 hb_tree_empty(hb_tree *tree, int del)
114 {
115 hb_node *node, *parent;
116
117 ASSERT(tree != NULL);
118
119 node = tree->root;
120
121 while (node) {
122 if (node->llink || node->rlink) {
123 node = node->llink ? node->llink : node->rlink;
124 continue;
125 }
126
127 if (del) {
128 if (tree->key_del)
129 tree->key_del(node->key);
130 if (tree->dat_del)
131 tree->dat_del(node->dat);
132 }
133
134 parent = node->parent;
135 FREE(node);
136
137 if (parent) {
138 if (parent->llink == node)
139 parent->llink = NULL;
140 else
141 parent->rlink = NULL;
142 }
143 node = parent;
144 }
145
146 tree->root = NULL;
147 tree->count = 0;
148 }
149
150 void *
151 hb_tree_search(hb_tree *tree, const void *key)
152 {
153 int rv;
154 hb_node *node;
155
156 ASSERT(tree != NULL);
157
158 node = tree->root;
159 while (node) {
160 rv = tree->key_cmp(key, node->key);
161 if (rv < 0)
162 node = node->llink;
163 else if (rv > 0)
164 node = node->rlink;
165 else
166 return node->dat;
167 }
168
169 return NULL;
170 }
171
172 int
173 hb_tree_insert(hb_tree *tree, void *key, void *dat, int overwrite)
174 {
175 int rv = 0;
176 hb_node *node, *parent = NULL, *q = NULL;
177
178 ASSERT(tree != NULL);
179
180 node = tree->root;
181 while (node) {
182 rv = tree->key_cmp(key, node->key);
183 if (rv < 0)
184 parent = node, node = node->llink;
185 else if (rv > 0)
186 parent = node, node = node->rlink;
187 else {
188 if (overwrite == 0)
189 return 1;
190 if (tree->key_del)
191 tree->key_del(node->key);
192 if (tree->dat_del)
193 tree->dat_del(node->dat);
194 node->key = key;
195 node->dat = dat;
196 return 0;
197 }
198 if (parent->bal)
199 q = parent;
200 }
201
202 if ((node = node_new(key, dat)) == NULL)
203 return -1;
204 if ((node->parent = parent) == NULL) {
205 tree->root = node;
206 ASSERT(tree->count == 0);
207 tree->count = 1;
208 return 0;
209 }
210 if (rv < 0)
211 parent->llink = node;
212 else
213 parent->rlink = node;
214
215 while (parent != q) {
216 parent->bal = (parent->rlink == node) * 2 - 1;
217 node = parent;
218 parent = node->parent;
219 }
220 if (q) {
221 if (q->llink == node) {
222 if (--q->bal == -2) {
223 if (q->llink->bal > 0)
224 rot_left(tree, q->llink);
225 rot_right(tree, q);
226 }
227 } else {
228 if (++q->bal == +2) {
229 if (q->rlink->bal < 0)
230 rot_right(tree, q->rlink);
231 rot_left(tree, q);
232 }
233 }
234 }
235 tree->count++;
236 return 0;
237 }
238
239 int
240 hb_tree_probe(hb_tree *tree, void *key, void **dat)
241 {
242 int rv = 0;
243 hb_node *node, *parent = NULL, *q = NULL;
244
245 ASSERT(tree != NULL);
246
247 node = tree->root;
248 while (node) {
249 rv = tree->key_cmp(key, node->key);
250 if (rv < 0)
251 parent = node, node = node->llink;
252 else if (rv > 0)
253 parent = node, node = node->rlink;
254 else {
255 *dat = node->dat;
256 return 0;
257 }
258 if (parent->bal)
259 q = parent;
260 }
261
262 if ((node = node_new(key, *dat)) == NULL)
263 return -1;
264 if ((node->parent = parent) == NULL) {
265 tree->root = node;
266 ASSERT(tree->count == 0);
267 tree->count = 1;
268 return 1;
269 }
270 if (rv < 0)
271 parent->llink = node;
272 else
273 parent->rlink = node;
274
275 while (parent != q) {
276 parent->bal = (parent->rlink == node) * 2 - 1;
277 node = parent;
278 parent = parent->parent;
279 }
280 if (q) {
281 if (q->llink == node) {
282 if (--q->bal == -2) {
283 if (q->llink->bal > 0)
284 rot_left(tree, q->llink);
285 rot_right(tree, q);
286 }
287 } else {
288 if (++q->bal == +2) {
289 if (q->rlink->bal < 0)
290 rot_right(tree, q->rlink);
291 rot_left(tree, q);
292 }
293 }
294 }
295 tree->count++;
296 return 1;
297 }
298
299 #define FREE_NODE(n) \
300 if (del) { \
301 if (tree->key_del) \
302 tree->key_del((n)->key); \
303 if (tree->dat_del) \
304 tree->dat_del((n)->dat); \
305 } \
306 FREE(n)
307
308 int
309 hb_tree_remove(hb_tree *tree, const void *key, int del)
310 {
311 int rv, left;
312 hb_node *node, *out, *parent = NULL;
313 void *tmp;
314
315 ASSERT(tree != NULL);
316
317 node = tree->root;
318 while (node) {
319 rv = tree->key_cmp(key, node->key);
320 if (rv == 0)
321 break;
322 parent = node;
323 node = rv < 0 ? node->llink : node->rlink;
324 }
325 if (node == NULL)
326 return -1;
327
328 if (node->llink && node->rlink) {
329 for (out = node->rlink; out->llink; out = out->llink)
330 ;
331 SWAP(node->key, out->key, tmp);
332 SWAP(node->dat, out->dat, tmp);
333 node = out;
334 parent = out->parent;
335 }
336
337 out = node->llink ? node->llink : node->rlink;
338 FREE_NODE(node);
339 if (out)
340 out->parent = parent;
341 if (parent == NULL) {
342 tree->root = out;
343 tree->count--;
344 return 0;
345 }
346
347 left = parent->llink == node;
348 if (left)
349 parent->llink = out;
350 else
351 parent->rlink = out;
352
353 for (;;) {
354 if (left) {
355 if (++parent->bal == 0) {
356 node = parent;
357 goto higher;
358 }
359 if (parent->bal == +2) {
360 ASSERT(parent->rlink != NULL);
361 if (parent->rlink->bal < 0) {
362 rot_right(tree, parent->rlink);
363 rot_left(tree, parent);
364 } else {
365 ASSERT(parent->rlink->rlink != NULL);
366 if (rot_left(tree, parent) == 0)
367 break;
368 }
369 } else {
370 break;
371 }
372 } else {
373 if (--parent->bal == 0) {
374 node = parent;
375 goto higher;
376 }
377 if (parent->bal == -2) {
378 ASSERT(parent->llink != NULL);
379 if (parent->llink->bal > 0) {
380 rot_left(tree, parent->llink);
381 rot_right(tree, parent);
382 } else {
383 ASSERT(parent->llink->llink != NULL);
384 if (rot_right(tree, parent) == 0)
385 break;
386 }
387 } else {
388 break;
389 }
390 }
391
392
393
394
395 node = parent->parent;
396 higher:
397 if ((parent = node->parent) == NULL)
398 break;
399 left = parent->llink == node;
400 }
401 tree->count--;
402 return 0;
403 }
404
405 const void *
406 hb_tree_min(const hb_tree *tree)
407 {
408 const hb_node *node;
409
410 ASSERT(tree != NULL);
411
412 if (tree->root == NULL)
413 return NULL;
414
415 for (node = tree->root; node->llink; node = node->llink)
416 ;
417 return node->key;
418 }
419
420 const void *
421 hb_tree_max(const hb_tree *tree)
422 {
423 const hb_node *node;
424
425 ASSERT(tree != NULL);
426
427 if ((node = tree->root) == NULL)
428 return NULL;
429
430 for (; node->rlink; node = node->rlink)
431 ;
432 return node->key;
433 }
434
435 void
436 hb_tree_walk(hb_tree *tree, dict_vis_func visit)
437 {
438 hb_node *node;
439
440 ASSERT(tree != NULL);
441
442 if (tree->root == NULL)
443 return;
444 for (node = node_min(tree->root); node; node = node_next(node))
445 if (visit(node->key, node->dat) == 0)
446 break;
447 }
448
449 unsigned
450 hb_tree_count(const hb_tree *tree)
451 {
452 ASSERT(tree != NULL);
453
454 return tree->count;
455 }
456
457 unsigned
458 hb_tree_height(const hb_tree *tree)
459 {
460 ASSERT(tree != NULL);
461
462 return tree->root ? node_height(tree->root) : 0;
463 }
464
465 unsigned
466 hb_tree_mheight(const hb_tree *tree)
467 {
468 ASSERT(tree != NULL);
469
470 return tree->root ? node_mheight(tree->root) : 0;
471 }
472
473 unsigned
474 hb_tree_pathlen(const hb_tree *tree)
475 {
476 ASSERT(tree != NULL);
477
478 return tree->root ? node_pathlen(tree->root, 1) : 0;
479 }
480
481 static hb_node *
482 node_new(void *key, void *dat)
483 {
484 hb_node *node;
485
486 if ((node = (hb_node*)MALLOC(sizeof(*node))) == NULL)
487 return NULL;
488
489 node->key = key;
490 node->dat = dat;
491 node->parent = NULL;
492 node->llink = NULL;
493 node->rlink = NULL;
494 node->bal = 0;
495
496 return node;
497 }
498
499 static hb_node *
500 node_min(hb_node *node)
501 {
502 ASSERT(node != NULL);
503
504 while (node->llink)
505 node = node->llink;
506 return node;
507 }
508
509 static hb_node *
510 node_max(hb_node *node)
511 {
512 ASSERT(node != NULL);
513
514 while (node->rlink)
515 node = node->rlink;
516 return node;
517 }
518
519 static hb_node *
520 node_next(hb_node *node)
521 {
522 hb_node *temp;
523
524 ASSERT(node != NULL);
525
526 if (node->rlink) {
527 for (node = node->rlink; node->llink; node = node->llink)
528 ;
529 return node;
530 }
531 temp = node->parent;
532 while (temp && temp->rlink == node) {
533 node = temp;
534 temp = temp->parent;
535 }
536 return temp;
537 }
538
539 static hb_node *
540 node_prev(hb_node *node)
541 {
542 hb_node *temp;
543
544 ASSERT(node != NULL);
545
546 if (node->llink) {
547 for (node = node->llink; node->rlink; node = node->rlink)
548 ;
549 return node;
550 }
551 temp = node->parent;
552 while (temp && temp->llink == node) {
553 node = temp;
554 temp = temp->parent;
555 }
556 return temp;
557 }
558
559 static unsigned
560 node_height(const hb_node *node)
561 {
562 unsigned l, r;
563
564 ASSERT(node != NULL);
565
566 l = node->llink ? node_height(node->llink) + 1 : 0;
567 r = node->rlink ? node_height(node->rlink) + 1 : 0;
568 return MAX(l, r);
569 }
570
571 static unsigned
572 node_mheight(const hb_node *node)
573 {
574 unsigned l, r;
575
576 ASSERT(node != NULL);
577
578 l = node->llink ? node_mheight(node->llink) + 1 : 0;
579 r = node->rlink ? node_mheight(node->rlink) + 1 : 0;
580 return MIN(l, r);
581 }
582
583 static unsigned
584 node_pathlen(const hb_node *node, unsigned level)
585 {
586 unsigned n = 0;
587
588 ASSERT(node != NULL);
589
590 if (node->llink)
591 n += level + node_pathlen(node->llink, level + 1);
592 if (node->rlink)
593 n += level + node_pathlen(node->rlink, level + 1);
594 return n;
595 }
596
597
598
599
600
601
602
603
604
605
606
607
608 static int
609 rot_left(hb_tree *tree, hb_node *node)
610 {
611 int hc;
612 hb_node *rlink, *parent;
613
614 ASSERT(tree != NULL);
615 ASSERT(node != NULL);
616 ASSERT(node->rlink != NULL);
617
618 rlink = node->rlink;
619 node->rlink = rlink->llink;
620 if (rlink->llink)
621 rlink->llink->parent = node;
622 parent = node->parent;
623 rlink->parent = parent;
624 if (parent) {
625 if (parent->llink == node)
626 parent->llink = rlink;
627 else
628 parent->rlink = rlink;
629 } else {
630 tree->root = rlink;
631 }
632 rlink->llink = node;
633 node->parent = rlink;
634
635 hc = rlink->bal != 0;
636 node->bal -= 1 + MAX(rlink->bal, 0);
637 rlink->bal -= 1 - MIN(node->bal, 0);
638 return hc;
639 }
640
641
642
643
644
645
646
647
648
649
650
651
652 static int
653 rot_right(hb_tree *tree, hb_node *node)
654 {
655 int hc;
656 hb_node *llink, *parent;
657
658 ASSERT(tree != NULL);
659 ASSERT(node != NULL);
660 ASSERT(node->llink != NULL);
661
662 llink = node->llink;
663 node->llink = llink->rlink;
664 if (llink->rlink)
665 llink->rlink->parent = node;
666 parent = node->parent;
667 llink->parent = parent;
668 if (parent) {
669 if (parent->llink == node)
670 parent->llink = llink;
671 else
672 parent->rlink = llink;
673 } else {
674 tree->root = llink;
675 }
676 llink->rlink = node;
677 node->parent = llink;
678
679 hc = llink->bal != 0;
680 node->bal += 1 - MIN(llink->bal, 0);
681 llink->bal += 1 + MAX(node->bal, 0);
682 return hc;
683 }
684
685 hb_itor *
686 hb_itor_new(hb_tree *tree)
687 {
688 hb_itor *itor;
689
690 ASSERT(tree != NULL);
691
692 if ((itor = (hb_itor*)MALLOC(sizeof(*itor))) == NULL)
693 return NULL;
694
695 itor->tree = tree;
696 hb_itor_first(itor);
697 return itor;
698 }
699
700 dict_itor *
701 hb_dict_itor_new(hb_tree *tree)
702 {
703 dict_itor *itor;
704
705 ASSERT(tree != NULL);
706
707 if ((itor = (dict_itor*)MALLOC(sizeof(*itor))) == NULL)
708 return NULL;
709
710 if ((itor->_itor = hb_itor_new(tree)) == NULL) {
711 FREE(itor);
712 return NULL;
713 }
714
715 itor->_destroy = (idestroy_func)hb_itor_destroy;
716 itor->_valid = (valid_func)hb_itor_valid;
717 itor->_invalid = (invalidate_func)hb_itor_invalidate;
718 itor->_next = (next_func)hb_itor_next;
719 itor->_prev = (prev_func)hb_itor_prev;
720 itor->_nextn = (nextn_func)hb_itor_nextn;
721 itor->_prevn = (prevn_func)hb_itor_prevn;
722 itor->_first = (first_func)hb_itor_first;
723 itor->_last = (last_func)hb_itor_last;
724 itor->_search = (isearch_func)hb_itor_search;
725 itor->_key = (key_func)hb_itor_key;
726 itor->_data = (data_func)hb_itor_data;
727 itor->_cdata = (cdata_func)hb_itor_cdata;
728 itor->_setdata = (dataset_func)hb_itor_set_data;
729
730 return itor;
731 }
732
733 void
734 hb_itor_destroy(hb_itor *itor)
735 {
736 ASSERT(itor != NULL);
737
738 FREE(itor);
739 }
740
741 #define RETVALID(itor) return itor->node != NULL
742
743 int
744 hb_itor_valid(const hb_itor *itor)
745 {
746 ASSERT(itor != NULL);
747
748 RETVALID(itor);
749 }
750
751 void
752 hb_itor_invalidate(hb_itor *itor)
753 {
754 ASSERT(itor != NULL);
755
756 itor->node = NULL;
757 }
758
759 int
760 hb_itor_next(hb_itor *itor)
761 {
762 ASSERT(itor != NULL);
763
764 if (itor->node == NULL)
765 hb_itor_first(itor);
766 else
767 itor->node = node_next(itor->node);
768 RETVALID(itor);
769 }
770
771 int
772 hb_itor_prev(hb_itor *itor)
773 {
774 ASSERT(itor != NULL);
775
776 if (itor->node == NULL)
777 hb_itor_last(itor);
778 else
779 itor->node = node_prev(itor->node);
780 RETVALID(itor);
781 }
782
783 int
784 hb_itor_nextn(hb_itor *itor, unsigned count)
785 {
786 ASSERT(itor != NULL);
787
788 if (count) {
789 if (itor->node == NULL) {
790 hb_itor_first(itor);
791 count--;
792 }
793
794 while (count-- && itor->node)
795 itor->node = node_next(itor->node);
796 }
797
798 RETVALID(itor);
799 }
800
801 int
802 hb_itor_prevn(hb_itor *itor, unsigned count)
803 {
804 ASSERT(itor != NULL);
805
806 if (count) {
807 if (itor->node == NULL) {
808 hb_itor_last(itor);
809 count--;
810 }
811
812 while (count-- && itor->node)
813 itor->node = node_prev(itor->node);
814 }
815
816 RETVALID(itor);
817 }
818
819 int
820 hb_itor_first(hb_itor *itor)
821 {
822 hb_tree *t;
823
824 ASSERT(itor != NULL);
825
826 t = itor->tree;
827 itor->node = t->root ? node_min(t->root) : NULL;
828 RETVALID(itor);
829 }
830
831 int
832 hb_itor_last(hb_itor *itor)
833 {
834 hb_tree *t;
835
836 ASSERT(itor != NULL);
837
838 t = itor->tree;
839 itor->node = t->root ? node_max(t->root) : NULL;
840 RETVALID(itor);
841 }
842
843 int
844 hb_itor_search(hb_itor *itor, const void *key)
845 {
846 int rv;
847 hb_node *node;
848 dict_cmp_func cmp;
849
850 ASSERT(itor != NULL);
851
852 cmp = itor->tree->key_cmp;
853 for (node = itor->tree->root; node;) {
854 rv = cmp(key, node->key);
855 if (rv == 0)
856 break;
857 node = rv < 0 ? node->llink : node->rlink;
858 }
859 itor->node = node;
860 RETVALID(itor);
861 }
862
863 const void *
864 hb_itor_key(const hb_itor *itor)
865 {
866 ASSERT(itor != NULL);
867
868 return itor->node ? itor->node->key : NULL;
869 }
870
871 void *
872 hb_itor_data(hb_itor *itor)
873 {
874 ASSERT(itor != NULL);
875
876 return itor->node ? itor->node->dat : NULL;
877 }
878
879 const void *
880 hb_itor_cdata(const hb_itor *itor)
881 {
882 ASSERT(itor != NULL);
883
884 return itor->node ? itor->node->dat : NULL;
885 }
886
887 int
888 hb_itor_set_data(hb_itor *itor, void *dat, int del)
889 {
890 ASSERT(itor != NULL);
891
892 if (itor->node == NULL)
893 return -1;
894
895 if (del && itor->tree->dat_del)
896 itor->tree->dat_del(itor->node->dat);
897 itor->node->dat = dat;
898 return 0;
899 }