[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_

#ifdef __cplusplus
extern "C" {
#endif

/*
 * 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(const 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 *, const struct rbt_tree *, const void *);
void *_rb_nfind(const struct rb_type *, const struct rbt_tree *, const void *);
void *_rb_root(const struct rb_type *, const struct rbt_tree *);
void *_rb_min(const struct rb_type *, const struct rbt_tree *);
void *_rb_max(const struct rb_type *, const 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(const 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(const 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(const struct _name *head)                     \
	{                                                                      \
		return (struct _type *)_rb_root(_name##_RB_TYPE,               \
						&head->rbh_root);              \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline int _name##_RB_EMPTY(        \
		const struct _name *head)                                      \
	{                                                                      \
		return _rb_empty(&head->rbh_root);                             \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_MIN(const struct _name *head)                      \
	{                                                                      \
		return (struct _type *)_rb_min(_name##_RB_TYPE,                \
					       &head->rbh_root);               \
	}                                                                      \
                                                                               \
	__attribute__((__unused__)) static inline struct _type                 \
		*_name##_RB_MAX(const 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))

#ifdef __cplusplus
}
#endif

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