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