view release on metacpan or  search on metacpan

libuv/include/uv/tree.h  view on Meta::CPAN

      }                                                                       \
      SPLAY_LINKRIGHT(head, __left, field);                                   \
    }                                                                         \
  }                                                                           \
  SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                      \
}                                                                             \
                                                                              \
/* Splay with either the minimum or the maximum element                       \
 * Used to find minimum or maximum element in tree.                           \
 */                                                                           \
void name##_SPLAY_MINMAX(struct name *head, int __comp)                       \
{                                                                             \
  struct type __node, *__left, *__right, *__tmp;                              \
                                                                              \
  SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;            \
  __left = __right = &__node;                                                 \
                                                                              \
  while (1) {                                                                 \
    if (__comp < 0) {                                                         \
      __tmp = SPLAY_LEFT((head)->sph_root, field);                            \
      if (__tmp == NULL)                                                      \
        break;                                                                \
      if (__comp < 0){                                                        \
        SPLAY_ROTATE_RIGHT(head, __tmp, field);                               \
        if (SPLAY_LEFT((head)->sph_root, field) == NULL)                      \
          break;                                                              \
      }                                                                       \
      SPLAY_LINKLEFT(head, __right, field);                                   \
    } else if (__comp > 0) {                                                  \
      __tmp = SPLAY_RIGHT((head)->sph_root, field);                           \
      if (__tmp == NULL)                                                      \
        break;                                                                \
      if (__comp > 0) {                                                       \
        SPLAY_ROTATE_LEFT(head, __tmp, field);                                \
        if (SPLAY_RIGHT((head)->sph_root, field) == NULL)                     \
          break;                                                              \
      }                                                                       \
      SPLAY_LINKRIGHT(head, __left, field);                                   \
    }                                                                         \
  }                                                                           \
  SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                      \
}

#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)        (SPLAY_EMPTY(x) ? NULL                      \
                                  : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
#define SPLAY_MAX(name, x)        (SPLAY_EMPTY(x) ? NULL                      \
                                  : name##_SPLAY_MIN_MAX(x, SPLAY_INF))

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

/* Macros that define a red-black tree */
#define RB_HEAD(name, type)                                                   \
struct name {                                                                 \
  struct type *rbh_root; /* root of the tree */                               \
}

#define RB_INITIALIZER(root)                                                  \
  { NULL }

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

#define RB_BLACK  0
#define RB_RED    1
#define RB_ENTRY(type)                                                        \
struct {                                                                      \
  struct type *rbe_left;        /* left element */                            \
  struct type *rbe_right;       /* right element */                           \
  struct type *rbe_parent;      /* parent element */                          \
  int rbe_color;                /* node color */                              \
}

#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) do {                                       \
  RB_PARENT(elm, field) = parent;                                             \
  RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;                          \
  RB_COLOR(elm, field) = RB_RED;                                              \
} while (/*CONSTCOND*/ 0)

#define RB_SET_BLACKRED(black, red, field) do {                               \
  RB_COLOR(black, field) = RB_BLACK;                                          \
  RB_COLOR(red, field) = RB_RED;                                              \
} while (/*CONSTCOND*/ 0)

#ifndef RB_AUGMENT
#define RB_AUGMENT(x)  do {} while (0)
#endif

#define RB_ROTATE_LEFT(head, elm, tmp, field) 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);                                                            \