Return to ngx_rbtree.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / nginx / src / core

Annotation of embedaddon/nginx/src/core/ngx_rbtree.h, revision 1.1.1.1

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