libarchive/libarchive/archive_rb.c

71 #define	RB_ROOT_P(rbt, rb)	((rbt)->rbt_root == (rb))
95 __archive_rb_tree_init(struct archive_rb_tree *rbt,
98 	rbt->rbt_ops = ops;
99 	*((struct archive_rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE;
103 __archive_rb_tree_find_node(struct archive_rb_tree *rbt, const void *key)
105 	archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
106 	struct archive_rb_node *parent = rbt->rbt_root;
119 __archive_rb_tree_find_node_geq(struct archive_rb_tree *rbt, const void *key)
121 	archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
122 	struct archive_rb_node *parent = rbt->rbt_root;
138 __archive_rb_tree_find_node_leq(struct archive_rb_tree *rbt, const void *key)
140 	archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
141 	struct archive_rb_node *parent = rbt->rbt_root;
158 __archive_rb_tree_insert_node(struct archive_rb_tree *rbt,
161 	archive_rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes;
166 	tmp = rbt->rbt_root;
168 	 * This is a hack.  Because rbt->rbt_root is just a
173 	 * update rbt->rbt_root.
175 	parent = (struct archive_rb_node *)(void *)&rbt->rbt_root;
199 	if (parent == (struct archive_rb_node *)(void *)&rbt->rbt_root) {
218 		__archive_rb_tree_insert_rebalance(rbt, self);
276 __archive_rb_tree_insert_rebalance(struct archive_rb_tree *rbt,
306 		if (RB_ROOT_P(rbt, grandpa)) {
347 	RB_MARK_BLACK(rbt->rbt_root);
352 __archive_rb_tree_prune_node(struct archive_rb_tree *rbt,
368 		__archive_rb_tree_removal_rebalance(rbt, father, which);
376 __archive_rb_tree_swap_prune_and_rebalance(struct archive_rb_tree *rbt,
468 		__archive_rb_tree_removal_rebalance(rbt, standin_father, standin_which);
473  *	__archive_rb_tree_node_swap(rbt, self, which);
474  *	__archive_rb_tree_prune_node(rbt, self, F);
497 __archive_rb_tree_remove_node(struct archive_rb_tree *rbt,
521 		const int rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
522 		__archive_rb_tree_prune_node(rbt, self, rebalance);
549 	standin = __archive_rb_tree_iterate(rbt, self, which);
550 	__archive_rb_tree_swap_prune_and_rebalance(rbt, self, standin);
554 __archive_rb_tree_removal_rebalance(struct archive_rb_tree *rbt,
598 				if (RB_ROOT_P(rbt, parent))
680 __archive_rb_tree_iterate(struct archive_rb_tree *rbt,
686 		self = rbt->rbt_root;
698 		while (!RB_ROOT_P(rbt, self)) {