Mercurial > hg > nginx

annotate src/core/ngx_rbtree.c @ 9274:46ecad404a29 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Mail: reset imap tag to empty after authentication attempt. We need to reset the imap tag to empty after an authentication attempt completes, otherwise if the next line parsed is incomplete with no tag (e.g. empty line) then we use the "tag" from the previous buffer which is now definitely wrong and has been partially overwritten with the most recently read data (e.g. CRLF). An example before this patch: S: * OK IMAP4 ready C: foobar login a b S: foobar NO Incorrect username or password. C: S: S: obar BAD invalid command Then with this patch: S: * OK IMAP4 ready C: foobar login a b S: foobar NO Incorrect username or password. C: S: * BAD invalid command
author Rob Mueller <robm@fastmailteam.com>
date Wed, 15 May 2024 10:06: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 }