Back to home page

Nginx displayed by LXR

Source navigation ]
Diff markup ]
Identifier search ]
general search ]
 
 
Version: nginx-1.13.12 ]​[ nginx-1.12.2 ]​

0001 
0002 /*
0003  * Copyright (C) Igor Sysoev
0004  * Copyright (C) Nginx, Inc.
0005  */
0006 
0007 
0008 #include <ngx_config.h>
0009 #include <ngx_core.h>
0010 
0011 
0012 /*
0013  * The red-black tree code is based on the algorithm described in
0014  * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
0015  */
0016 
0017 
0018 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
0019     ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
0020 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
0021     ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
0022 
0023 
0024 void
0025 ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
0026 {
0027     ngx_rbtree_node_t  **root, *temp, *sentinel;
0028 
0029     /* a binary tree insert */
0030 
0031     root = &tree->root;
0032     sentinel = tree->sentinel;
0033 
0034     if (*root == sentinel) {
0035         node->parent = NULL;
0036         node->left = sentinel;
0037         node->right = sentinel;
0038         ngx_rbt_black(node);
0039         *root = node;
0040 
0041         return;
0042     }
0043 
0044     tree->insert(*root, node, sentinel);
0045 
0046     /* re-balance tree */
0047 
0048     while (node != *root && ngx_rbt_is_red(node->parent)) {
0049 
0050         if (node->parent == node->parent->parent->left) {
0051             temp = node->parent->parent->right;
0052 
0053             if (ngx_rbt_is_red(temp)) {
0054                 ngx_rbt_black(node->parent);
0055                 ngx_rbt_black(temp);
0056                 ngx_rbt_red(node->parent->parent);
0057                 node = node->parent->parent;
0058 
0059             } else {
0060                 if (node == node->parent->right) {
0061                     node = node->parent;
0062                     ngx_rbtree_left_rotate(root, sentinel, node);
0063                 }
0064 
0065                 ngx_rbt_black(node->parent);
0066                 ngx_rbt_red(node->parent->parent);
0067                 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
0068             }
0069 
0070         } else {
0071             temp = node->parent->parent->left;
0072 
0073             if (ngx_rbt_is_red(temp)) {
0074                 ngx_rbt_black(node->parent);
0075                 ngx_rbt_black(temp);
0076                 ngx_rbt_red(node->parent->parent);
0077                 node = node->parent->parent;
0078 
0079             } else {
0080                 if (node == node->parent->left) {
0081                     node = node->parent;
0082                     ngx_rbtree_right_rotate(root, sentinel, node);
0083                 }
0084 
0085                 ngx_rbt_black(node->parent);
0086                 ngx_rbt_red(node->parent->parent);
0087                 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
0088             }
0089         }
0090     }
0091 
0092     ngx_rbt_black(*root);
0093 }
0094 
0095 
0096 void
0097 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
0098     ngx_rbtree_node_t *sentinel)
0099 {
0100     ngx_rbtree_node_t  **p;
0101 
0102     for ( ;; ) {
0103 
0104         p = (node->key < temp->key) ? &temp->left : &temp->right;
0105 
0106         if (*p == sentinel) {
0107             break;
0108         }
0109 
0110         temp = *p;
0111     }
0112 
0113     *p = node;
0114     node->parent = temp;
0115     node->left = sentinel;
0116     node->right = sentinel;
0117     ngx_rbt_red(node);
0118 }
0119 
0120 
0121 void
0122 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
0123     ngx_rbtree_node_t *sentinel)
0124 {
0125     ngx_rbtree_node_t  **p;
0126 
0127     for ( ;; ) {
0128 
0129         /*
0130          * Timer values
0131          * 1) are spread in small range, usually several minutes,
0132          * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
0133          * The comparison takes into account that overflow.
0134          */
0135 
0136         /*  node->key < temp->key */
0137 
0138         p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
0139             ? &temp->left : &temp->right;
0140 
0141         if (*p == sentinel) {
0142             break;
0143         }
0144 
0145         temp = *p;
0146     }
0147 
0148     *p = node;
0149     node->parent = temp;
0150     node->left = sentinel;
0151     node->right = sentinel;
0152     ngx_rbt_red(node);
0153 }
0154 
0155 
0156 void
0157 ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
0158 {
0159     ngx_uint_t           red;
0160     ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;
0161 
0162     /* a binary tree delete */
0163 
0164     root = &tree->root;
0165     sentinel = tree->sentinel;
0166 
0167     if (node->left == sentinel) {
0168         temp = node->right;
0169         subst = node;
0170 
0171     } else if (node->right == sentinel) {
0172         temp = node->left;
0173         subst = node;
0174 
0175     } else {
0176         subst = ngx_rbtree_min(node->right, sentinel);
0177 
0178         if (subst->left != sentinel) {
0179             temp = subst->left;
0180         } else {
0181             temp = subst->right;
0182         }
0183     }
0184 
0185     if (subst == *root) {
0186         *root = temp;
0187         ngx_rbt_black(temp);
0188 
0189         /* DEBUG stuff */
0190         node->left = NULL;
0191         node->right = NULL;
0192         node->parent = NULL;
0193         node->key = 0;
0194 
0195         return;
0196     }
0197 
0198     red = ngx_rbt_is_red(subst);
0199 
0200     if (subst == subst->parent->left) {
0201         subst->parent->left = temp;
0202 
0203     } else {
0204         subst->parent->right = temp;
0205     }
0206 
0207     if (subst == node) {
0208 
0209         temp->parent = subst->parent;
0210 
0211     } else {
0212 
0213         if (subst->parent == node) {
0214             temp->parent = subst;
0215 
0216         } else {
0217             temp->parent = subst->parent;
0218         }
0219 
0220         subst->left = node->left;
0221         subst->right = node->right;
0222         subst->parent = node->parent;
0223         ngx_rbt_copy_color(subst, node);
0224 
0225         if (node == *root) {
0226             *root = subst;
0227 
0228         } else {
0229             if (node == node->parent->left) {
0230                 node->parent->left = subst;
0231             } else {
0232                 node->parent->right = subst;
0233             }
0234         }
0235 
0236         if (subst->left != sentinel) {
0237             subst->left->parent = subst;
0238         }
0239 
0240         if (subst->right != sentinel) {
0241             subst->right->parent = subst;
0242         }
0243     }
0244 
0245     /* DEBUG stuff */
0246     node->left = NULL;
0247     node->right = NULL;
0248     node->parent = NULL;
0249     node->key = 0;
0250 
0251     if (red) {
0252         return;
0253     }
0254 
0255     /* a delete fixup */
0256 
0257     while (temp != *root && ngx_rbt_is_black(temp)) {
0258 
0259         if (temp == temp->parent->left) {
0260             w = temp->parent->right;
0261 
0262             if (ngx_rbt_is_red(w)) {
0263                 ngx_rbt_black(w);
0264                 ngx_rbt_red(temp->parent);
0265                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
0266                 w = temp->parent->right;
0267             }
0268 
0269             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
0270                 ngx_rbt_red(w);
0271                 temp = temp->parent;
0272 
0273             } else {
0274                 if (ngx_rbt_is_black(w->right)) {
0275                     ngx_rbt_black(w->left);
0276                     ngx_rbt_red(w);
0277                     ngx_rbtree_right_rotate(root, sentinel, w);
0278                     w = temp->parent->right;
0279                 }
0280 
0281                 ngx_rbt_copy_color(w, temp->parent);
0282                 ngx_rbt_black(temp->parent);
0283                 ngx_rbt_black(w->right);
0284                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
0285                 temp = *root;
0286             }
0287 
0288         } else {
0289             w = temp->parent->left;
0290 
0291             if (ngx_rbt_is_red(w)) {
0292                 ngx_rbt_black(w);
0293                 ngx_rbt_red(temp->parent);
0294                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
0295                 w = temp->parent->left;
0296             }
0297 
0298             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
0299                 ngx_rbt_red(w);
0300                 temp = temp->parent;
0301 
0302             } else {
0303                 if (ngx_rbt_is_black(w->left)) {
0304                     ngx_rbt_black(w->right);
0305                     ngx_rbt_red(w);
0306                     ngx_rbtree_left_rotate(root, sentinel, w);
0307                     w = temp->parent->left;
0308                 }
0309 
0310                 ngx_rbt_copy_color(w, temp->parent);
0311                 ngx_rbt_black(temp->parent);
0312                 ngx_rbt_black(w->left);
0313                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
0314                 temp = *root;
0315             }
0316         }
0317     }
0318 
0319     ngx_rbt_black(temp);
0320 }
0321 
0322 
0323 static ngx_inline void
0324 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
0325     ngx_rbtree_node_t *node)
0326 {
0327     ngx_rbtree_node_t  *temp;
0328 
0329     temp = node->right;
0330     node->right = temp->left;
0331 
0332     if (temp->left != sentinel) {
0333         temp->left->parent = node;
0334     }
0335 
0336     temp->parent = node->parent;
0337 
0338     if (node == *root) {
0339         *root = temp;
0340 
0341     } else if (node == node->parent->left) {
0342         node->parent->left = temp;
0343 
0344     } else {
0345         node->parent->right = temp;
0346     }
0347 
0348     temp->left = node;
0349     node->parent = temp;
0350 }
0351 
0352 
0353 static ngx_inline void
0354 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
0355     ngx_rbtree_node_t *node)
0356 {
0357     ngx_rbtree_node_t  *temp;
0358 
0359     temp = node->left;
0360     node->left = temp->right;
0361 
0362     if (temp->right != sentinel) {
0363         temp->right->parent = node;
0364     }
0365 
0366     temp->parent = node->parent;
0367 
0368     if (node == *root) {
0369         *root = temp;
0370 
0371     } else if (node == node->parent->right) {
0372         node->parent->right = temp;
0373 
0374     } else {
0375         node->parent->left = temp;
0376     }
0377 
0378     temp->right = node;
0379     node->parent = temp;
0380 }
0381 
0382 
0383 ngx_rbtree_node_t *
0384 ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
0385 {
0386     ngx_rbtree_node_t  *root, *sentinel, *parent;
0387 
0388     sentinel = tree->sentinel;
0389 
0390     if (node->right != sentinel) {
0391         return ngx_rbtree_min(node->right, sentinel);
0392     }
0393 
0394     root = tree->root;
0395 
0396     for ( ;; ) {
0397         parent = node->parent;
0398 
0399         if (node == root) {
0400             return NULL;
0401         }
0402 
0403         if (node == parent->left) {
0404             return parent;
0405         }
0406 
0407         node = parent;
0408     }
0409 }