Mercurial > hg > nginx

comparison src/core/ngx_rbtree.c @ 826:4390fcad6628

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