tree.h File Reference

Go to the source code of this file.

Macros
#define	_SYS_TREE_H_
#define	SPLAY_HEAD(name, type)
#define	SPLAY_INITIALIZER(root)   { NULL }
#define	SPLAY_INIT(root)
#define	SPLAY_ENTRY(type)
#define	SPLAY_LEFT(elm, field)   (elm)->field.spe_left
#define	SPLAY_RIGHT(elm, field)   (elm)->field.spe_right
#define	SPLAY_ROOT(head)   (head)->sph_root
#define	SPLAY_EMPTY(head)   (SPLAY_ROOT(head) == NULL)
#define	SPLAY_ROTATE_RIGHT(head, tmp, field)
#define	SPLAY_ROTATE_LEFT(head, tmp, field)
#define	SPLAY_LINKLEFT(head, tmp, field)
#define	SPLAY_LINKRIGHT(head, tmp, field)
#define	SPLAY_ASSEMBLE(head, node, left, right, field)
#define	SPLAY_PROTOTYPE(name, type, field, cmp)
#define	SPLAY_GENERATE(name, type, field, cmp)
#define	SPLAY_NEGINF   -1
#define	SPLAY_INF   1
#define	SPLAY_INSERT(name, x, y)   name##_SPLAY_INSERT(x, y)
#define	SPLAY_REMOVE(name, x, y)   name##_SPLAY_REMOVE(x, y)
#define	SPLAY_FIND(name, x, y)   name##_SPLAY_FIND(x, y)
#define	SPLAY_NEXT(name, x, y)   name##_SPLAY_NEXT(x, y)
#define	SPLAY_MIN(name, x)
#define	SPLAY_MAX(name, x)
#define	SPLAY_FOREACH(x, name, head)
#define	RB_HEAD(name, type)
#define	RB_INITIALIZER(root)   { NULL }
#define	RB_INIT(root)
#define	RB_BLACK   0
#define	RB_RED   1
#define	RB_ENTRY(type)
#define	RB_LEFT(elm, field)   (elm)->field.rbe_left
#define	RB_RIGHT(elm, field)   (elm)->field.rbe_right
#define	RB_PARENT(elm, field)   (elm)->field.rbe_parent
#define	RB_COLOR(elm, field)   (elm)->field.rbe_color
#define	RB_ROOT(head)   (head)->rbh_root
#define	RB_EMPTY(head)   (RB_ROOT(head) == NULL)
#define	RB_SET(elm, parent, field)
#define	RB_SET_BLACKRED(black, red, field)
#define	RB_AUGMENT(x)   do {} while (0)
#define	RB_ROTATE_LEFT(head, elm, tmp, field)
#define	RB_ROTATE_RIGHT(head, elm, tmp, field)
#define	RB_PROTOTYPE(name, type, field, cmp)   RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
#define	RB_PROTOTYPE_STATIC(name, type, field, cmp)   RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
#define	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)
#define	RB_GENERATE(name, type, field, cmp)   RB_GENERATE_INTERNAL(name, type, field, cmp,)
#define	RB_GENERATE_STATIC(name, type, field, cmp)   RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
#define	RB_GENERATE_INTERNAL(name, type, field, cmp, attr)
#define	RB_NEGINF   -1
#define	RB_INF   1
#define	RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
#define	RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
#define	RB_FIND(name, x, y)   name##_RB_FIND(x, y)
#define	RB_NFIND(name, x, y)   name##_RB_NFIND(x, y)
#define	RB_NEXT(name, x, y)   name##_RB_NEXT(y)
#define	RB_PREV(name, x, y)   name##_RB_PREV(y)
#define	RB_MIN(name, x)   name##_RB_MINMAX(x, RB_NEGINF)
#define	RB_MAX(name, x)   name##_RB_MINMAX(x, RB_INF)
#define	RB_FOREACH(x, name, head)
#define	RB_FOREACH_SAFE(x, name, head, y)
#define	RB_FOREACH_REVERSE(x, name, head)
#define	RB_FOREACH_REVERSE_SAFE(x, name, head, y)

Detailed Description

Author

Niels Provos

Date

2002

Copyright

2-clause BSD License

This file defines data structures for different types of trees: splay trees and red-black trees.

A splay tree is a self-organizing data structure. Every operation on the tree causes a splay to happen. The splay moves the requested node to the root of the tree and partly rebalances it.

This has the benefit that request locality causes faster lookups as the requested nodes move to the top of the tree. On the other hand, every lookup causes memory writes.

The Balance Theorem bounds the total access time for m operations and n inserts on an initially empty tree as O((m + n)lg n). The amortized cost for a sequence of m accesses to a splay tree is O(lg n);

A red-black tree is a binary search tree with the node color as an extra attribute. It fulfills a set of conditions:

• every search path from the root to a leaf consists of the same number of black nodes,
• each red node (except for the root) has a black parent,
• each leaf node is black.

Every operation on a red-black tree is bounded as O(lg n). The maximum height of a red-black tree is 2lg (n+1).

Macro Definition Documentation

RB_ENTRY

#define 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 */        \
}

RB_FOREACH

#define RB_FOREACH	(		x,
			name,
			head
	)

Value:

for ((x) = RB_MIN(name, head);                  \
         (x) != NULL;                       \
         (x) = name##_RB_NEXT(x))

RB_FOREACH_REVERSE

#define RB_FOREACH_REVERSE	(		x,
			name,
			head
	)

Value:

for ((x) = RB_MAX(name, head);                  \
         (x) != NULL;                       \
         (x) = name##_RB_PREV(x))

RB_FOREACH_REVERSE_SAFE

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

Value:

for ((x) = RB_MAX(name, head);                  \
        ((x) != NULL) && ((y) = name##_RB_PREV(x), 1);      \
         (x) = (y))

RB_FOREACH_SAFE

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

Value:

for ((x) = RB_MIN(name, head);                  \
        ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1);      \
         (x) = (y))

RB_HEAD

#define RB_HEAD	(		name,
			type
	)

Value:

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

RB_INIT

#define RB_INIT

(

root

)

Value:

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

RB_PROTOTYPE_INTERNAL

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

Value:

attr void name##_RB_INSERT_COLOR(struct name *, struct type *);     \
attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
attr struct type *name##_RB_REMOVE(struct name *, struct type *);   \
attr struct type *name##_RB_INSERT(struct name *, struct type *);   \
attr struct type *name##_RB_FIND(struct name *, struct type *);     \
attr struct type *name##_RB_NFIND(struct name *, struct type *);    \
attr struct type *name##_RB_NEXT(struct type *);            \
attr struct type *name##_RB_PREV(struct type *);            \
attr struct type *name##_RB_MINMAX(struct name *, int);         \
                                    \

RB_ROTATE_LEFT

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

Value:

do {            \
    (tmp) = RB_RIGHT(elm, field);                   \
    if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {     \
        RB_PARENT(RB_LEFT(tmp, field), field) = (elm);      \
    }                               \
    RB_AUGMENT(elm);                        \
    if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {      \
        if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
            RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
        else                            \
            RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
    } else                              \
        (head)->rbh_root = (tmp);               \
    RB_LEFT(tmp, field) = (elm);                    \
    RB_PARENT(elm, field) = (tmp);                  \
    RB_AUGMENT(tmp);                        \
    if ((RB_PARENT(tmp, field)))                    \
        RB_AUGMENT(RB_PARENT(tmp, field));          \
} while (0)

RB_ROTATE_RIGHT

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

Value:

do {            \
    (tmp) = RB_LEFT(elm, field);                    \
    if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {     \
        RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);     \
    }                               \
    RB_AUGMENT(elm);                        \
    if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {      \
        if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
            RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
        else                            \
            RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
    } else                              \
        (head)->rbh_root = (tmp);               \
    RB_RIGHT(tmp, field) = (elm);                   \
    RB_PARENT(elm, field) = (tmp);                  \
    RB_AUGMENT(tmp);                        \
    if ((RB_PARENT(tmp, field)))                    \
        RB_AUGMENT(RB_PARENT(tmp, field));          \
} while (0)

RB_SET

#define RB_SET	(		elm,
			parent,
			field
	)

Value:

do {                    \
    RB_PARENT(elm, field) = parent;                 \
    RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;      \
    RB_COLOR(elm, field) = RB_RED;                  \
} while (0)

RB_SET_BLACKRED

#define RB_SET_BLACKRED	(		black,
			red,
			field
	)

Value:

do {                \
    RB_COLOR(black, field) = RB_BLACK;              \
    RB_COLOR(red, field) = RB_RED;                  \
} while (0)

SPLAY_ASSEMBLE

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

Value:

do {        \
    SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
    SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
    SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
    SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
} while (0)

SPLAY_ENTRY

#define SPLAY_ENTRY

(

type

)

Value:

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

SPLAY_FOREACH

#define SPLAY_FOREACH	(		x,
			name,
			head
	)

Value:

for ((x) = SPLAY_MIN(name, head);               \
         (x) != NULL;                       \
         (x) = SPLAY_NEXT(name, head, x))

SPLAY_HEAD

#define SPLAY_HEAD	(		name,
			type
	)

Value:

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

SPLAY_INIT

#define SPLAY_INIT

(

root

)

Value:

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

SPLAY_LINKLEFT

#define SPLAY_LINKLEFT	(		head,
			tmp,
			field
	)

Value:

do {                \
    SPLAY_LEFT(tmp, field) = (head)->sph_root;          \
    tmp = (head)->sph_root;                     \
    (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);     \
} while (0)

SPLAY_LINKRIGHT

#define SPLAY_LINKRIGHT	(		head,
			tmp,
			field
	)

Value:

do {                \
    SPLAY_RIGHT(tmp, field) = (head)->sph_root;         \
    tmp = (head)->sph_root;                     \
    (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);    \
} while (0)

SPLAY_MAX

#define SPLAY_MAX	(		name,
			x
	)

Value:

(SPLAY_EMPTY(x) ? NULL  \
                    : name##_SPLAY_MIN_MAX(x, SPLAY_INF))

SPLAY_MIN

#define SPLAY_MIN	(		name,
			x
	)

Value:

(SPLAY_EMPTY(x) ? NULL  \
                    : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))

SPLAY_ROTATE_LEFT

#define SPLAY_ROTATE_LEFT	(		head,
			tmp,
			field
	)

Value:

do {            \
    SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
    SPLAY_LEFT(tmp, field) = (head)->sph_root;          \
    (head)->sph_root = tmp;                     \
} while (0)

SPLAY_ROTATE_RIGHT

#define SPLAY_ROTATE_RIGHT	(		head,
			tmp,
			field
	)

Value:

do {            \
    SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
    SPLAY_RIGHT(tmp, field) = (head)->sph_root;         \
    (head)->sph_root = tmp;                     \
} while (0)