Annotation of embedaddon/nginx/src/core/ngx_rbtree.c, revision 1.1
1.1 ! misho 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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ngx_rbtree.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / nginx / src / core