src/core/ngx_rbtree.h - nginx-1.7.10

Data types defined

Functions defined

Macros defined

Source code


  1. /*
  2. * Copyright (C) Igor Sysoev
  3. * Copyright (C) Nginx, Inc.
  4. */


  5. #ifndef _NGX_RBTREE_H_INCLUDED_
  6. #define _NGX_RBTREE_H_INCLUDED_


  7. #include <ngx_config.h>
  8. #include <ngx_core.h>


  9. typedef ngx_uint_t  ngx_rbtree_key_t;
  10. typedef ngx_int_t   ngx_rbtree_key_int_t;


  11. typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;

  12. struct ngx_rbtree_node_s {
  13.     ngx_rbtree_key_t       key;
  14.     ngx_rbtree_node_t     *left;
  15.     ngx_rbtree_node_t     *right;
  16.     ngx_rbtree_node_t     *parent;
  17.     u_char                 color;
  18.     u_char                 data;
  19. };


  20. typedef struct ngx_rbtree_s  ngx_rbtree_t;

  21. typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
  22.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

  23. struct ngx_rbtree_s {
  24.     ngx_rbtree_node_t     *root;
  25.     ngx_rbtree_node_t     *sentinel;
  26.     ngx_rbtree_insert_pt   insert;
  27. };


  28. #define ngx_rbtree_init(tree, s, i)                                           \
  29.     ngx_rbtree_sentinel_init(s);                                              \
  30.     (tree)->root = s;                                                         \
  31.     (tree)->sentinel = s;                                                     \
  32.     (tree)->insert = i


  33. void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
  34. void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
  35. void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
  36.     ngx_rbtree_node_t *sentinel);
  37. void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
  38.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);


  39. #define ngx_rbt_red(node)               ((node)->color = 1)
  40. #define ngx_rbt_black(node)             ((node)->color = 0)
  41. #define ngx_rbt_is_red(node)            ((node)->color)
  42. #define ngx_rbt_is_black(node)          (!ngx_rbt_is_red(node))
  43. #define ngx_rbt_copy_color(n1, n2)      (n1->color = n2->color)


  44. /* a sentinel must be black */

  45. #define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)


  46. static ngx_inline ngx_rbtree_node_t *
  47. ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
  48. {
  49.     while (node->left != sentinel) {
  50.         node = node->left;
  51.     }

  52.     return node;
  53. }


  54. #endif /* _NGX_RBTREE_H_INCLUDED_ */