mirror of https://github.com/F-Stack/f-stack.git
782 lines
29 KiB
C
782 lines
29 KiB
C
/*-
|
|
* SPDX-License-Identifier: BSD-2-Clause-FreeBSD
|
|
*
|
|
* Copyright 2002 Niels Provos <provos@citi.umich.edu>
|
|
* Copyright 2018-2019 Netflix, Inc.
|
|
* 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.
|
|
*
|
|
* $FreeBSD$
|
|
*/
|
|
|
|
#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_REINSERT(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_REINSERT(name, type, attr) \
|
|
attr struct type *name##_ARB_REINSERT(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_REINSERT(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_REINSERT(name, type, field, cmp, attr) \
|
|
attr struct type * \
|
|
name##_ARB_REINSERT(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_REINSERT(name, x, y) name##_ARB_REINSERT(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)
|
|
|
|
#define ARB_RESET_TREE(head, name, maxn) \
|
|
*(head) = ARB_INITIALIZER(name, maxn)
|
|
|
|
#endif /* _SYS_ARB_H_ */
|