[mirror_frr.git] / lib / openbsd-tree.c

// SPDX-License-Identifier: ISC AND BSD-2-Clause
/*	$OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */

/*
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 */

/*
 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdlib.h>

#include <lib/openbsd-tree.h>

static inline struct rb_entry *rb_n2e(const struct rb_type *t, void *node)
{
	unsigned long addr = (unsigned long)node;

	return ((struct rb_entry *)(addr + t->t_offset));
}

static inline void *rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
{
	unsigned long addr = (unsigned long)rbe;

	return ((void *)(addr - t->t_offset));
}

#define RBE_LEFT(_rbe)		(_rbe)->rbt_left
#define RBE_RIGHT(_rbe)		(_rbe)->rbt_right
#define RBE_PARENT(_rbe)	(_rbe)->rbt_parent
#define RBE_COLOR(_rbe)		(_rbe)->rbt_color

#define RBH_ROOT(_rbt)		(_rbt)->rbt_root

static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
{
	RBE_PARENT(rbe) = parent;
	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
	RBE_COLOR(rbe) = RB_RED;
}

static inline void rbe_set_blackred(struct rb_entry *black,
				    struct rb_entry *red)
{
	RBE_COLOR(black) = RB_BLACK;
	RBE_COLOR(red) = RB_RED;
}

static inline void rbe_augment(const struct rb_type *t, struct rb_entry *rbe)
{
	(*t->t_augment)(rb_e2n(t, rbe));
}

static inline void rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
{
	if (t->t_augment != NULL)
		rbe_augment(t, rbe);
}

static inline void rbe_rotate_left(const struct rb_type *t,
				   struct rbt_tree *rbt, struct rb_entry *rbe)
{
	struct rb_entry *parent;
	struct rb_entry *tmp;

	tmp = RBE_RIGHT(rbe);
	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
	if (RBE_RIGHT(rbe) != NULL)
		RBE_PARENT(RBE_LEFT(tmp)) = rbe;

	parent = RBE_PARENT(rbe);
	RBE_PARENT(tmp) = parent;
	if (parent != NULL) {
		if (rbe == RBE_LEFT(parent))
			RBE_LEFT(parent) = tmp;
		else
			RBE_RIGHT(parent) = tmp;
	} else
		RBH_ROOT(rbt) = tmp;

	RBE_LEFT(tmp) = rbe;
	RBE_PARENT(rbe) = tmp;

	if (t->t_augment != NULL) {
		rbe_augment(t, rbe);
		rbe_augment(t, tmp);
		parent = RBE_PARENT(tmp);
		if (parent != NULL)
			rbe_augment(t, parent);
	}
}

static inline void rbe_rotate_right(const struct rb_type *t,
				    struct rbt_tree *rbt, struct rb_entry *rbe)
{
	struct rb_entry *parent;
	struct rb_entry *tmp;

	tmp = RBE_LEFT(rbe);
	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
	if (RBE_LEFT(rbe) != NULL)
		RBE_PARENT(RBE_RIGHT(tmp)) = rbe;

	parent = RBE_PARENT(rbe);
	RBE_PARENT(tmp) = parent;
	if (parent != NULL) {
		if (rbe == RBE_LEFT(parent))
			RBE_LEFT(parent) = tmp;
		else
			RBE_RIGHT(parent) = tmp;
	} else
		RBH_ROOT(rbt) = tmp;

	RBE_RIGHT(tmp) = rbe;
	RBE_PARENT(rbe) = tmp;

	if (t->t_augment != NULL) {
		rbe_augment(t, rbe);
		rbe_augment(t, tmp);
		parent = RBE_PARENT(tmp);
		if (parent != NULL)
			rbe_augment(t, parent);
	}
}

static inline void rbe_insert_color(const struct rb_type *t,
				    struct rbt_tree *rbt, struct rb_entry *rbe)
{
	struct rb_entry *parent, *gparent, *tmp;

	while ((parent = RBE_PARENT(rbe)) != NULL
	       && RBE_COLOR(parent) == RB_RED) {
		gparent = RBE_PARENT(parent);

		if (parent == RBE_LEFT(gparent)) {
			tmp = RBE_RIGHT(gparent);
			if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
				RBE_COLOR(tmp) = RB_BLACK;
				rbe_set_blackred(parent, gparent);
				rbe = gparent;
				continue;
			}

			if (RBE_RIGHT(parent) == rbe) {
				rbe_rotate_left(t, rbt, parent);
				tmp = parent;
				parent = rbe;
				rbe = tmp;
			}

			rbe_set_blackred(parent, gparent);
			rbe_rotate_right(t, rbt, gparent);
		} else {
			tmp = RBE_LEFT(gparent);
			if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
				RBE_COLOR(tmp) = RB_BLACK;
				rbe_set_blackred(parent, gparent);
				rbe = gparent;
				continue;
			}

			if (RBE_LEFT(parent) == rbe) {
				rbe_rotate_right(t, rbt, parent);
				tmp = parent;
				parent = rbe;
				rbe = tmp;
			}

			rbe_set_blackred(parent, gparent);
			rbe_rotate_left(t, rbt, gparent);
		}
	}

	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
}

static inline void rbe_remove_color(const struct rb_type *t,
				    struct rbt_tree *rbt,
				    struct rb_entry *parent,
				    struct rb_entry *rbe)
{
	struct rb_entry *tmp;

	while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
	       && rbe != RBH_ROOT(rbt) && parent) {
		if (RBE_LEFT(parent) == rbe) {
			tmp = RBE_RIGHT(parent);
			if (RBE_COLOR(tmp) == RB_RED) {
				rbe_set_blackred(tmp, parent);
				rbe_rotate_left(t, rbt, parent);
				tmp = RBE_RIGHT(parent);
			}
			if ((RBE_LEFT(tmp) == NULL
			     || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
			    && (RBE_RIGHT(tmp) == NULL
				|| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
				RBE_COLOR(tmp) = RB_RED;
				rbe = parent;
				parent = RBE_PARENT(rbe);
			} else {
				if (RBE_RIGHT(tmp) == NULL
				    || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
					struct rb_entry *oleft;

					oleft = RBE_LEFT(tmp);
					if (oleft != NULL)
						RBE_COLOR(oleft) = RB_BLACK;

					RBE_COLOR(tmp) = RB_RED;
					rbe_rotate_right(t, rbt, tmp);
					tmp = RBE_RIGHT(parent);
				}

				RBE_COLOR(tmp) = RBE_COLOR(parent);
				RBE_COLOR(parent) = RB_BLACK;
				if (RBE_RIGHT(tmp))
					RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;

				rbe_rotate_left(t, rbt, parent);
				rbe = RBH_ROOT(rbt);
				break;
			}
		} else {
			tmp = RBE_LEFT(parent);
			if (RBE_COLOR(tmp) == RB_RED) {
				rbe_set_blackred(tmp, parent);
				rbe_rotate_right(t, rbt, parent);
				tmp = RBE_LEFT(parent);
			}

			if ((RBE_LEFT(tmp) == NULL
			     || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
			    && (RBE_RIGHT(tmp) == NULL
				|| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
				RBE_COLOR(tmp) = RB_RED;
				rbe = parent;
				parent = RBE_PARENT(rbe);
			} else {
				if (RBE_LEFT(tmp) == NULL
				    || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
					struct rb_entry *oright;

					oright = RBE_RIGHT(tmp);
					if (oright != NULL)
						RBE_COLOR(oright) = RB_BLACK;

					RBE_COLOR(tmp) = RB_RED;
					rbe_rotate_left(t, rbt, tmp);
					tmp = RBE_LEFT(parent);
				}

				RBE_COLOR(tmp) = RBE_COLOR(parent);
				RBE_COLOR(parent) = RB_BLACK;
				if (RBE_LEFT(tmp) != NULL)
					RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;

				rbe_rotate_right(t, rbt, parent);
				rbe = RBH_ROOT(rbt);
				break;
			}
		}
	}

	if (rbe != NULL)
		RBE_COLOR(rbe) = RB_BLACK;
}

static inline struct rb_entry *
rbe_remove(const struct rb_type *t, struct rbt_tree *rbt, struct rb_entry *rbe)
{
	struct rb_entry *child, *parent, *old = rbe;
	unsigned int color;

	if (RBE_LEFT(rbe) == NULL)
		child = RBE_RIGHT(rbe);
	else if (RBE_RIGHT(rbe) == NULL)
		child = RBE_LEFT(rbe);
	else {
		struct rb_entry *tmp;

		rbe = RBE_RIGHT(rbe);
		while ((tmp = RBE_LEFT(rbe)) != NULL)
			rbe = tmp;

		child = RBE_RIGHT(rbe);
		parent = RBE_PARENT(rbe);
		color = RBE_COLOR(rbe);
		if (child != NULL)
			RBE_PARENT(child) = parent;
		if (parent != NULL) {
			if (RBE_LEFT(parent) == rbe)
				RBE_LEFT(parent) = child;
			else
				RBE_RIGHT(parent) = child;

			rbe_if_augment(t, parent);
		} else
			RBH_ROOT(rbt) = child;
		if (RBE_PARENT(rbe) == old)
			parent = rbe;
		*rbe = *old;

		tmp = RBE_PARENT(old);
		if (tmp != NULL) {
			if (RBE_LEFT(tmp) == old)
				RBE_LEFT(tmp) = rbe;
			else
				RBE_RIGHT(tmp) = rbe;

			rbe_if_augment(t, tmp);
		} else
			RBH_ROOT(rbt) = rbe;

		RBE_PARENT(RBE_LEFT(old)) = rbe;
		if (RBE_RIGHT(old))
			RBE_PARENT(RBE_RIGHT(old)) = rbe;

		if (t->t_augment != NULL && parent != NULL) {
			tmp = parent;
			do {
				rbe_augment(t, tmp);
				tmp = RBE_PARENT(tmp);
			} while (tmp != NULL);
		}

		goto color;
	}

	parent = RBE_PARENT(rbe);
	color = RBE_COLOR(rbe);

	if (child != NULL)
		RBE_PARENT(child) = parent;
	if (parent != NULL) {
		if (RBE_LEFT(parent) == rbe)
			RBE_LEFT(parent) = child;
		else
			RBE_RIGHT(parent) = child;

		rbe_if_augment(t, parent);
	} else
		RBH_ROOT(rbt) = child;
color:
	if (color == RB_BLACK)
		rbe_remove_color(t, rbt, parent, child);

	return (old);
}

void *_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
{
	struct rb_entry *rbe = rb_n2e(t, elm);
	struct rb_entry *old;

	old = rbe_remove(t, rbt, rbe);

	return (old == NULL ? NULL : rb_e2n(t, old));
}

void *_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
{
	struct rb_entry *rbe = rb_n2e(t, elm);
	struct rb_entry *tmp;
	struct rb_entry *parent = NULL;
	void *node;
	int comp = 0;

	tmp = RBH_ROOT(rbt);
	while (tmp != NULL) {
		parent = tmp;

		node = rb_e2n(t, tmp);
		comp = (*t->t_compare)(elm, node);
		if (comp < 0)
			tmp = RBE_LEFT(tmp);
		else if (comp > 0)
			tmp = RBE_RIGHT(tmp);
		else
			return (node);
	}

	rbe_set(rbe, parent);

	if (parent != NULL) {
		if (comp < 0)
			RBE_LEFT(parent) = rbe;
		else
			RBE_RIGHT(parent) = rbe;

		rbe_if_augment(t, parent);
	} else
		RBH_ROOT(rbt) = rbe;

	rbe_insert_color(t, rbt, rbe);

	return NULL;
}

/* Finds the node with the same key as elm */
void *_rb_find(const struct rb_type *t, const struct rbt_tree *rbt,
	       const void *key)
{
	struct rb_entry *tmp = RBH_ROOT(rbt);
	void *node;
	int comp;

	while (tmp != NULL) {
		node = rb_e2n(t, tmp);
		comp = (*t->t_compare)(key, node);
		if (comp < 0)
			tmp = RBE_LEFT(tmp);
		else if (comp > 0)
			tmp = RBE_RIGHT(tmp);
		else
			return (node);
	}

	return NULL;
}

/* Finds the first node greater than or equal to the search key */
void *_rb_nfind(const struct rb_type *t, const struct rbt_tree *rbt,
		const void *key)
{
	struct rb_entry *tmp = RBH_ROOT(rbt);
	void *node;
	void *res = NULL;
	int comp;

	while (tmp != NULL) {
		node = rb_e2n(t, tmp);
		comp = (*t->t_compare)(key, node);
		if (comp < 0) {
			res = node;
			tmp = RBE_LEFT(tmp);
		} else if (comp > 0)
			tmp = RBE_RIGHT(tmp);
		else
			return (node);
	}

	return (res);
}

void *_rb_next(const struct rb_type *t, void *elm)
{
	struct rb_entry *rbe = rb_n2e(t, elm);

	if (RBE_RIGHT(rbe) != NULL) {
		rbe = RBE_RIGHT(rbe);
		while (RBE_LEFT(rbe) != NULL)
			rbe = RBE_LEFT(rbe);
	} else {
		if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
			rbe = RBE_PARENT(rbe);
		else {
			while (RBE_PARENT(rbe)
			       && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
				rbe = RBE_PARENT(rbe);
			rbe = RBE_PARENT(rbe);
		}
	}

	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
}

void *_rb_prev(const struct rb_type *t, void *elm)
{
	struct rb_entry *rbe = rb_n2e(t, elm);

	if (RBE_LEFT(rbe)) {
		rbe = RBE_LEFT(rbe);
		while (RBE_RIGHT(rbe))
			rbe = RBE_RIGHT(rbe);
	} else {
		if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
			rbe = RBE_PARENT(rbe);
		else {
			while (RBE_PARENT(rbe)
			       && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
				rbe = RBE_PARENT(rbe);
			rbe = RBE_PARENT(rbe);
		}
	}

	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
}

void *_rb_root(const struct rb_type *t, const struct rbt_tree *rbt)
{
	struct rb_entry *rbe = RBH_ROOT(rbt);

	return (rbe == NULL ? rbe : rb_e2n(t, rbe));
}

void *_rb_min(const struct rb_type *t, const struct rbt_tree *rbt)
{
	struct rb_entry *rbe = RBH_ROOT(rbt);
	struct rb_entry *parent = NULL;

	while (rbe != NULL) {
		parent = rbe;
		rbe = RBE_LEFT(rbe);
	}

	return (parent == NULL ? NULL : rb_e2n(t, parent));
}

void *_rb_max(const struct rb_type *t, const struct rbt_tree *rbt)
{
	struct rb_entry *rbe = RBH_ROOT(rbt);
	struct rb_entry *parent = NULL;

	while (rbe != NULL) {
		parent = rbe;
		rbe = RBE_RIGHT(rbe);
	}

	return (parent == NULL ? NULL : rb_e2n(t, parent));
}

void *_rb_left(const struct rb_type *t, void *node)
{
	struct rb_entry *rbe = rb_n2e(t, node);
	rbe = RBE_LEFT(rbe);
	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
}

void *_rb_right(const struct rb_type *t, void *node)
{
	struct rb_entry *rbe = rb_n2e(t, node);
	rbe = RBE_RIGHT(rbe);
	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
}

void *_rb_parent(const struct rb_type *t, void *node)
{
	struct rb_entry *rbe = rb_n2e(t, node);
	rbe = RBE_PARENT(rbe);
	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
}

void _rb_set_left(const struct rb_type *t, void *node, void *left)
{
	struct rb_entry *rbe = rb_n2e(t, node);
	struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);

	RBE_LEFT(rbe) = rbl;
}

void _rb_set_right(const struct rb_type *t, void *node, void *right)
{
	struct rb_entry *rbe = rb_n2e(t, node);
	struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);

	RBE_RIGHT(rbe) = rbr;
}

void _rb_set_parent(const struct rb_type *t, void *node, void *parent)
{
	struct rb_entry *rbe = rb_n2e(t, node);
	struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);

	RBE_PARENT(rbe) = rbp;
}

void _rb_poison(const struct rb_type *t, void *node, unsigned long poison)
{
	struct rb_entry *rbe = rb_n2e(t, node);

	RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
		(struct rb_entry *)poison;
}

int _rb_check(const struct rb_type *t, void *node, unsigned long poison)
{
	struct rb_entry *rbe = rb_n2e(t, node);

	return ((unsigned long)RBE_PARENT(rbe) == poison
		&& (unsigned long)RBE_LEFT(rbe) == poison
		&& (unsigned long)RBE_RIGHT(rbe) == poison);
}
Commit	Line	Data
47a3a827	1	// SPDX-License-Identifier: ISC AND BSD-2-Clause
45926e58 RZ	2	/* $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */
	3
	4	/*
	5	* Copyright 2002 Niels Provos <provos@citi.umich.edu>
45926e58 RZ	6	*/
	7
	8	/*
	9	* Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
45926e58 RZ	10	*/
45926e58 RZ	11
b45ac5f5 DL	12	#ifdef HAVE_CONFIG_H
	13	#include "config.h"
	14	#endif
	15
45926e58 RZ	16	#include <stdlib.h>
	17
	18	#include <lib/openbsd-tree.h>
	19
996c9314	20	static inline struct rb_entry rb_n2e(const struct rb_type t, void *node)
45926e58 RZ	21	{
	22	unsigned long addr = (unsigned long)node;
	23
	24	return ((struct rb_entry *)(addr + t->t_offset));
	25	}
	26
996c9314	27	static inline void rb_e2n(const struct rb_type t, struct rb_entry *rbe)
45926e58 RZ	28	{
	29	unsigned long addr = (unsigned long)rbe;
	30
	31	return ((void *)(addr - t->t_offset));
	32	}
	33
	34	#define RBE_LEFT(_rbe) (_rbe)->rbt_left
	35	#define RBE_RIGHT(_rbe) (_rbe)->rbt_right
	36	#define RBE_PARENT(_rbe) (_rbe)->rbt_parent
	37	#define RBE_COLOR(_rbe) (_rbe)->rbt_color
	38
	39	#define RBH_ROOT(_rbt) (_rbt)->rbt_root
	40
996c9314	41	static inline void rbe_set(struct rb_entry rbe, struct rb_entry parent)
45926e58 RZ	42	{
	43	RBE_PARENT(rbe) = parent;
	44	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
	45	RBE_COLOR(rbe) = RB_RED;
	46	}
	47
996c9314 LB	48	static inline void rbe_set_blackred(struct rb_entry *black,
996c9314 LB	49	struct rb_entry *red)
45926e58 RZ	50	{
	51	RBE_COLOR(black) = RB_BLACK;
	52	RBE_COLOR(red) = RB_RED;
	53	}
	54
996c9314	55	static inline void rbe_augment(const struct rb_type t, struct rb_entry rbe)
45926e58 RZ	56	{
	57	(*t->t_augment)(rb_e2n(t, rbe));
	58	}
	59
996c9314	60	static inline void rbe_if_augment(const struct rb_type t, struct rb_entry rbe)
45926e58 RZ	61	{
	62	if (t->t_augment != NULL)
	63	rbe_augment(t, rbe);
	64	}
	65
996c9314 LB	66	static inline void rbe_rotate_left(const struct rb_type *t,
996c9314 LB	67	struct rbt_tree rbt, struct rb_entry rbe)
45926e58 RZ	68	{
	69	struct rb_entry *parent;
	70	struct rb_entry *tmp;
	71
	72	tmp = RBE_RIGHT(rbe);
	73	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
	74	if (RBE_RIGHT(rbe) != NULL)
	75	RBE_PARENT(RBE_LEFT(tmp)) = rbe;
	76
	77	parent = RBE_PARENT(rbe);
	78	RBE_PARENT(tmp) = parent;
	79	if (parent != NULL) {
	80	if (rbe == RBE_LEFT(parent))
	81	RBE_LEFT(parent) = tmp;
	82	else
	83	RBE_RIGHT(parent) = tmp;
	84	} else
	85	RBH_ROOT(rbt) = tmp;
	86
	87	RBE_LEFT(tmp) = rbe;
	88	RBE_PARENT(rbe) = tmp;
	89
	90	if (t->t_augment != NULL) {
	91	rbe_augment(t, rbe);
	92	rbe_augment(t, tmp);
	93	parent = RBE_PARENT(tmp);
	94	if (parent != NULL)
	95	rbe_augment(t, parent);
	96	}
	97	}
	98
996c9314 LB	99	static inline void rbe_rotate_right(const struct rb_type *t,
996c9314 LB	100	struct rbt_tree rbt, struct rb_entry rbe)
45926e58 RZ	101	{
	102	struct rb_entry *parent;
	103	struct rb_entry *tmp;
	104
	105	tmp = RBE_LEFT(rbe);
	106	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
	107	if (RBE_LEFT(rbe) != NULL)
	108	RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
	109
	110	parent = RBE_PARENT(rbe);
	111	RBE_PARENT(tmp) = parent;
	112	if (parent != NULL) {
	113	if (rbe == RBE_LEFT(parent))
	114	RBE_LEFT(parent) = tmp;
	115	else
	116	RBE_RIGHT(parent) = tmp;
	117	} else
	118	RBH_ROOT(rbt) = tmp;
	119
	120	RBE_RIGHT(tmp) = rbe;
	121	RBE_PARENT(rbe) = tmp;
	122
	123	if (t->t_augment != NULL) {
	124	rbe_augment(t, rbe);
	125	rbe_augment(t, tmp);
	126	parent = RBE_PARENT(tmp);
	127	if (parent != NULL)
	128	rbe_augment(t, parent);
	129	}
	130	}
	131
996c9314 LB	132	static inline void rbe_insert_color(const struct rb_type *t,
996c9314 LB	133	struct rbt_tree rbt, struct rb_entry rbe)
45926e58 RZ	134	{
	135	struct rb_entry parent, gparent, *tmp;
	136
996c9314 LB	137	while ((parent = RBE_PARENT(rbe)) != NULL
996c9314 LB	138	&& RBE_COLOR(parent) == RB_RED) {
45926e58 RZ	139	gparent = RBE_PARENT(parent);
	140
	141	if (parent == RBE_LEFT(gparent)) {
	142	tmp = RBE_RIGHT(gparent);
	143	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
	144	RBE_COLOR(tmp) = RB_BLACK;
	145	rbe_set_blackred(parent, gparent);
	146	rbe = gparent;
	147	continue;
	148	}
	149
	150	if (RBE_RIGHT(parent) == rbe) {
	151	rbe_rotate_left(t, rbt, parent);
	152	tmp = parent;
	153	parent = rbe;
	154	rbe = tmp;
	155	}
	156
	157	rbe_set_blackred(parent, gparent);
	158	rbe_rotate_right(t, rbt, gparent);
	159	} else {
	160	tmp = RBE_LEFT(gparent);
	161	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
	162	RBE_COLOR(tmp) = RB_BLACK;
	163	rbe_set_blackred(parent, gparent);
	164	rbe = gparent;
	165	continue;
	166	}
	167
	168	if (RBE_LEFT(parent) == rbe) {
	169	rbe_rotate_right(t, rbt, parent);
	170	tmp = parent;
	171	parent = rbe;
	172	rbe = tmp;
	173	}
	174
	175	rbe_set_blackred(parent, gparent);
	176	rbe_rotate_left(t, rbt, gparent);
	177	}
	178	}
	179
	180	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
	181	}
	182
996c9314 LB	183	static inline void rbe_remove_color(const struct rb_type *t,
	184	struct rbt_tree *rbt,
	185	struct rb_entry *parent,
	186	struct rb_entry *rbe)
45926e58 RZ	187	{
	188	struct rb_entry *tmp;
	189
996c9314 LB	190	while ((rbe == NULL \|\| RBE_COLOR(rbe) == RB_BLACK)
996c9314 LB	191	&& rbe != RBH_ROOT(rbt) && parent) {
45926e58 RZ	192	if (RBE_LEFT(parent) == rbe) {
	193	tmp = RBE_RIGHT(parent);
	194	if (RBE_COLOR(tmp) == RB_RED) {
	195	rbe_set_blackred(tmp, parent);
	196	rbe_rotate_left(t, rbt, parent);
	197	tmp = RBE_RIGHT(parent);
	198	}
996c9314 LB	199	if ((RBE_LEFT(tmp) == NULL
	200	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
	201	&& (RBE_RIGHT(tmp) == NULL
	202	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
45926e58 RZ	203	RBE_COLOR(tmp) = RB_RED;
	204	rbe = parent;
	205	parent = RBE_PARENT(rbe);
	206	} else {
996c9314 LB	207	if (RBE_RIGHT(tmp) == NULL
996c9314 LB	208	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
45926e58 RZ	209	struct rb_entry *oleft;
	210
	211	oleft = RBE_LEFT(tmp);
	212	if (oleft != NULL)
	213	RBE_COLOR(oleft) = RB_BLACK;
	214
	215	RBE_COLOR(tmp) = RB_RED;
	216	rbe_rotate_right(t, rbt, tmp);
	217	tmp = RBE_RIGHT(parent);
	218	}
	219
	220	RBE_COLOR(tmp) = RBE_COLOR(parent);
	221	RBE_COLOR(parent) = RB_BLACK;
	222	if (RBE_RIGHT(tmp))
	223	RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
	224
	225	rbe_rotate_left(t, rbt, parent);
	226	rbe = RBH_ROOT(rbt);
	227	break;
	228	}
	229	} else {
	230	tmp = RBE_LEFT(parent);
	231	if (RBE_COLOR(tmp) == RB_RED) {
	232	rbe_set_blackred(tmp, parent);
	233	rbe_rotate_right(t, rbt, parent);
	234	tmp = RBE_LEFT(parent);
	235	}
	236
996c9314 LB	237	if ((RBE_LEFT(tmp) == NULL
	238	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
	239	&& (RBE_RIGHT(tmp) == NULL
	240	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
45926e58 RZ	241	RBE_COLOR(tmp) = RB_RED;
	242	rbe = parent;
	243	parent = RBE_PARENT(rbe);
	244	} else {
996c9314 LB	245	if (RBE_LEFT(tmp) == NULL
996c9314 LB	246	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
45926e58 RZ	247	struct rb_entry *oright;
	248
	249	oright = RBE_RIGHT(tmp);
	250	if (oright != NULL)
	251	RBE_COLOR(oright) = RB_BLACK;
	252
	253	RBE_COLOR(tmp) = RB_RED;
	254	rbe_rotate_left(t, rbt, tmp);
	255	tmp = RBE_LEFT(parent);
	256	}
	257
	258	RBE_COLOR(tmp) = RBE_COLOR(parent);
	259	RBE_COLOR(parent) = RB_BLACK;
	260	if (RBE_LEFT(tmp) != NULL)
	261	RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
	262
	263	rbe_rotate_right(t, rbt, parent);
	264	rbe = RBH_ROOT(rbt);
	265	break;
	266	}
	267	}
	268	}
	269
	270	if (rbe != NULL)
	271	RBE_COLOR(rbe) = RB_BLACK;
	272	}
	273
	274	static inline struct rb_entry *
55087642	275	rbe_remove(const struct rb_type t, struct rbt_tree rbt, struct rb_entry *rbe)
45926e58 RZ	276	{
	277	struct rb_entry child, parent, *old = rbe;
	278	unsigned int color;
	279
	280	if (RBE_LEFT(rbe) == NULL)
	281	child = RBE_RIGHT(rbe);
	282	else if (RBE_RIGHT(rbe) == NULL)
	283	child = RBE_LEFT(rbe);
	284	else {
	285	struct rb_entry *tmp;
	286
	287	rbe = RBE_RIGHT(rbe);
	288	while ((tmp = RBE_LEFT(rbe)) != NULL)
	289	rbe = tmp;
	290
	291	child = RBE_RIGHT(rbe);
	292	parent = RBE_PARENT(rbe);
	293	color = RBE_COLOR(rbe);
	294	if (child != NULL)
	295	RBE_PARENT(child) = parent;
	296	if (parent != NULL) {
	297	if (RBE_LEFT(parent) == rbe)
	298	RBE_LEFT(parent) = child;
	299	else
	300	RBE_RIGHT(parent) = child;
	301
	302	rbe_if_augment(t, parent);
	303	} else
	304	RBH_ROOT(rbt) = child;
	305	if (RBE_PARENT(rbe) == old)
	306	parent = rbe;
	307	rbe = old;
	308
	309	tmp = RBE_PARENT(old);
	310	if (tmp != NULL) {
	311	if (RBE_LEFT(tmp) == old)
	312	RBE_LEFT(tmp) = rbe;
	313	else
	314	RBE_RIGHT(tmp) = rbe;
	315
01faf8f4	316	rbe_if_augment(t, tmp);
45926e58 RZ	317	} else
	318	RBH_ROOT(rbt) = rbe;
	319
	320	RBE_PARENT(RBE_LEFT(old)) = rbe;
	321	if (RBE_RIGHT(old))
	322	RBE_PARENT(RBE_RIGHT(old)) = rbe;
	323
	324	if (t->t_augment != NULL && parent != NULL) {
	325	tmp = parent;
	326	do {
	327	rbe_augment(t, tmp);
	328	tmp = RBE_PARENT(tmp);
	329	} while (tmp != NULL);
	330	}
	331
	332	goto color;
	333	}
	334
	335	parent = RBE_PARENT(rbe);
	336	color = RBE_COLOR(rbe);
	337
	338	if (child != NULL)
	339	RBE_PARENT(child) = parent;
	340	if (parent != NULL) {
	341	if (RBE_LEFT(parent) == rbe)
	342	RBE_LEFT(parent) = child;
	343	else
	344	RBE_RIGHT(parent) = child;
	345
	346	rbe_if_augment(t, parent);
	347	} else
	348	RBH_ROOT(rbt) = child;
	349	color:
	350	if (color == RB_BLACK)
	351	rbe_remove_color(t, rbt, parent, child);
	352
	353	return (old);
	354	}
	355
996c9314	356	void _rb_remove(const struct rb_type t, struct rbt_tree rbt, void elm)
45926e58 RZ	357	{
	358	struct rb_entry *rbe = rb_n2e(t, elm);
	359	struct rb_entry *old;
	360
	361	old = rbe_remove(t, rbt, rbe);
	362
	363	return (old == NULL ? NULL : rb_e2n(t, old));
	364	}
	365
996c9314	366	void _rb_insert(const struct rb_type t, struct rbt_tree rbt, void elm)
45926e58 RZ	367	{
	368	struct rb_entry *rbe = rb_n2e(t, elm);
	369	struct rb_entry *tmp;
	370	struct rb_entry *parent = NULL;
	371	void *node;
	372	int comp = 0;
	373
	374	tmp = RBH_ROOT(rbt);
	375	while (tmp != NULL) {
	376	parent = tmp;
	377
	378	node = rb_e2n(t, tmp);
	379	comp = (*t->t_compare)(elm, node);
	380	if (comp < 0)
	381	tmp = RBE_LEFT(tmp);
	382	else if (comp > 0)
	383	tmp = RBE_RIGHT(tmp);
	384	else
	385	return (node);
	386	}
	387
	388	rbe_set(rbe, parent);
	389
	390	if (parent != NULL) {
	391	if (comp < 0)
	392	RBE_LEFT(parent) = rbe;
	393	else
	394	RBE_RIGHT(parent) = rbe;
	395
	396	rbe_if_augment(t, parent);
	397	} else
	398	RBH_ROOT(rbt) = rbe;
	399
	400	rbe_insert_color(t, rbt, rbe);
	401
95f7965d	402	return NULL;
45926e58 RZ	403	}
	404
	405	/* Finds the node with the same key as elm */
5208931b SW	406	void _rb_find(const struct rb_type t, const struct rbt_tree *rbt,
5208931b SW	407	const void *key)
45926e58 RZ	408	{
	409	struct rb_entry *tmp = RBH_ROOT(rbt);
	410	void *node;
	411	int comp;
	412
	413	while (tmp != NULL) {
	414	node = rb_e2n(t, tmp);
	415	comp = (*t->t_compare)(key, node);
	416	if (comp < 0)
	417	tmp = RBE_LEFT(tmp);
	418	else if (comp > 0)
	419	tmp = RBE_RIGHT(tmp);
	420	else
	421	return (node);
	422	}
	423
95f7965d	424	return NULL;
45926e58 RZ	425	}
	426
	427	/* Finds the first node greater than or equal to the search key */
5208931b SW	428	void _rb_nfind(const struct rb_type t, const struct rbt_tree *rbt,
5208931b SW	429	const void *key)
45926e58 RZ	430	{
	431	struct rb_entry *tmp = RBH_ROOT(rbt);
	432	void *node;
	433	void *res = NULL;
	434	int comp;
	435
	436	while (tmp != NULL) {
	437	node = rb_e2n(t, tmp);
	438	comp = (*t->t_compare)(key, node);
	439	if (comp < 0) {
	440	res = node;
	441	tmp = RBE_LEFT(tmp);
	442	} else if (comp > 0)
	443	tmp = RBE_RIGHT(tmp);
	444	else
	445	return (node);
	446	}
	447
	448	return (res);
	449	}
	450
996c9314	451	void _rb_next(const struct rb_type t, void *elm)
45926e58 RZ	452	{
	453	struct rb_entry *rbe = rb_n2e(t, elm);
	454
	455	if (RBE_RIGHT(rbe) != NULL) {
	456	rbe = RBE_RIGHT(rbe);
	457	while (RBE_LEFT(rbe) != NULL)
	458	rbe = RBE_LEFT(rbe);
	459	} else {
996c9314	460	if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
45926e58 RZ	461	rbe = RBE_PARENT(rbe);
45926e58 RZ	462	else {
996c9314 LB	463	while (RBE_PARENT(rbe)
996c9314 LB	464	&& (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
45926e58 RZ	465	rbe = RBE_PARENT(rbe);
	466	rbe = RBE_PARENT(rbe);
	467	}
	468	}
	469
	470	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	471	}
	472
996c9314	473	void _rb_prev(const struct rb_type t, void *elm)
45926e58 RZ	474	{
	475	struct rb_entry *rbe = rb_n2e(t, elm);
	476
	477	if (RBE_LEFT(rbe)) {
	478	rbe = RBE_LEFT(rbe);
	479	while (RBE_RIGHT(rbe))
	480	rbe = RBE_RIGHT(rbe);
	481	} else {
996c9314	482	if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
45926e58 RZ	483	rbe = RBE_PARENT(rbe);
45926e58 RZ	484	else {
996c9314 LB	485	while (RBE_PARENT(rbe)
996c9314 LB	486	&& (rbe == RBE_LEFT(RBE_PARENT(rbe))))
45926e58 RZ	487	rbe = RBE_PARENT(rbe);
	488	rbe = RBE_PARENT(rbe);
	489	}
	490	}
	491
	492	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	493	}
	494
5208931b	495	void _rb_root(const struct rb_type t, const struct rbt_tree *rbt)
45926e58 RZ	496	{
	497	struct rb_entry *rbe = RBH_ROOT(rbt);
	498
	499	return (rbe == NULL ? rbe : rb_e2n(t, rbe));
	500	}
	501
5208931b	502	void _rb_min(const struct rb_type t, const struct rbt_tree *rbt)
45926e58 RZ	503	{
	504	struct rb_entry *rbe = RBH_ROOT(rbt);
	505	struct rb_entry *parent = NULL;
	506
	507	while (rbe != NULL) {
	508	parent = rbe;
	509	rbe = RBE_LEFT(rbe);
	510	}
	511
	512	return (parent == NULL ? NULL : rb_e2n(t, parent));
	513	}
	514
5208931b	515	void _rb_max(const struct rb_type t, const struct rbt_tree *rbt)
45926e58 RZ	516	{
	517	struct rb_entry *rbe = RBH_ROOT(rbt);
	518	struct rb_entry *parent = NULL;
	519
	520	while (rbe != NULL) {
	521	parent = rbe;
	522	rbe = RBE_RIGHT(rbe);
	523	}
	524
	525	return (parent == NULL ? NULL : rb_e2n(t, parent));
	526	}
	527
996c9314	528	void _rb_left(const struct rb_type t, void *node)
45926e58 RZ	529	{
	530	struct rb_entry *rbe = rb_n2e(t, node);
	531	rbe = RBE_LEFT(rbe);
	532	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	533	}
	534
996c9314	535	void _rb_right(const struct rb_type t, void *node)
45926e58 RZ	536	{
	537	struct rb_entry *rbe = rb_n2e(t, node);
	538	rbe = RBE_RIGHT(rbe);
	539	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	540	}
	541
996c9314	542	void _rb_parent(const struct rb_type t, void *node)
45926e58 RZ	543	{
	544	struct rb_entry *rbe = rb_n2e(t, node);
	545	rbe = RBE_PARENT(rbe);
	546	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	547	}
	548
996c9314	549	void _rb_set_left(const struct rb_type t, void node, void *left)
45926e58 RZ	550	{
	551	struct rb_entry *rbe = rb_n2e(t, node);
	552	struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);
	553
	554	RBE_LEFT(rbe) = rbl;
	555	}
	556
996c9314	557	void _rb_set_right(const struct rb_type t, void node, void *right)
45926e58 RZ	558	{
	559	struct rb_entry *rbe = rb_n2e(t, node);
	560	struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);
	561
	562	RBE_RIGHT(rbe) = rbr;
	563	}
	564
996c9314	565	void _rb_set_parent(const struct rb_type t, void node, void *parent)
45926e58 RZ	566	{
	567	struct rb_entry *rbe = rb_n2e(t, node);
	568	struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);
	569
	570	RBE_PARENT(rbe) = rbp;
	571	}
	572
996c9314	573	void _rb_poison(const struct rb_type t, void node, unsigned long poison)
45926e58 RZ	574	{
	575	struct rb_entry *rbe = rb_n2e(t, node);
	576
	577	RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
996c9314	578	(struct rb_entry *)poison;
45926e58 RZ	579	}
45926e58 RZ	580
996c9314	581	int _rb_check(const struct rb_type t, void node, unsigned long poison)
45926e58 RZ	582	{
	583	struct rb_entry *rbe = rb_n2e(t, node);
	584
996c9314 LB	585	return ((unsigned long)RBE_PARENT(rbe) == poison
	586	&& (unsigned long)RBE_LEFT(rbe) == poison
	587	&& (unsigned long)RBE_RIGHT(rbe) == poison);
45926e58	588	}