tree.h File Reference

Go to the source code of this file.

Macros
#define	UV__UNUSED
#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, UV__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, UV__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_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

)

do {} while (0)

RB_BLACK

#define RB_BLACK   0

RB_COLOR

#define RB_COLOR	(		elm,
			field
	)		(elm)->field.rbe_color

RB_EMPTY

#define RB_EMPTY

(

head

)

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

)

{ NULL }

RB_INSERT

#define RB_INSERT	(		name,
			x,
			y
	)		name##_RB_INSERT(x, y)

RB_LEFT

#define RB_LEFT	(		elm,
			field
	)		(elm)->field.rbe_left

RB_MAX

#define RB_MAX	(		name,
			x
	)		name##_RB_MINMAX(x, RB_INF)

RB_MIN

#define RB_MIN	(		name,
			x
	)		name##_RB_MINMAX(x, RB_NEGINF)

RB_NEGINF

#define RB_NEGINF   -1

RB_NEXT

#define RB_NEXT	(		name,
			x,
			y
	)		name##_RB_NEXT(y)

RB_NFIND

#define RB_NFIND	(		name,
			x,
			y
	)		name##_RB_NFIND(x, y)

RB_PARENT

#define RB_PARENT	(		elm,
			field
	)		(elm)->field.rbe_parent

RB_PREV

#define RB_PREV	(		name,
			x,
			y
	)		name##_RB_PREV(y)

RB_PROTOTYPE

#define RB_PROTOTYPE	(		name,
			type,
			field,
			cmp
	)		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
	)		RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static)

RB_RED

#define RB_RED   1

RB_REMOVE

#define RB_REMOVE	(		name,
			x,
			y
	)		name##_RB_REMOVE(x, y)

RB_RIGHT

#define RB_RIGHT	(		elm,
			field
	)		(elm)->field.rbe_right

RB_ROOT

#define RB_ROOT

(

head

)

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

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 (/*CONSTCOND*/ 0)

SPLAY_EMPTY

#define SPLAY_EMPTY

(

head

)

(SPLAY_ROOT(head) == NULL)

SPLAY_ENTRY

#define SPLAY_ENTRY

(

type

)

Value:

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

SPLAY_FIND

#define SPLAY_FIND	(		name,
			x,
			y
	)		name##_SPLAY_FIND(x, y)

SPLAY_FOREACH

#define SPLAY_FOREACH	(		x,
			name,
			head
	)

Value:

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

SPLAY_GENERATE

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

SPLAY_HEAD

#define SPLAY_HEAD	(		name,
			type
	)

Value:

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

SPLAY_INF

#define SPLAY_INF   1

SPLAY_INIT

#define SPLAY_INIT

(

root

)

Value:

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

SPLAY_INITIALIZER

#define SPLAY_INITIALIZER

(

root

)

{ NULL }

SPLAY_INSERT

#define SPLAY_INSERT	(		name,
			x,
			y
	)		name##_SPLAY_INSERT(x, y)

SPLAY_LEFT

#define SPLAY_LEFT	(		elm,
			field
	)		(elm)->field.spe_left

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 (/*CONSTCOND*/ 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 (/*CONSTCOND*/ 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_NEGINF

#define SPLAY_NEGINF   -1

SPLAY_NEXT

#define SPLAY_NEXT	(		name,
			x,
			y
	)		name##_SPLAY_NEXT(x, y)

SPLAY_PROTOTYPE

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

SPLAY_REMOVE

#define SPLAY_REMOVE	(		name,
			x,
			y
	)		name##_SPLAY_REMOVE(x, y)

SPLAY_RIGHT

#define SPLAY_RIGHT	(		elm,
			field
	)		(elm)->field.spe_right

SPLAY_ROOT

#define SPLAY_ROOT

(

head

)

(head)->sph_root

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 (/*CONSTCOND*/ 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 (/*CONSTCOND*/ 0)

UV__UNUSED

#define UV__UNUSED