10Sigor@sysoev.ru 20Sigor@sysoev.ru /* 30Sigor@sysoev.ru * Copyright (C) Igor Sysoev 40Sigor@sysoev.ru * Copyright (C) NGINX, Inc. 50Sigor@sysoev.ru */ 60Sigor@sysoev.ru 70Sigor@sysoev.ru #ifndef _NXT_RBTREE_H_INCLUDED_ 80Sigor@sysoev.ru #define _NXT_RBTREE_H_INCLUDED_ 90Sigor@sysoev.ru 100Sigor@sysoev.ru 110Sigor@sysoev.ru typedef struct nxt_rbtree_node_s nxt_rbtree_node_t; 120Sigor@sysoev.ru 130Sigor@sysoev.ru struct nxt_rbtree_node_s { 14*5Sigor@sysoev.ru nxt_rbtree_node_t *left; 15*5Sigor@sysoev.ru nxt_rbtree_node_t *right; 16*5Sigor@sysoev.ru nxt_rbtree_node_t *parent; 170Sigor@sysoev.ru 18*5Sigor@sysoev.ru uint8_t color; 190Sigor@sysoev.ru }; 200Sigor@sysoev.ru 210Sigor@sysoev.ru 220Sigor@sysoev.ru typedef struct { 23*5Sigor@sysoev.ru nxt_rbtree_node_t *left; 24*5Sigor@sysoev.ru nxt_rbtree_node_t *right; 25*5Sigor@sysoev.ru nxt_rbtree_node_t *parent; 260Sigor@sysoev.ru } nxt_rbtree_part_t; 270Sigor@sysoev.ru 280Sigor@sysoev.ru 290Sigor@sysoev.ru #define NXT_RBTREE_NODE(node) \ 30*5Sigor@sysoev.ru nxt_rbtree_part_t node; \ 31*5Sigor@sysoev.ru uint8_t node##_color 320Sigor@sysoev.ru 330Sigor@sysoev.ru 340Sigor@sysoev.ru #define NXT_RBTREE_NODE_INIT { NULL, NULL, NULL }, 0 350Sigor@sysoev.ru 360Sigor@sysoev.ru 370Sigor@sysoev.ru typedef struct { 38*5Sigor@sysoev.ru nxt_rbtree_node_t sentinel; 390Sigor@sysoev.ru } nxt_rbtree_t; 400Sigor@sysoev.ru 410Sigor@sysoev.ru 42*5Sigor@sysoev.ru /* 43*5Sigor@sysoev.ru * A comparison function should return intptr_t result because 44*5Sigor@sysoev.ru * this eliminates overhead required to implement correct addresses 45*5Sigor@sysoev.ru * comparison without result truncation. 46*5Sigor@sysoev.ru */ 47*5Sigor@sysoev.ru typedef intptr_t (*nxt_rbtree_compare_t)(nxt_rbtree_node_t *node1, 480Sigor@sysoev.ru nxt_rbtree_node_t *node2); 490Sigor@sysoev.ru 500Sigor@sysoev.ru 51*5Sigor@sysoev.ru #define nxt_rbtree_root(tree) \ 520Sigor@sysoev.ru ((tree)->sentinel.left) 530Sigor@sysoev.ru 540Sigor@sysoev.ru 550Sigor@sysoev.ru #define nxt_rbtree_sentinel(tree) \ 560Sigor@sysoev.ru (&(tree)->sentinel) 570Sigor@sysoev.ru 580Sigor@sysoev.ru 590Sigor@sysoev.ru #define nxt_rbtree_is_empty(tree) \ 600Sigor@sysoev.ru (nxt_rbtree_root(tree) == nxt_rbtree_sentinel(tree)) 610Sigor@sysoev.ru 620Sigor@sysoev.ru 630Sigor@sysoev.ru #define nxt_rbtree_min(tree) \ 640Sigor@sysoev.ru nxt_rbtree_branch_min(tree, &(tree)->sentinel) 650Sigor@sysoev.ru 660Sigor@sysoev.ru 670Sigor@sysoev.ru nxt_inline nxt_rbtree_node_t * 680Sigor@sysoev.ru nxt_rbtree_branch_min(nxt_rbtree_t *tree, nxt_rbtree_node_t *node) 690Sigor@sysoev.ru { 700Sigor@sysoev.ru while (node->left != nxt_rbtree_sentinel(tree)) { 710Sigor@sysoev.ru node = node->left; 720Sigor@sysoev.ru } 730Sigor@sysoev.ru 740Sigor@sysoev.ru return node; 750Sigor@sysoev.ru } 760Sigor@sysoev.ru 770Sigor@sysoev.ru 780Sigor@sysoev.ru #define nxt_rbtree_is_there_successor(tree, node) \ 790Sigor@sysoev.ru ((node) != nxt_rbtree_sentinel(tree)) 800Sigor@sysoev.ru 810Sigor@sysoev.ru 820Sigor@sysoev.ru nxt_inline nxt_rbtree_node_t * 830Sigor@sysoev.ru nxt_rbtree_node_successor(nxt_rbtree_t *tree, nxt_rbtree_node_t *node) 840Sigor@sysoev.ru { 850Sigor@sysoev.ru nxt_rbtree_node_t *parent; 860Sigor@sysoev.ru 870Sigor@sysoev.ru if (node->right != nxt_rbtree_sentinel(tree)) { 880Sigor@sysoev.ru return nxt_rbtree_branch_min(tree, node->right); 890Sigor@sysoev.ru } 900Sigor@sysoev.ru 910Sigor@sysoev.ru for ( ;; ) { 920Sigor@sysoev.ru parent = node->parent; 930Sigor@sysoev.ru 940Sigor@sysoev.ru /* 950Sigor@sysoev.ru * Explicit test for a root node is not required here, because 960Sigor@sysoev.ru * the root node is always the left child of the sentinel. 970Sigor@sysoev.ru */ 980Sigor@sysoev.ru if (node == parent->left) { 990Sigor@sysoev.ru return parent; 1000Sigor@sysoev.ru } 1010Sigor@sysoev.ru 1020Sigor@sysoev.ru node = parent; 1030Sigor@sysoev.ru } 1040Sigor@sysoev.ru } 1050Sigor@sysoev.ru 1060Sigor@sysoev.ru 1070Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_init(nxt_rbtree_t *tree, 108*5Sigor@sysoev.ru nxt_rbtree_compare_t compare); 1090Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *node); 1100Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find(nxt_rbtree_t *tree, 1110Sigor@sysoev.ru nxt_rbtree_part_t *node); 1120Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, 1130Sigor@sysoev.ru nxt_rbtree_part_t *node); 114*5Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t 115*5Sigor@sysoev.ru *nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, 1160Sigor@sysoev.ru nxt_rbtree_part_t *node); 1170Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *node); 1180Sigor@sysoev.ru 1190Sigor@sysoev.ru 1200Sigor@sysoev.ru #endif /* _NXT_RBTREE_H_INCLUDED_ */ 121