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

/*	$OpenBSD: tree.h,v 1.14 2015/05/25 03:07:49 deraadt 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.
 */

#ifndef _SYS_TREE_H_
#define	_SYS_TREE_H_

/*
 * This file defines data structures for different types of trees:
 * splay trees and red-black trees.
 *
 * A splay tree is a self-organizing data structure.  Every operation
 * on the tree causes a splay to happen.  The splay moves the requested
 * node to the root of the tree and partly rebalances it.
 *
 * This has the benefit that request locality causes faster lookups as
 * the requested nodes move to the top of the tree.  On the other hand,
 * every lookup causes memory writes.
 *
 * The Balance Theorem bounds the total access time for m operations
 * and n inserts on an initially empty tree as O((m + n)lg n).  The
 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
 *
 * A red-black tree is a binary search tree with the node color as an
 * extra attribute.  It fulfills a set of conditions:
 *	- every search path from the root to a leaf consists of the
 *	  same number of black nodes,
 *	- each red node (except for the root) has a black parent,
 *	- each leaf node is black.
 *
 * Every operation on a red-black tree is bounded as O(lg n).
 * The maximum height of a red-black tree is 2lg (n+1).
 */

#define SPLAY_HEAD(name, type)                                                 \
	struct name {                                                          \
		struct type *sph_root; /* root of the tree */                  \
	}

#define SPLAY_INITIALIZER(root)                                                \
	{                                                                      \
		NULL                                                           \
	}

#define SPLAY_INIT(root)                                                       \
	do {                                                                   \
		(root)->sph_root = NULL;                                       \
	} while (0)

#define SPLAY_ENTRY(type)                                                      \
	struct {                                                               \
		struct type *spe_left;  /* left element */                     \
		struct type *spe_right; /* right element */                    \
	}

#define SPLAY_LEFT(elm, field)		(elm)->field.spe_left
#define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right
#define SPLAY_ROOT(head)		(head)->sph_root
#define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)

/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
#define SPLAY_ROTATE_RIGHT(head, tmp, field)                                   \
	do {                                                                   \
		SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
		SPLAY_RIGHT(tmp, field) = (head)->sph_root;                    \
		(head)->sph_root = tmp;                                        \
	} while (0)

#define SPLAY_ROTATE_LEFT(head, tmp, field)                                    \
	do {                                                                   \
		SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
		SPLAY_LEFT(tmp, field) = (head)->sph_root;                     \
		(head)->sph_root = tmp;                                        \
	} while (0)

#define SPLAY_LINKLEFT(head, tmp, field)                                       \
	do {                                                                   \
		SPLAY_LEFT(tmp, field) = (head)->sph_root;                     \
		tmp = (head)->sph_root;                                        \
		(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);        \
	} while (0)

#define SPLAY_LINKRIGHT(head, tmp, field)                                      \
	do {                                                                   \
		SPLAY_RIGHT(tmp, field) = (head)->sph_root;                    \
		tmp = (head)->sph_root;                                        \
		(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);       \
	} while (0)

#define SPLAY_ASSEMBLE(head, node, left, right, field)                         \
	do {                                                                   \
		SPLAY_RIGHT(left, field) =                                     \
			SPLAY_LEFT((head)->sph_root, field);                   \
		SPLAY_LEFT(right, field) =                                     \
			SPLAY_RIGHT((head)->sph_root, field);                  \
		SPLAY_LEFT((head)->sph_root, field) =                          \
			SPLAY_RIGHT(node, field);                              \
		SPLAY_RIGHT((head)->sph_root, field) =                         \
			SPLAY_LEFT(node, field);                               \
	} while (0)

/* Generates prototypes and inline functions */

#define SPLAY_PROTOTYPE(name, type, field, cmp)                                \
	void name##_SPLAY(struct name *, struct type *);                       \
	void name##_SPLAY_MINMAX(struct name *, int);                          \
	struct type *name##_SPLAY_INSERT(struct name *, struct type *);        \
	struct type *name##_SPLAY_REMOVE(struct name *, struct type *);        \
                                                                               \
	/* Finds the node with the same key as elm */                          \
	static __inline struct type *name##_SPLAY_FIND(struct name *head,      \
						       struct type *elm)       \
	{                                                                      \
		if (SPLAY_EMPTY(head))                                         \
			return (NULL);                                         \
		name##_SPLAY(head, elm);                                       \
		if ((cmp)(elm, (head)->sph_root) == 0)                         \
			return (head->sph_root);                               \
		return (NULL);                                                 \
	}                                                                      \
                                                                               \
	static __inline struct type *name##_SPLAY_NEXT(struct name *head,      \
						       struct type *elm)       \
	{                                                                      \
		name##_SPLAY(head, elm);                                       \
		if (SPLAY_RIGHT(elm, field) != NULL) {                         \
			elm = SPLAY_RIGHT(elm, field);                         \
			while (SPLAY_LEFT(elm, field) != NULL) {               \
				elm = SPLAY_LEFT(elm, field);                  \
			}                                                      \
		} else                                                         \
			elm = NULL;                                            \
		return (elm);                                                  \
	}                                                                      \
                                                                               \
	static __inline struct type *name##_SPLAY_MIN_MAX(struct name *head,   \
							  int val)             \
	{                                                                      \
		name##_SPLAY_MINMAX(head, val);                                \
		return (SPLAY_ROOT(head));                                     \
	}

/* Main splay operation.
 * Moves node close to the key of elm to top
 */
#define SPLAY_GENERATE(name, type, field, cmp)                                 \
	struct type *name##_SPLAY_INSERT(struct name *head, struct type *elm)  \
	{                                                                      \
		if (SPLAY_EMPTY(head)) {                                       \
			SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) =     \
				NULL;                                          \
		} else {                                                       \
			int __comp;                                            \
			name##_SPLAY(head, elm);                               \
			__comp = (cmp)(elm, (head)->sph_root);                 \
			if (__comp < 0) {                                      \
				SPLAY_LEFT(elm, field) =                       \
					SPLAY_LEFT((head)->sph_root, field);   \
				SPLAY_RIGHT(elm, field) = (head)->sph_root;    \
				SPLAY_LEFT((head)->sph_root, field) = NULL;    \
			} else if (__comp > 0) {                               \
				SPLAY_RIGHT(elm, field) =                      \
					SPLAY_RIGHT((head)->sph_root, field);  \
				SPLAY_LEFT(elm, field) = (head)->sph_root;     \
				SPLAY_RIGHT((head)->sph_root, field) = NULL;   \
			} else                                                 \
				return ((head)->sph_root);                     \
		}                                                              \
		(head)->sph_root = (elm);                                      \
		return (NULL);                                                 \
	}                                                                      \
                                                                               \
	struct type *name##_SPLAY_REMOVE(struct name *head, struct type *elm)  \
	{                                                                      \
		struct type *__tmp;                                            \
		if (SPLAY_EMPTY(head))                                         \
			return (NULL);                                         \
		name##_SPLAY(head, elm);                                       \
		if ((cmp)(elm, (head)->sph_root) == 0) {                       \
			if (SPLAY_LEFT((head)->sph_root, field) == NULL) {     \
				(head)->sph_root =                             \
					SPLAY_RIGHT((head)->sph_root, field);  \
			} else {                                               \
				__tmp = SPLAY_RIGHT((head)->sph_root, field);  \
				(head)->sph_root =                             \
					SPLAY_LEFT((head)->sph_root, field);   \
				name##_SPLAY(head, elm);                       \
				SPLAY_RIGHT((head)->sph_root, field) = __tmp;  \
			}                                                      \
			return (elm);                                          \
		}                                                              \
		return (NULL);                                                 \
	}                                                                      \
                                                                               \
	void name##_SPLAY(struct name *head, struct type *elm)                 \
	{                                                                      \
		struct type __node, *__left, *__right, *__tmp;                 \
		int __comp;                                                    \
                                                                               \
		SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) =     \
			NULL;                                                  \
		__left = __right = &__node;                                    \
                                                                               \
		while ((__comp = (cmp)(elm, (head)->sph_root))) {              \
			if (__comp < 0) {                                      \
				__tmp = SPLAY_LEFT((head)->sph_root, field);   \
				if (__tmp == NULL)                             \
					break;                                 \
				if ((cmp)(elm, __tmp) < 0) {                   \
					SPLAY_ROTATE_RIGHT(head, __tmp,        \
							   field);             \
					if (SPLAY_LEFT((head)->sph_root,       \
						       field)                  \
					    == NULL)                           \
						break;                         \
				}                                              \
				SPLAY_LINKLEFT(head, __right, field);          \
			} else if (__comp > 0) {                               \
				__tmp = SPLAY_RIGHT((head)->sph_root, field);  \
				if (__tmp == NULL)                             \
					break;                                 \
				if ((cmp)(elm, __tmp) > 0) {                   \
					SPLAY_ROTATE_LEFT(head, __tmp, field); \
					if (SPLAY_RIGHT((head)->sph_root,      \
							field)                 \
					    == NULL)                           \
						break;                         \
				}                                              \
				SPLAY_LINKRIGHT(head, __left, field);          \
			}                                                      \
		}                                                              \
		SPLAY_ASSEMBLE(head, &__node, __left, __right, field);         \
	}                                                                      \
                                                                               \
	/* Splay with either the minimum or the maximum element                \
	 * Used to find minimum or maximum element in tree.                    \
	 */                                                                    \
	void name##_SPLAY_MINMAX(struct name *head, int __comp)                \
	{                                                                      \
		struct type __node, *__left, *__right, *__tmp;                 \
                                                                               \
		SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) =     \
			NULL;                                                  \
		__left = __right = &__node;                                    \
                                                                               \
		while (1) {                                                    \
			if (__comp < 0) {                                      \
				__tmp = SPLAY_LEFT((head)->sph_root, field);   \
				if (__tmp == NULL)                             \
					break;                                 \
				if (__comp < 0) {                              \
					SPLAY_ROTATE_RIGHT(head, __tmp,        \
							   field);             \
					if (SPLAY_LEFT((head)->sph_root,       \
						       field)                  \
					    == NULL)                           \
						break;                         \
				}                                              \
				SPLAY_LINKLEFT(head, __right, field);          \
			} else if (__comp > 0) {                               \
				__tmp = SPLAY_RIGHT((head)->sph_root, field);  \
				if (__tmp == NULL)                             \
					break;                                 \
				if (__comp > 0) {                              \
					SPLAY_ROTATE_LEFT(head, __tmp, field); \
					if (SPLAY_RIGHT((head)->sph_root,      \
							field)                 \
					    == NULL)                           \
						break;                         \
				}                                              \
				SPLAY_LINKRIGHT(head, __left, field);          \
			}                                                      \
		}                                                              \
		SPLAY_ASSEMBLE(head, &__node, __left, __right, field);         \
	}

#define SPLAY_NEGINF	-1
#define SPLAY_INF	1

#define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)
#define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)
#define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)
#define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)
#define SPLAY_MIN(name, x)                                                     \
	(SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
#define SPLAY_MAX(name, x)                                                     \
	(SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))

#define SPLAY_FOREACH(x, name, head)                                           \
	for ((x) = SPLAY_MIN(name, head); (x) != NULL;                         \
	     (x) = SPLAY_NEXT(name, head, x))

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

#define RB_BLACK	0
#define RB_RED		1

struct rb_type {
	int (*t_compare)(const void *, const void *);
	void (*t_augment)(void *);
	unsigned int t_offset; /* offset of rb_entry in type */
};

struct rbt_tree {
	struct rb_entry *rbt_root;
};

struct rb_entry {
	struct rb_entry *rbt_parent;
	struct rb_entry *rbt_left;
	struct rb_entry *rbt_right;
	unsigned int rbt_color;
};

#define RB_HEAD(_name, _type)                                                  \
	struct _name {                                                         \
		struct rbt_tree rbh_root;                                      \
	}

#define RB_ENTRY(_type)	struct rb_entry

static inline void _rb_init(struct rbt_tree *rbt)
{
	rbt->rbt_root = NULL;
}

static inline int _rb_empty(struct rbt_tree *rbt)
{
	return (rbt->rbt_root == NULL);
}

void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *);
void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *);
void *_rb_find(const struct rb_type *, struct rbt_tree *, const void *);
void *_rb_nfind(const struct rb_type *, struct rbt_tree *, const void *);
void *_rb_root(const struct rb_type *, struct rbt_tree *);
void *_rb_min(const struct rb_type *, struct rbt_tree *);
void *_rb_max(const struct rb_type *, struct rbt_tree *);
void *_rb_next(const struct rb_type *, void *);
void *_rb_prev(const struct rb_type *, void *);
void *_rb_left(const struct rb_type *, void *);
void *_rb_right(const struct rb_type *, void *);
void *_rb_parent(const struct rb_type *, void *);
void _rb_set_left(const struct rb_type *, void *, void *);
void _rb_set_right(const struct rb_type *, void *, void *);
void _rb_set_parent(const struct rb_type *, void *, void *);
void _rb_poison(const struct rb_type *, void *, unsigned long);
int _rb_check(const struct rb_type *, void *, unsigned long);

#define RB_INITIALIZER(_head)	{ { NULL } }

#define RB_PROTOTYPE(_name, _type, _field, _cmp)                               \
	extern const struct rb_type *const _name##_RB_TYPE;                    \
                                                                               \
	__attribute__((__unused__)) static inline void _name##_RB_INIT(        \
		struct _name *head)                                            \
	{                                                                      \
		_rb_init(&head->rbh_root);                                     \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_INSERT(struct _name *head, struct _type *elm)      \
	{                                                                      \
		return (struct _type *)_rb_insert(                             \
			_name##_RB_TYPE, &head->rbh_root, elm);                \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_REMOVE(struct _name *head, struct _type *elm)      \
	{                                                                      \
		return (struct _type *)_rb_remove(                             \
			_name##_RB_TYPE, &head->rbh_root, elm);                \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_FIND(struct _name *head, const struct _type *key)  \
	{                                                                      \
		return (struct _type *)_rb_find(                               \
			_name##_RB_TYPE, &head->rbh_root, key);                \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_NFIND(struct _name *head, const struct _type *key) \
	{                                                                      \
		return (struct _type *)_rb_nfind(                              \
			_name##_RB_TYPE, &head->rbh_root, key);                \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_ROOT(struct _name *head)                           \
	{                                                                      \
		return (struct _type *)_rb_root(                               \
			_name##_RB_TYPE, &head->rbh_root);                     \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline int _name##_RB_EMPTY(        \
		struct _name *head)                                            \
	{                                                                      \
		return _rb_empty(&head->rbh_root);                             \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_MIN(struct _name *head)                            \
	{                                                                      \
		return (struct _type *)_rb_min(                                \
			_name##_RB_TYPE, &head->rbh_root);                     \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_MAX(struct _name *head)                            \
	{                                                                      \
		return (struct _type *)_rb_max(                                \
			_name##_RB_TYPE, &head->rbh_root);                     \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_NEXT(struct _type *elm)                            \
	{                                                                      \
		return (struct _type *)_rb_next(_name##_RB_TYPE, elm);         \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_PREV(struct _type *elm)                            \
	{                                                                      \
		return (struct _type *)_rb_prev(_name##_RB_TYPE, elm);         \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_LEFT(struct _type *elm)                            \
	{                                                                      \
		return (struct _type *)_rb_left(_name##_RB_TYPE, elm);         \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_RIGHT(struct _type *elm)                           \
	{                                                                      \
		return (struct _type *)_rb_right(_name##_RB_TYPE, elm);        \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_PARENT(struct _type *elm)                          \
	{                                                                      \
		return (struct _type *)_rb_parent(_name##_RB_TYPE, elm);       \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline void _name##_RB_SET_LEFT(    \
		struct _type *elm, struct _type *left)                         \
	{                                                                      \
		_rb_set_left(_name##_RB_TYPE, elm, left);                      \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline void _name##_RB_SET_RIGHT(   \
		struct _type *elm, struct _type *right)                        \
	{                                                                      \
		_rb_set_right(_name##_RB_TYPE, elm, right);                    \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline void _name##_RB_SET_PARENT(  \
		struct _type *elm, struct _type *parent)                       \
	{                                                                      \
		_rb_set_parent(_name##_RB_TYPE, elm, parent);                  \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline void _name##_RB_POISON(      \
		struct _type *elm, unsigned long poison)                       \
	{                                                                      \
		_rb_poison(_name##_RB_TYPE, elm, poison);                      \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline int _name##_RB_CHECK(        \
		struct _type *elm, unsigned long poison)                       \
	{                                                                      \
		return _rb_check(_name##_RB_TYPE, elm, poison);                \
	}

#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug)                 \
	static int _name##_RB_COMPARE(const void *lptr, const void *rptr)      \
	{                                                                      \
		const struct _type *l = lptr, *r = rptr;                       \
		return _cmp(l, r);                                             \
	}                                                                      \
	static const struct rb_type _name##_RB_INFO = {                        \
		_name##_RB_COMPARE, _aug, offsetof(struct _type, _field),      \
	};                                                                     \
	const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO;

#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug)                  \
	static void _name##_RB_AUGMENT(void *ptr)                              \
	{                                                                      \
		struct _type *p = ptr;                                         \
		return _aug(p);                                                \
	}                                                                      \
	RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT)

#define RB_GENERATE(_name, _type, _field, _cmp)                                \
	RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)

#define RB_INIT(_name, _head)		_name##_RB_INIT(_head)
#define RB_INSERT(_name, _head, _elm)	_name##_RB_INSERT(_head, _elm)
#define RB_REMOVE(_name, _head, _elm)	_name##_RB_REMOVE(_head, _elm)
#define RB_FIND(_name, _head, _key)	_name##_RB_FIND(_head, _key)
#define RB_NFIND(_name, _head, _key)	_name##_RB_NFIND(_head, _key)
#define RB_ROOT(_name, _head)		_name##_RB_ROOT(_head)
#define RB_EMPTY(_name, _head)		_name##_RB_EMPTY(_head)
#define RB_MIN(_name, _head)		_name##_RB_MIN(_head)
#define RB_MAX(_name, _head)		_name##_RB_MAX(_head)
#define RB_NEXT(_name, _elm)		_name##_RB_NEXT(_elm)
#define RB_PREV(_name, _elm)		_name##_RB_PREV(_elm)
#define RB_LEFT(_name, _elm)		_name##_RB_LEFT(_elm)
#define RB_RIGHT(_name, _elm)		_name##_RB_RIGHT(_elm)
#define RB_PARENT(_name, _elm)		_name##_RB_PARENT(_elm)
#define RB_SET_LEFT(_name, _elm, _l)	_name##_RB_SET_LEFT(_elm, _l)
#define RB_SET_RIGHT(_name, _elm, _r)	_name##_RB_SET_RIGHT(_elm, _r)
#define RB_SET_PARENT(_name, _elm, _p)	_name##_RB_SET_PARENT(_elm, _p)
#define RB_POISON(_name, _elm, _p)	_name##_RB_POISON(_elm, _p)
#define RB_CHECK(_name, _elm, _p)	_name##_RB_CHECK(_elm, _p)

#define RB_FOREACH(_e, _name, _head)                                           \
	for ((_e) = RB_MIN(_name, (_head)); (_e) != NULL;                      \
	     (_e) = RB_NEXT(_name, (_e)))

#define RB_FOREACH_SAFE(_e, _name, _head, _n)                                  \
	for ((_e) = RB_MIN(_name, (_head));                                    \
	     (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); (_e) = (_n))

#define RB_FOREACH_REVERSE(_e, _name, _head)                                   \
	for ((_e) = RB_MAX(_name, (_head)); (_e) != NULL;                      \
	     (_e) = RB_PREV(_name, (_e)))

#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n)                          \
	for ((_e) = RB_MAX(_name, (_head));                                    \
	     (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); (_e) = (_n))

#endif /* _SYS_TREE_H_ */
Commit	Line	Data
8429abe0 RW	1	/* $OpenBSD: tree.h,v 1.14 2015/05/25 03:07:49 deraadt Exp $ */
	2	/*
	3	* Copyright 2002 Niels Provos <provos@citi.umich.edu>
	4	* All rights reserved.
	5	*
	6	* Redistribution and use in source and binary forms, with or without
	7	* modification, are permitted provided that the following conditions
	8	* are met:
	9	* 1. Redistributions of source code must retain the above copyright
	10	* notice, this list of conditions and the following disclaimer.
	11	* 2. Redistributions in binary form must reproduce the above copyright
	12	* notice, this list of conditions and the following disclaimer in the
	13	* documentation and/or other materials provided with the distribution.
	14	*
	15	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
	16	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
	17	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
	18	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
	19	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
	20	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	21	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	22	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	23	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
	24	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	25	*/
	26
996c9314	27	#ifndef _SYS_TREE_H_
8429abe0 RW	28	#define _SYS_TREE_H_
	29
	30	/*
	31	* This file defines data structures for different types of trees:
	32	* splay trees and red-black trees.
	33	*
	34	* A splay tree is a self-organizing data structure. Every operation
	35	* on the tree causes a splay to happen. The splay moves the requested
	36	* node to the root of the tree and partly rebalances it.
	37	*
	38	* This has the benefit that request locality causes faster lookups as
	39	* the requested nodes move to the top of the tree. On the other hand,
	40	* every lookup causes memory writes.
	41	*
	42	* The Balance Theorem bounds the total access time for m operations
	43	* and n inserts on an initially empty tree as O((m + n)lg n). The
	44	* amortized cost for a sequence of m accesses to a splay tree is O(lg n);
	45	*
	46	* A red-black tree is a binary search tree with the node color as an
	47	* extra attribute. It fulfills a set of conditions:
	48	* - every search path from the root to a leaf consists of the
	49	* same number of black nodes,
	50	* - each red node (except for the root) has a black parent,
	51	* - each leaf node is black.
	52	*
	53	* Every operation on a red-black tree is bounded as O(lg n).
	54	* The maximum height of a red-black tree is 2lg (n+1).
	55	*/
	56
996c9314 LB	57	#define SPLAY_HEAD(name, type) \
	58	struct name { \
	59	struct type sph_root; / root of the tree */ \
	60	}
8429abe0	61
996c9314 LB	62	#define SPLAY_INITIALIZER(root) \
	63	{ \
	64	NULL \
	65	}
8429abe0	66
996c9314 LB	67	#define SPLAY_INIT(root) \
	68	do { \
	69	(root)->sph_root = NULL; \
	70	} while (0)
8429abe0	71
996c9314 LB	72	#define SPLAY_ENTRY(type) \
	73	struct { \
	74	struct type spe_left; / left element */ \
	75	struct type spe_right; / right element */ \
	76	}
8429abe0 RW	77
	78	#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
	79	#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
	80	#define SPLAY_ROOT(head) (head)->sph_root
	81	#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
	82
	83	/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
996c9314 LB	84	#define SPLAY_ROTATE_RIGHT(head, tmp, field) \
	85	do { \
	86	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
	87	SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
	88	(head)->sph_root = tmp; \
	89	} while (0)
	90
	91	#define SPLAY_ROTATE_LEFT(head, tmp, field) \
	92	do { \
	93	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
	94	SPLAY_LEFT(tmp, field) = (head)->sph_root; \
	95	(head)->sph_root = tmp; \
	96	} while (0)
	97
	98	#define SPLAY_LINKLEFT(head, tmp, field) \
	99	do { \
	100	SPLAY_LEFT(tmp, field) = (head)->sph_root; \
	101	tmp = (head)->sph_root; \
	102	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
	103	} while (0)
	104
	105	#define SPLAY_LINKRIGHT(head, tmp, field) \
	106	do { \
	107	SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
	108	tmp = (head)->sph_root; \
	109	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
	110	} while (0)
	111
	112	#define SPLAY_ASSEMBLE(head, node, left, right, field) \
	113	do { \
	114	SPLAY_RIGHT(left, field) = \
	115	SPLAY_LEFT((head)->sph_root, field); \
	116	SPLAY_LEFT(right, field) = \
	117	SPLAY_RIGHT((head)->sph_root, field); \
	118	SPLAY_LEFT((head)->sph_root, field) = \
	119	SPLAY_RIGHT(node, field); \
	120	SPLAY_RIGHT((head)->sph_root, field) = \
	121	SPLAY_LEFT(node, field); \
	122	} while (0)
8429abe0 RW	123
	124	/* Generates prototypes and inline functions */
	125
996c9314 LB	126	#define SPLAY_PROTOTYPE(name, type, field, cmp) \
	127	void name##_SPLAY(struct name , struct type ); \
	128	void name##_SPLAY_MINMAX(struct name *, int); \
	129	struct type name##_SPLAY_INSERT(struct name , struct type *); \
	130	struct type name##_SPLAY_REMOVE(struct name , struct type *); \
	131	\
	132	/* Finds the node with the same key as elm */ \
	133	static __inline struct type name##_SPLAY_FIND(struct name head, \
	134	struct type *elm) \
	135	{ \
	136	if (SPLAY_EMPTY(head)) \
	137	return (NULL); \
	138	name##_SPLAY(head, elm); \
	139	if ((cmp)(elm, (head)->sph_root) == 0) \
	140	return (head->sph_root); \
	141	return (NULL); \
	142	} \
	143	\
	144	static __inline struct type name##_SPLAY_NEXT(struct name head, \
	145	struct type *elm) \
	146	{ \
	147	name##_SPLAY(head, elm); \
	148	if (SPLAY_RIGHT(elm, field) != NULL) { \
	149	elm = SPLAY_RIGHT(elm, field); \
	150	while (SPLAY_LEFT(elm, field) != NULL) { \
	151	elm = SPLAY_LEFT(elm, field); \
	152	} \
	153	} else \
	154	elm = NULL; \
	155	return (elm); \
	156	} \
	157	\
	158	static __inline struct type name##_SPLAY_MIN_MAX(struct name head, \
	159	int val) \
	160	{ \
	161	name##_SPLAY_MINMAX(head, val); \
	162	return (SPLAY_ROOT(head)); \
	163	}
8429abe0 RW	164
	165	/* Main splay operation.
	166	* Moves node close to the key of elm to top
	167	*/
996c9314 LB	168	#define SPLAY_GENERATE(name, type, field, cmp) \
	169	struct type name##_SPLAY_INSERT(struct name head, struct type *elm) \
	170	{ \
	171	if (SPLAY_EMPTY(head)) { \
	172	SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = \
	173	NULL; \
	174	} else { \
	175	int __comp; \
	176	name##_SPLAY(head, elm); \
	177	__comp = (cmp)(elm, (head)->sph_root); \
	178	if (__comp < 0) { \
	179	SPLAY_LEFT(elm, field) = \
	180	SPLAY_LEFT((head)->sph_root, field); \
	181	SPLAY_RIGHT(elm, field) = (head)->sph_root; \
	182	SPLAY_LEFT((head)->sph_root, field) = NULL; \
	183	} else if (__comp > 0) { \
	184	SPLAY_RIGHT(elm, field) = \
	185	SPLAY_RIGHT((head)->sph_root, field); \
	186	SPLAY_LEFT(elm, field) = (head)->sph_root; \
	187	SPLAY_RIGHT((head)->sph_root, field) = NULL; \
	188	} else \
	189	return ((head)->sph_root); \
	190	} \
	191	(head)->sph_root = (elm); \
	192	return (NULL); \
	193	} \
	194	\
	195	struct type name##_SPLAY_REMOVE(struct name head, struct type *elm) \
	196	{ \
	197	struct type *__tmp; \
	198	if (SPLAY_EMPTY(head)) \
	199	return (NULL); \
	200	name##_SPLAY(head, elm); \
	201	if ((cmp)(elm, (head)->sph_root) == 0) { \
	202	if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
	203	(head)->sph_root = \
	204	SPLAY_RIGHT((head)->sph_root, field); \
	205	} else { \
	206	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
	207	(head)->sph_root = \
	208	SPLAY_LEFT((head)->sph_root, field); \
	209	name##_SPLAY(head, elm); \
	210	SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
	211	} \
	212	return (elm); \
	213	} \
	214	return (NULL); \
	215	} \
	216	\
	217	void name##_SPLAY(struct name head, struct type elm) \
	218	{ \
	219	struct type __node, __left, __right, *__tmp; \
	220	int __comp; \
	221	\
	222	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \
	223	NULL; \
	224	__left = __right = &__node; \
	225	\
	226	while ((__comp = (cmp)(elm, (head)->sph_root))) { \
	227	if (__comp < 0) { \
	228	__tmp = SPLAY_LEFT((head)->sph_root, field); \
	229	if (__tmp == NULL) \
	230	break; \
	231	if ((cmp)(elm, __tmp) < 0) { \
232	SPLAY_ROTATE_RIGHT(head, __tmp, \
233	field); \
234	if (SPLAY_LEFT((head)->sph_root, \
235	field) \
236	== NULL) \
237	break; \
238	} \
239	SPLAY_LINKLEFT(head, __right, field); \
240	} else if (__comp > 0) { \
241	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
242	if (__tmp == NULL) \
243	break; \
244	if ((cmp)(elm, __tmp) > 0) { \
245	SPLAY_ROTATE_LEFT(head, __tmp, field); \
246	if (SPLAY_RIGHT((head)->sph_root, \
247	field) \
248	== NULL) \
249	break; \
250	} \
251	SPLAY_LINKRIGHT(head, __left, field); \
252	} \
253	} \
254	SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
255	} \
256	\
257	/* Splay with either the minimum or the maximum element \
258	* Used to find minimum or maximum element in tree. \
259	*/ \
260	void name##_SPLAY_MINMAX(struct name *head, int __comp) \
261	{ \
262	struct type __node, __left, __right, *__tmp; \
263	\
264	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \
265	NULL; \
266	__left = __right = &__node; \
267	\
268	while (1) { \
269	if (__comp < 0) { \
270	__tmp = SPLAY_LEFT((head)->sph_root, field); \
271	if (__tmp == NULL) \
272	break; \
273	if (__comp < 0) { \
274	SPLAY_ROTATE_RIGHT(head, __tmp, \
275	field); \
276	if (SPLAY_LEFT((head)->sph_root, \
277	field) \
278	== NULL) \
279	break; \
280	} \
281	SPLAY_LINKLEFT(head, __right, field); \
282	} else if (__comp > 0) { \
283	__tmp = SPLAY_RIGHT((head)->sph_root, field); \
284	if (__tmp == NULL) \
285	break; \
286	if (__comp > 0) { \
287	SPLAY_ROTATE_LEFT(head, __tmp, field); \
288	if (SPLAY_RIGHT((head)->sph_root, \
289	field) \
290	== NULL) \
291	break; \
292	} \
293	SPLAY_LINKRIGHT(head, __left, field); \
294	} \
295	} \
296	SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
297	}
8429abe0 RW	298
	299	#define SPLAY_NEGINF -1
	300	#define SPLAY_INF 1
	301
	302	#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
	303	#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
	304	#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
	305	#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
996c9314 LB	306	#define SPLAY_MIN(name, x) \
	307	(SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
	308	#define SPLAY_MAX(name, x) \
	309	(SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
	310
	311	#define SPLAY_FOREACH(x, name, head) \
	312	for ((x) = SPLAY_MIN(name, head); (x) != NULL; \
8429abe0 RW	313	(x) = SPLAY_NEXT(name, head, x))
8429abe0 RW	314
45926e58 RZ	315	/*
	316	* Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
	317	*
	318	* Permission to use, copy, modify, and distribute this software for any
	319	* purpose with or without fee is hereby granted, provided that the above
	320	* copyright notice and this permission notice appear in all copies.
	321	*
	322	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	323	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	324	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
	325	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	326	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	327	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	328	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
	329	*/
8429abe0 RW	330
	331	#define RB_BLACK 0
	332	#define RB_RED 1
8429abe0	333
45926e58	334	struct rb_type {
996c9314 LB	335	int (t_compare)(const void , const void *);
	336	void (t_augment)(void );
	337	unsigned int t_offset; /* offset of rb_entry in type */
45926e58 RZ	338	};
45926e58 RZ	339
55087642	340	struct rbt_tree {
996c9314	341	struct rb_entry *rbt_root;
45926e58 RZ	342	};
	343
	344	struct rb_entry {
996c9314 LB	345	struct rb_entry *rbt_parent;
	346	struct rb_entry *rbt_left;
	347	struct rb_entry *rbt_right;
	348	unsigned int rbt_color;
45926e58 RZ	349	};
45926e58 RZ	350
996c9314 LB	351	#define RB_HEAD(_name, _type) \
	352	struct _name { \
	353	struct rbt_tree rbh_root; \
	354	}
8429abe0	355
45926e58	356	#define RB_ENTRY(_type) struct rb_entry
8429abe0	357
996c9314	358	static inline void _rb_init(struct rbt_tree *rbt)
45926e58 RZ	359	{
	360	rbt->rbt_root = NULL;
	361	}
8429abe0	362
996c9314	363	static inline int _rb_empty(struct rbt_tree *rbt)
45926e58 RZ	364	{
	365	return (rbt->rbt_root == NULL);
	366	}
8429abe0	367
996c9314 LB	368	void _rb_insert(const struct rb_type , struct rbt_tree , void );
	369	void _rb_remove(const struct rb_type , struct rbt_tree , void );
	370	void _rb_find(const struct rb_type , struct rbt_tree , const void );
	371	void _rb_nfind(const struct rb_type , struct rbt_tree , const void );
	372	void _rb_root(const struct rb_type , struct rbt_tree *);
	373	void _rb_min(const struct rb_type , struct rbt_tree *);
	374	void _rb_max(const struct rb_type , struct rbt_tree *);
	375	void _rb_next(const struct rb_type , void *);
	376	void _rb_prev(const struct rb_type , void *);
	377	void _rb_left(const struct rb_type , void *);
	378	void _rb_right(const struct rb_type , void *);
	379	void _rb_parent(const struct rb_type , void *);
	380	void _rb_set_left(const struct rb_type , void , void *);
	381	void _rb_set_right(const struct rb_type , void , void *);
	382	void _rb_set_parent(const struct rb_type , void , void *);
	383	void _rb_poison(const struct rb_type , void , unsigned long);
	384	int _rb_check(const struct rb_type , void , unsigned long);
45926e58 RZ	385
	386	#define RB_INITIALIZER(_head) { { NULL } }
	387
996c9314 LB	388	#define RB_PROTOTYPE(_name, _type, _field, _cmp) \
	389	extern const struct rb_type *const _name##_RB_TYPE; \
	390	\
	391	__attribute__((__unused__)) static inline void _name##_RB_INIT( \
	392	struct _name *head) \
	393	{ \
	394	_rb_init(&head->rbh_root); \
	395	} \
	396	\
	397	__attribute__((__unused__)) static inline struct _type \
	398	_name##_RB_INSERT(struct _name head, struct _type *elm) \
	399	{ \
d01b92fd MS	400	return (struct _type *)_rb_insert( \
d01b92fd MS	401	_name##_RB_TYPE, &head->rbh_root, elm); \
996c9314 LB	402	} \
	403	\
	404	__attribute__((__unused__)) static inline struct _type \
	405	_name##_RB_REMOVE(struct _name head, struct _type *elm) \
	406	{ \
d01b92fd MS	407	return (struct _type *)_rb_remove( \
d01b92fd MS	408	_name##_RB_TYPE, &head->rbh_root, elm); \
996c9314 LB	409	} \
	410	\
	411	__attribute__((__unused__)) static inline struct _type \
	412	_name##_RB_FIND(struct _name head, const struct _type *key) \
	413	{ \
d01b92fd MS	414	return (struct _type *)_rb_find( \
d01b92fd MS	415	_name##_RB_TYPE, &head->rbh_root, key); \
996c9314 LB	416	} \
	417	\
	418	__attribute__((__unused__)) static inline struct _type \
	419	_name##_RB_NFIND(struct _name head, const struct _type *key) \
	420	{ \
d01b92fd MS	421	return (struct _type *)_rb_nfind( \
d01b92fd MS	422	_name##_RB_TYPE, &head->rbh_root, key); \
996c9314 LB	423	} \
	424	\
	425	__attribute__((__unused__)) static inline struct _type \
	426	_name##_RB_ROOT(struct _name head) \
	427	{ \
d01b92fd MS	428	return (struct _type *)_rb_root( \
d01b92fd MS	429	_name##_RB_TYPE, &head->rbh_root); \
996c9314 LB	430	} \
	431	\
	432	__attribute__((__unused__)) static inline int _name##_RB_EMPTY( \
	433	struct _name *head) \
	434	{ \
	435	return _rb_empty(&head->rbh_root); \
	436	} \
	437	\
	438	__attribute__((__unused__)) static inline struct _type \
	439	_name##_RB_MIN(struct _name head) \
	440	{ \
d01b92fd MS	441	return (struct _type *)_rb_min( \
d01b92fd MS	442	_name##_RB_TYPE, &head->rbh_root); \
996c9314 LB	443	} \
	444	\
	445	__attribute__((__unused__)) static inline struct _type \
	446	_name##_RB_MAX(struct _name head) \
	447	{ \
d01b92fd MS	448	return (struct _type *)_rb_max( \
d01b92fd MS	449	_name##_RB_TYPE, &head->rbh_root); \
996c9314 LB	450	} \
	451	\
	452	__attribute__((__unused__)) static inline struct _type \
	453	_name##_RB_NEXT(struct _type elm) \
	454	{ \
d01b92fd	455	return (struct _type *)_rb_next(_name##_RB_TYPE, elm); \
996c9314 LB	456	} \
	457	\
	458	__attribute__((__unused__)) static inline struct _type \
	459	_name##_RB_PREV(struct _type elm) \
	460	{ \
d01b92fd	461	return (struct _type *)_rb_prev(_name##_RB_TYPE, elm); \
996c9314 LB	462	} \
	463	\
	464	__attribute__((__unused__)) static inline struct _type \
	465	_name##_RB_LEFT(struct _type elm) \
	466	{ \
d01b92fd	467	return (struct _type *)_rb_left(_name##_RB_TYPE, elm); \
996c9314 LB	468	} \
	469	\
	470	__attribute__((__unused__)) static inline struct _type \
	471	_name##_RB_RIGHT(struct _type elm) \
	472	{ \
d01b92fd	473	return (struct _type *)_rb_right(_name##_RB_TYPE, elm); \
996c9314 LB	474	} \
	475	\
	476	__attribute__((__unused__)) static inline struct _type \
	477	_name##_RB_PARENT(struct _type elm) \
	478	{ \
d01b92fd	479	return (struct _type *)_rb_parent(_name##_RB_TYPE, elm); \
996c9314 LB	480	} \
	481	\
	482	__attribute__((__unused__)) static inline void _name##_RB_SET_LEFT( \
	483	struct _type elm, struct _type left) \
	484	{ \
d90b788e	485	_rb_set_left(_name##_RB_TYPE, elm, left); \
996c9314 LB	486	} \
	487	\
	488	__attribute__((__unused__)) static inline void _name##_RB_SET_RIGHT( \
	489	struct _type elm, struct _type right) \
	490	{ \
d90b788e	491	_rb_set_right(_name##_RB_TYPE, elm, right); \
996c9314 LB	492	} \
	493	\
	494	__attribute__((__unused__)) static inline void _name##_RB_SET_PARENT( \
	495	struct _type elm, struct _type parent) \
	496	{ \
d90b788e	497	_rb_set_parent(_name##_RB_TYPE, elm, parent); \
996c9314 LB	498	} \
	499	\
	500	__attribute__((__unused__)) static inline void _name##_RB_POISON( \
	501	struct _type *elm, unsigned long poison) \
	502	{ \
d90b788e	503	_rb_poison(_name##_RB_TYPE, elm, poison); \
996c9314 LB	504	} \
	505	\
	506	__attribute__((__unused__)) static inline int _name##_RB_CHECK( \
	507	struct _type *elm, unsigned long poison) \
	508	{ \
	509	return _rb_check(_name##_RB_TYPE, elm, poison); \
	510	}
	511
	512	#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \
	513	static int _name##_RB_COMPARE(const void lptr, const void rptr) \
	514	{ \
	515	const struct _type l = lptr, r = rptr; \
	516	return _cmp(l, r); \
	517	} \
	518	static const struct rb_type _name##_RB_INFO = { \
	519	_name##_RB_COMPARE, _aug, offsetof(struct _type, _field), \
	520	}; \
	521	const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO;
	522
	523	#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \
	524	static void _name##_RB_AUGMENT(void *ptr) \
	525	{ \
	526	struct _type *p = ptr; \
	527	return _aug(p); \
	528	} \
	529	RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT)
	530
	531	#define RB_GENERATE(_name, _type, _field, _cmp) \
	532	RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
45926e58 RZ	533
	534	#define RB_INIT(_name, _head) _name##_RB_INIT(_head)
	535	#define RB_INSERT(_name, _head, _elm) _name##_RB_INSERT(_head, _elm)
	536	#define RB_REMOVE(_name, _head, _elm) _name##_RB_REMOVE(_head, _elm)
	537	#define RB_FIND(_name, _head, _key) _name##_RB_FIND(_head, _key)
	538	#define RB_NFIND(_name, _head, _key) _name##_RB_NFIND(_head, _key)
	539	#define RB_ROOT(_name, _head) _name##_RB_ROOT(_head)
	540	#define RB_EMPTY(_name, _head) _name##_RB_EMPTY(_head)
	541	#define RB_MIN(_name, _head) _name##_RB_MIN(_head)
	542	#define RB_MAX(_name, _head) _name##_RB_MAX(_head)
	543	#define RB_NEXT(_name, _elm) _name##_RB_NEXT(_elm)
	544	#define RB_PREV(_name, _elm) _name##_RB_PREV(_elm)
	545	#define RB_LEFT(_name, _elm) _name##_RB_LEFT(_elm)
	546	#define RB_RIGHT(_name, _elm) _name##_RB_RIGHT(_elm)
	547	#define RB_PARENT(_name, _elm) _name##_RB_PARENT(_elm)
	548	#define RB_SET_LEFT(_name, _elm, _l) _name##_RB_SET_LEFT(_elm, _l)
	549	#define RB_SET_RIGHT(_name, _elm, _r) _name##_RB_SET_RIGHT(_elm, _r)
	550	#define RB_SET_PARENT(_name, _elm, _p) _name##_RB_SET_PARENT(_elm, _p)
	551	#define RB_POISON(_name, _elm, _p) _name##_RB_POISON(_elm, _p)
	552	#define RB_CHECK(_name, _elm, _p) _name##_RB_CHECK(_elm, _p)
	553
996c9314 LB	554	#define RB_FOREACH(_e, _name, _head) \
996c9314 LB	555	for ((_e) = RB_MIN(_name, (_head)); (_e) != NULL; \
45926e58 RZ	556	(_e) = RB_NEXT(_name, (_e)))
45926e58 RZ	557
996c9314 LB	558	#define RB_FOREACH_SAFE(_e, _name, _head, _n) \
	559	for ((_e) = RB_MIN(_name, (_head)); \
	560	(_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); (_e) = (_n))
45926e58	561
996c9314 LB	562	#define RB_FOREACH_REVERSE(_e, _name, _head) \
996c9314 LB	563	for ((_e) = RB_MAX(_name, (_head)); (_e) != NULL; \
45926e58 RZ	564	(_e) = RB_PREV(_name, (_e)))
45926e58 RZ	565
996c9314 LB	566	#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \
	567	for ((_e) = RB_MAX(_name, (_head)); \
	568	(_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); (_e) = (_n))
8429abe0	569
996c9314	570	#endif /* _SYS_TREE_H_ */