hfscommon/headers/RedBlackTree.h

74  * thus making node linkage as compact as is possible for red-black trees.
308  * Find a match if it exists.  Otherwise, find the next greater node, if one
329  * Find a match if it exists.  Otherwise, find the previous lesser node, if one
458 			/* rbp_i_c is the top of a logical 4-node, so split it.   */\
460 			/* disruptiveness of node splitting.                      */\
504     /* rbp_i_p now refers to the node under which to insert.          */\
534     /* node is not a 2-node.  This allows simple deletion once a leaf */\
536     /* be no way to convert it from a 2-node to a 3-node.             */\
557 				/* Delete root node (which is also a leaf node).      */\
566 				/* This is the node we want to delete, but we will    */\
611 					/* rbp_r_c now refers to the successor node to    */\
646 				/* Check whether to delete this node (it has to be    */\
647 				/* the correct node and a leaf node).                 */\
651 						/* Delete leaf node.                          */\
665 						/* This is the node we want to delete, but we */\
721 a_prefix##next(a_tree_type *tree, a_type *node) {			\
723     rb_next(a_type, a_field, a_cmp, tree, node, ret);			\
727 a_prefix##prev(a_tree_type *tree, a_type *node) {			\
729     rb_prev(a_type, a_field, a_cmp, tree, node, ret);			\
751 a_prefix##insert(a_tree_type *tree, a_type *node) {			\
752     rb_insert(a_type, a_field, a_cmp, tree, node);			\
755 a_prefix##remove(a_tree_type *tree, a_type *node) {			\
756     rb_remove(a_type, a_field, a_cmp, tree, node);			\
770  *       a_type *node, *tnode;
772  *       rb_foreach_begin(a_type, a_field, a_tree, node) {
774  *           rb_next(a_type, a_field, a_cmp, a_tree, node, tnode);
775  *           rb_remove(a_type, a_field, a_cmp, a_tree, node);
778  *       } rb_foreach_end(a_type, a_field, a_tree, node)
854 				/* The successor is the left-most node in the right   */\
864 				/* The successor is above the current node.  Unwind   */\
945 				/* The predecessor is the right-most node in the left */\
955 				/* The predecessor is above the current node.  Unwind */\