bsd-tree.h File Reference

This header file provides a red-black tree implementation. More...

#include <sys/cdefs.h>

Go to the source code of this file.

Macros
#define	RTEMS_SPLAY_HEAD(name, type)
#define	RTEMS_SPLAY_INITIALIZER(root)    { NULL }
#define	RTEMS_SPLAY_INIT(root)
#define	RTEMS_SPLAY_ENTRY(type)
#define	RTEMS_SPLAY_LEFT(elm, field)   (elm)->field.spe_left
#define	RTEMS_SPLAY_RIGHT(elm, field)   (elm)->field.spe_right
#define	RTEMS_SPLAY_ROOT(head)   (head)->sph_root
#define	RTEMS_SPLAY_EMPTY(head)   (RTEMS_SPLAY_ROOT(head) == NULL)
#define	RTEMS_SPLAY_ROTATE_RIGHT(head, tmp, field)
#define	RTEMS_SPLAY_ROTATE_LEFT(head, tmp, field)
#define	RTEMS_SPLAY_LINKLEFT(head, tmp, field)
#define	RTEMS_SPLAY_LINKRIGHT(head, tmp, field)
#define	RTEMS_SPLAY_ASSEMBLE(head, node, left, right, field)
#define	RTEMS_SPLAY_PROTOTYPE(name, type, field, cmp)
#define	RTEMS_SPLAY_GENERATE(name, type, field, cmp)
#define	RTEMS_SPLAY_NEGINF   -1
#define	RTEMS_SPLAY_INF   1
#define	RTEMS_SPLAY_INSERT(name, x, y)   name##_RTEMS_SPLAY_INSERT(x, y)
#define	RTEMS_SPLAY_REMOVE(name, x, y)   name##_RTEMS_SPLAY_REMOVE(x, y)
#define	RTEMS_SPLAY_FIND(name, x, y)   name##_RTEMS_SPLAY_FIND(x, y)
#define	RTEMS_SPLAY_NEXT(name, x, y)   name##_RTEMS_SPLAY_NEXT(x, y)
#define	RTEMS_SPLAY_MIN(name, x)
#define	RTEMS_SPLAY_MAX(name, x)
#define	RTEMS_SPLAY_FOREACH(x, name, head)
#define	RTEMS_RB_HEAD(name, type)
#define	RTEMS_RB_INITIALIZER(root)    { NULL }
#define	RTEMS_RB_INIT(root)
#define	RTEMS_RB_BLACK   0
#define	RTEMS_RB_RED   1
#define	RTEMS_RB_ENTRY(type)
#define	RTEMS_RB_LEFT(elm, field)   (elm)->field.rbe_left
#define	RTEMS_RB_RIGHT(elm, field)   (elm)->field.rbe_right
#define	RTEMS_RB_PARENT(elm, field)   (elm)->field.rbe_parent
#define	RTEMS_RB_COLOR(elm, field)   (elm)->field.rbe_color
#define	RTEMS_RB_ISRED(elm, field)   ((elm) != NULL && RTEMS_RB_COLOR(elm, field) == RTEMS_RB_RED)
#define	RTEMS_RB_ROOT(head)   (head)->rbh_root
#define	RTEMS_RB_EMPTY(head)   (RTEMS_RB_ROOT(head) == NULL)
#define	RTEMS_RB_SET_PARENT(dst, src, field)
#define	RTEMS_RB_SET(elm, parent, field)
#define	RTEMS_RB_SET_BLACKRED(black, red, field)
#define	RTEMS_RB_AUGMENT(x)   break
#define	RTEMS_RB_SWAP_CHILD(head, out, in, field)
#define	RTEMS_RB_ROTATE_LEFT(head, elm, tmp, field)
#define	RTEMS_RB_ROTATE_RIGHT(head, elm, tmp, field)
#define	RTEMS_RB_PARENT_ROTATE_LEFT(parent, left, tmp, field)
#define	RTEMS_RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field)
#define	RTEMS_RB_RED_ROTATE_LEFT(head, elm, tmp, field)
#define	RTEMS_RB_RED_ROTATE_RIGHT(head, elm, tmp, field)
#define	RTEMS_RB_PROTOTYPE(name, type, field, cmp)    RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
#define	RTEMS_RB_PROTOTYPE_STATIC(name, type, field, cmp)    RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
#define	RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)
#define	RTEMS_RB_PROTOTYPE_INSERT_COLOR(name, type, attr)    attr void name##_RTEMS_RB_INSERT_COLOR(struct name *, struct type *)
#define	RTEMS_RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)    attr void name##_RTEMS_RB_REMOVE_COLOR(struct name *, struct type *)
#define	RTEMS_RB_PROTOTYPE_REMOVE(name, type, attr)    attr struct type *name##_RTEMS_RB_REMOVE(struct name *, struct type *)
#define	RTEMS_RB_PROTOTYPE_INSERT(name, type, attr)    attr struct type *name##_RTEMS_RB_INSERT(struct name *, struct type *)
#define	RTEMS_RB_PROTOTYPE_FIND(name, type, attr)    attr struct type *name##_RTEMS_RB_FIND(struct name *, struct type *)
#define	RTEMS_RB_PROTOTYPE_NFIND(name, type, attr)    attr struct type *name##_RTEMS_RB_NFIND(struct name *, struct type *)
#define	RTEMS_RB_PROTOTYPE_NEXT(name, type, attr)    attr struct type *name##_RTEMS_RB_NEXT(struct type *)
#define	RTEMS_RB_PROTOTYPE_PREV(name, type, attr)    attr struct type *name##_RTEMS_RB_PREV(struct type *)
#define	RTEMS_RB_PROTOTYPE_MINMAX(name, type, attr)    attr struct type *name##_RTEMS_RB_MINMAX(struct name *, int)
#define	RTEMS_RB_PROTOTYPE_REINSERT(name, type, attr)    attr struct type *name##_RTEMS_RB_REINSERT(struct name *, struct type *)
#define	RTEMS_RB_GENERATE(name, type, field, cmp)    RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp,)
#define	RTEMS_RB_GENERATE_STATIC(name, type, field, cmp)    RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
#define	RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp, attr)
#define	RTEMS_RB_GENERATE_INSERT_COLOR(name, type, field, attr)
#define	RTEMS_RB_GENERATE_REMOVE_COLOR(name, type, field, attr)
#define	RTEMS_RB_GENERATE_REMOVE(name, type, field, attr)
#define	RTEMS_RB_GENERATE_INSERT(name, type, field, cmp, attr)
#define	RTEMS_RB_GENERATE_FIND(name, type, field, cmp, attr)
#define	RTEMS_RB_GENERATE_NFIND(name, type, field, cmp, attr)
#define	RTEMS_RB_GENERATE_NEXT(name, type, field, attr)
#define	RTEMS_RB_GENERATE_PREV(name, type, field, attr)
#define	RTEMS_RB_GENERATE_MINMAX(name, type, field, attr)
#define	RTEMS_RB_GENERATE_REINSERT(name, type, field, cmp, attr)
#define	RTEMS_RB_NEGINF   -1
#define	RTEMS_RB_INF   1
#define	RTEMS_RB_INSERT(name, x, y)   name##_RTEMS_RB_INSERT(x, y)
#define	RTEMS_RB_REMOVE(name, x, y)   name##_RTEMS_RB_REMOVE(x, y)
#define	RTEMS_RB_FIND(name, x, y)   name##_RTEMS_RB_FIND(x, y)
#define	RTEMS_RB_NFIND(name, x, y)   name##_RTEMS_RB_NFIND(x, y)
#define	RTEMS_RB_NEXT(name, x, y)   name##_RTEMS_RB_NEXT(y)
#define	RTEMS_RB_PREV(name, x, y)   name##_RTEMS_RB_PREV(y)
#define	RTEMS_RB_MIN(name, x)   name##_RTEMS_RB_MINMAX(x, RTEMS_RB_NEGINF)
#define	RTEMS_RB_MAX(name, x)   name##_RTEMS_RB_MINMAX(x, RTEMS_RB_INF)
#define	RTEMS_RB_REINSERT(name, x, y)   name##_RTEMS_RB_REINSERT(x, y)
#define	RTEMS_RB_FOREACH(x, name, head)
#define	RTEMS_RB_FOREACH_FROM(x, name, y)
#define	RTEMS_RB_FOREACH_SAFE(x, name, head, y)
#define	RTEMS_RB_FOREACH_REVERSE(x, name, head)
#define	RTEMS_RB_FOREACH_REVERSE_FROM(x, name, y)
#define	RTEMS_RB_FOREACH_REVERSE_SAFE(x, name, head, y)

Detailed Description

This header file provides a red-black tree implementation.

The contents of this file come from the above version of FreeBSD with local changes applied in Newlib and then migrated to RTEMS. These changes lock RTEMS to a specific version of this file. As a result, the macros defined in this file have been scoped with an RTEMS_ namespace. This allows other versions of tree.h to be used by RTEMS libraries and applications without conflicts.

Macro Definition Documentation

RTEMS_RB_ENTRY

#define RTEMS_RB_ENTRY

(

type

)

Value:

struct {                                \
    struct type *rbe_left;      /* left element */      \
    struct type *rbe_right;     /* right element */     \
    struct type *rbe_parent;    /* parent element */        \
    int rbe_color;          /* node color */        \
}

RTEMS_RB_FOREACH

#define RTEMS_RB_FOREACH	(		x,
			name,
			head
	)

Value:

    for ((x) = RTEMS_RB_MIN(name, head);                    \
         (x) != NULL;                       \
         (x) = name##_RTEMS_RB_NEXT(x))

RTEMS_RB_FOREACH_FROM

#define RTEMS_RB_FOREACH_FROM	(		x,
			name,
			y
	)

Value:

    for ((x) = (y);                         \
        ((x) != NULL) && ((y) = name##_RTEMS_RB_NEXT(x), (x) != NULL);  \
         (x) = (y))

RTEMS_RB_FOREACH_REVERSE

#define RTEMS_RB_FOREACH_REVERSE	(		x,
			name,
			head
	)

Value:

    for ((x) = RTEMS_RB_MAX(name, head);                    \
         (x) != NULL;                       \
         (x) = name##_RTEMS_RB_PREV(x))

RTEMS_RB_FOREACH_REVERSE_FROM

#define RTEMS_RB_FOREACH_REVERSE_FROM	(		x,
			name,
			y
	)

Value:

    for ((x) = (y);                         \
        ((x) != NULL) && ((y) = name##_RTEMS_RB_PREV(x), (x) != NULL);  \
         (x) = (y))

RTEMS_RB_FOREACH_REVERSE_SAFE

#define RTEMS_RB_FOREACH_REVERSE_SAFE	(		x,
			name,
			head,
			y
	)

Value:

    for ((x) = RTEMS_RB_MAX(name, head);                    \
        ((x) != NULL) && ((y) = name##_RTEMS_RB_PREV(x), (x) != NULL);  \
         (x) = (y))

RTEMS_RB_FOREACH_SAFE

#define RTEMS_RB_FOREACH_SAFE	(		x,
			name,
			head,
			y
	)

Value:

    for ((x) = RTEMS_RB_MIN(name, head);                    \
        ((x) != NULL) && ((y) = name##_RTEMS_RB_NEXT(x), (x) != NULL);  \
         (x) = (y))

RTEMS_RB_GENERATE_FIND

#define RTEMS_RB_GENERATE_FIND	(		name,
			type,
			field,
			cmp,
			attr
	)

Value:

/* Finds the node with the same key as elm */               \
attr struct type *                          \
name##_RTEMS_RB_FIND(struct name *head, struct type *elm)           \
{                                   \
    struct type *tmp = RTEMS_RB_ROOT(head);             \
    int comp;                           \
    while (tmp) {                           \
        comp = cmp(elm, tmp);                   \
        if (comp < 0)                       \
            tmp = RTEMS_RB_LEFT(tmp, field);            \
        else if (comp > 0)                  \
            tmp = RTEMS_RB_RIGHT(tmp, field);           \
        else                            \
            return (tmp);                   \
    }                               \
    return (NULL);                          \
}

RTEMS_RB_GENERATE_INTERNAL

#define RTEMS_RB_GENERATE_INTERNAL	(		name,
			type,
			field,
			cmp,
			attr
	)

Value:

    RTEMS_RB_GENERATE_INSERT_COLOR(name, type, field, attr)     \
    RTEMS_RB_GENERATE_REMOVE_COLOR(name, type, field, attr)     \
    RTEMS_RB_GENERATE_INSERT(name, type, field, cmp, attr)      \
    RTEMS_RB_GENERATE_REMOVE(name, type, field, attr)           \
    RTEMS_RB_GENERATE_FIND(name, type, field, cmp, attr)            \
    RTEMS_RB_GENERATE_NFIND(name, type, field, cmp, attr)           \
    RTEMS_RB_GENERATE_NEXT(name, type, field, attr)         \
    RTEMS_RB_GENERATE_PREV(name, type, field, attr)         \
    RTEMS_RB_GENERATE_MINMAX(name, type, field, attr)           \
    RTEMS_RB_GENERATE_REINSERT(name, type, field, cmp, attr)

RTEMS_RB_GENERATE_MINMAX

#define RTEMS_RB_GENERATE_MINMAX	(		name,
			type,
			field,
			attr
	)

Value:

attr struct type *                          \
name##_RTEMS_RB_MINMAX(struct name *head, int val)              \
{                                   \
    struct type *tmp = RTEMS_RB_ROOT(head);             \
    struct type *parent = NULL;                 \
    while (tmp) {                           \
        parent = tmp;                       \
        if (val < 0)                        \
            tmp = RTEMS_RB_LEFT(tmp, field);            \
        else                            \
            tmp = RTEMS_RB_RIGHT(tmp, field);           \
    }                               \
    return (parent);                        \
}

RTEMS_RB_GENERATE_NEXT

#define RTEMS_RB_GENERATE_NEXT	(		name,
			type,
			field,
			attr
	)

Value:

/* ARGSUSED */                              \
attr struct type *                          \
name##_RTEMS_RB_NEXT(struct type *elm)                  \
{                                   \
    if (RTEMS_RB_RIGHT(elm, field)) {                   \
        elm = RTEMS_RB_RIGHT(elm, field);               \
        while (RTEMS_RB_LEFT(elm, field))               \
            elm = RTEMS_RB_LEFT(elm, field);            \
    } else {                            \
        if (RTEMS_RB_PARENT(elm, field) &&              \
            (elm == RTEMS_RB_LEFT(RTEMS_RB_PARENT(elm, field), field))) \
            elm = RTEMS_RB_PARENT(elm, field);          \
        else {                          \
            while (RTEMS_RB_PARENT(elm, field) &&           \
                (elm == RTEMS_RB_RIGHT(RTEMS_RB_PARENT(elm, field), field)))\
                elm = RTEMS_RB_PARENT(elm, field);      \
            elm = RTEMS_RB_PARENT(elm, field);          \
        }                           \
    }                               \
    return (elm);                           \
}

RTEMS_RB_GENERATE_NFIND

#define RTEMS_RB_GENERATE_NFIND	(		name,
			type,
			field,
			cmp,
			attr
	)

Value:

/* Finds the first node greater than or equal to the search key */  \
attr struct type *                          \
name##_RTEMS_RB_NFIND(struct name *head, struct type *elm)          \
{                                   \
    struct type *tmp = RTEMS_RB_ROOT(head);             \
    struct type *res = NULL;                    \
    int comp;                           \
    while (tmp) {                           \
        comp = cmp(elm, tmp);                   \
        if (comp < 0) {                     \
            res = tmp;                  \
            tmp = RTEMS_RB_LEFT(tmp, field);            \
        }                           \
        else if (comp > 0)                  \
            tmp = RTEMS_RB_RIGHT(tmp, field);           \
        else                            \
            return (tmp);                   \
    }                               \
    return (res);                           \
}

RTEMS_RB_GENERATE_PREV

#define RTEMS_RB_GENERATE_PREV	(		name,
			type,
			field,
			attr
	)

Value:

/* ARGSUSED */                              \
attr struct type *                          \
name##_RTEMS_RB_PREV(struct type *elm)                  \
{                                   \
    if (RTEMS_RB_LEFT(elm, field)) {                    \
        elm = RTEMS_RB_LEFT(elm, field);                \
        while (RTEMS_RB_RIGHT(elm, field))              \
            elm = RTEMS_RB_RIGHT(elm, field);           \
    } else {                            \
        if (RTEMS_RB_PARENT(elm, field) &&              \
            (elm == RTEMS_RB_RIGHT(RTEMS_RB_PARENT(elm, field), field)))    \
            elm = RTEMS_RB_PARENT(elm, field);          \
        else {                          \
            while (RTEMS_RB_PARENT(elm, field) &&           \
                (elm == RTEMS_RB_LEFT(RTEMS_RB_PARENT(elm, field), field)))\
                elm = RTEMS_RB_PARENT(elm, field);      \
            elm = RTEMS_RB_PARENT(elm, field);          \
        }                           \
    }                               \
    return (elm);                           \
}

RTEMS_RB_GENERATE_REINSERT

#define RTEMS_RB_GENERATE_REINSERT	(		name,
			type,
			field,
			cmp,
			attr
	)

Value:

attr struct type *                          \
name##_RTEMS_RB_REINSERT(struct name *head, struct type *elm)           \
{                                   \
    struct type *cmpelm;                        \
    if (((cmpelm = RTEMS_RB_PREV(name, head, elm)) != NULL &&       \
        cmp(cmpelm, elm) >= 0) ||                   \
        ((cmpelm = RTEMS_RB_NEXT(name, head, elm)) != NULL &&       \
        cmp(elm, cmpelm) >= 0)) {                   \
        /* XXXLAS: Remove/insert is heavy handed. */        \
        RTEMS_RB_REMOVE(name, head, elm);               \
        return (RTEMS_RB_INSERT(name, head, elm));          \
    }                               \
    return (NULL);                          \
}                                   \

RTEMS_RB_HEAD

#define RTEMS_RB_HEAD	(		name,
			type
	)

Value:

struct name {                               \
    struct type *rbh_root; /* root of the tree */           \
}

RTEMS_RB_INIT

#define RTEMS_RB_INIT

(

root

)

Value:

    do {                        \
    (root)->rbh_root = NULL;                    \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_PARENT_ROTATE_LEFT

#define RTEMS_RB_PARENT_ROTATE_LEFT	(		parent,
			left,
			tmp,
			field
	)

Value:

    do {        \
    (tmp) = RTEMS_RB_RIGHT(left, field);                    \
    if ((RTEMS_RB_RIGHT(left, field) = RTEMS_RB_LEFT(tmp, field)) != NULL) {    \
        RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(left, field), left, field);  \
    }                               \
    RTEMS_RB_SET_PARENT(tmp, parent, field);                \
    RTEMS_RB_LEFT(parent, field) = (tmp);                   \
    RTEMS_RB_LEFT(tmp, field) = (left);                 \
    RTEMS_RB_SET_PARENT(left, tmp, field);              \
    RTEMS_RB_AUGMENT(left);                     \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_PARENT_ROTATE_RIGHT

#define RTEMS_RB_PARENT_ROTATE_RIGHT	(		parent,
			right,
			tmp,
			field
	)

Value:

    do {        \
    (tmp) = RTEMS_RB_LEFT(right, field);                    \
    if ((RTEMS_RB_LEFT(right, field) = RTEMS_RB_RIGHT(tmp, field)) != NULL) {   \
        RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(right, field), right, field); \
    }                               \
    RTEMS_RB_SET_PARENT(tmp, parent, field);                \
    RTEMS_RB_RIGHT(parent, field) = (tmp);              \
    RTEMS_RB_RIGHT(tmp, field) = (right);                   \
    RTEMS_RB_SET_PARENT(right, tmp, field);             \
    RTEMS_RB_AUGMENT(right);                        \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_PROTOTYPE_INTERNAL

#define RTEMS_RB_PROTOTYPE_INTERNAL	(		name,
			type,
			field,
			cmp,
			attr
	)

Value:

    RTEMS_RB_PROTOTYPE_INSERT_COLOR(name, type, attr);          \
    RTEMS_RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);          \
    RTEMS_RB_PROTOTYPE_INSERT(name, type, attr);                \
    RTEMS_RB_PROTOTYPE_REMOVE(name, type, attr);                \
    RTEMS_RB_PROTOTYPE_FIND(name, type, attr);              \
    RTEMS_RB_PROTOTYPE_NFIND(name, type, attr);             \
    RTEMS_RB_PROTOTYPE_NEXT(name, type, attr);              \
    RTEMS_RB_PROTOTYPE_PREV(name, type, attr);              \
    RTEMS_RB_PROTOTYPE_MINMAX(name, type, attr);                \
    RTEMS_RB_PROTOTYPE_REINSERT(name, type, attr);

RTEMS_RB_RED_ROTATE_LEFT

#define RTEMS_RB_RED_ROTATE_LEFT	(		head,
			elm,
			tmp,
			field
	)

Value:

    do {            \
    (tmp) = RTEMS_RB_RIGHT(elm, field);                 \
    RTEMS_RB_RIGHT(elm, field) = RTEMS_RB_LEFT(tmp, field);         \
    RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(elm, field), elm, field);        \
    RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field);       \
    RTEMS_RB_SWAP_CHILD(head, elm, tmp, field);             \
    RTEMS_RB_LEFT(tmp, field) = (elm);                  \
    RTEMS_RB_SET_PARENT(elm, tmp, field);                   \
    RTEMS_RB_AUGMENT(elm);                      \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_RED_ROTATE_RIGHT

#define RTEMS_RB_RED_ROTATE_RIGHT	(		head,
			elm,
			tmp,
			field
	)

Value:

    do {            \
    (tmp) = RTEMS_RB_LEFT(elm, field);                  \
    RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(tmp, field);         \
    RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(elm, field), elm, field);         \
    RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field);       \
    RTEMS_RB_SWAP_CHILD(head, elm, tmp, field);             \
    RTEMS_RB_RIGHT(tmp, field) = (elm);                 \
    RTEMS_RB_SET_PARENT(elm, tmp, field);                   \
    RTEMS_RB_AUGMENT(elm);                      \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_ROTATE_LEFT

#define RTEMS_RB_ROTATE_LEFT	(		head,
			elm,
			tmp,
			field
	)

Value:

    do {            \
    (tmp) = RTEMS_RB_RIGHT(elm, field);                 \
    if ((RTEMS_RB_RIGHT(elm, field) = RTEMS_RB_LEFT(tmp, field)) != NULL) { \
        RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(elm, field), elm, field);    \
    }                               \
    RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field);       \
    RTEMS_RB_SWAP_CHILD(head, elm, tmp, field);             \
    RTEMS_RB_LEFT(tmp, field) = (elm);                  \
    RTEMS_RB_SET_PARENT(elm, tmp, field);                   \
    RTEMS_RB_AUGMENT(elm);                      \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_ROTATE_RIGHT

#define RTEMS_RB_ROTATE_RIGHT	(		head,
			elm,
			tmp,
			field
	)

Value:

    do {            \
    (tmp) = RTEMS_RB_LEFT(elm, field);                  \
    if ((RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(tmp, field)) != NULL) { \
        RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(elm, field), elm, field);     \
    }                               \
    RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field);       \
    RTEMS_RB_SWAP_CHILD(head, elm, tmp, field);             \
    RTEMS_RB_RIGHT(tmp, field) = (elm);                 \
    RTEMS_RB_SET_PARENT(elm, tmp, field);                   \
    RTEMS_RB_AUGMENT(elm);                      \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_SET

#define RTEMS_RB_SET	(		elm,
			parent,
			field
	)

Value:

    do {                    \
    RTEMS_RB_SET_PARENT(elm, parent, field);                \
    RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(elm, field) = NULL;      \
    RTEMS_RB_COLOR(elm, field) = RTEMS_RB_RED;                  \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_SET_BLACKRED

#define RTEMS_RB_SET_BLACKRED	(		black,
			red,
			field
	)

Value:

    do {                \
    RTEMS_RB_COLOR(black, field) = RTEMS_RB_BLACK;              \
    RTEMS_RB_COLOR(red, field) = RTEMS_RB_RED;                  \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_SET_PARENT

#define RTEMS_RB_SET_PARENT	(		dst,
			src,
			field
	)

Value:

    do {                \
    RTEMS_RB_PARENT(dst, field) = src;                  \
} while (/*CONSTCOND*/ 0)

RTEMS_RB_SWAP_CHILD

#define RTEMS_RB_SWAP_CHILD	(		head,
			out,
			in,
			field
	)

Value:

    do {            \
    if (RTEMS_RB_PARENT(out, field) == NULL)                \
        RTEMS_RB_ROOT(head) = (in);                 \
    else if ((out) == RTEMS_RB_LEFT(RTEMS_RB_PARENT(out, field), field))    \
        RTEMS_RB_LEFT(RTEMS_RB_PARENT(out, field), field) = (in);       \
    else                                \
        RTEMS_RB_RIGHT(RTEMS_RB_PARENT(out, field), field) = (in);      \
} while (/*CONSTCOND*/ 0)

RTEMS_SPLAY_ASSEMBLE

#define RTEMS_SPLAY_ASSEMBLE	(		head,
			node,
			left,
			right,
			field
	)

Value:

    do {        \
    RTEMS_SPLAY_RIGHT(left, field) = RTEMS_SPLAY_LEFT((head)->sph_root, field); \
    RTEMS_SPLAY_LEFT(right, field) = RTEMS_SPLAY_RIGHT((head)->sph_root, field);\
    RTEMS_SPLAY_LEFT((head)->sph_root, field) = RTEMS_SPLAY_RIGHT(node, field); \
    RTEMS_SPLAY_RIGHT((head)->sph_root, field) = RTEMS_SPLAY_LEFT(node, field); \
} while (/*CONSTCOND*/ 0)

RTEMS_SPLAY_ENTRY

#define RTEMS_SPLAY_ENTRY

(

type

)

Value:

struct {                                \
    struct type *spe_left; /* left element */           \
    struct type *spe_right; /* right element */         \
}

RTEMS_SPLAY_FOREACH

#define RTEMS_SPLAY_FOREACH	(		x,
			name,
			head
	)

Value:

    for ((x) = RTEMS_SPLAY_MIN(name, head);             \
         (x) != NULL;                       \
         (x) = RTEMS_SPLAY_NEXT(name, head, x))

RTEMS_SPLAY_HEAD

#define RTEMS_SPLAY_HEAD	(		name,
			type
	)

Value:

struct name {                               \
    struct type *sph_root; /* root of the tree */           \
}

RTEMS_SPLAY_INIT

#define RTEMS_SPLAY_INIT

(

root

)

Value:

    do {                        \
    (root)->sph_root = NULL;                    \
} while (/*CONSTCOND*/ 0)

RTEMS_SPLAY_LINKLEFT

#define RTEMS_SPLAY_LINKLEFT	(		head,
			tmp,
			field
	)

Value:

    do {                \
    RTEMS_SPLAY_LEFT(tmp, field) = (head)->sph_root;            \
    tmp = (head)->sph_root;                     \
    (head)->sph_root = RTEMS_SPLAY_LEFT((head)->sph_root, field);       \
} while (/*CONSTCOND*/ 0)

RTEMS_SPLAY_LINKRIGHT

#define RTEMS_SPLAY_LINKRIGHT	(		head,
			tmp,
			field
	)

Value:

    do {                \
    RTEMS_SPLAY_RIGHT(tmp, field) = (head)->sph_root;           \
    tmp = (head)->sph_root;                     \
    (head)->sph_root = RTEMS_SPLAY_RIGHT((head)->sph_root, field);  \
} while (/*CONSTCOND*/ 0)

RTEMS_SPLAY_MAX

#define RTEMS_SPLAY_MAX	(		name,
			x
	)

Value:

                    (RTEMS_SPLAY_EMPTY(x) ? NULL    \
                    : name##_RTEMS_SPLAY_MIN_MAX(x, RTEMS_SPLAY_INF))

RTEMS_SPLAY_MIN

#define RTEMS_SPLAY_MIN	(		name,
			x
	)

Value:

                    (RTEMS_SPLAY_EMPTY(x) ? NULL    \
                    : name##_RTEMS_SPLAY_MIN_MAX(x, RTEMS_SPLAY_NEGINF))

RTEMS_SPLAY_ROTATE_LEFT

#define RTEMS_SPLAY_ROTATE_LEFT	(		head,
			tmp,
			field
	)

Value:

    do {            \
    RTEMS_SPLAY_RIGHT((head)->sph_root, field) = RTEMS_SPLAY_LEFT(tmp, field);  \
    RTEMS_SPLAY_LEFT(tmp, field) = (head)->sph_root;            \
    (head)->sph_root = tmp;                     \
} while (/*CONSTCOND*/ 0)

RTEMS_SPLAY_ROTATE_RIGHT

#define RTEMS_SPLAY_ROTATE_RIGHT	(		head,
			tmp,
			field
	)

Value:

    do {            \
    RTEMS_SPLAY_LEFT((head)->sph_root, field) = RTEMS_SPLAY_RIGHT(tmp, field);  \
    RTEMS_SPLAY_RIGHT(tmp, field) = (head)->sph_root;           \
    (head)->sph_root = tmp;                     \
} while (/*CONSTCOND*/ 0)