tree.h File Reference

Go to the source code of this file.

Macros
#define	UV__UNUSED
#define	RB_HEAD(name, type)
#define	RB_INITIALIZER(root)
#define	RB_INIT(root)
#define	RB_BLACK   0
#define	RB_RED   1
#define	RB_ENTRY(type)
#define	RB_LEFT(elm, field)
#define	RB_RIGHT(elm, field)
#define	RB_PARENT(elm, field)
#define	RB_COLOR(elm, field)
#define	RB_ROOT(head)
#define	RB_EMPTY(head)
#define	RB_SET(elm, parent, field)
#define	RB_SET_BLACKRED(black, red, field)
#define	RB_AUGMENT(x)
#define	RB_ROTATE_LEFT(head, elm, tmp, field)
#define	RB_ROTATE_RIGHT(head, elm, tmp, field)
#define	RB_PROTOTYPE(name, type, field, cmp)
#define	RB_PROTOTYPE_STATIC(name, type, field, cmp)
#define	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)
#define	RB_GENERATE(name, type, field, cmp)
#define	RB_GENERATE_STATIC(name, type, field, cmp)
#define	RB_GENERATE_INTERNAL(name, type, field, cmp, attr)
#define	RB_NEGINF   -1
#define	RB_INF   1
#define	RB_INSERT(name, x, y)
#define	RB_REMOVE(name, x, y)
#define	RB_FIND(name, x, y)
#define	RB_NFIND(name, x, y)
#define	RB_NEXT(name, x)
#define	RB_PREV(name, x)
#define	RB_MIN(name, x)
#define	RB_MAX(name, x)
#define	RB_FOREACH(x, name, head)
#define	RB_FOREACH_FROM(x, name, y)
#define	RB_FOREACH_SAFE(x, name, head, y)
#define	RB_FOREACH_REVERSE(x, name, head)
#define	RB_FOREACH_REVERSE_FROM(x, name, y)
#define	RB_FOREACH_REVERSE_SAFE(x, name, head, y)

Macro Definition Documentation

RB_AUGMENT

#define RB_AUGMENT

(

x

)

Value:

do {} while (0)

RB_BLACK

#define RB_BLACK   0

RB_COLOR

#define RB_COLOR	(		elm,
			field )

Value:

(elm)->field.rbe_color

RB_EMPTY

#define RB_EMPTY

(

head

)

Value:

(RB_ROOT(head) == NULL)

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_FIND

#define RB_FIND	(		name,
			x,
			y )

Value:

name##_RB_FIND(x, y)

RB_FOREACH

#define RB_FOREACH	(		x,
			name,
			head )

Value:

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

RB_FOREACH_FROM

#define RB_FOREACH_FROM	(		x,
			name,
			y )

Value:

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

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_FROM

#define RB_FOREACH_REVERSE_FROM	(		x,
			name,
			y )

Value:

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

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), (x) != NULL);                \
       (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), (x) != NULL);                \
       (x) = (y))

RB_GENERATE

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

Value:

  RB_GENERATE_INTERNAL(name, type, field, cmp,)

RB_GENERATE_INTERNAL

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

RB_GENERATE_STATIC

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

Value:

  RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static)

RB_HEAD

#define RB_HEAD	(		name,
			type )

Value:

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

RB_INF

#define RB_INF   1

RB_INIT

#define RB_INIT

(

root

)

Value:

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

RB_INITIALIZER

#define RB_INITIALIZER

(

root

)

Value:

  { NULL }

RB_INSERT

#define RB_INSERT	(		name,
			x,
			y )

Value:

name##_RB_INSERT(x, y)

RB_LEFT

#define RB_LEFT	(		elm,
			field )

Value:

(elm)->field.rbe_left

RB_MAX

#define RB_MAX	(		name,
			x )

Value:

name##_RB_MINMAX(x, RB_INF)

RB_MIN

#define RB_MIN	(		name,
			x )

Value:

name##_RB_MINMAX(x, RB_NEGINF)

RB_NEGINF

#define RB_NEGINF   -1

RB_NEXT

#define RB_NEXT	(		name,
			x )

Value:

name##_RB_NEXT(x)

RB_NFIND

#define RB_NFIND	(		name,
			x,
			y )

Value:

name##_RB_NFIND(x, y)

RB_PARENT

#define RB_PARENT	(		elm,
			field )

Value:

(elm)->field.rbe_parent

RB_PREV

#define RB_PREV	(		name,
			x )

Value:

name##_RB_PREV(x)

RB_PROTOTYPE

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

Value:

  RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)

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_PROTOTYPE_STATIC

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

Value:

  RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static)

RB_RED

#define RB_RED   1

RB_REMOVE

#define RB_REMOVE	(		name,
			x,
			y )

Value:

name##_RB_REMOVE(x, y)

RB_RIGHT

#define RB_RIGHT	(		elm,
			field )

Value:

(elm)->field.rbe_right

RB_ROOT

#define RB_ROOT

(

head

)

Value:

(head)->rbh_root

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)) != NULL) {                 \
    RB_PARENT(RB_LEFT(tmp, field), field) = (elm);                            \
  }                                                                           \
  RB_AUGMENT(elm);                                                            \
  if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {              \
    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 (/*CONSTCOND*/ 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)) != NULL) {                 \
    RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);                           \
  }                                                                           \
  RB_AUGMENT(elm);                                                            \
  if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {              \
    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 (/*CONSTCOND*/ 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 (/*CONSTCOND*/ 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 (/*CONSTCOND*/ 0)

UV__UNUSED

#define UV__UNUSED