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

#include <sys/cdefs.h>

Macros
#define	RTEMS_SPLAY_HEAD(name, type)
#define	RTEMS_SPLAY_INITIALIZER(root)
#define	RTEMS_SPLAY_INIT(root)
#define	RTEMS_SPLAY_ENTRY(type)
#define	RTEMS_SPLAY_LEFT(elm, field)
#define	RTEMS_SPLAY_RIGHT(elm, field)
#define	RTEMS_SPLAY_ROOT(head)
#define	RTEMS_SPLAY_EMPTY(head)
#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)
#define	RTEMS_SPLAY_REMOVE(name, x, y)
#define	RTEMS_SPLAY_FIND(name, x, y)
#define	RTEMS_SPLAY_NEXT(name, 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)
#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)
#define	RTEMS_RB_RIGHT(elm, field)
#define	RTEMS_RB_PARENT(elm, field)
#define	RTEMS_RB_COLOR(elm, field)
#define	RTEMS_RB_ISRED(elm, field)
#define	RTEMS_RB_ROOT(head)
#define	RTEMS_RB_EMPTY(head)
#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)
#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)
#define	RTEMS_RB_PROTOTYPE_STATIC(name, type, field, cmp)
#define	RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)
#define	RTEMS_RB_PROTOTYPE_INSERT_COLOR(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_REMOVE(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_INSERT(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_FIND(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_NFIND(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_NEXT(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_PREV(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_MINMAX(name, type, attr)
#define	RTEMS_RB_PROTOTYPE_REINSERT(name, type, attr)
#define	RTEMS_RB_GENERATE(name, type, field, cmp)
#define	RTEMS_RB_GENERATE_STATIC(name, type, field, cmp)
#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)
#define	RTEMS_RB_REMOVE(name, x, y)
#define	RTEMS_RB_FIND(name, x, y)
#define	RTEMS_RB_NFIND(name, x, y)
#define	RTEMS_RB_NEXT(name, x, y)
#define	RTEMS_RB_PREV(name, x, y)
#define	RTEMS_RB_MIN(name, x)
#define	RTEMS_RB_MAX(name, x)
#define	RTEMS_RB_REINSERT(name, 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_AUGMENT

#define RTEMS_RB_AUGMENT ( x )

Value:

break

◆ RTEMS_RB_COLOR

#define RTEMS_RB_COLOR	(		elm,
			field )

Value:

(elm)->field.rbe_color

◆ RTEMS_RB_EMPTY

#define RTEMS_RB_EMPTY ( head )

Value:

(RTEMS_RB_ROOT(head) == NULL)

◆ RTEMS_RB_ENTRY

#define RTEMS_RB_ENTRY ( type )

Value:

struct {                                \
    struct type *rbe_left;              \
    struct type *rbe_right;             \
    struct type *rbe_parent;            \
    int rbe_color;                  \
}

◆ RTEMS_RB_FIND

#define RTEMS_RB_FIND	(	name,
		x,
		y )

Value:

name##_RTEMS_RB_FIND(x, y)

◆ 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

#define RTEMS_RB_GENERATE	(	name,
		type,
		field,
		cmp )

Value:

RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp,)

◆ RTEMS_RB_GENERATE_FIND

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

Value:

                \
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:

                                \
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:

    \
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:

                                \
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)) {                   \
                \
        RTEMS_RB_REMOVE(name, head, elm);               \
        return (RTEMS_RB_INSERT(name, head, elm));          \
    }                               \
    return (NULL);                          \
}                                   \

◆ RTEMS_RB_GENERATE_STATIC

#define RTEMS_RB_GENERATE_STATIC	(	name,
		type,
		field,
		cmp )

Value:

RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)

◆ RTEMS_RB_HEAD

#define RTEMS_RB_HEAD	(		name,
			type )

Value:

struct name {                               \
    struct type *rbh_root;              \
}

◆ RTEMS_RB_INIT

#define RTEMS_RB_INIT ( root )

Value:

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

◆ RTEMS_RB_INITIALIZER

#define RTEMS_RB_INITIALIZER ( root )

Value:

{ NULL }

◆ RTEMS_RB_INSERT

#define RTEMS_RB_INSERT	(	name,
		x,
		y )

Value:

name##_RTEMS_RB_INSERT(x, y)

◆ RTEMS_RB_ISRED

#define RTEMS_RB_ISRED	(		elm,
			field )

Value:

((elm) != NULL && RTEMS_RB_COLOR(elm, field) == RTEMS_RB_RED)

◆ RTEMS_RB_LEFT

#define RTEMS_RB_LEFT	(		elm,
			field )

Value:

(elm)->field.rbe_left

◆ RTEMS_RB_MAX

#define RTEMS_RB_MAX	(		name,
			x )

Value:

name##_RTEMS_RB_MINMAX(x, RTEMS_RB_INF)

◆ RTEMS_RB_MIN

#define RTEMS_RB_MIN	(		name,
			x )

Value:

name##_RTEMS_RB_MINMAX(x, RTEMS_RB_NEGINF)

◆ RTEMS_RB_NEXT

#define RTEMS_RB_NEXT	(	name,
		x,
		y )

Value:

name##_RTEMS_RB_NEXT(y)

◆ RTEMS_RB_NFIND

#define RTEMS_RB_NFIND	(	name,
		x,
		y )

Value:

name##_RTEMS_RB_NFIND(x, y)

◆ RTEMS_RB_PARENT

#define RTEMS_RB_PARENT	(		elm,
			field )

Value:

(elm)->field.rbe_parent

◆ 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 (  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 (  0)

◆ RTEMS_RB_PREV

#define RTEMS_RB_PREV	(	name,
		x,
		y )

Value:

name##_RTEMS_RB_PREV(y)

◆ RTEMS_RB_PROTOTYPE

#define RTEMS_RB_PROTOTYPE	(	name,
		type,
		field,
		cmp )

Value:

RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)

◆ RTEMS_RB_PROTOTYPE_FIND

#define RTEMS_RB_PROTOTYPE_FIND	(	name,
		type,
		attr )

Value:

attr struct type *name##_RTEMS_RB_FIND(struct name *, struct type *)

◆ RTEMS_RB_PROTOTYPE_INSERT

#define RTEMS_RB_PROTOTYPE_INSERT	(	name,
		type,
		attr )

Value:

attr struct type *name##_RTEMS_RB_INSERT(struct name *, struct type *)

◆ RTEMS_RB_PROTOTYPE_INSERT_COLOR

#define RTEMS_RB_PROTOTYPE_INSERT_COLOR	(	name,
		type,
		attr )

Value:

attr void name##_RTEMS_RB_INSERT_COLOR(struct name *, struct type *)

◆ 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_PROTOTYPE_MINMAX

#define RTEMS_RB_PROTOTYPE_MINMAX	(	name,
		type,
		attr )

Value:

attr struct type *name##_RTEMS_RB_MINMAX(struct name *, int)

◆ RTEMS_RB_PROTOTYPE_NEXT

#define RTEMS_RB_PROTOTYPE_NEXT	(	name,
		type,
		attr )

Value:

attr struct type *name##_RTEMS_RB_NEXT(struct type *)

◆ RTEMS_RB_PROTOTYPE_NFIND

#define RTEMS_RB_PROTOTYPE_NFIND	(	name,
		type,
		attr )

Value:

attr struct type *name##_RTEMS_RB_NFIND(struct name *, struct type *)

◆ RTEMS_RB_PROTOTYPE_PREV

#define RTEMS_RB_PROTOTYPE_PREV	(	name,
		type,
		attr )

Value:

attr struct type *name##_RTEMS_RB_PREV(struct type *)

◆ RTEMS_RB_PROTOTYPE_REINSERT

#define RTEMS_RB_PROTOTYPE_REINSERT	(	name,
		type,
		attr )

Value:

attr struct type *name##_RTEMS_RB_REINSERT(struct name *, struct type *)

◆ RTEMS_RB_PROTOTYPE_REMOVE

#define RTEMS_RB_PROTOTYPE_REMOVE	(	name,
		type,
		attr )

Value:

attr struct type *name##_RTEMS_RB_REMOVE(struct name *, struct type *)

◆ RTEMS_RB_PROTOTYPE_REMOVE_COLOR

#define RTEMS_RB_PROTOTYPE_REMOVE_COLOR	(	name,
		type,
		attr )

Value:

attr void name##_RTEMS_RB_REMOVE_COLOR(struct name *, struct type *)

◆ RTEMS_RB_PROTOTYPE_STATIC

#define RTEMS_RB_PROTOTYPE_STATIC	(	name,
		type,
		field,
		cmp )

Value:

RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)

◆ 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 (  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 (  0)

◆ RTEMS_RB_REINSERT

#define RTEMS_RB_REINSERT	(	name,
		x,
		y )

Value:

name##_RTEMS_RB_REINSERT(x, y)

◆ RTEMS_RB_REMOVE

#define RTEMS_RB_REMOVE	(	name,
		x,
		y )

Value:

name##_RTEMS_RB_REMOVE(x, y)

◆ RTEMS_RB_RIGHT

#define RTEMS_RB_RIGHT	(		elm,
			field )

Value:

(elm)->field.rbe_right

◆ RTEMS_RB_ROOT

#define RTEMS_RB_ROOT ( head )

Value:

(head)->rbh_root

◆ 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 (  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 (  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 (  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 (  0)

◆ RTEMS_RB_SET_PARENT

#define RTEMS_RB_SET_PARENT	(	dst,
		src,
		field )

Value:

    do {                \
    RTEMS_RB_PARENT(dst, field) = src;                  \
} while (  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 (  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 (  0)

◆ RTEMS_SPLAY_EMPTY

#define RTEMS_SPLAY_EMPTY ( head )

Value:

(RTEMS_SPLAY_ROOT(head) == NULL)

◆ RTEMS_SPLAY_ENTRY

#define RTEMS_SPLAY_ENTRY ( type )

Value:

struct {                                \
    struct type *spe_left;              \
    struct type *spe_right;             \
}

◆ RTEMS_SPLAY_FIND

#define RTEMS_SPLAY_FIND	(	name,
		x,
		y )

Value:

name##_RTEMS_SPLAY_FIND(x, y)

◆ 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;              \
}

◆ RTEMS_SPLAY_INIT

#define RTEMS_SPLAY_INIT ( root )

Value:

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

◆ RTEMS_SPLAY_INITIALIZER

#define RTEMS_SPLAY_INITIALIZER ( root )

Value:

{ NULL }

◆ RTEMS_SPLAY_INSERT

#define RTEMS_SPLAY_INSERT	(	name,
		x,
		y )

Value:

name##_RTEMS_SPLAY_INSERT(x, y)

◆ RTEMS_SPLAY_LEFT

#define RTEMS_SPLAY_LEFT	(		elm,
			field )

Value:

(elm)->field.spe_left

◆ 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 (  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 (  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_NEXT

#define RTEMS_SPLAY_NEXT	(	name,
		x,
		y )

Value:

name##_RTEMS_SPLAY_NEXT(x, y)

◆ RTEMS_SPLAY_REMOVE

#define RTEMS_SPLAY_REMOVE	(	name,
		x,
		y )

Value:

name##_RTEMS_SPLAY_REMOVE(x, y)

◆ RTEMS_SPLAY_RIGHT

#define RTEMS_SPLAY_RIGHT	(		elm,
			field )

Value:

(elm)->field.spe_right

◆ RTEMS_SPLAY_ROOT

#define RTEMS_SPLAY_ROOT ( head )

Value:

(head)->sph_root

◆ 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 (  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 (  0)

Macros

Detailed Description

Macro Definition Documentation

◆ RTEMS_RB_AUGMENT

◆ RTEMS_RB_COLOR

◆ RTEMS_RB_EMPTY

◆ RTEMS_RB_ENTRY

◆ RTEMS_RB_FIND

◆ RTEMS_RB_FOREACH

◆ RTEMS_RB_FOREACH_FROM

◆ RTEMS_RB_FOREACH_REVERSE

◆ RTEMS_RB_FOREACH_REVERSE_FROM

◆ RTEMS_RB_FOREACH_REVERSE_SAFE

◆ RTEMS_RB_FOREACH_SAFE

◆ RTEMS_RB_GENERATE

◆ RTEMS_RB_GENERATE_FIND

◆ RTEMS_RB_GENERATE_INTERNAL

◆ RTEMS_RB_GENERATE_MINMAX

◆ RTEMS_RB_GENERATE_NEXT

◆ RTEMS_RB_GENERATE_NFIND

◆ RTEMS_RB_GENERATE_PREV

◆ RTEMS_RB_GENERATE_REINSERT

◆ RTEMS_RB_GENERATE_STATIC

◆ RTEMS_RB_HEAD

◆ RTEMS_RB_INIT

◆ RTEMS_RB_INITIALIZER

◆ RTEMS_RB_INSERT

◆ RTEMS_RB_ISRED

◆ RTEMS_RB_LEFT

◆ RTEMS_RB_MAX

◆ RTEMS_RB_MIN

◆ RTEMS_RB_NEXT

◆ RTEMS_RB_NFIND

◆ RTEMS_RB_PARENT

◆ RTEMS_RB_PARENT_ROTATE_LEFT

◆ RTEMS_RB_PARENT_ROTATE_RIGHT

◆ RTEMS_RB_PREV

◆ RTEMS_RB_PROTOTYPE

◆ RTEMS_RB_PROTOTYPE_FIND

◆ RTEMS_RB_PROTOTYPE_INSERT

◆ RTEMS_RB_PROTOTYPE_INSERT_COLOR

◆ RTEMS_RB_PROTOTYPE_INTERNAL

◆ RTEMS_RB_PROTOTYPE_MINMAX

◆ RTEMS_RB_PROTOTYPE_NEXT

◆ RTEMS_RB_PROTOTYPE_NFIND

◆ RTEMS_RB_PROTOTYPE_PREV

◆ RTEMS_RB_PROTOTYPE_REINSERT

◆ RTEMS_RB_PROTOTYPE_REMOVE

◆ RTEMS_RB_PROTOTYPE_REMOVE_COLOR

◆ RTEMS_RB_PROTOTYPE_STATIC

◆ RTEMS_RB_RED_ROTATE_LEFT

◆ RTEMS_RB_RED_ROTATE_RIGHT

◆ RTEMS_RB_REINSERT

◆ RTEMS_RB_REMOVE

◆ RTEMS_RB_RIGHT

◆ RTEMS_RB_ROOT

◆ RTEMS_RB_ROTATE_LEFT

◆ RTEMS_RB_ROTATE_RIGHT

◆ RTEMS_RB_SET

◆ RTEMS_RB_SET_BLACKRED

◆ RTEMS_RB_SET_PARENT

◆ RTEMS_RB_SWAP_CHILD

◆ RTEMS_SPLAY_ASSEMBLE

◆ RTEMS_SPLAY_EMPTY

◆ RTEMS_SPLAY_ENTRY

◆ RTEMS_SPLAY_FIND

◆ RTEMS_SPLAY_FOREACH

◆ RTEMS_SPLAY_HEAD

◆ RTEMS_SPLAY_INIT

◆ RTEMS_SPLAY_INITIALIZER

◆ RTEMS_SPLAY_INSERT

◆ RTEMS_SPLAY_LEFT

◆ RTEMS_SPLAY_LINKLEFT

◆ RTEMS_SPLAY_LINKRIGHT

◆ RTEMS_SPLAY_MAX

◆ RTEMS_SPLAY_MIN

◆ RTEMS_SPLAY_NEXT

◆ RTEMS_SPLAY_REMOVE

◆ RTEMS_SPLAY_RIGHT

◆ RTEMS_SPLAY_ROOT