nginx/src/core/ngx_rbtree.h

   1
   2 /*
   3  * Copyright (C) Igor Sysoev
   4  */
   5
   6
   7 #ifndef _NGX_RBTREE_H_INCLUDED_
   8 #define _NGX_RBTREE_H_INCLUDED_
   9
  10
  11 #include <ngx_config.h>
  12 #include <ngx_core.h>
  13
  14
  15 typedef ngx_uint_t  ngx_rbtree_key_t;
  16 typedef ngx_int_t   ngx_rbtree_key_int_t;
  17
  18
  19 typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;
  20
  21 struct ngx_rbtree_node_s {
  22     ngx_rbtree_key_t       key;
  23     ngx_rbtree_node_t     *left;
  24     ngx_rbtree_node_t     *right;
  25     ngx_rbtree_node_t     *parent;
  26     u_char                 color;
  27     u_char                 data;
  28 };
  29
  30
  31 typedef struct ngx_rbtree_s  ngx_rbtree_t;
  32
  33 typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
  34     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
  35
  36 struct ngx_rbtree_s {
  37     ngx_rbtree_node_t     *root;
  38     ngx_rbtree_node_t     *sentinel;
  39     ngx_rbtree_insert_pt   insert;
  40 };
  41
  42
  43 #define ngx_rbtree_init(tree, s, i)                                           \
  44     ngx_rbtree_sentinel_init(s);                                              \
  45     (tree)->root = s;                                                         \
  46     (tree)->sentinel = s;                                                     \
  47     (tree)->insert = i
  48
  49
  50 void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
  51     ngx_rbtree_node_t *node);
  52 void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,
  53     ngx_rbtree_node_t *node);
  54 void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
  55     ngx_rbtree_node_t *sentinel);
  56 void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
  57     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
  58
  59
  60 #define ngx_rbt_red(node)               ((node)->color = 1)
  61 #define ngx_rbt_black(node)             ((node)->color = 0)
  62 #define ngx_rbt_is_red(node)            ((node)->color)
  63 #define ngx_rbt_is_black(node)          (!ngx_rbt_is_red(node))
  64 #define ngx_rbt_copy_color(n1, n2)      (n1->color = n2->color)
  65
  66
  67 /* a sentinel must be black */
  68
  69 #define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)
  70
  71
  72 static ngx_inline ngx_rbtree_node_t *
  73 ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
  74 {
  75     while (node->left != sentinel) {
  76         node = node->left;
  77     }
  78
  79     return node;
  80 }
  81
  82
  83 #endif /* _NGX_RBTREE_H_INCLUDED_ */