![[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|
Return to ngx_rbtree.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / nginx / src / core |
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: }