nginx/src/core/ngx_rbtree.c

   1
   2 /*
   3  * Copyright (C) Igor Sysoev
   4  */
   5
   6
   7 #include <ngx_config.h>
   8 #include <ngx_core.h>
   9
  10
  11 /*
  12  * The red-black tree code is based on the algorithm described in
  13  * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
  14  */
  15
  16
  17 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
  18     ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
  19 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
  20     ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
  21
  22
  23 void
  24 ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
  25     ngx_rbtree_node_t *node)
  26 {
  27     ngx_rbtree_node_t  **root, *temp, *sentinel;
  28
  29     /* a binary tree insert */
  30
  31     root = (ngx_rbtree_node_t **) &tree->root;
  32     sentinel = tree->sentinel;
  33
  34     if (*root == sentinel) {
  35         node->parent = NULL;
  36         node->left = sentinel;
  37         node->right = sentinel;
  38         ngx_rbt_black(node);
  39         *root = node;
  40
  41         return;
  42     }
  43
  44     tree->insert(*root, node, sentinel);
  45
  46     /* re-balance tree */
  47
  48     while (node != *root && ngx_rbt_is_red(node->parent)) {
  49
  50         if (node->parent == node->parent->parent->left) {
  51             temp = node->parent->parent->right;
  52
  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;
  58
  59             } else {
  60                 if (node == node->parent->right) {
  61                     node = node->parent;
  62                     ngx_rbtree_left_rotate(root, sentinel, node);
  63                 }
  64
  65                 ngx_rbt_black(node->parent);
  66                 ngx_rbt_red(node->parent->parent);
  67                 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
  68             }
  69
  70         } else {
  71             temp = node->parent->parent->left;
  72
  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;
  78
  79             } else {
  80                 if (node == node->parent->left) {
  81                     node = node->parent;
  82                     ngx_rbtree_right_rotate(root, sentinel, node);
  83                 }
  84
  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     }
  91
  92     ngx_rbt_black(*root);
  93 }
  94
  95
  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;
 101
 102     for ( ;; ) {
 103
 104         p = (node->key < temp->key) ? &temp->left : &temp->right;
 105
 106         if (*p == sentinel) {
 107             break;
 108         }
 109
 110         temp = *p;
 111     }
 112
 113     *p = node;
 114     node->parent = temp;
 115     node->left = sentinel;
 116     node->right = sentinel;
 117     ngx_rbt_red(node);
 118 }
 119
 120
 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;
 126
 127     for ( ;; ) {
 128
 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          */
 135
 136         /*  node->key < temp->key */
 137
 138         p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
 139               < 0)
 140             ? &temp->left : &temp->right;
 141
 142         if (*p == sentinel) {
 143             break;
 144         }
 145
 146         temp = *p;
 147     }
 148
 149     *p = node;
 150     node->parent = temp;
 151     node->left = sentinel;
 152     node->right = sentinel;
 153     ngx_rbt_red(node);
 154 }
 155
 156
 157 void
 158 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,
 159     ngx_rbtree_node_t *node)
 160 {
 161     ngx_uint_t           red;
 162     ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;
 163
 164     /* a binary tree delete */
 165
 166     root = (ngx_rbtree_node_t **) &tree->root;
 167     sentinel = tree->sentinel;
 168
 169     if (node->left == sentinel) {
 170         temp = node->right;
 171         subst = node;
 172
 173     } else if (node->right == sentinel) {
 174         temp = node->left;
 175         subst = node;
 176
 177     } else {
 178         subst = ngx_rbtree_min(node->right, sentinel);
 179
 180         if (subst->left != sentinel) {
 181             temp = subst->left;
 182         } else {
 183             temp = subst->right;
 184         }
 185     }
 186
 187     if (subst == *root) {
 188         *root = temp;
 189         ngx_rbt_black(temp);
 190
 191         /* DEBUG stuff */
 192         node->left = NULL;
 193         node->right = NULL;
 194         node->parent = NULL;
 195         node->key = 0;
 196
 197         return;
 198     }
 199
 200     red = ngx_rbt_is_red(subst);
 201
 202     if (subst == subst->parent->left) {
 203         subst->parent->left = temp;
 204
 205     } else {
 206         subst->parent->right = temp;
 207     }
 208
 209     if (subst == node) {
 210
 211         temp->parent = subst->parent;
 212
 213     } else {
 214
 215         if (subst->parent == node) {
 216             temp->parent = subst;
 217
 218         } else {
 219             temp->parent = subst->parent;
 220         }
 221
 222         subst->left = node->left;
 223         subst->right = node->right;
 224         subst->parent = node->parent;
 225         ngx_rbt_copy_color(subst, node);
 226
 227         if (node == *root) {
 228             *root = subst;
 229
 230         } else {
 231             if (node == node->parent->left) {
 232                 node->parent->left = subst;
 233             } else {
 234                 node->parent->right = subst;
 235             }
 236         }
 237
 238         if (subst->left != sentinel) {
 239             subst->left->parent = subst;
 240         }
 241
 242         if (subst->right != sentinel) {
 243             subst->right->parent = subst;
 244         }
 245     }
 246
 247     /* DEBUG stuff */
 248     node->left = NULL;
 249     node->right = NULL;
 250     node->parent = NULL;
 251     node->key = 0;
 252
 253     if (red) {
 254         return;
 255     }
 256
 257     /* a delete fixup */
 258
 259     while (temp != *root && ngx_rbt_is_black(temp)) {
 260
 261         if (temp == temp->parent->left) {
 262             w = temp->parent->right;
 263
 264             if (ngx_rbt_is_red(w)) {
 265                 ngx_rbt_black(w);
 266                 ngx_rbt_red(temp->parent);
 267                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
 268                 w = temp->parent->right;
 269             }
 270
 271             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
 272                 ngx_rbt_red(w);
 273                 temp = temp->parent;
 274
 275             } else {
 276                 if (ngx_rbt_is_black(w->right)) {
 277                     ngx_rbt_black(w->left);
 278                     ngx_rbt_red(w);
 279                     ngx_rbtree_right_rotate(root, sentinel, w);
 280                     w = temp->parent->right;
 281                 }
 282
 283                 ngx_rbt_copy_color(w, temp->parent);
 284                 ngx_rbt_black(temp->parent);
 285                 ngx_rbt_black(w->right);
 286                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
 287                 temp = *root;
 288             }
 289
 290         } else {
 291             w = temp->parent->left;
 292
 293             if (ngx_rbt_is_red(w)) {
 294                 ngx_rbt_black(w);
 295                 ngx_rbt_red(temp->parent);
 296                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
 297                 w = temp->parent->left;
 298             }
 299
 300             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
 301                 ngx_rbt_red(w);
 302                 temp = temp->parent;
 303
 304             } else {
 305                 if (ngx_rbt_is_black(w->left)) {
 306                     ngx_rbt_black(w->right);
 307                     ngx_rbt_red(w);
 308                     ngx_rbtree_left_rotate(root, sentinel, w);
 309                     w = temp->parent->left;
 310                 }
 311
 312                 ngx_rbt_copy_color(w, temp->parent);
 313                 ngx_rbt_black(temp->parent);
 314                 ngx_rbt_black(w->left);
 315                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
 316                 temp = *root;
 317             }
 318         }
 319     }
 320
 321     ngx_rbt_black(temp);
 322 }
 323
 324
 325 static ngx_inline void
 326 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
 327     ngx_rbtree_node_t *node)
 328 {
 329     ngx_rbtree_node_t  *temp;
 330
 331     temp = node->right;
 332     node->right = temp->left;
 333
 334     if (temp->left != sentinel) {
 335         temp->left->parent = node;
 336     }
 337
 338     temp->parent = node->parent;
 339
 340     if (node == *root) {
 341         *root = temp;
 342
 343     } else if (node == node->parent->left) {
 344         node->parent->left = temp;
 345
 346     } else {
 347         node->parent->right = temp;
 348     }
 349
 350     temp->left = node;
 351     node->parent = temp;
 352 }
 353
 354
 355 static ngx_inline void
 356 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
 357     ngx_rbtree_node_t *node)
 358 {
 359     ngx_rbtree_node_t  *temp;
 360
 361     temp = node->left;
 362     node->left = temp->right;
 363
 364     if (temp->right != sentinel) {
 365         temp->right->parent = node;
 366     }
 367
 368     temp->parent = node->parent;
 369
 370     if (node == *root) {
 371         *root = temp;
 372
 373     } else if (node == node->parent->right) {
 374         node->parent->right = temp;
 375
 376     } else {
 377         node->parent->left = temp;
 378     }
 379
 380     temp->right = node;
 381     node->parent = temp;
 382 }