[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.
 */

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