Mercurial > hg > nginx

comparison src/core/ngx_rbtree.c @ 853:a7c8cbb4c55f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rbtree insert procedure
author Igor Sysoev <igor@sysoev.ru>
date Thu, 16 Nov 2006 15:34:52 +0000
parents 629b5e4f8931
children 4924b71d77f6
comparison
equal deleted inserted replaced
852:629b5e4f8931 853:a7c8cbb4c55f
45 *root = node; 45 *root = node;
46 46
47 return; 47 return;
48 } 48 }
49 49
50 /* 50 tree->insert(*root, node, sentinel);
51 * The rbtree is currently used by event timers only. Timer values
52 * 1) are spread in small range, usually several minutes,
53 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
54 * The below comparison takes into account that overflow.
55 *
56 * If there will be a necessity to use the rbtree for values with
57 * other comparison rules, then a whole "for ( ;; )" loop should
58 * be made as tree->insert() function.
59 */
60
61 temp = *root;
62
63 for ( ;; ) {
64
65 /* node->key < temp->key */
66
67 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
68 < 0)
69 {
70 if (temp->left == sentinel) {
71 temp->left = node;
72 break;
73 }
74
75 temp = temp->left;
76 continue;
77 }
78
79 if (temp->right == sentinel) {
80 temp->right = node;
81 break;
82 }
83
84 temp = temp->right;
85 continue;
86 }
87
88 node->parent = temp;
89 node->left = sentinel;
90 node->right = sentinel;
91
92 51
93 /* re-balance tree */ 52 /* re-balance tree */
94
95 ngx_rbt_red(node);
96 53
97 while (node != *root && ngx_rbt_is_red(node->parent)) { 54 while (node != *root && ngx_rbt_is_red(node->parent)) {
98 55
99 if (node->parent == node->parent->parent->left) { 56 if (node->parent == node->parent->parent->left) {
100 temp = node->parent->parent->right; 57 temp = node->parent->parent->right;
134 ngx_rbt_black(node->parent); 91 ngx_rbt_black(node->parent);
135 ngx_rbt_red(node->parent->parent); 92 ngx_rbt_red(node->parent->parent);
136 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); 93 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
137 } 94 }
138 } 95 }
139
140 } 96 }
141 97
142 ngx_rbt_black(*root); 98 ngx_rbt_black(*root);
99 }
100
101
102 void
103 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
104 ngx_rbtree_node_t *sentinel)
105 {
106 for ( ;; ) {
107
108 /*
109 * Timer values
110 * 1) are spread in small range, usually several minutes,
111 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
112 * The comparison takes into account that overflow.
113 */
114
115 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
116 < 0)
117 {
118 /* node->key < temp->key */
119
120 if (temp->left == sentinel) {
121 temp->left = node;
122 break;
123 }
124
125 temp = temp->left;
126
127 } else {
128
129 if (temp->right == sentinel) {
130 temp->right = node;
131 break;
132 }
133
134 temp = temp->right;
135 }
136 }
137
138 node->parent = temp;
139 node->left = sentinel;
140 node->right = sentinel;
141 ngx_rbt_red(node);
143 } 142 }
144 143
145 144
146 void 145 void
147 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, 146 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,
148 ngx_rbtree_node_t *node) 147 ngx_rbtree_node_t *node)
149 { 148 {
150 ngx_int_t red; 149 ngx_uint_t red;
151 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; 150 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;
152 151
153 /* a binary tree delete */ 152 /* a binary tree delete */
154 153
155 root = (ngx_rbtree_node_t **) &tree->root; 154 root = (ngx_rbtree_node_t **) &tree->root;