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

/*	$OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */

/*
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#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, parent);
		} 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, 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, 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, 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, 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, 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
45926e58 RZ	1	/* $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */
	2
	3	/*
	4	* Copyright 2002 Niels Provos <provos@citi.umich.edu>
	5	* All rights reserved.
	6	*
	7	* Redistribution and use in source and binary forms, with or without
	8	* modification, are permitted provided that the following conditions
	9	* are met:
	10	* 1. Redistributions of source code must retain the above copyright
	11	* notice, this list of conditions and the following disclaimer.
	12	* 2. Redistributions in binary form must reproduce the above copyright
	13	* notice, this list of conditions and the following disclaimer in the
	14	* documentation and/or other materials provided with the distribution.
	15	*
	16	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
	17	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
	18	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
	19	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
	20	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
	21	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	22	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	23	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	24	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
	25	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	26	*/
	27
	28	/*
	29	* Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
	30	*
	31	* Permission to use, copy, modify, and distribute this software for any
	32	* purpose with or without fee is hereby granted, provided that the above
	33	* copyright notice and this permission notice appear in all copies.
	34	*
	35	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	36	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	37	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
	38	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	39	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	40	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	41	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
	42	*/
	43
	44	#include <stdlib.h>
	45
	46	#include <lib/openbsd-tree.h>
	47
52535bee RW	48	static inline struct rb_entry *
52535bee RW	49	rb_n2e(const struct rb_type t, void node)
45926e58 RZ	50	{
	51	unsigned long addr = (unsigned long)node;
	52
	53	return ((struct rb_entry *)(addr + t->t_offset));
	54	}
	55
52535bee RW	56	static inline void *
52535bee RW	57	rb_e2n(const struct rb_type t, struct rb_entry rbe)
45926e58 RZ	58	{
	59	unsigned long addr = (unsigned long)rbe;
	60
	61	return ((void *)(addr - t->t_offset));
	62	}
	63
	64	#define RBE_LEFT(_rbe) (_rbe)->rbt_left
	65	#define RBE_RIGHT(_rbe) (_rbe)->rbt_right
	66	#define RBE_PARENT(_rbe) (_rbe)->rbt_parent
	67	#define RBE_COLOR(_rbe) (_rbe)->rbt_color
	68
	69	#define RBH_ROOT(_rbt) (_rbt)->rbt_root
	70
52535bee RW	71	static inline void
52535bee RW	72	rbe_set(struct rb_entry rbe, struct rb_entry parent)
45926e58 RZ	73	{
	74	RBE_PARENT(rbe) = parent;
	75	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
	76	RBE_COLOR(rbe) = RB_RED;
	77	}
	78
52535bee RW	79	static inline void
52535bee RW	80	rbe_set_blackred(struct rb_entry black, struct rb_entry red)
45926e58 RZ	81	{
	82	RBE_COLOR(black) = RB_BLACK;
	83	RBE_COLOR(red) = RB_RED;
	84	}
	85
52535bee RW	86	static inline void
52535bee RW	87	rbe_augment(const struct rb_type t, struct rb_entry rbe)
45926e58 RZ	88	{
	89	(*t->t_augment)(rb_e2n(t, rbe));
	90	}
	91
52535bee RW	92	static inline void
52535bee RW	93	rbe_if_augment(const struct rb_type t, struct rb_entry rbe)
45926e58 RZ	94	{
	95	if (t->t_augment != NULL)
	96	rbe_augment(t, rbe);
	97	}
	98
52535bee RW	99	static inline void
	100	rbe_rotate_left(const struct rb_type t, struct rbt_tree rbt,
	101	struct rb_entry *rbe)
45926e58 RZ	102	{
	103	struct rb_entry *parent;
	104	struct rb_entry *tmp;
	105
	106	tmp = RBE_RIGHT(rbe);
	107	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
	108	if (RBE_RIGHT(rbe) != NULL)
	109	RBE_PARENT(RBE_LEFT(tmp)) = rbe;
	110
	111	parent = RBE_PARENT(rbe);
	112	RBE_PARENT(tmp) = parent;
	113	if (parent != NULL) {
	114	if (rbe == RBE_LEFT(parent))
	115	RBE_LEFT(parent) = tmp;
	116	else
	117	RBE_RIGHT(parent) = tmp;
	118	} else
	119	RBH_ROOT(rbt) = tmp;
	120
	121	RBE_LEFT(tmp) = rbe;
	122	RBE_PARENT(rbe) = tmp;
	123
	124	if (t->t_augment != NULL) {
	125	rbe_augment(t, rbe);
	126	rbe_augment(t, tmp);
	127	parent = RBE_PARENT(tmp);
	128	if (parent != NULL)
	129	rbe_augment(t, parent);
	130	}
	131	}
	132
52535bee RW	133	static inline void
	134	rbe_rotate_right(const struct rb_type t, struct rbt_tree rbt,
	135	struct rb_entry *rbe)
45926e58 RZ	136	{
	137	struct rb_entry *parent;
	138	struct rb_entry *tmp;
	139
	140	tmp = RBE_LEFT(rbe);
	141	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
	142	if (RBE_LEFT(rbe) != NULL)
	143	RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
	144
	145	parent = RBE_PARENT(rbe);
	146	RBE_PARENT(tmp) = parent;
	147	if (parent != NULL) {
	148	if (rbe == RBE_LEFT(parent))
	149	RBE_LEFT(parent) = tmp;
	150	else
	151	RBE_RIGHT(parent) = tmp;
	152	} else
	153	RBH_ROOT(rbt) = tmp;
	154
	155	RBE_RIGHT(tmp) = rbe;
	156	RBE_PARENT(rbe) = tmp;
	157
	158	if (t->t_augment != NULL) {
	159	rbe_augment(t, rbe);
	160	rbe_augment(t, tmp);
	161	parent = RBE_PARENT(tmp);
	162	if (parent != NULL)
	163	rbe_augment(t, parent);
	164	}
	165	}
	166
52535bee RW	167	static inline void
	168	rbe_insert_color(const struct rb_type t, struct rbt_tree rbt,
	169	struct rb_entry *rbe)
45926e58 RZ	170	{
	171	struct rb_entry parent, gparent, *tmp;
	172
52535bee RW	173	while ((parent = RBE_PARENT(rbe)) != NULL &&
52535bee RW	174	RBE_COLOR(parent) == RB_RED) {
45926e58 RZ	175	gparent = RBE_PARENT(parent);
	176
	177	if (parent == RBE_LEFT(gparent)) {
	178	tmp = RBE_RIGHT(gparent);
	179	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
	180	RBE_COLOR(tmp) = RB_BLACK;
	181	rbe_set_blackred(parent, gparent);
	182	rbe = gparent;
	183	continue;
	184	}
	185
	186	if (RBE_RIGHT(parent) == rbe) {
	187	rbe_rotate_left(t, rbt, parent);
	188	tmp = parent;
	189	parent = rbe;
	190	rbe = tmp;
	191	}
	192
	193	rbe_set_blackred(parent, gparent);
	194	rbe_rotate_right(t, rbt, gparent);
	195	} else {
	196	tmp = RBE_LEFT(gparent);
	197	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
	198	RBE_COLOR(tmp) = RB_BLACK;
	199	rbe_set_blackred(parent, gparent);
	200	rbe = gparent;
	201	continue;
	202	}
	203
	204	if (RBE_LEFT(parent) == rbe) {
	205	rbe_rotate_right(t, rbt, parent);
	206	tmp = parent;
	207	parent = rbe;
	208	rbe = tmp;
	209	}
	210
	211	rbe_set_blackred(parent, gparent);
	212	rbe_rotate_left(t, rbt, gparent);
	213	}
	214	}
	215
	216	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
	217	}
	218
52535bee RW	219	static inline void
	220	rbe_remove_color(const struct rb_type t, struct rbt_tree rbt,
	221	struct rb_entry parent, struct rb_entry rbe)
45926e58 RZ	222	{
	223	struct rb_entry *tmp;
	224
52535bee	225	while ((rbe == NULL \|\| RBE_COLOR(rbe) == RB_BLACK) &&
145b2051	226	rbe != RBH_ROOT(rbt) && parent) {
45926e58 RZ	227	if (RBE_LEFT(parent) == rbe) {
	228	tmp = RBE_RIGHT(parent);
	229	if (RBE_COLOR(tmp) == RB_RED) {
	230	rbe_set_blackred(tmp, parent);
	231	rbe_rotate_left(t, rbt, parent);
	232	tmp = RBE_RIGHT(parent);
	233	}
52535bee RW	234	if ((RBE_LEFT(tmp) == NULL \|\|
	235	RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) &&
	236	(RBE_RIGHT(tmp) == NULL \|\|
	237	RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
45926e58 RZ	238	RBE_COLOR(tmp) = RB_RED;
	239	rbe = parent;
	240	parent = RBE_PARENT(rbe);
	241	} else {
52535bee RW	242	if (RBE_RIGHT(tmp) == NULL \|\|
52535bee RW	243	RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
45926e58 RZ	244	struct rb_entry *oleft;
	245
	246	oleft = RBE_LEFT(tmp);
	247	if (oleft != NULL)
	248	RBE_COLOR(oleft) = RB_BLACK;
	249
	250	RBE_COLOR(tmp) = RB_RED;
	251	rbe_rotate_right(t, rbt, tmp);
	252	tmp = RBE_RIGHT(parent);
	253	}
	254
	255	RBE_COLOR(tmp) = RBE_COLOR(parent);
	256	RBE_COLOR(parent) = RB_BLACK;
	257	if (RBE_RIGHT(tmp))
	258	RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
	259
	260	rbe_rotate_left(t, rbt, parent);
	261	rbe = RBH_ROOT(rbt);
	262	break;
	263	}
	264	} else {
	265	tmp = RBE_LEFT(parent);
	266	if (RBE_COLOR(tmp) == RB_RED) {
	267	rbe_set_blackred(tmp, parent);
	268	rbe_rotate_right(t, rbt, parent);
	269	tmp = RBE_LEFT(parent);
	270	}
	271
52535bee RW	272	if ((RBE_LEFT(tmp) == NULL \|\|
	273	RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) &&
	274	(RBE_RIGHT(tmp) == NULL \|\|
	275	RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
45926e58 RZ	276	RBE_COLOR(tmp) = RB_RED;
	277	rbe = parent;
	278	parent = RBE_PARENT(rbe);
	279	} else {
52535bee RW	280	if (RBE_LEFT(tmp) == NULL \|\|
52535bee RW	281	RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
45926e58 RZ	282	struct rb_entry *oright;
	283
	284	oright = RBE_RIGHT(tmp);
	285	if (oright != NULL)
	286	RBE_COLOR(oright) = RB_BLACK;
	287
	288	RBE_COLOR(tmp) = RB_RED;
	289	rbe_rotate_left(t, rbt, tmp);
	290	tmp = RBE_LEFT(parent);
	291	}
	292
	293	RBE_COLOR(tmp) = RBE_COLOR(parent);
	294	RBE_COLOR(parent) = RB_BLACK;
	295	if (RBE_LEFT(tmp) != NULL)
	296	RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
	297
	298	rbe_rotate_right(t, rbt, parent);
	299	rbe = RBH_ROOT(rbt);
	300	break;
	301	}
	302	}
	303	}
	304
	305	if (rbe != NULL)
	306	RBE_COLOR(rbe) = RB_BLACK;
	307	}
	308
	309	static inline struct rb_entry *
55087642	310	rbe_remove(const struct rb_type t, struct rbt_tree rbt, struct rb_entry *rbe)
45926e58 RZ	311	{
	312	struct rb_entry child, parent, *old = rbe;
	313	unsigned int color;
	314
	315	if (RBE_LEFT(rbe) == NULL)
	316	child = RBE_RIGHT(rbe);
	317	else if (RBE_RIGHT(rbe) == NULL)
	318	child = RBE_LEFT(rbe);
	319	else {
	320	struct rb_entry *tmp;
	321
	322	rbe = RBE_RIGHT(rbe);
	323	while ((tmp = RBE_LEFT(rbe)) != NULL)
	324	rbe = tmp;
	325
	326	child = RBE_RIGHT(rbe);
	327	parent = RBE_PARENT(rbe);
	328	color = RBE_COLOR(rbe);
	329	if (child != NULL)
	330	RBE_PARENT(child) = parent;
	331	if (parent != NULL) {
	332	if (RBE_LEFT(parent) == rbe)
	333	RBE_LEFT(parent) = child;
	334	else
	335	RBE_RIGHT(parent) = child;
	336
	337	rbe_if_augment(t, parent);
	338	} else
	339	RBH_ROOT(rbt) = child;
	340	if (RBE_PARENT(rbe) == old)
	341	parent = rbe;
	342	rbe = old;
	343
	344	tmp = RBE_PARENT(old);
	345	if (tmp != NULL) {
	346	if (RBE_LEFT(tmp) == old)
	347	RBE_LEFT(tmp) = rbe;
	348	else
	349	RBE_RIGHT(tmp) = rbe;
	350
	351	rbe_if_augment(t, parent);
	352	} else
	353	RBH_ROOT(rbt) = rbe;
	354
	355	RBE_PARENT(RBE_LEFT(old)) = rbe;
	356	if (RBE_RIGHT(old))
	357	RBE_PARENT(RBE_RIGHT(old)) = rbe;
	358
	359	if (t->t_augment != NULL && parent != NULL) {
	360	tmp = parent;
	361	do {
	362	rbe_augment(t, tmp);
	363	tmp = RBE_PARENT(tmp);
	364	} while (tmp != NULL);
	365	}
	366
	367	goto color;
	368	}
	369
	370	parent = RBE_PARENT(rbe);
	371	color = RBE_COLOR(rbe);
	372
	373	if (child != NULL)
	374	RBE_PARENT(child) = parent;
375	if (parent != NULL) {
376	if (RBE_LEFT(parent) == rbe)
377	RBE_LEFT(parent) = child;
378	else
379	RBE_RIGHT(parent) = child;
380
381	rbe_if_augment(t, parent);
382	} else
383	RBH_ROOT(rbt) = child;
384	color:
385	if (color == RB_BLACK)
386	rbe_remove_color(t, rbt, parent, child);
387
388	return (old);
389	}
390
52535bee RW	391	void *
52535bee RW	392	_rb_remove(const struct rb_type t, struct rbt_tree rbt, void *elm)
45926e58 RZ	393	{
	394	struct rb_entry *rbe = rb_n2e(t, elm);
	395	struct rb_entry *old;
	396
	397	old = rbe_remove(t, rbt, rbe);
	398
	399	return (old == NULL ? NULL : rb_e2n(t, old));
	400	}
	401
52535bee RW	402	void *
52535bee RW	403	_rb_insert(const struct rb_type t, struct rbt_tree rbt, void *elm)
45926e58 RZ	404	{
	405	struct rb_entry *rbe = rb_n2e(t, elm);
	406	struct rb_entry *tmp;
	407	struct rb_entry *parent = NULL;
	408	void *node;
	409	int comp = 0;
	410
	411	tmp = RBH_ROOT(rbt);
	412	while (tmp != NULL) {
	413	parent = tmp;
	414
	415	node = rb_e2n(t, tmp);
	416	comp = (*t->t_compare)(elm, node);
	417	if (comp < 0)
	418	tmp = RBE_LEFT(tmp);
	419	else if (comp > 0)
	420	tmp = RBE_RIGHT(tmp);
	421	else
	422	return (node);
	423	}
	424
	425	rbe_set(rbe, parent);
	426
	427	if (parent != NULL) {
	428	if (comp < 0)
	429	RBE_LEFT(parent) = rbe;
	430	else
	431	RBE_RIGHT(parent) = rbe;
	432
	433	rbe_if_augment(t, parent);
	434	} else
	435	RBH_ROOT(rbt) = rbe;
	436
	437	rbe_insert_color(t, rbt, rbe);
	438
	439	return (NULL);
	440	}
	441
	442	/* Finds the node with the same key as elm */
52535bee RW	443	void *
52535bee RW	444	_rb_find(const struct rb_type t, struct rbt_tree rbt, const void *key)
45926e58 RZ	445	{
	446	struct rb_entry *tmp = RBH_ROOT(rbt);
	447	void *node;
	448	int comp;
	449
	450	while (tmp != NULL) {
	451	node = rb_e2n(t, tmp);
	452	comp = (*t->t_compare)(key, node);
	453	if (comp < 0)
	454	tmp = RBE_LEFT(tmp);
	455	else if (comp > 0)
	456	tmp = RBE_RIGHT(tmp);
	457	else
	458	return (node);
	459	}
	460
	461	return (NULL);
	462	}
	463
	464	/* Finds the first node greater than or equal to the search key */
52535bee RW	465	void *
52535bee RW	466	_rb_nfind(const struct rb_type t, struct rbt_tree rbt, const void *key)
45926e58 RZ	467	{
	468	struct rb_entry *tmp = RBH_ROOT(rbt);
	469	void *node;
	470	void *res = NULL;
	471	int comp;
	472
	473	while (tmp != NULL) {
	474	node = rb_e2n(t, tmp);
	475	comp = (*t->t_compare)(key, node);
	476	if (comp < 0) {
	477	res = node;
	478	tmp = RBE_LEFT(tmp);
	479	} else if (comp > 0)
	480	tmp = RBE_RIGHT(tmp);
	481	else
	482	return (node);
	483	}
	484
	485	return (res);
	486	}
	487
52535bee RW	488	void *
52535bee RW	489	_rb_next(const struct rb_type t, void elm)
45926e58 RZ	490	{
	491	struct rb_entry *rbe = rb_n2e(t, elm);
	492
	493	if (RBE_RIGHT(rbe) != NULL) {
	494	rbe = RBE_RIGHT(rbe);
	495	while (RBE_LEFT(rbe) != NULL)
	496	rbe = RBE_LEFT(rbe);
	497	} else {
52535bee RW	498	if (RBE_PARENT(rbe) &&
52535bee RW	499	(rbe == RBE_LEFT(RBE_PARENT(rbe))))
45926e58 RZ	500	rbe = RBE_PARENT(rbe);
45926e58 RZ	501	else {
52535bee RW	502	while (RBE_PARENT(rbe) &&
52535bee RW	503	(rbe == RBE_RIGHT(RBE_PARENT(rbe))))
45926e58 RZ	504	rbe = RBE_PARENT(rbe);
	505	rbe = RBE_PARENT(rbe);
	506	}
	507	}
	508
	509	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	510	}
	511
52535bee RW	512	void *
52535bee RW	513	_rb_prev(const struct rb_type t, void elm)
45926e58 RZ	514	{
	515	struct rb_entry *rbe = rb_n2e(t, elm);
	516
	517	if (RBE_LEFT(rbe)) {
	518	rbe = RBE_LEFT(rbe);
	519	while (RBE_RIGHT(rbe))
	520	rbe = RBE_RIGHT(rbe);
	521	} else {
52535bee RW	522	if (RBE_PARENT(rbe) &&
52535bee RW	523	(rbe == RBE_RIGHT(RBE_PARENT(rbe))))
45926e58 RZ	524	rbe = RBE_PARENT(rbe);
45926e58 RZ	525	else {
52535bee RW	526	while (RBE_PARENT(rbe) &&
52535bee RW	527	(rbe == RBE_LEFT(RBE_PARENT(rbe))))
45926e58 RZ	528	rbe = RBE_PARENT(rbe);
	529	rbe = RBE_PARENT(rbe);
	530	}
	531	}
	532
	533	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	534	}
	535
52535bee RW	536	void *
52535bee RW	537	_rb_root(const struct rb_type t, struct rbt_tree rbt)
45926e58 RZ	538	{
	539	struct rb_entry *rbe = RBH_ROOT(rbt);
	540
	541	return (rbe == NULL ? rbe : rb_e2n(t, rbe));
	542	}
	543
52535bee RW	544	void *
52535bee RW	545	_rb_min(const struct rb_type t, struct rbt_tree rbt)
45926e58 RZ	546	{
	547	struct rb_entry *rbe = RBH_ROOT(rbt);
	548	struct rb_entry *parent = NULL;
	549
	550	while (rbe != NULL) {
	551	parent = rbe;
	552	rbe = RBE_LEFT(rbe);
	553	}
	554
	555	return (parent == NULL ? NULL : rb_e2n(t, parent));
	556	}
	557
52535bee RW	558	void *
52535bee RW	559	_rb_max(const struct rb_type t, struct rbt_tree rbt)
45926e58 RZ	560	{
	561	struct rb_entry *rbe = RBH_ROOT(rbt);
	562	struct rb_entry *parent = NULL;
	563
	564	while (rbe != NULL) {
	565	parent = rbe;
	566	rbe = RBE_RIGHT(rbe);
	567	}
	568
	569	return (parent == NULL ? NULL : rb_e2n(t, parent));
	570	}
	571
52535bee RW	572	void *
52535bee RW	573	_rb_left(const struct rb_type t, void node)
45926e58 RZ	574	{
	575	struct rb_entry *rbe = rb_n2e(t, node);
	576	rbe = RBE_LEFT(rbe);
	577	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	578	}
	579
52535bee RW	580	void *
52535bee RW	581	_rb_right(const struct rb_type t, void node)
45926e58 RZ	582	{
	583	struct rb_entry *rbe = rb_n2e(t, node);
	584	rbe = RBE_RIGHT(rbe);
	585	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	586	}
	587
52535bee RW	588	void *
52535bee RW	589	_rb_parent(const struct rb_type t, void node)
45926e58 RZ	590	{
	591	struct rb_entry *rbe = rb_n2e(t, node);
	592	rbe = RBE_PARENT(rbe);
	593	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
	594	}
	595
52535bee RW	596	void
52535bee RW	597	_rb_set_left(const struct rb_type t, void node, void *left)
45926e58 RZ	598	{
	599	struct rb_entry *rbe = rb_n2e(t, node);
	600	struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);
	601
	602	RBE_LEFT(rbe) = rbl;
	603	}
	604
52535bee RW	605	void
52535bee RW	606	_rb_set_right(const struct rb_type t, void node, void *right)
45926e58 RZ	607	{
	608	struct rb_entry *rbe = rb_n2e(t, node);
	609	struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);
	610
	611	RBE_RIGHT(rbe) = rbr;
	612	}
	613
52535bee RW	614	void
52535bee RW	615	_rb_set_parent(const struct rb_type t, void node, void *parent)
45926e58 RZ	616	{
	617	struct rb_entry *rbe = rb_n2e(t, node);
	618	struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);
	619
	620	RBE_PARENT(rbe) = rbp;
	621	}
	622
52535bee RW	623	void
52535bee RW	624	_rb_poison(const struct rb_type t, void node, unsigned long poison)
45926e58 RZ	625	{
	626	struct rb_entry *rbe = rb_n2e(t, node);
	627
	628	RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
52535bee	629	(struct rb_entry *)poison;
45926e58 RZ	630	}
45926e58 RZ	631
52535bee RW	632	int
52535bee RW	633	_rb_check(const struct rb_type t, void node, unsigned long poison)
45926e58 RZ	634	{
	635	struct rb_entry *rbe = rb_n2e(t, node);
	636
52535bee RW	637	return ((unsigned long)RBE_PARENT(rbe) == poison &&
	638	(unsigned long)RBE_LEFT(rbe) == poison &&
	639	(unsigned long)RBE_RIGHT(rbe) == poison);
45926e58	640	}