diff options
author | Igor Sysoev <igor@sysoev.ru> | 2003-12-05 20:07:27 +0300 |
---|---|---|
committer | Igor Sysoev <igor@sysoev.ru> | 2003-12-05 20:07:27 +0300 |
commit | 62260f2a158e27e5f6b1689e10dc25ea3c617473 (patch) | |
tree | d37c7d3f837c9f477a5010adedcbe98be89e735c /src/core/ngx_rbtree.c | |
parent | faca119aa5b2375d247c4948ba6791e7d8d2b8bc (diff) |
nginx-0.0.1-2003-12-05-20:07:27 import
Diffstat (limited to 'src/core/ngx_rbtree.c')
-rw-r--r-- | src/core/ngx_rbtree.c | 79 |
1 files changed, 43 insertions, 36 deletions
diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c index ea78e2254..3e6025f12 100644 --- a/src/core/ngx_rbtree.c +++ b/src/core/ngx_rbtree.c @@ -15,23 +15,25 @@ #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color) -ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node); +ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, + ngx_rbtree_t *sentinel, + ngx_rbtree_t *node); ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, + ngx_rbtree_t *sentinel, ngx_rbtree_t *node); -ngx_rbtree_t sentinel; - -void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node) +void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, + ngx_rbtree_t *node) { ngx_rbtree_t *temp; /* a binary tree insert */ - if (*root == &sentinel) { - node->parent = &sentinel; - node->left = &sentinel; - node->right = &sentinel; + if (*root == sentinel) { + node->parent = sentinel; + node->left = sentinel; + node->right = sentinel; ngx_rbt_black(node); *root = node; @@ -42,7 +44,7 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node) for ( ;; ) { if (node->key < temp->key) { - if (temp->left == &sentinel) { + if (temp->left == sentinel) { temp->left = node; break; } @@ -51,7 +53,7 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node) continue; } - if (temp->right == &sentinel) { + if (temp->right == sentinel) { temp->right = node; break; } @@ -61,8 +63,8 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node) } node->parent = temp; - node->left = &sentinel; - node->right = &sentinel; + node->left = sentinel; + node->right = sentinel; /* re-balance tree */ @@ -83,12 +85,12 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node) } else { if (node == node->parent->right) { node = node->parent; - ngx_rbtree_left_rotate(root, node); + ngx_rbtree_left_rotate(root, sentinel, node); } ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); - ngx_rbtree_right_rotate(root, node->parent->parent); + ngx_rbtree_right_rotate(root, sentinel, node->parent->parent); } } else { @@ -103,12 +105,12 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node) } else { if (node == node->parent->left) { node = node->parent; - ngx_rbtree_right_rotate(root, node); + ngx_rbtree_right_rotate(root, sentinel, node); } ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); - ngx_rbtree_left_rotate(root, node->parent->parent); + ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); } } @@ -118,34 +120,35 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node) } -void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node) +void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, + ngx_rbtree_t *node) { ngx_rbtree_t *subst, *temp, *w; /* a binary tree delete */ - if (node->left == &sentinel || node->right == &sentinel) { + if (node->left == sentinel || node->right == sentinel) { subst = node; } else { /* find a node successor */ - if (node->right == &sentinel) { + if (node->right == sentinel) { temp = node; subst = node->parent; - while (subst != &sentinel && temp == subst->right) { + while (subst != sentinel && temp == subst->right) { temp = subst; subst = subst->parent; } } else { - subst = ngx_rbtree_min(node->right); + subst = ngx_rbtree_min(node->right, sentinel); } } - if (subst->left != &sentinel) { + if (subst->left != sentinel) { temp = subst->left; } else { temp = subst->right; @@ -153,7 +156,7 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node) temp->parent = subst->parent; - if (subst->parent == &sentinel) { + if (subst->parent == sentinel) { *root = temp; } else if (subst == subst->parent->left) { @@ -174,14 +177,14 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node) /* a delete fixup */ - while (temp->parent != &sentinel && ngx_rbt_is_black(temp)) { + while (temp->parent != sentinel && ngx_rbt_is_black(temp)) { if (temp == temp->parent->left) { w = temp->parent->right; if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); - ngx_rbtree_left_rotate(root, temp->parent); + ngx_rbtree_left_rotate(root, sentinel, temp->parent); w = temp->parent->right; } @@ -193,14 +196,14 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node) if (ngx_rbt_is_black(w->right)) { ngx_rbt_black(w->left); ngx_rbt_red(w); - ngx_rbtree_right_rotate(root, w); + ngx_rbtree_right_rotate(root, sentinel, w); w = temp->parent->right; } ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->right); - ngx_rbtree_left_rotate(root, temp->parent); + ngx_rbtree_left_rotate(root, sentinel, temp->parent); temp = *root; } @@ -210,7 +213,7 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node) if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); - ngx_rbtree_right_rotate(root, temp->parent); + ngx_rbtree_right_rotate(root, sentinel, temp->parent); w = temp->parent->left; } @@ -222,14 +225,14 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node) if (ngx_rbt_is_black(w->left)) { ngx_rbt_black(w->right); ngx_rbt_red(w); - ngx_rbtree_left_rotate(root, w); + ngx_rbtree_left_rotate(root, sentinel, w); w = temp->parent->left; } ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->left); - ngx_rbtree_right_rotate(root, temp->parent); + ngx_rbtree_right_rotate(root, sentinel, temp->parent); temp = *root; } } @@ -239,20 +242,22 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node) } -ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node) +ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, + ngx_rbtree_t *sentinel, + ngx_rbtree_t *node) { ngx_rbtree_t *temp; temp = node->right; node->right = temp->left; - if (temp->left != &sentinel) { + if (temp->left != sentinel) { temp->left->parent = node; } temp->parent = node->parent; - if (node->parent == &sentinel) { + if (node->parent == sentinel) { *root = temp; } else if (node == node->parent->left) { @@ -267,20 +272,22 @@ ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node) } -ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node) +ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, + ngx_rbtree_t *sentinel, + ngx_rbtree_t *node) { ngx_rbtree_t *temp; temp = node->left; node->left = temp->right; - if (temp->right != &sentinel) { + if (temp->right != sentinel) { temp->right->parent = node; } temp->parent = node->parent; - if (node->parent == &sentinel) { + if (node->parent == sentinel) { *root = temp; } else if (node == node->parent->right) { |