release/src/router/nginx/src/core/ngx_rbtree.c

   1
   2 /*
   3  * Copyright (C) Igor Sysoev
   4  * Copyright (C) Nginx, Inc.
   5  */
   6
   7
   8 #include <ngx_config.h>
   9 #include <ngx_core.h>
  10
  11
  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  */
  16
  17
  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);
  22
  23
  24 void
  25 ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
  26     ngx_rbtree_node_t *node)
  27 {
  28     ngx_rbtree_node_t  **root, *temp, *sentinel;
  29
  30     /* a binary tree insert */
  31
  32     root = (ngx_rbtree_node_t **) &tree->root;
  33     sentinel = tree->sentinel;
  34
  35     if (*root == sentinel) {
  36         node->parent = NULL;
  37         node->left = sentinel;
  38         node->right = sentinel;
  39         ngx_rbt_black(node);
  40         *root = node;
  41
  42         return;
  43     }
  44
  45     tree->insert(*root, node, sentinel);
  46
  47     /* re-balance tree */
  48
  49     while (node != *root && ngx_rbt_is_red(node->parent)) {
  50
  51         if (node->parent == node->parent->parent->left) {
  52             temp = node->parent->parent->right;
  53
  54             if (ngx_rbt_is_red(temp)) {
  55                 ngx_rbt_black(node->parent);
  56                 ngx_rbt_black(temp);
  57                 ngx_rbt_red(node->parent->parent);
  58                 node = node->parent->parent;
  59
  60             } else {
  61                 if (node == node->parent->right) {
  62                     node = node->parent;
  63                     ngx_rbtree_left_rotate(root, sentinel, node);
  64                 }
  65
  66                 ngx_rbt_black(node->parent);
  67                 ngx_rbt_red(node->parent->parent);
  68                 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
  69             }
  70
  71         } else {
  72             temp = node->parent->parent->left;
  73
  74             if (ngx_rbt_is_red(temp)) {
  75                 ngx_rbt_black(node->parent);
  76                 ngx_rbt_black(temp);
  77                 ngx_rbt_red(node->parent->parent);
  78                 node = node->parent->parent;
  79
  80             } else {
  81                 if (node == node->parent->left) {
  82                     node = node->parent;
  83                     ngx_rbtree_right_rotate(root, sentinel, node);
  84                 }
  85
  86                 ngx_rbt_black(node->parent);
  87                 ngx_rbt_red(node->parent->parent);
  88                 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
  89             }
  90         }
  91     }
  92
  93     ngx_rbt_black(*root);
  94 }
  95
  96
  97 void
  98 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
  99     ngx_rbtree_node_t *sentinel)
 100 {
 101     ngx_rbtree_node_t  **p;
 102
 103     for ( ;; ) {
 104
 105         p = (node->key < temp->key) ? &temp->left : &temp->right;
 106
 107         if (*p == sentinel) {
 108             break;
 109         }
 110
 111         temp = *p;
 112     }
 113
 114     *p = node;
 115     node->parent = temp;
 116     node->left = sentinel;
 117     node->right = sentinel;
 118     ngx_rbt_red(node);
 119 }
 120
 121
 122 void
 123 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
 124     ngx_rbtree_node_t *sentinel)
 125 {
 126     ngx_rbtree_node_t  **p;
 127
 128     for ( ;; ) {
 129
 130         /*
 131          * Timer values
 132          * 1) are spread in small range, usually several minutes,
 133          * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
 134          * The comparison takes into account that overflow.
 135          */
 136
 137         /*  node->key < temp->key */
 138
 139         p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 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 }