Mercurial > hg > nginx

annotate src/core/ngx_rbtree.c @ 7660:d33e17499088

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Version bump.
author Maxim Dounin <mdounin@mdounin.ru>
date Tue, 26 May 2020 22:03:00 +0300
parents 7fdcf308e0f0
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
441
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 229
diff changeset
1
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 229
diff changeset
2 /*
444
42d11f017717 nginx-0.1.0-2004-09-29-20:00:49 import; remove years from copyright
Igor Sysoev <igor@sysoev.ru>
parents: 441
diff changeset
3 * Copyright (C) Igor Sysoev
4412
d620f497c50f Copyright updated.
Maxim Konovalov <maxim@nginx.com>
parents: 1764
diff changeset
4 * Copyright (C) Nginx, Inc.
441
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 229
diff changeset
5 */
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 229
diff changeset
6
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
7
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
8 #include <ngx_config.h>
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
9 #include <ngx_core.h>
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
10
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
11
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
12 /*
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
13 * The red-black tree code is based on the algorithm described in
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
14 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
15 */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
16
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
17
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
18 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
19 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
20 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
21 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
22
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
23
493
975f62e77f02 nginx-0.1.21-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 467
diff changeset
24 void
5894
1f513d7f1b45 Events: removed broken thread support from event timers.
Valentin Bartenev <vbart@nginx.com>
parents: 4576
diff changeset
25 ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
26 {
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
27 ngx_rbtree_node_t **root, *temp, *sentinel;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
28
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
29 /* a binary tree insert */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
30
6925
b3c5b4312667 Removed casts not needed after 1f513d7f1b45.
Ruslan Ermilov <ru@nginx.com>
parents: 5894
diff changeset
31 root = &tree->root;
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
32 sentinel = tree->sentinel;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
33
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
34 if (*root == sentinel) {
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
35 node->parent = NULL;
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
36 node->left = sentinel;
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
37 node->right = sentinel;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
38 ngx_rbt_black(node);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
39 *root = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
40
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
41 return;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
42 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
43
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
44 tree->insert(*root, node, sentinel);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
45
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
46 /* re-balance tree */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
47
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
48 while (node != *root && ngx_rbt_is_red(node->parent)) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
49
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
50 if (node->parent == node->parent->parent->left) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
51 temp = node->parent->parent->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
52
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
53 if (ngx_rbt_is_red(temp)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
54 ngx_rbt_black(node->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
55 ngx_rbt_black(temp);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
56 ngx_rbt_red(node->parent->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
57 node = node->parent->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
58
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
59 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
60 if (node == node->parent->right) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
61 node = node->parent;
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
62 ngx_rbtree_left_rotate(root, sentinel, node);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
63 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
64
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
65 ngx_rbt_black(node->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
66 ngx_rbt_red(node->parent->parent);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
67 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
68 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
69
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
70 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
71 temp = node->parent->parent->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
72
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
73 if (ngx_rbt_is_red(temp)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
74 ngx_rbt_black(node->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
75 ngx_rbt_black(temp);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
76 ngx_rbt_red(node->parent->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
77 node = node->parent->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
78
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
79 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
80 if (node == node->parent->left) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
81 node = node->parent;
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
82 ngx_rbtree_right_rotate(root, sentinel, node);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
83 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
84
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
85 ngx_rbt_black(node->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
86 ngx_rbt_red(node->parent->parent);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
87 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
88 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
89 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
90 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
91
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
92 ngx_rbt_black(*root);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
93 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
94
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
95
493
975f62e77f02 nginx-0.1.21-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 467
diff changeset
96 void
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
97 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
98 ngx_rbtree_node_t *sentinel)
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
99 {
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
100 ngx_rbtree_node_t **p;
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
101
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
102 for ( ;; ) {
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
103
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
104 p = (node->key < temp->key) ? &temp->left : &temp->right;
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
105
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
106 if (*p == sentinel) {
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
107 break;
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
108 }
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
109
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
110 temp = *p;
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
111 }
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
112
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
113 *p = node;
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
114 node->parent = temp;
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
115 node->left = sentinel;
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
116 node->right = sentinel;
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
117 ngx_rbt_red(node);
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
118 }
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
119
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
120
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
121 void
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
122 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
123 ngx_rbtree_node_t *sentinel)
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
124 {
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
125 ngx_rbtree_node_t **p;
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
126
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
127 for ( ;; ) {
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
128
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
129 /*
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
130 * Timer values
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
131 * 1) are spread in small range, usually several minutes,
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
132 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
133 * The comparison takes into account that overflow.
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
134 */
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
135
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
136 /* node->key < temp->key */
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
137
4576
876e6b0814a5 Fixed signed integer overflows in timer code (ticket #145).
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
138 p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
139 ? &temp->left : &temp->right;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
140
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
141 if (*p == sentinel) {
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
142 break;
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
143 }
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
144
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
145 temp = *p;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
146 }
1746
3c0b44825071 style fix: remove trailing spaces
Igor Sysoev <igor@sysoev.ru>
parents: 1743
diff changeset
147
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
148 *p = node;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
149 node->parent = temp;
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
150 node->left = sentinel;
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
151 node->right = sentinel;
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
152 ngx_rbt_red(node);
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
153 }
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
154
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
155
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
156 void
5894
1f513d7f1b45 Events: removed broken thread support from event timers.
Valentin Bartenev <vbart@nginx.com>
parents: 4576
diff changeset
157 ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
158 {
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
159 ngx_uint_t red;
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
160 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
161
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
162 /* a binary tree delete */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
163
6925
b3c5b4312667 Removed casts not needed after 1f513d7f1b45.
Ruslan Ermilov <ru@nginx.com>
parents: 5894
diff changeset
164 root = &tree->root;
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
165 sentinel = tree->sentinel;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
166
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
167 if (node->left == sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
168 temp = node->right;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
169 subst = node;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
170
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
171 } else if (node->right == sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
172 temp = node->left;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
173 subst = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
174
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
175 } else {
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
176 subst = ngx_rbtree_min(node->right, sentinel);
7576
7fdcf308e0f0 Core: removed dead code in ngx_rbtree_delete().
Vladimir Homutov <vl@nginx.com>
parents: 6928
diff changeset
177 temp = subst->right;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
178 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
179
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
180 if (subst == *root) {
229
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
181 *root = temp;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
182 ngx_rbt_black(temp);
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
183
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
184 /* DEBUG stuff */
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
185 node->left = NULL;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
186 node->right = NULL;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
187 node->parent = NULL;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
188 node->key = 0;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
189
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
190 return;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
191 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
192
852
629b5e4f8931 change variable name
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
193 red = ngx_rbt_is_red(subst);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
194
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
195 if (subst == subst->parent->left) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
196 subst->parent->left = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
197
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
198 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
199 subst->parent->right = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
200 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
201
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
202 if (subst == node) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
203
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
204 temp->parent = subst->parent;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
205
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
206 } else {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
207
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
208 if (subst->parent == node) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
209 temp->parent = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
210
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
211 } else {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
212 temp->parent = subst->parent;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
213 }
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
214
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
215 subst->left = node->left;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
216 subst->right = node->right;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
217 subst->parent = node->parent;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
218 ngx_rbt_copy_color(subst, node);
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
219
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
220 if (node == *root) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
221 *root = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
222
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
223 } else {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
224 if (node == node->parent->left) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
225 node->parent->left = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
226 } else {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
227 node->parent->right = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
228 }
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
229 }
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
230
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
231 if (subst->left != sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
232 subst->left->parent = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
233 }
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
234
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
235 if (subst->right != sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
236 subst->right->parent = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
237 }
1764
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
238 }
229
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
239
1764
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
240 /* DEBUG stuff */
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
241 node->left = NULL;
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
242 node->right = NULL;
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
243 node->parent = NULL;
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
244 node->key = 0;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
245
852
629b5e4f8931 change variable name
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
246 if (red) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
247 return;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
248 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
249
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
250 /* a delete fixup */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
251
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
252 while (temp != *root && ngx_rbt_is_black(temp)) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
253
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
254 if (temp == temp->parent->left) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
255 w = temp->parent->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
256
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
257 if (ngx_rbt_is_red(w)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
258 ngx_rbt_black(w);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
259 ngx_rbt_red(temp->parent);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
260 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
261 w = temp->parent->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
262 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
263
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
264 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
265 ngx_rbt_red(w);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
266 temp = temp->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
267
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
268 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
269 if (ngx_rbt_is_black(w->right)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
270 ngx_rbt_black(w->left);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
271 ngx_rbt_red(w);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
272 ngx_rbtree_right_rotate(root, sentinel, w);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
273 w = temp->parent->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
274 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
275
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
276 ngx_rbt_copy_color(w, temp->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
277 ngx_rbt_black(temp->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
278 ngx_rbt_black(w->right);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
279 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
280 temp = *root;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
281 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
282
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
283 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
284 w = temp->parent->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
285
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
286 if (ngx_rbt_is_red(w)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
287 ngx_rbt_black(w);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
288 ngx_rbt_red(temp->parent);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
289 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
290 w = temp->parent->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
291 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
292
213
f536f91e8e99 nginx-0.0.1-2003-12-19-15:45:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 212
diff changeset
293 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
294 ngx_rbt_red(w);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
295 temp = temp->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
296
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
297 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
298 if (ngx_rbt_is_black(w->left)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
299 ngx_rbt_black(w->right);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
300 ngx_rbt_red(w);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
301 ngx_rbtree_left_rotate(root, sentinel, w);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
302 w = temp->parent->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
303 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
304
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
305 ngx_rbt_copy_color(w, temp->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
306 ngx_rbt_black(temp->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
307 ngx_rbt_black(w->left);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
308 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
309 temp = *root;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
310 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
311 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
312 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
313
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
314 ngx_rbt_black(temp);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
315 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
316
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
317
493
975f62e77f02 nginx-0.1.21-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 467
diff changeset
318 static ngx_inline void
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
319 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
320 ngx_rbtree_node_t *node)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
321 {
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
322 ngx_rbtree_node_t *temp;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
323
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
324 temp = node->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
325 node->right = temp->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
326
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
327 if (temp->left != sentinel) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
328 temp->left->parent = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
329 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
330
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
331 temp->parent = node->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
332
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
333 if (node == *root) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
334 *root = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
335
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
336 } else if (node == node->parent->left) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
337 node->parent->left = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
338
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
339 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
340 node->parent->right = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
341 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
342
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
343 temp->left = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
344 node->parent = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
345 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
346
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
347
493
975f62e77f02 nginx-0.1.21-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 467
diff changeset
348 static ngx_inline void
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
349 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
350 ngx_rbtree_node_t *node)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
351 {
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
352 ngx_rbtree_node_t *temp;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
353
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
354 temp = node->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
355 node->left = temp->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
356
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
357 if (temp->right != sentinel) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
358 temp->right->parent = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
359 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
360
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
361 temp->parent = node->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
362
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
363 if (node == *root) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
364 *root = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
365
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
366 } else if (node == node->parent->right) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
367 node->parent->right = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
368
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
369 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
370 node->parent->left = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
371 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
372
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
373 temp->right = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
374 node->parent = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
375 }
6928
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
376
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
377
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
378 ngx_rbtree_node_t *
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
379 ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
380 {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
381 ngx_rbtree_node_t *root, *sentinel, *parent;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
382
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
383 sentinel = tree->sentinel;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
384
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
385 if (node->right != sentinel) {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
386 return ngx_rbtree_min(node->right, sentinel);
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
387 }
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
388
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
389 root = tree->root;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
390
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
391 for ( ;; ) {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
392 parent = node->parent;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
393
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
394 if (node == root) {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
395 return NULL;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
396 }
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
397
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
398 if (node == parent->left) {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
399 return parent;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
400 }
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
401
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
402 node = parent;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
403 }
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
404 }