One Level Up Top Level

src/core/ngx_rbtree.c - nginx-1.7.10

Functions defined

Source code


  2. /*
  3. * Copyright (C) Igor Sysoev
  4. * Copyright (C) Nginx, Inc.
  5. */


  8. #include <ngx_config.h>
  9. #include <ngx_core.h>


  12. /*
  13. * The red-black tree code is based on the algorithm described in
  14. * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
  15. */


  18. static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
  19.     ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
  20. static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
  21.     ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);


  24. void
  25. ‌ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
  26. {
  27.     ngx_rbtree_node_t  **root, *temp, *sentinel;

  29.     /* a binary tree insert */

  31.     root = (ngx_rbtree_node_t **) &tree->root;
  32.     sentinel = tree->sentinel;

  34.     if (*root == sentinel) {
  35.         node->parent = NULL;
  36.         node->left = sentinel;
  37.         node->right = sentinel;
  38.         ngx_rbt_black(node);
  39.         *root = node;

  41.         return;
  42.     }

  44.     tree->insert(*root, node, sentinel);

  46.     /* re-balance tree */

  48.     while (node != *root && ngx_rbt_is_red(node->parent)) {

  50.         if (node->parent == node->parent->parent->left) {
  51.             temp = node->parent->parent->right;

  53.             if (ngx_rbt_is_red(temp)) {
  54.                 ngx_rbt_black(node->parent);
  55.                 ngx_rbt_black(temp);
  56.                 ngx_rbt_red(node->parent->parent);
  57.                 node = node->parent->parent;

  59.             } else {
  60.                 if (node == node->parent->right) {
  61.                     node = node->parent;
  62.                     ngx_rbtree_left_rotate(root, sentinel, node);
  63.                 }

  65.                 ngx_rbt_black(node->parent);
  66.                 ngx_rbt_red(node->parent->parent);
  67.                 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
  68.             }

  70.         } else {
  71.             temp = node->parent->parent->left;

  73.             if (ngx_rbt_is_red(temp)) {
  74.                 ngx_rbt_black(node->parent);
  75.                 ngx_rbt_black(temp);
  76.                 ngx_rbt_red(node->parent->parent);
  77.                 node = node->parent->parent;

  79.             } else {
  80.                 if (node == node->parent->left) {
  81.                     node = node->parent;
  82.                     ngx_rbtree_right_rotate(root, sentinel, node);
  83.                 }

  85.                 ngx_rbt_black(node->parent);
  86.                 ngx_rbt_red(node->parent->parent);
  87.                 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
  88.             }
  89.         }
  90.     }

  92.     ngx_rbt_black(*root);
  93. }


  96. void
  97. ‌ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
  98.     ngx_rbtree_node_t *sentinel)
  99. {
  100.     ngx_rbtree_node_t  **p;

  102.     for ( ;; ) {

  104.         p = (node->key < temp->key) ? &temp->left : &temp->right;

  106.         if (*p == sentinel) {
  107.             break;
  108.         }

  110.         temp = *p;
  111.     }

  113.     *p = node;
  114.     node->parent = temp;
  115.     node->left = sentinel;
  116.     node->right = sentinel;
  117.     ngx_rbt_red(node);
  118. }


  121. void
  122. ‌ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
  123.     ngx_rbtree_node_t *sentinel)
  124. {
  125.     ngx_rbtree_node_t  **p;

  127.     for ( ;; ) {

  129.         /*
  130.          * Timer values
  131.          * 1) are spread in small range, usually several minutes,
  132.          * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
  133.          * The comparison takes into account that overflow.
  134.          */

  136.         /*  node->key < temp->key */

  138.         p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
  139.             ? &temp->left : &temp->right;

  141.         if (*p == sentinel) {
  142.             break;
  143.         }

  145.         temp = *p;
  146.     }

  148.     *p = node;
  149.     node->parent = temp;
  150.     node->left = sentinel;
  151.     node->right = sentinel;
  152.     ngx_rbt_red(node);
  153. }


  156. void
  157. ‌ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
  158. {
  159.     ngx_uint_t           red;
  160.     ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;

  162.     /* a binary tree delete */

  164.     root = (ngx_rbtree_node_t **) &tree->root;
  165.     sentinel = tree->sentinel;

  167.     if (node->left == sentinel) {
  168.         temp = node->right;
  169.         subst = node;

  171.     } else if (node->right == sentinel) {
  172.         temp = node->left;
  173.         subst = node;

  175.     } else {
  176.         subst = ngx_rbtree_min(node->right, sentinel);

  178.         if (subst->left != sentinel) {
  179.             temp = subst->left;
  180.         } else {
  181.             temp = subst->right;
  182.         }
  183.     }

  185.     if (subst == *root) {
  186.         *root = temp;
  187.         ngx_rbt_black(temp);

  189.         /* DEBUG stuff */
  190.         node->left = NULL;
  191.         node->right = NULL;
  192.         node->parent = NULL;
  193.         node->key = 0;

  195.         return;
  196.     }

  198.     red = ngx_rbt_is_red(subst);

  200.     if (subst == subst->parent->left) {
  201.         subst->parent->left = temp;

  203.     } else {
  204.         subst->parent->right = temp;
  205.     }

  207.     if (subst == node) {

  209.         temp->parent = subst->parent;

  211.     } else {

  213.         if (subst->parent == node) {
  214.             temp->parent = subst;

  216.         } else {
  217.             temp->parent = subst->parent;
  218.         }

  220.         subst->left = node->left;
  221.         subst->right = node->right;
  222.         subst->parent = node->parent;
  223.         ngx_rbt_copy_color(subst, node);

  225.         if (node == *root) {
  226.             *root = subst;

  228.         } else {
  229.             if (node == node->parent->left) {
  230.                 node->parent->left = subst;
  231.             } else {
  232.                 node->parent->right = subst;
  233.             }
  234.         }

  236.         if (subst->left != sentinel) {
  237.             subst->left->parent = subst;
  238.         }

  240.         if (subst->right != sentinel) {
  241.             subst->right->parent = subst;
  242.         }
  243.     }

  245.     /* DEBUG stuff */
  246.     node->left = NULL;
  247.     node->right = NULL;
  248.     node->parent = NULL;
  249.     node->key = 0;

  251.     if (red) {
  252.         return;
  253.     }

  255.     /* a delete fixup */

  257.     while (temp != *root && ngx_rbt_is_black(temp)) {

  259.         if (temp == temp->parent->left) {
  260.             w = temp->parent->right;

  262.             if (ngx_rbt_is_red(w)) {
  263.                 ngx_rbt_black(w);
  264.                 ngx_rbt_red(temp->parent);
  265.                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
  266.                 w = temp->parent->right;
  267.             }

  269.             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
  270.                 ngx_rbt_red(w);
  271.                 temp = temp->parent;

  273.             } else {
  274.                 if (ngx_rbt_is_black(w->right)) {
  275.                     ngx_rbt_black(w->left);
  276.                     ngx_rbt_red(w);
  277.                     ngx_rbtree_right_rotate(root, sentinel, w);
  278.                     w = temp->parent->right;
  279.                 }

  281.                 ngx_rbt_copy_color(w, temp->parent);
  282.                 ngx_rbt_black(temp->parent);
  283.                 ngx_rbt_black(w->right);
  284.                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
  285.                 temp = *root;
  286.             }

  288.         } else {
  289.             w = temp->parent->left;

  291.             if (ngx_rbt_is_red(w)) {
  292.                 ngx_rbt_black(w);
  293.                 ngx_rbt_red(temp->parent);
  294.                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
  295.                 w = temp->parent->left;
  296.             }

  298.             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
  299.                 ngx_rbt_red(w);
  300.                 temp = temp->parent;

  302.             } else {
  303.                 if (ngx_rbt_is_black(w->left)) {
  304.                     ngx_rbt_black(w->right);
  305.                     ngx_rbt_red(w);
  306.                     ngx_rbtree_left_rotate(root, sentinel, w);
  307.                     w = temp->parent->left;
  308.                 }

  310.                 ngx_rbt_copy_color(w, temp->parent);
  311.                 ngx_rbt_black(temp->parent);
  312.                 ngx_rbt_black(w->left);
  313.                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
  314.                 temp = *root;
  315.             }
  316.         }
  317.     }

  319.     ngx_rbt_black(temp);
  320. }


  323. static ngx_inline void
  324. ‌ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
  325.     ngx_rbtree_node_t *node)
  326. {
  327.     ngx_rbtree_node_t  *temp;

  329.     temp = node->right;
  330.     node->right = temp->left;

  332.     if (temp->left != sentinel) {
  333.         temp->left->parent = node;
  334.     }

  336.     temp->parent = node->parent;

  338.     if (node == *root) {
  339.         *root = temp;

  341.     } else if (node == node->parent->left) {
  342.         node->parent->left = temp;

  344.     } else {
  345.         node->parent->right = temp;
  346.     }

  348.     temp->left = node;
  349.     node->parent = temp;
  350. }


  353. static ngx_inline void
  354. ‌ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
  355.     ngx_rbtree_node_t *node)
  356. {
  357.     ngx_rbtree_node_t  *temp;

  359.     temp = node->left;
  360.     node->left = temp->right;

  362.     if (temp->right != sentinel) {
  363.         temp->right->parent = node;
  364.     }

  366.     temp->parent = node->parent;

  368.     if (node == *root) {
  369.         *root = temp;

  371.     } else if (node == node->parent->right) {
  372.         node->parent->right = temp;

  374.     } else {
  375.         node->parent->left = temp;
  376.     }

  378.     temp->right = node;
  379.     node->parent = temp;
  380. }

One Level Up Top Level