Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libc/gen/tree.c	Lines:	0	272	0.0 %
Date:	2017-11-07	Branches:	0	186	0.0 %


/*	$OpenBSD: tree.c,v 1.1 2017/06/19 03:06:26 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 <sys/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 rb_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 rb_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 rb_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 rb_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)) {
		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 rb_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 rb_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));
}
DEF_STRONG(_rb_remove);

void *
_rb_insert(const struct rb_type *t, struct rb_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);
}
DEF_STRONG(_rb_insert);

/* Finds the node with the same key as elm */
void *
_rb_find(const struct rb_type *t, struct rb_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);
}
DEF_STRONG(_rb_find);

/* Finds the first node greater than or equal to the search key */
void *
_rb_nfind(const struct rb_type *t, struct rb_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);
}
DEF_STRONG(_rb_nfind);

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));
}
DEF_STRONG(_rb_next);

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));
}
DEF_STRONG(_rb_prev);

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

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

void *
_rb_min(const struct rb_type *t, struct rb_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));
}
DEF_STRONG(_rb_min);

void *
_rb_max(const struct rb_type *t, struct rb_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));
}
DEF_STRONG(_rb_max);

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));
}
DEF_STRONG(_rb_left);

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));
}
DEF_STRONG(_rb_right);

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));
}
DEF_STRONG(_rb_parent);

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;
}
DEF_STRONG(_rb_set_left);

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;
}
DEF_STRONG(_rb_set_right);

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;
}
DEF_STRONG(_rb_set_parent);

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;
}
DEF_STRONG(_rb_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);
}
DEF_STRONG(_rb_check);


Generated by: GCOVR (Version 3.3)

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