1*0Sigor@sysoev.ru 2*0Sigor@sysoev.ru /* 3*0Sigor@sysoev.ru * Copyright (C) Igor Sysoev 4*0Sigor@sysoev.ru * Copyright (C) NGINX, Inc. 5*0Sigor@sysoev.ru */ 6*0Sigor@sysoev.ru 7*0Sigor@sysoev.ru #ifndef _NXT_RBTREE_H_INCLUDED_ 8*0Sigor@sysoev.ru #define _NXT_RBTREE_H_INCLUDED_ 9*0Sigor@sysoev.ru 10*0Sigor@sysoev.ru 11*0Sigor@sysoev.ru typedef struct nxt_rbtree_node_s nxt_rbtree_node_t; 12*0Sigor@sysoev.ru 13*0Sigor@sysoev.ru struct nxt_rbtree_node_s { 14*0Sigor@sysoev.ru nxt_rbtree_node_t *left; 15*0Sigor@sysoev.ru nxt_rbtree_node_t *right; 16*0Sigor@sysoev.ru nxt_rbtree_node_t *parent; 17*0Sigor@sysoev.ru 18*0Sigor@sysoev.ru uint8_t color; 19*0Sigor@sysoev.ru uint8_t spare; 20*0Sigor@sysoev.ru }; 21*0Sigor@sysoev.ru 22*0Sigor@sysoev.ru 23*0Sigor@sysoev.ru typedef struct { 24*0Sigor@sysoev.ru nxt_rbtree_node_t *left; 25*0Sigor@sysoev.ru nxt_rbtree_node_t *right; 26*0Sigor@sysoev.ru nxt_rbtree_node_t *parent; 27*0Sigor@sysoev.ru } nxt_rbtree_part_t; 28*0Sigor@sysoev.ru 29*0Sigor@sysoev.ru 30*0Sigor@sysoev.ru #define NXT_RBTREE_NODE(node) \ 31*0Sigor@sysoev.ru nxt_rbtree_part_t node; \ 32*0Sigor@sysoev.ru uint8_t color 33*0Sigor@sysoev.ru 34*0Sigor@sysoev.ru 35*0Sigor@sysoev.ru #define NXT_RBTREE_NODE_INIT { NULL, NULL, NULL }, 0 36*0Sigor@sysoev.ru 37*0Sigor@sysoev.ru 38*0Sigor@sysoev.ru typedef struct { 39*0Sigor@sysoev.ru nxt_rbtree_node_t sentinel; 40*0Sigor@sysoev.ru } nxt_rbtree_t; 41*0Sigor@sysoev.ru 42*0Sigor@sysoev.ru 43*0Sigor@sysoev.ru typedef void (*nxt_rbtree_insert_t)(nxt_rbtree_node_t *root, 44*0Sigor@sysoev.ru nxt_rbtree_node_t *node, nxt_rbtree_node_t *sentinel); 45*0Sigor@sysoev.ru 46*0Sigor@sysoev.ru typedef nxt_int_t (*nxt_rbtree_compare_t)(nxt_rbtree_node_t *node1, 47*0Sigor@sysoev.ru nxt_rbtree_node_t *node2); 48*0Sigor@sysoev.ru 49*0Sigor@sysoev.ru 50*0Sigor@sysoev.ru #define \ 51*0Sigor@sysoev.ru nxt_rbtree_root(tree) \ 52*0Sigor@sysoev.ru ((tree)->sentinel.left) 53*0Sigor@sysoev.ru 54*0Sigor@sysoev.ru 55*0Sigor@sysoev.ru #define nxt_rbtree_sentinel(tree) \ 56*0Sigor@sysoev.ru (&(tree)->sentinel) 57*0Sigor@sysoev.ru 58*0Sigor@sysoev.ru 59*0Sigor@sysoev.ru #define nxt_rbtree_is_empty(tree) \ 60*0Sigor@sysoev.ru (nxt_rbtree_root(tree) == nxt_rbtree_sentinel(tree)) 61*0Sigor@sysoev.ru 62*0Sigor@sysoev.ru 63*0Sigor@sysoev.ru #define nxt_rbtree_min(tree) \ 64*0Sigor@sysoev.ru nxt_rbtree_branch_min(tree, &(tree)->sentinel) 65*0Sigor@sysoev.ru 66*0Sigor@sysoev.ru 67*0Sigor@sysoev.ru nxt_inline nxt_rbtree_node_t * 68*0Sigor@sysoev.ru nxt_rbtree_branch_min(nxt_rbtree_t *tree, nxt_rbtree_node_t *node) 69*0Sigor@sysoev.ru { 70*0Sigor@sysoev.ru while (node->left != nxt_rbtree_sentinel(tree)) { 71*0Sigor@sysoev.ru node = node->left; 72*0Sigor@sysoev.ru } 73*0Sigor@sysoev.ru 74*0Sigor@sysoev.ru return node; 75*0Sigor@sysoev.ru } 76*0Sigor@sysoev.ru 77*0Sigor@sysoev.ru 78*0Sigor@sysoev.ru #define nxt_rbtree_is_there_successor(tree, node) \ 79*0Sigor@sysoev.ru ((node) != nxt_rbtree_sentinel(tree)) 80*0Sigor@sysoev.ru 81*0Sigor@sysoev.ru 82*0Sigor@sysoev.ru nxt_inline nxt_rbtree_node_t * 83*0Sigor@sysoev.ru nxt_rbtree_node_successor(nxt_rbtree_t *tree, nxt_rbtree_node_t *node) 84*0Sigor@sysoev.ru { 85*0Sigor@sysoev.ru nxt_rbtree_node_t *parent; 86*0Sigor@sysoev.ru 87*0Sigor@sysoev.ru if (node->right != nxt_rbtree_sentinel(tree)) { 88*0Sigor@sysoev.ru return nxt_rbtree_branch_min(tree, node->right); 89*0Sigor@sysoev.ru } 90*0Sigor@sysoev.ru 91*0Sigor@sysoev.ru for ( ;; ) { 92*0Sigor@sysoev.ru parent = node->parent; 93*0Sigor@sysoev.ru 94*0Sigor@sysoev.ru /* 95*0Sigor@sysoev.ru * Explicit test for a root node is not required here, because 96*0Sigor@sysoev.ru * the root node is always the left child of the sentinel. 97*0Sigor@sysoev.ru */ 98*0Sigor@sysoev.ru if (node == parent->left) { 99*0Sigor@sysoev.ru return parent; 100*0Sigor@sysoev.ru } 101*0Sigor@sysoev.ru 102*0Sigor@sysoev.ru node = parent; 103*0Sigor@sysoev.ru } 104*0Sigor@sysoev.ru } 105*0Sigor@sysoev.ru 106*0Sigor@sysoev.ru 107*0Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_init(nxt_rbtree_t *tree, 108*0Sigor@sysoev.ru nxt_rbtree_compare_t compare, nxt_rbtree_insert_t insert); 109*0Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *node); 110*0Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find(nxt_rbtree_t *tree, 111*0Sigor@sysoev.ru nxt_rbtree_part_t *node); 112*0Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, 113*0Sigor@sysoev.ru nxt_rbtree_part_t *node); 114*0Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t * 115*0Sigor@sysoev.ru nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, 116*0Sigor@sysoev.ru nxt_rbtree_part_t *node); 117*0Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *node); 118*0Sigor@sysoev.ru 119*0Sigor@sysoev.ru 120*0Sigor@sysoev.ru #endif /* _NXT_RBTREE_H_INCLUDED_ */ 121