![Logo](../../1_trinitycore.png) |
TrinityCore
|
Go to the documentation of this file.
27 #define rb_node(a_type) \
30 a_type *rbn_right_red; \
33 #define rb_node(a_type) \
42 #define rb_tree(a_type) \
49 #define rbtn_left_get(a_type, a_field, a_node) \
50 ((a_node)->a_field.rbn_left)
51 #define rbtn_left_set(a_type, a_field, a_node, a_left) do { \
52 (a_node)->a_field.rbn_left = a_left; \
57 #define rbtn_right_get(a_type, a_field, a_node) \
58 ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \
60 #define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
61 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
62 | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \
66 #define rbtn_red_get(a_type, a_field, a_node) \
67 ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \
69 #define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
70 (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \
71 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \
72 | ((ssize_t)a_red)); \
74 #define rbtn_red_set(a_type, a_field, a_node) do { \
75 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \
76 (a_node)->a_field.rbn_right_red) | ((size_t)1)); \
78 #define rbtn_black_set(a_type, a_field, a_node) do { \
79 (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \
80 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \
84 #define rbtn_right_get(a_type, a_field, a_node) \
85 ((a_node)->a_field.rbn_right)
86 #define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
87 (a_node)->a_field.rbn_right = a_right; \
91 #define rbtn_red_get(a_type, a_field, a_node) \
92 ((a_node)->a_field.rbn_red)
93 #define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
94 (a_node)->a_field.rbn_red = (a_red); \
96 #define rbtn_red_set(a_type, a_field, a_node) do { \
97 (a_node)->a_field.rbn_red = true; \
99 #define rbtn_black_set(a_type, a_field, a_node) do { \
100 (a_node)->a_field.rbn_red = false; \
105 #define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \
106 rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \
107 rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \
108 rbtn_red_set(a_type, a_field, (a_node)); \
112 #define rb_new(a_type, a_field, a_rbt) do { \
113 (a_rbt)->rbt_root = &(a_rbt)->rbt_nil; \
114 rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil); \
115 rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil); \
119 #define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \
120 (r_node) = (a_root); \
121 if ((r_node) != &(a_rbt)->rbt_nil) { \
123 rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\
124 (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \
129 #define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \
130 (r_node) = (a_root); \
131 if ((r_node) != &(a_rbt)->rbt_nil) { \
132 for (; rbtn_right_get(a_type, a_field, (r_node)) != \
133 &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \
139 #define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \
140 (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \
141 rbtn_right_set(a_type, a_field, (a_node), \
142 rbtn_left_get(a_type, a_field, (r_node))); \
143 rbtn_left_set(a_type, a_field, (r_node), (a_node)); \
146 #define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \
147 (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \
148 rbtn_left_set(a_type, a_field, (a_node), \
149 rbtn_right_get(a_type, a_field, (r_node))); \
150 rbtn_right_set(a_type, a_field, (r_node), (a_node)); \
158 #define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \
160 a_prefix##new(a_rbt_type *rbtree); \
162 a_prefix##first(a_rbt_type *rbtree); \
164 a_prefix##last(a_rbt_type *rbtree); \
166 a_prefix##next(a_rbt_type *rbtree, a_type *node); \
168 a_prefix##prev(a_rbt_type *rbtree, a_type *node); \
170 a_prefix##search(a_rbt_type *rbtree, a_type *key); \
172 a_prefix##nsearch(a_rbt_type *rbtree, a_type *key); \
174 a_prefix##psearch(a_rbt_type *rbtree, a_type *key); \
176 a_prefix##insert(a_rbt_type *rbtree, a_type *node); \
178 a_prefix##remove(a_rbt_type *rbtree, a_type *node); \
180 a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
181 a_rbt_type *, a_type *, void *), void *arg); \
183 a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
184 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg);
307 #define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \
309 a_prefix##new(a_rbt_type *rbtree) { \
310 rb_new(a_type, a_field, rbtree); \
313 a_prefix##first(a_rbt_type *rbtree) { \
315 rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
316 if (ret == &rbtree->rbt_nil) { \
322 a_prefix##last(a_rbt_type *rbtree) { \
324 rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
325 if (ret == &rbtree->rbt_nil) { \
331 a_prefix##next(a_rbt_type *rbtree, a_type *node) { \
333 if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) { \
334 rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \
335 a_field, node), ret); \
337 a_type *tnode = rbtree->rbt_root; \
338 assert(tnode != &rbtree->rbt_nil); \
339 ret = &rbtree->rbt_nil; \
341 int cmp = (a_cmp)(node, tnode); \
344 tnode = rbtn_left_get(a_type, a_field, tnode); \
345 } else if (cmp > 0) { \
346 tnode = rbtn_right_get(a_type, a_field, tnode); \
350 assert(tnode != &rbtree->rbt_nil); \
353 if (ret == &rbtree->rbt_nil) { \
359 a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \
361 if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) { \
362 rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \
363 a_field, node), ret); \
365 a_type *tnode = rbtree->rbt_root; \
366 assert(tnode != &rbtree->rbt_nil); \
367 ret = &rbtree->rbt_nil; \
369 int cmp = (a_cmp)(node, tnode); \
371 tnode = rbtn_left_get(a_type, a_field, tnode); \
372 } else if (cmp > 0) { \
374 tnode = rbtn_right_get(a_type, a_field, tnode); \
378 assert(tnode != &rbtree->rbt_nil); \
381 if (ret == &rbtree->rbt_nil) { \
387 a_prefix##search(a_rbt_type *rbtree, a_type *key) { \
390 ret = rbtree->rbt_root; \
391 while (ret != &rbtree->rbt_nil \
392 && (cmp = (a_cmp)(key, ret)) != 0) { \
394 ret = rbtn_left_get(a_type, a_field, ret); \
396 ret = rbtn_right_get(a_type, a_field, ret); \
399 if (ret == &rbtree->rbt_nil) { \
405 a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) { \
407 a_type *tnode = rbtree->rbt_root; \
408 ret = &rbtree->rbt_nil; \
409 while (tnode != &rbtree->rbt_nil) { \
410 int cmp = (a_cmp)(key, tnode); \
413 tnode = rbtn_left_get(a_type, a_field, tnode); \
414 } else if (cmp > 0) { \
415 tnode = rbtn_right_get(a_type, a_field, tnode); \
421 if (ret == &rbtree->rbt_nil) { \
427 a_prefix##psearch(a_rbt_type *rbtree, a_type *key) { \
429 a_type *tnode = rbtree->rbt_root; \
430 ret = &rbtree->rbt_nil; \
431 while (tnode != &rbtree->rbt_nil) { \
432 int cmp = (a_cmp)(key, tnode); \
434 tnode = rbtn_left_get(a_type, a_field, tnode); \
435 } else if (cmp > 0) { \
437 tnode = rbtn_right_get(a_type, a_field, tnode); \
443 if (ret == &rbtree->rbt_nil) { \
449 a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \
453 } path[sizeof(void *) << 4], *pathp; \
454 rbt_node_new(a_type, a_field, rbtree, node); \
456 path->node = rbtree->rbt_root; \
457 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
458 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
461 pathp[1].node = rbtn_left_get(a_type, a_field, \
464 pathp[1].node = rbtn_right_get(a_type, a_field, \
468 pathp->node = node; \
470 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
471 a_type *cnode = pathp->node; \
472 if (pathp->cmp < 0) { \
473 a_type *left = pathp[1].node; \
474 rbtn_left_set(a_type, a_field, cnode, left); \
475 if (rbtn_red_get(a_type, a_field, left)) { \
476 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
477 if (rbtn_red_get(a_type, a_field, leftleft)) { \
480 rbtn_black_set(a_type, a_field, leftleft); \
481 rbtn_rotate_right(a_type, a_field, cnode, tnode); \
488 a_type *right = pathp[1].node; \
489 rbtn_right_set(a_type, a_field, cnode, right); \
490 if (rbtn_red_get(a_type, a_field, right)) { \
491 a_type *left = rbtn_left_get(a_type, a_field, cnode); \
492 if (rbtn_red_get(a_type, a_field, left)) { \
494 rbtn_black_set(a_type, a_field, left); \
495 rbtn_black_set(a_type, a_field, right); \
496 rbtn_red_set(a_type, a_field, cnode); \
500 bool tred = rbtn_red_get(a_type, a_field, cnode); \
501 rbtn_rotate_left(a_type, a_field, cnode, tnode); \
502 rbtn_color_set(a_type, a_field, tnode, tred); \
503 rbtn_red_set(a_type, a_field, cnode); \
510 pathp->node = cnode; \
513 rbtree->rbt_root = path->node; \
514 rbtn_black_set(a_type, a_field, rbtree->rbt_root); \
517 a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \
521 } *pathp, *nodep, path[sizeof(void *) << 4]; \
524 path->node = rbtree->rbt_root; \
525 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
526 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
528 pathp[1].node = rbtn_left_get(a_type, a_field, \
531 pathp[1].node = rbtn_right_get(a_type, a_field, \
537 for (pathp++; pathp->node != &rbtree->rbt_nil; \
540 pathp[1].node = rbtn_left_get(a_type, a_field, \
547 assert(nodep->node == node); \
549 if (pathp->node != node) { \
551 bool tred = rbtn_red_get(a_type, a_field, pathp->node); \
552 rbtn_color_set(a_type, a_field, pathp->node, \
553 rbtn_red_get(a_type, a_field, node)); \
554 rbtn_left_set(a_type, a_field, pathp->node, \
555 rbtn_left_get(a_type, a_field, node)); \
560 rbtn_right_set(a_type, a_field, pathp->node, \
561 rbtn_right_get(a_type, a_field, node)); \
562 rbtn_color_set(a_type, a_field, node, tred); \
565 nodep->node = pathp->node; \
566 pathp->node = node; \
567 if (nodep == path) { \
568 rbtree->rbt_root = nodep->node; \
570 if (nodep[-1].cmp < 0) { \
571 rbtn_left_set(a_type, a_field, nodep[-1].node, \
574 rbtn_right_set(a_type, a_field, nodep[-1].node, \
579 a_type *left = rbtn_left_get(a_type, a_field, node); \
580 if (left != &rbtree->rbt_nil) { \
583 assert(rbtn_red_get(a_type, a_field, node) == false); \
584 assert(rbtn_red_get(a_type, a_field, left)); \
585 rbtn_black_set(a_type, a_field, left); \
586 if (pathp == path) { \
587 rbtree->rbt_root = left; \
589 if (pathp[-1].cmp < 0) { \
590 rbtn_left_set(a_type, a_field, pathp[-1].node, \
593 rbtn_right_set(a_type, a_field, pathp[-1].node, \
598 } else if (pathp == path) { \
600 rbtree->rbt_root = &rbtree->rbt_nil; \
604 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
606 assert(pathp[-1].cmp < 0); \
607 rbtn_left_set(a_type, a_field, pathp[-1].node, \
613 pathp->node = &rbtree->rbt_nil; \
614 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
615 assert(pathp->cmp != 0); \
616 if (pathp->cmp < 0) { \
617 rbtn_left_set(a_type, a_field, pathp->node, \
619 assert(rbtn_red_get(a_type, a_field, pathp[1].node) \
621 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
622 a_type *right = rbtn_right_get(a_type, a_field, \
624 a_type *rightleft = rbtn_left_get(a_type, a_field, \
627 if (rbtn_red_get(a_type, a_field, rightleft)) { \
638 rbtn_black_set(a_type, a_field, pathp->node); \
639 rbtn_rotate_right(a_type, a_field, right, tnode); \
640 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
641 rbtn_rotate_left(a_type, a_field, pathp->node, \
651 rbtn_rotate_left(a_type, a_field, pathp->node, \
656 assert((uintptr_t)pathp > (uintptr_t)path); \
657 if (pathp[-1].cmp < 0) { \
658 rbtn_left_set(a_type, a_field, pathp[-1].node, \
661 rbtn_right_set(a_type, a_field, pathp[-1].node, \
666 a_type *right = rbtn_right_get(a_type, a_field, \
668 a_type *rightleft = rbtn_left_get(a_type, a_field, \
670 if (rbtn_red_get(a_type, a_field, rightleft)) { \
678 rbtn_black_set(a_type, a_field, rightleft); \
679 rbtn_rotate_right(a_type, a_field, right, tnode); \
680 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
681 rbtn_rotate_left(a_type, a_field, pathp->node, \
686 if (pathp == path) { \
688 rbtree->rbt_root = tnode; \
690 if (pathp[-1].cmp < 0) { \
691 rbtn_left_set(a_type, a_field, \
692 pathp[-1].node, tnode); \
694 rbtn_right_set(a_type, a_field, \
695 pathp[-1].node, tnode); \
707 rbtn_red_set(a_type, a_field, pathp->node); \
708 rbtn_rotate_left(a_type, a_field, pathp->node, \
710 pathp->node = tnode; \
715 rbtn_right_set(a_type, a_field, pathp->node, \
717 left = rbtn_left_get(a_type, a_field, pathp->node); \
718 if (rbtn_red_get(a_type, a_field, left)) { \
720 a_type *leftright = rbtn_right_get(a_type, a_field, \
722 a_type *leftrightleft = rbtn_left_get(a_type, a_field, \
724 if (rbtn_red_get(a_type, a_field, leftrightleft)) { \
734 rbtn_black_set(a_type, a_field, leftrightleft); \
735 rbtn_rotate_right(a_type, a_field, pathp->node, \
737 rbtn_rotate_right(a_type, a_field, pathp->node, \
739 rbtn_right_set(a_type, a_field, unode, tnode); \
740 rbtn_rotate_left(a_type, a_field, unode, tnode); \
750 assert(leftright != &rbtree->rbt_nil); \
751 rbtn_red_set(a_type, a_field, leftright); \
752 rbtn_rotate_right(a_type, a_field, pathp->node, \
754 rbtn_black_set(a_type, a_field, tnode); \
758 if (pathp == path) { \
760 rbtree->rbt_root = tnode; \
762 if (pathp[-1].cmp < 0) { \
763 rbtn_left_set(a_type, a_field, pathp[-1].node, \
766 rbtn_right_set(a_type, a_field, pathp[-1].node, \
771 } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \
772 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
773 if (rbtn_red_get(a_type, a_field, leftleft)) { \
781 rbtn_black_set(a_type, a_field, pathp->node); \
782 rbtn_red_set(a_type, a_field, left); \
783 rbtn_black_set(a_type, a_field, leftleft); \
784 rbtn_rotate_right(a_type, a_field, pathp->node, \
788 assert((uintptr_t)pathp > (uintptr_t)path); \
789 if (pathp[-1].cmp < 0) { \
790 rbtn_left_set(a_type, a_field, pathp[-1].node, \
793 rbtn_right_set(a_type, a_field, pathp[-1].node, \
804 rbtn_red_set(a_type, a_field, left); \
805 rbtn_black_set(a_type, a_field, pathp->node); \
810 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
811 if (rbtn_red_get(a_type, a_field, leftleft)) { \
819 rbtn_black_set(a_type, a_field, leftleft); \
820 rbtn_rotate_right(a_type, a_field, pathp->node, \
825 if (pathp == path) { \
827 rbtree->rbt_root = tnode; \
829 if (pathp[-1].cmp < 0) { \
830 rbtn_left_set(a_type, a_field, \
831 pathp[-1].node, tnode); \
833 rbtn_right_set(a_type, a_field, \
834 pathp[-1].node, tnode); \
845 rbtn_red_set(a_type, a_field, left); \
851 rbtree->rbt_root = path->node; \
852 assert(rbtn_red_get(a_type, a_field, rbtree->rbt_root) == false); \
855 a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \
856 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
857 if (node == &rbtree->rbt_nil) { \
858 return (&rbtree->rbt_nil); \
861 if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \
862 a_field, node), cb, arg)) != &rbtree->rbt_nil \
863 || (ret = cb(rbtree, node, arg)) != NULL) { \
866 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
867 a_field, node), cb, arg)); \
871 a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \
872 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
873 int cmp = a_cmp(start, node); \
876 if ((ret = a_prefix##iter_start(rbtree, start, \
877 rbtn_left_get(a_type, a_field, node), cb, arg)) != \
878 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
881 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
882 a_field, node), cb, arg)); \
883 } else if (cmp > 0) { \
884 return (a_prefix##iter_start(rbtree, start, \
885 rbtn_right_get(a_type, a_field, node), cb, arg)); \
888 if ((ret = cb(rbtree, node, arg)) != NULL) { \
891 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
892 a_field, node), cb, arg)); \
896 a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
897 a_rbt_type *, a_type *, void *), void *arg) { \
899 if (start != NULL) { \
900 ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \
903 ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\
905 if (ret == &rbtree->rbt_nil) { \
911 a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \
912 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
913 if (node == &rbtree->rbt_nil) { \
914 return (&rbtree->rbt_nil); \
917 if ((ret = a_prefix##reverse_iter_recurse(rbtree, \
918 rbtn_right_get(a_type, a_field, node), cb, arg)) != \
919 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
922 return (a_prefix##reverse_iter_recurse(rbtree, \
923 rbtn_left_get(a_type, a_field, node), cb, arg)); \
927 a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \
928 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \
930 int cmp = a_cmp(start, node); \
933 if ((ret = a_prefix##reverse_iter_start(rbtree, start, \
934 rbtn_right_get(a_type, a_field, node), cb, arg)) != \
935 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
938 return (a_prefix##reverse_iter_recurse(rbtree, \
939 rbtn_left_get(a_type, a_field, node), cb, arg)); \
940 } else if (cmp < 0) { \
941 return (a_prefix##reverse_iter_start(rbtree, start, \
942 rbtn_left_get(a_type, a_field, node), cb, arg)); \
945 if ((ret = cb(rbtree, node, arg)) != NULL) { \
948 return (a_prefix##reverse_iter_recurse(rbtree, \
949 rbtn_left_get(a_type, a_field, node), cb, arg)); \
953 a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
954 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
956 if (start != NULL) { \
957 ret = a_prefix##reverse_iter_start(rbtree, start, \
958 rbtree->rbt_root, cb, arg); \
960 ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \
963 if (ret == &rbtree->rbt_nil) { \