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