aboutsummaryrefslogtreecommitdiff
path: root/sys/sys/arb.h
diff options
context:
space:
mode:
authorEdward Tomasz Napierala <trasz@FreeBSD.org>2019-09-14 19:23:46 +0000
committerEdward Tomasz Napierala <trasz@FreeBSD.org>2019-09-14 19:23:46 +0000
commitfad4b12b9007f59d78a92b35669ffb13bd71b82f (patch)
tree8b9284077e4e083454151eb46e1cccc05850f531 /sys/sys/arb.h
parentcf38985293be425552c13d54018a2d1aa29b7be9 (diff)
downloadsrc-fad4b12b9007f59d78a92b35669ffb13bd71b82f.tar.gz
src-fad4b12b9007f59d78a92b35669ffb13bd71b82f.zip
Introduce arb(3), the Array-based Red-Black Tree macros: similar
to the traditional tree(3) RB trees, but using an array (preallocated, linear chunk of memory) to store the tree. This avoids allocation overhead, improves memory locality, and makes it trivially easy to share/transfer/copy the entire tree without the need for marshalling. The downside is that the size is fixed at initialization time; there is no mechanism to resize it. This is one of the dependencies for the new stats(3) framework (https://reviews.freebsd.org/D20477). Reviewed by: bcr (man pages), markj Discussed with: cem MFC after: 2 weeks Sponsored by: Klara Inc, Netflix Obtained from: Netflix Differential Revision: https://reviews.freebsd.org/D20324
Notes
Notes: svn path=/head/; revision=352337
Diffstat (limited to 'sys/sys/arb.h')
-rw-r--r--sys/sys/arb.h779
1 files changed, 779 insertions, 0 deletions
diff --git a/sys/sys/arb.h b/sys/sys/arb.h
new file mode 100644
index 000000000000..71b81b645d04
--- /dev/null
+++ b/sys/sys/arb.h
@@ -0,0 +1,779 @@
+/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
+/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
+/* $FreeBSD$ */
+
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * 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_ARB_H_
+#define _SYS_ARB_H_
+
+#include <sys/cdefs.h>
+
+/* Array-based red-black trees. */
+
+#define ARB_NULLIDX -1
+#define ARB_NULLCOL -1
+
+#define ARB_BLACK 0
+#define ARB_RED 1
+
+#define ARB_NEGINF -1
+#define ARB_INF 1
+
+#define ARB_HEAD(name, type, idxbits) \
+struct name { \
+ int##idxbits##_t arb_curnodes; \
+ int##idxbits##_t arb_maxnodes; \
+ int##idxbits##_t arb_root_idx; \
+ int##idxbits##_t arb_free_idx; \
+ int##idxbits##_t arb_min_idx; \
+ int##idxbits##_t arb_max_idx; \
+ struct type arb_nodes[]; \
+}
+#define ARB8_HEAD(name, type) ARB_HEAD(name, type, 8)
+#define ARB16_HEAD(name, type) ARB_HEAD(name, type, 16)
+#define ARB32_HEAD(name, type) ARB_HEAD(name, type, 32)
+
+#define ARB_ALLOCSIZE(head, maxn, x) \
+ (sizeof(*head) + (maxn) * sizeof(*x))
+
+#define ARB_INITIALIZER(name, maxn) \
+ ((struct name){ 0, maxn, ARB_NULLIDX, ARB_NULLIDX, \
+ ARB_NULLIDX, ARB_NULLIDX })
+
+#define ARB_INIT(x, field, head, maxn) \
+ (head)->arb_curnodes = 0; \
+ (head)->arb_maxnodes = (maxn); \
+ (head)->arb_root_idx = (head)->arb_free_idx = \
+ (head)->arb_min_idx = (head)->arb_max_idx = ARB_NULLIDX; \
+ /* The ARB_RETURNFREE() puts all entries on the free list. */ \
+ ARB_ARRFOREACH_REVWCOND(x, field, head, \
+ ARB_RETURNFREE(head, x, field))
+
+#define ARB_ENTRY(idxbits) \
+struct { \
+ int##idxbits##_t arbe_parent_idx; \
+ int##idxbits##_t arbe_left_idx; \
+ int##idxbits##_t arbe_right_idx; \
+ int8_t arbe_color; \
+}
+#define ARB8_ENTRY() ARB_ENTRY(8)
+#define ARB16_ENTRY() ARB_ENTRY(16)
+#define ARB32_ENTRY() ARB_ENTRY(32)
+
+#define ARB_ENTRYINIT(elm, field) do { \
+ (elm)->field.arbe_parent_idx = \
+ (elm)->field.arbe_left_idx = \
+ (elm)->field.arbe_right_idx = ARB_NULLIDX; \
+ (elm)->field.arbe_color = ARB_NULLCOL; \
+} while (/*CONSTCOND*/ 0)
+
+#define ARB_ELMTYPE(head) __typeof(&(head)->arb_nodes[0])
+#define ARB_NODES(head) (head)->arb_nodes
+#define ARB_MAXNODES(head) (head)->arb_maxnodes
+#define ARB_CURNODES(head) (head)->arb_curnodes
+#define ARB_EMPTY(head) ((head)->arb_curnodes == 0)
+#define ARB_FULL(head) ((head)->arb_curnodes >= (head)->arb_maxnodes)
+#define ARB_CNODE(head, idx) \
+ ((((intptr_t)(idx) <= ARB_NULLIDX) || ((idx) >= ARB_MAXNODES(head))) ? \
+ NULL : ((const ARB_ELMTYPE(head))(ARB_NODES(head) + (idx))))
+#define ARB_NODE(head, idx) \
+ (__DECONST(ARB_ELMTYPE(head), ARB_CNODE(head, idx)))
+#define ARB_ROOT(head) ARB_NODE(head, ARB_ROOTIDX(head))
+#define ARB_LEFT(head, elm, field) ARB_NODE(head, ARB_LEFTIDX(elm, field))
+#define ARB_RIGHT(head, elm, field) ARB_NODE(head, ARB_RIGHTIDX(elm, field))
+#define ARB_PARENT(head, elm, field) ARB_NODE(head, ARB_PARENTIDX(elm, field))
+#define ARB_FREEIDX(head) (head)->arb_free_idx
+#define ARB_ROOTIDX(head) (head)->arb_root_idx
+#define ARB_MINIDX(head) (head)->arb_min_idx
+#define ARB_MAXIDX(head) (head)->arb_max_idx
+#define ARB_SELFIDX(head, elm) \
+ ((elm) ? ((intptr_t)((((const uint8_t *)(elm)) - \
+ ((const uint8_t *)ARB_NODES(head))) / sizeof(*(elm)))) : \
+ (intptr_t)ARB_NULLIDX)
+#define ARB_LEFTIDX(elm, field) (elm)->field.arbe_left_idx
+#define ARB_RIGHTIDX(elm, field) (elm)->field.arbe_right_idx
+#define ARB_PARENTIDX(elm, field) (elm)->field.arbe_parent_idx
+#define ARB_COLOR(elm, field) (elm)->field.arbe_color
+#define ARB_PREVFREE(head, elm, field) \
+ ARB_NODE(head, ARB_PREVFREEIDX(elm, field))
+#define ARB_PREVFREEIDX(elm, field) ARB_LEFTIDX(elm, field)
+#define ARB_NEXTFREE(head, elm, field) \
+ ARB_NODE(head, ARB_NEXTFREEIDX(elm, field))
+#define ARB_NEXTFREEIDX(elm, field) ARB_RIGHTIDX(elm, field)
+#define ARB_ISFREE(elm, field) (ARB_COLOR(elm, field) == ARB_NULLCOL)
+
+#define ARB_SET(head, elm, parent, field) do { \
+ ARB_PARENTIDX(elm, field) = \
+ parent ? ARB_SELFIDX(head, parent) : ARB_NULLIDX; \
+ ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(elm, field) = ARB_NULLIDX; \
+ ARB_COLOR(elm, field) = ARB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#define ARB_SET_BLACKRED(black, red, field) do { \
+ ARB_COLOR(black, field) = ARB_BLACK; \
+ ARB_COLOR(red, field) = ARB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#ifndef ARB_AUGMENT
+#define ARB_AUGMENT(x) do {} while (0)
+#endif
+
+#define ARB_ROTATE_LEFT(head, elm, tmp, field) do { \
+ __typeof(ARB_RIGHTIDX(elm, field)) _tmpidx; \
+ (tmp) = ARB_RIGHT(head, elm, field); \
+ _tmpidx = ARB_RIGHTIDX(elm, field); \
+ ARB_RIGHTIDX(elm, field) = ARB_LEFTIDX(tmp, field); \
+ if (ARB_RIGHTIDX(elm, field) != ARB_NULLIDX) { \
+ ARB_PARENTIDX(ARB_LEFT(head, tmp, field), field) = \
+ ARB_SELFIDX(head, elm); \
+ } \
+ ARB_AUGMENT(elm); \
+ ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \
+ if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \
+ if (ARB_SELFIDX(head, elm) == \
+ ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \
+ ARB_LEFTIDX(ARB_PARENT(head, elm, field), \
+ field) = _tmpidx; \
+ else \
+ ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \
+ field) = _tmpidx; \
+ } else \
+ ARB_ROOTIDX(head) = _tmpidx; \
+ ARB_LEFTIDX(tmp, field) = ARB_SELFIDX(head, elm); \
+ ARB_PARENTIDX(elm, field) = _tmpidx; \
+ ARB_AUGMENT(tmp); \
+ if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \
+ ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \
+} while (/*CONSTCOND*/ 0)
+
+#define ARB_ROTATE_RIGHT(head, elm, tmp, field) do { \
+ __typeof(ARB_LEFTIDX(elm, field)) _tmpidx; \
+ (tmp) = ARB_LEFT(head, elm, field); \
+ _tmpidx = ARB_LEFTIDX(elm, field); \
+ ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(tmp, field); \
+ if (ARB_LEFTIDX(elm, field) != ARB_NULLIDX) { \
+ ARB_PARENTIDX(ARB_RIGHT(head, tmp, field), field) = \
+ ARB_SELFIDX(head, elm); \
+ } \
+ ARB_AUGMENT(elm); \
+ ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \
+ if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \
+ if (ARB_SELFIDX(head, elm) == \
+ ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \
+ ARB_LEFTIDX(ARB_PARENT(head, elm, field), \
+ field) = _tmpidx; \
+ else \
+ ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \
+ field) = _tmpidx; \
+ } else \
+ ARB_ROOTIDX(head) = _tmpidx; \
+ ARB_RIGHTIDX(tmp, field) = ARB_SELFIDX(head, elm); \
+ ARB_PARENTIDX(elm, field) = _tmpidx; \
+ ARB_AUGMENT(tmp); \
+ if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \
+ ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \
+} while (/*CONSTCOND*/ 0)
+
+#define ARB_RETURNFREE(head, elm, field) \
+({ \
+ ARB_COLOR(elm, field) = ARB_NULLCOL; \
+ ARB_NEXTFREEIDX(elm, field) = ARB_FREEIDX(head); \
+ ARB_FREEIDX(head) = ARB_SELFIDX(head, elm); \
+ elm; \
+})
+
+#define ARB_GETFREEAT(head, field, fidx) \
+({ \
+ __typeof(ARB_NODE(head, 0)) _elm, _prevelm; \
+ int _idx = fidx; \
+ if (ARB_FREEIDX(head) == ARB_NULLIDX && !ARB_FULL(head)) { \
+ /* Populate the free list. */ \
+ ARB_ARRFOREACH_REVERSE(_elm, field, head) { \
+ if (ARB_ISFREE(_elm, field)) \
+ ARB_RETURNFREE(head, _elm, field); \
+ } \
+ } \
+ _elm = _prevelm = ARB_NODE(head, ARB_FREEIDX(head)); \
+ for (; _idx > 0 && _elm != NULL; _idx--, _prevelm = _elm) \
+ _elm = ARB_NODE(head, ARB_NEXTFREEIDX(_elm, field)); \
+ if (_elm) { \
+ if (fidx == 0) \
+ ARB_FREEIDX(head) = \
+ ARB_NEXTFREEIDX(_elm, field); \
+ else \
+ ARB_NEXTFREEIDX(_prevelm, field) = \
+ ARB_NEXTFREEIDX(_elm, field); \
+ } \
+ _elm; \
+})
+#define ARB_GETFREE(head, field) ARB_GETFREEAT(head, field, 0)
+
+/* Generates prototypes and inline functions */
+#define ARB_PROTOTYPE(name, type, field, cmp) \
+ ARB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define ARB_PROTOTYPE_STATIC(name, type, field, cmp) \
+ ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
+#define ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+ ARB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
+ ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
+ ARB_PROTOTYPE_INSERT(name, type, attr); \
+ ARB_PROTOTYPE_REMOVE(name, type, attr); \
+ ARB_PROTOTYPE_CFIND(name, type, attr); \
+ ARB_PROTOTYPE_FIND(name, type, attr); \
+ ARB_PROTOTYPE_NFIND(name, type, attr); \
+ ARB_PROTOTYPE_CNEXT(name, type, attr); \
+ ARB_PROTOTYPE_NEXT(name, type, attr); \
+ ARB_PROTOTYPE_CPREV(name, type, attr); \
+ ARB_PROTOTYPE_PREV(name, type, attr); \
+ ARB_PROTOTYPE_CMINMAX(name, type, attr); \
+ ARB_PROTOTYPE_MINMAX(name, type, attr); \
+ ARB_PROTOTYPE_REBALANCE(name, type, attr);
+#define ARB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
+ attr void name##_ARB_INSERT_COLOR(struct name *, struct type *)
+#define ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
+ attr void name##_ARB_REMOVE_COLOR(struct name *, struct type *, struct type *)
+#define ARB_PROTOTYPE_REMOVE(name, type, attr) \
+ attr struct type *name##_ARB_REMOVE(struct name *, struct type *)
+#define ARB_PROTOTYPE_INSERT(name, type, attr) \
+ attr struct type *name##_ARB_INSERT(struct name *, struct type *)
+#define ARB_PROTOTYPE_CFIND(name, type, attr) \
+ attr const struct type *name##_ARB_CFIND(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_FIND(name, type, attr) \
+ attr struct type *name##_ARB_FIND(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_NFIND(name, type, attr) \
+ attr struct type *name##_ARB_NFIND(struct name *, struct type *)
+#define ARB_PROTOTYPE_CNFIND(name, type, attr) \
+ attr const struct type *name##_ARB_CNFIND(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_CNEXT(name, type, attr) \
+ attr const struct type *name##_ARB_CNEXT(const struct name *head,\
+ const struct type *)
+#define ARB_PROTOTYPE_NEXT(name, type, attr) \
+ attr struct type *name##_ARB_NEXT(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_CPREV(name, type, attr) \
+ attr const struct type *name##_ARB_CPREV(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_PREV(name, type, attr) \
+ attr struct type *name##_ARB_PREV(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_CMINMAX(name, type, attr) \
+ attr const struct type *name##_ARB_CMINMAX(const struct name *, int)
+#define ARB_PROTOTYPE_MINMAX(name, type, attr) \
+ attr struct type *name##_ARB_MINMAX(const struct name *, int)
+#define ARB_PROTOTYPE_REBALANCE(name, type, attr) \
+ attr struct type *name##_ARB_REBALANCE(struct name *, struct type *)
+
+#define ARB_GENERATE(name, type, field, cmp) \
+ ARB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define ARB_GENERATE_STATIC(name, type, field, cmp) \
+ ARB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
+#define ARB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+ ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+ ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
+ ARB_GENERATE_INSERT(name, type, field, cmp, attr) \
+ ARB_GENERATE_REMOVE(name, type, field, attr) \
+ ARB_GENERATE_CFIND(name, type, field, cmp, attr) \
+ ARB_GENERATE_FIND(name, type, field, cmp, attr) \
+ ARB_GENERATE_CNEXT(name, type, field, attr) \
+ ARB_GENERATE_NEXT(name, type, field, attr) \
+ ARB_GENERATE_CPREV(name, type, field, attr) \
+ ARB_GENERATE_PREV(name, type, field, attr) \
+ ARB_GENERATE_CMINMAX(name, type, field, attr) \
+ ARB_GENERATE_MINMAX(name, type, field, attr) \
+ ARB_GENERATE_REBALANCE(name, type, field, cmp, attr)
+
+#define ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+attr void \
+name##_ARB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *gparent, *tmp; \
+ while ((parent = ARB_PARENT(head, elm, field)) != NULL && \
+ ARB_COLOR(parent, field) == ARB_RED) { \
+ gparent = ARB_PARENT(head, parent, field); \
+ if (parent == ARB_LEFT(head, gparent, field)) { \
+ tmp = ARB_RIGHT(head, gparent, field); \
+ if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \
+ ARB_COLOR(tmp, field) = ARB_BLACK; \
+ ARB_SET_BLACKRED(parent, gparent, field); \
+ elm = gparent; \
+ continue; \
+ } \
+ if (ARB_RIGHT(head, parent, field) == elm) { \
+ ARB_ROTATE_LEFT(head, parent, tmp, field); \
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ ARB_SET_BLACKRED(parent, gparent, field); \
+ ARB_ROTATE_RIGHT(head, gparent, tmp, field); \
+ } else { \
+ tmp = ARB_LEFT(head, gparent, field); \
+ if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \
+ ARB_COLOR(tmp, field) = ARB_BLACK; \
+ ARB_SET_BLACKRED(parent, gparent, field); \
+ elm = gparent; \
+ continue; \
+ } \
+ if (ARB_LEFT(head, parent, field) == elm) { \
+ ARB_ROTATE_RIGHT(head, parent, tmp, field); \
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ ARB_SET_BLACKRED(parent, gparent, field); \
+ ARB_ROTATE_LEFT(head, gparent, tmp, field); \
+ } \
+ } \
+ ARB_COLOR(ARB_ROOT(head), field) = ARB_BLACK; \
+}
+
+#define ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
+attr void \
+name##_ARB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{ \
+ struct type *tmp; \
+ while ((elm == NULL || ARB_COLOR(elm, field) == ARB_BLACK) && \
+ elm != ARB_ROOT(head)) { \
+ if (ARB_LEFT(head, parent, field) == elm) { \
+ tmp = ARB_RIGHT(head, parent, field); \
+ if (ARB_COLOR(tmp, field) == ARB_RED) { \
+ ARB_SET_BLACKRED(tmp, parent, field); \
+ ARB_ROTATE_LEFT(head, parent, tmp, field); \
+ tmp = ARB_RIGHT(head, parent, field); \
+ } \
+ if ((ARB_LEFT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \
+ (ARB_RIGHT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \
+ ARB_COLOR(tmp, field) = ARB_RED; \
+ elm = parent; \
+ parent = ARB_PARENT(head, elm, field); \
+ } else { \
+ if (ARB_RIGHT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK) { \
+ struct type *oleft; \
+ if ((oleft = ARB_LEFT(head, tmp, field)) \
+ != NULL) \
+ ARB_COLOR(oleft, field) = ARB_BLACK; \
+ ARB_COLOR(tmp, field) = ARB_RED; \
+ ARB_ROTATE_RIGHT(head, tmp, oleft, field); \
+ tmp = ARB_RIGHT(head, parent, field); \
+ } \
+ ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
+ ARB_COLOR(parent, field) = ARB_BLACK; \
+ if (ARB_RIGHT(head, tmp, field)) \
+ ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = ARB_BLACK; \
+ ARB_ROTATE_LEFT(head, parent, tmp, field); \
+ elm = ARB_ROOT(head); \
+ break; \
+ } \
+ } else { \
+ tmp = ARB_LEFT(head, parent, field); \
+ if (ARB_COLOR(tmp, field) == ARB_RED) { \
+ ARB_SET_BLACKRED(tmp, parent, field); \
+ ARB_ROTATE_RIGHT(head, parent, tmp, field); \
+ tmp = ARB_LEFT(head, parent, field); \
+ } \
+ if ((ARB_LEFT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \
+ (ARB_RIGHT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \
+ ARB_COLOR(tmp, field) = ARB_RED; \
+ elm = parent; \
+ parent = ARB_PARENT(head, elm, field); \
+ } else { \
+ if (ARB_LEFT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) { \
+ struct type *oright; \
+ if ((oright = ARB_RIGHT(head, tmp, field)) \
+ != NULL) \
+ ARB_COLOR(oright, field) = ARB_BLACK; \
+ ARB_COLOR(tmp, field) = ARB_RED; \
+ ARB_ROTATE_LEFT(head, tmp, oright, field); \
+ tmp = ARB_LEFT(head, parent, field); \
+ } \
+ ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
+ ARB_COLOR(parent, field) = ARB_BLACK; \
+ if (ARB_LEFT(head, tmp, field)) \
+ ARB_COLOR(ARB_LEFT(head, tmp, field), field) = ARB_BLACK; \
+ ARB_ROTATE_RIGHT(head, parent, tmp, field); \
+ elm = ARB_ROOT(head); \
+ break; \
+ } \
+ } \
+ } \
+ if (elm) \
+ ARB_COLOR(elm, field) = ARB_BLACK; \
+}
+
+#define ARB_GENERATE_REMOVE(name, type, field, attr) \
+attr struct type * \
+name##_ARB_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *child, *parent, *old = elm; \
+ int color; \
+ if (ARB_LEFT(head, elm, field) == NULL) \
+ child = ARB_RIGHT(head, elm, field); \
+ else if (ARB_RIGHT(head, elm, field) == NULL) \
+ child = ARB_LEFT(head, elm, field); \
+ else { \
+ struct type *left; \
+ elm = ARB_RIGHT(head, elm, field); \
+ while ((left = ARB_LEFT(head, elm, field)) != NULL) \
+ elm = left; \
+ child = ARB_RIGHT(head, elm, field); \
+ parent = ARB_PARENT(head, elm, field); \
+ color = ARB_COLOR(elm, field); \
+ if (child) \
+ ARB_PARENTIDX(child, field) = \
+ ARB_SELFIDX(head, parent); \
+ if (parent) { \
+ if (ARB_LEFT(head, parent, field) == elm) \
+ ARB_LEFTIDX(parent, field) = \
+ ARB_SELFIDX(head, child); \
+ else \
+ ARB_RIGHTIDX(parent, field) = \
+ ARB_SELFIDX(head, child); \
+ ARB_AUGMENT(parent); \
+ } else \
+ ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \
+ if (ARB_PARENT(head, elm, field) == old) \
+ parent = elm; \
+ (elm)->field = (old)->field; \
+ if (ARB_PARENT(head, old, field)) { \
+ if (ARB_LEFT(head, ARB_PARENT(head, old, field), \
+ field) == old) \
+ ARB_LEFTIDX(ARB_PARENT(head, old, field), \
+ field) = ARB_SELFIDX(head, elm); \
+ else \
+ ARB_RIGHTIDX(ARB_PARENT(head, old, field),\
+ field) = ARB_SELFIDX(head, elm); \
+ ARB_AUGMENT(ARB_PARENT(head, old, field)); \
+ } else \
+ ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \
+ ARB_PARENTIDX(ARB_LEFT(head, old, field), field) = \
+ ARB_SELFIDX(head, elm); \
+ if (ARB_RIGHT(head, old, field)) \
+ ARB_PARENTIDX(ARB_RIGHT(head, old, field), \
+ field) = ARB_SELFIDX(head, elm); \
+ if (parent) { \
+ left = parent; \
+ do { \
+ ARB_AUGMENT(left); \
+ } while ((left = ARB_PARENT(head, left, field)) \
+ != NULL); \
+ } \
+ goto color; \
+ } \
+ parent = ARB_PARENT(head, elm, field); \
+ color = ARB_COLOR(elm, field); \
+ if (child) \
+ ARB_PARENTIDX(child, field) = ARB_SELFIDX(head, parent);\
+ if (parent) { \
+ if (ARB_LEFT(head, parent, field) == elm) \
+ ARB_LEFTIDX(parent, field) = \
+ ARB_SELFIDX(head, child); \
+ else \
+ ARB_RIGHTIDX(parent, field) = \
+ ARB_SELFIDX(head, child); \
+ ARB_AUGMENT(parent); \
+ } else \
+ ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \
+color: \
+ if (color == ARB_BLACK) \
+ name##_ARB_REMOVE_COLOR(head, parent, child); \
+ ARB_CURNODES(head) -= 1; \
+ if (ARB_MINIDX(head) == ARB_SELFIDX(head, old)) \
+ ARB_MINIDX(head) = ARB_PARENTIDX(old, field); \
+ if (ARB_MAXIDX(head) == ARB_SELFIDX(head, old)) \
+ ARB_MAXIDX(head) = ARB_PARENTIDX(old, field); \
+ ARB_RETURNFREE(head, old, field); \
+ return (old); \
+} \
+
+#define ARB_GENERATE_INSERT(name, type, field, cmp, attr) \
+/* Inserts a node into the RB tree */ \
+attr struct type * \
+name##_ARB_INSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp; \
+ struct type *parent = NULL; \
+ int comp = 0; \
+ tmp = ARB_ROOT(head); \
+ while (tmp) { \
+ parent = tmp; \
+ comp = (cmp)(elm, parent); \
+ if (comp < 0) \
+ tmp = ARB_LEFT(head, tmp, field); \
+ else if (comp > 0) \
+ tmp = ARB_RIGHT(head, tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ ARB_SET(head, elm, parent, field); \
+ if (parent != NULL) { \
+ if (comp < 0) \
+ ARB_LEFTIDX(parent, field) = \
+ ARB_SELFIDX(head, elm); \
+ else \
+ ARB_RIGHTIDX(parent, field) = \
+ ARB_SELFIDX(head, elm); \
+ ARB_AUGMENT(parent); \
+ } else \
+ ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \
+ name##_ARB_INSERT_COLOR(head, elm); \
+ ARB_CURNODES(head) += 1; \
+ if (ARB_MINIDX(head) == ARB_NULLIDX || \
+ (ARB_PARENTIDX(elm, field) == ARB_MINIDX(head) && \
+ ARB_LEFTIDX(parent, field) == ARB_SELFIDX(head, elm))) \
+ ARB_MINIDX(head) = ARB_SELFIDX(head, elm); \
+ if (ARB_MAXIDX(head) == ARB_NULLIDX || \
+ (ARB_PARENTIDX(elm, field) == ARB_MAXIDX(head) && \
+ ARB_RIGHTIDX(parent, field) == ARB_SELFIDX(head, elm))) \
+ ARB_MAXIDX(head) = ARB_SELFIDX(head, elm); \
+ return (NULL); \
+}
+
+#define ARB_GENERATE_CFIND(name, type, field, cmp, attr) \
+/* Finds the node with the same key as elm */ \
+attr const struct type * \
+name##_ARB_CFIND(const struct name *head, const struct type *elm) \
+{ \
+ const struct type *tmp = ARB_ROOT(head); \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) \
+ tmp = ARB_LEFT(head, tmp, field); \
+ else if (comp > 0) \
+ tmp = ARB_RIGHT(head, tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (NULL); \
+}
+
+#define ARB_GENERATE_FIND(name, type, field, cmp, attr) \
+attr struct type * \
+name##_ARB_FIND(const struct name *head, const struct type *elm) \
+{ return (__DECONST(struct type *, name##_ARB_CFIND(head, elm))); }
+
+#define ARB_GENERATE_CNFIND(name, type, field, cmp, attr) \
+/* Finds the first node greater than or equal to the search key */ \
+attr const struct type * \
+name##_ARB_CNFIND(const struct name *head, const struct type *elm) \
+{ \
+ const struct type *tmp = ARB_ROOT(head); \
+ const struct type *res = NULL; \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) { \
+ res = tmp; \
+ tmp = ARB_LEFT(head, tmp, field); \
+ } \
+ else if (comp > 0) \
+ tmp = ARB_RIGHT(head, tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (res); \
+}
+
+#define ARB_GENERATE_NFIND(name, type, field, cmp, attr) \
+attr struct type * \
+name##_ARB_NFIND(const struct name *head, const struct type *elm) \
+{ return (__DECONST(struct type *, name##_ARB_CNFIND(head, elm))); }
+
+#define ARB_GENERATE_CNEXT(name, type, field, attr) \
+/* ARGSUSED */ \
+attr const struct type * \
+name##_ARB_CNEXT(const struct name *head, const struct type *elm) \
+{ \
+ if (ARB_RIGHT(head, elm, field)) { \
+ elm = ARB_RIGHT(head, elm, field); \
+ while (ARB_LEFT(head, elm, field)) \
+ elm = ARB_LEFT(head, elm, field); \
+ } else { \
+ if (ARB_PARENT(head, elm, field) && \
+ (elm == ARB_LEFT(head, ARB_PARENT(head, elm, field),\
+ field))) \
+ elm = ARB_PARENT(head, elm, field); \
+ else { \
+ while (ARB_PARENT(head, elm, field) && \
+ (elm == ARB_RIGHT(head, ARB_PARENT(head, \
+ elm, field), field))) \
+ elm = ARB_PARENT(head, elm, field); \
+ elm = ARB_PARENT(head, elm, field); \
+ } \
+ } \
+ return (elm); \
+}
+
+#define ARB_GENERATE_NEXT(name, type, field, attr) \
+attr struct type * \
+name##_ARB_NEXT(const struct name *head, const struct type *elm) \
+{ return (__DECONST(struct type *, name##_ARB_CNEXT(head, elm))); }
+
+#define ARB_GENERATE_CPREV(name, type, field, attr) \
+/* ARGSUSED */ \
+attr const struct type * \
+name##_ARB_CPREV(const struct name *head, const struct type *elm) \
+{ \
+ if (ARB_LEFT(head, elm, field)) { \
+ elm = ARB_LEFT(head, elm, field); \
+ while (ARB_RIGHT(head, elm, field)) \
+ elm = ARB_RIGHT(head, elm, field); \
+ } else { \
+ if (ARB_PARENT(head, elm, field) && \
+ (elm == ARB_RIGHT(head, ARB_PARENT(head, elm, \
+ field), field))) \
+ elm = ARB_PARENT(head, elm, field); \
+ else { \
+ while (ARB_PARENT(head, elm, field) && \
+ (elm == ARB_LEFT(head, ARB_PARENT(head, elm,\
+ field), field))) \
+ elm = ARB_PARENT(head, elm, field); \
+ elm = ARB_PARENT(head, elm, field); \
+ } \
+ } \
+ return (elm); \
+}
+
+#define ARB_GENERATE_PREV(name, type, field, attr) \
+attr struct type * \
+name##_ARB_PREV(const struct name *head, const struct type *elm) \
+{ return (__DECONST(struct type *, name##_ARB_CPREV(head, elm))); }
+
+#define ARB_GENERATE_CMINMAX(name, type, field, attr) \
+attr const struct type * \
+name##_ARB_CMINMAX(const struct name *head, int val) \
+{ \
+ const struct type *tmp = ARB_EMPTY(head) ? NULL : ARB_ROOT(head);\
+ const struct type *parent = NULL; \
+ while (tmp) { \
+ parent = tmp; \
+ if (val < 0) \
+ tmp = ARB_LEFT(head, tmp, field); \
+ else \
+ tmp = ARB_RIGHT(head, tmp, field); \
+ } \
+ return (__DECONST(struct type *, parent)); \
+}
+
+#define ARB_GENERATE_MINMAX(name, type, field, attr) \
+attr struct type * \
+name##_ARB_MINMAX(const struct name *head, int val) \
+{ return (__DECONST(struct type *, name##_ARB_CMINMAX(head, val))); }
+
+#define ARB_GENERATE_REBALANCE(name, type, field, cmp, attr) \
+attr struct type * \
+name##_ARB_REBALANCE(struct name *head, struct type *elm) \
+{ \
+ struct type *cmpelm; \
+ if (((cmpelm = ARB_PREV(name, head, elm)) != NULL && \
+ (cmp)(cmpelm, elm) >= 0) || \
+ ((cmpelm = ARB_NEXT(name, head, elm)) != NULL && \
+ (cmp)(elm, cmpelm) >= 0)) { \
+ /* XXXLAS: Remove/insert is heavy handed. */ \
+ ARB_REMOVE(name, head, elm); \
+ /* Remove puts elm on the free list. */ \
+ elm = ARB_GETFREE(head, field); \
+ return (ARB_INSERT(name, head, elm)); \
+ } \
+ return (NULL); \
+} \
+
+#define ARB_INSERT(name, x, y) name##_ARB_INSERT(x, y)
+#define ARB_REMOVE(name, x, y) name##_ARB_REMOVE(x, y)
+#define ARB_CFIND(name, x, y) name##_ARB_CFIND(x, y)
+#define ARB_FIND(name, x, y) name##_ARB_FIND(x, y)
+#define ARB_CNFIND(name, x, y) name##_ARB_CNFIND(x, y)
+#define ARB_NFIND(name, x, y) name##_ARB_NFIND(x, y)
+#define ARB_CNEXT(name, x, y) name##_ARB_CNEXT(x, y)
+#define ARB_NEXT(name, x, y) name##_ARB_NEXT(x, y)
+#define ARB_CPREV(name, x, y) name##_ARB_CPREV(x, y)
+#define ARB_PREV(name, x, y) name##_ARB_PREV(x, y)
+#define ARB_CMIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \
+ name##_ARB_CMINMAX(x, ARB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x)))
+#define ARB_MIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \
+ name##_ARB_MINMAX(x, ARB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x)))
+#define ARB_CMAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
+ name##_ARB_CMINMAX(x, ARB_INF) : ARB_CNODE(x, ARB_MAXIDX(x)))
+#define ARB_MAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
+ name##_ARB_MINMAX(x, ARB_INF) : ARB_NODE(x, ARB_MAXIDX(x)))
+#define ARB_REBALANCE(name, x, y) name##_ARB_REBALANCE(x, y)
+
+#define ARB_FOREACH(x, name, head) \
+ for ((x) = ARB_MIN(name, head); \
+ (x) != NULL; \
+ (x) = name##_ARB_NEXT(head, x))
+
+#define ARB_FOREACH_FROM(x, name, y) \
+ for ((x) = (y); \
+ ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \
+ (x) = (y))
+
+#define ARB_FOREACH_SAFE(x, name, head, y) \
+ for ((x) = ARB_MIN(name, head); \
+ ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \
+ (x) = (y))
+
+#define ARB_FOREACH_REVERSE(x, name, head) \
+ for ((x) = ARB_MAX(name, head); \
+ (x) != NULL; \
+ (x) = name##_ARB_PREV(x))
+
+#define ARB_FOREACH_REVERSE_FROM(x, name, y) \
+ for ((x) = (y); \
+ ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \
+ (x) = (y))
+
+#define ARB_FOREACH_REVERSE_SAFE(x, name, head, y) \
+ for ((x) = ARB_MAX(name, head); \
+ ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \
+ (x) = (y))
+
+#define ARB_ARRFOREACH(x, field, head) \
+ for ((x) = ARB_NODES(head); \
+ ARB_SELFIDX(head, x) < ARB_MAXNODES(head); \
+ (x)++)
+
+#define ARB_ARRFOREACH_REVWCOND(x, field, head, extracond) \
+ for ((x) = ARB_NODES(head) + (ARB_MAXNODES(head) - 1); \
+ (x) >= ARB_NODES(head) && (extracond); \
+ (x)--)
+
+#define ARB_ARRFOREACH_REVERSE(x, field, head) \
+ ARB_ARRFOREACH_REVWCOND(x, field, head, 1)
+
+#endif /* _SYS_ARB_H_ */