Mercurial > hg > Members > Moririn

comparison src/parallel_execution/rb_tree.c @ 119:b224aa7b80a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove code stack, stack clear is directly called
author ikkun
date Mon, 26 Sep 2016 20:20:16 +0900
parents 32773f506410
children 2493f4226ca6
comparison
equal deleted inserted replaced
118:32773f506410 119:b224aa7b80a0
14 allocator(context); 14 allocator(context);
15 15
16 // we don't need this push 16 // we don't need this push
17 stack_push(context->code_stack, &context->next); 17 stack_push(context->code_stack, &context->next);
18 18
19 // after insert or replace, go to stack clear direct, we don't need this push
20 context->next = StackClear;
21 stack_push(context->code_stack, &context->next);
22
23 tree->root = &context->data[context->dataNum]->node; 19 tree->root = &context->data[context->dataNum]->node;
24 20
25 if (root) { 21 if (root) {
26 traverse->current = root; 22 traverse->current = root;
27 // traverse->result=compare(...) 23 // traverse->result=compare(...)
98 if (!isEmpty(context->node_stack)) // parent!=null 94 if (!isEmpty(context->node_stack)) // parent!=null
99 goto meta(context, InsertCase2); 95 goto meta(context, InsertCase2);
100 96
101 tree->root->color = Black; 97 tree->root->color = Black;
102 98
103 //go to stack clear 99 goto meta(context, StackClear);
104 stack_pop(context->code_stack, &context->next);
105 goto meta(context, context->next);
106 } 100 }
107 101
108 __code insert1_stub(struct Context* context) { 102 __code insert1_stub(struct Context* context) {
109 goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current); 103 goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current);
110 } 104 }
112 __code insertCase2(struct Context* context, struct Node* current) { 106 __code insertCase2(struct Context* context, struct Node* current) {
113 struct Node* parent; 107 struct Node* parent;
114 stack_pop(context->node_stack, &parent); 108 stack_pop(context->node_stack, &parent);
115 109
116 if (parent->color == Black) { 110 if (parent->color == Black) {
117 stack_pop(context->code_stack, &context->next); 111 goto meta(context, StackClear);
118 goto meta(context, context->next);
119 } 112 }
120 113
121 stack_push(context->node_stack, &parent); 114 stack_push(context->node_stack, &parent);
122 goto meta(context, InsertCase3); 115 goto meta(context, InsertCase3);
123 } 116 }
168 stack_push(context->node_stack, &grandparent); 161 stack_push(context->node_stack, &grandparent);
169 162
170 traverse->current = parent; 163 traverse->current = parent;
171 164
172 if ((current == parent->right) && (parent == grandparent->left)) { 165 if ((current == parent->right) && (parent == grandparent->left)) {
173 traverse->next = InsertCase4_1; 166 traverse->rotateNext = InsertCase4_1;
174 goto meta(context, RotateL); 167 goto meta(context, RotateL);
175 } else if ((current == parent->left) && (parent == grandparent->right)) { 168 } else if ((current == parent->left) && (parent == grandparent->right)) {
176 traverse->next = InsertCase4_2; 169 traverse->rotateNext = InsertCase4_2;
177 goto meta(context, RotateR); 170 goto meta(context, RotateR);
178 } 171 }
179 172
180 stack_push(context->node_stack, &parent); 173 stack_push(context->node_stack, &parent);
181 traverse->current = current; 174 traverse->current = current;
215 208
216 parent->color = Black; 209 parent->color = Black;
217 grandparent->color = Red; 210 grandparent->color = Red;
218 211
219 traverse->current = grandparent; 212 traverse->current = grandparent;
220 traverse->next = context->next; 213 traverse->rotateNext = StackClear;
221 if ((current == parent->left) && (parent == grandparent->left)) 214 if ((current == parent->left) && (parent == grandparent->left))
222 goto meta(context, RotateR); 215 goto meta(context, RotateR);
223 else 216 else
224 goto meta(context, RotateL); 217 goto meta(context, RotateL);
225 } 218 }
249 242
250 node->right = tmp->left; 243 node->right = tmp->left;
251 tmp->left = node; 244 tmp->left = node;
252 traverse->current = tmp; 245 traverse->current = tmp;
253 246
254 goto meta(context, traverse->next); 247 goto meta(context, traverse->rotateNext);
255 } 248 }
256 249
257 __code rotateLeft_stub(struct Context* context) { 250 __code rotateLeft_stub(struct Context* context) {
258 goto rotateLeft(context, 251 goto rotateLeft(context,
259 context->data[Traverse]->traverse.current, 252 context->data[Traverse]->traverse.current,
280 273
281 node->left = tmp->right; 274 node->left = tmp->right;
282 tmp->right = node; 275 tmp->right = node;
283 traverse->current = tmp; 276 traverse->current = tmp;
284 277
285 goto meta(context, traverse->next); 278 goto meta(context, traverse->rotateNext);
286 } 279 }
287 280
288 __code rotateRight_stub(struct Context* context) { 281 __code rotateRight_stub(struct Context* context) {
289 goto rotateRight(context, 282 goto rotateRight(context,
290 context->data[Traverse]->traverse.current, 283 context->data[Traverse]->traverse.current,
296 if (stack_pop(node_stack, &traverse->current) == 0) 289 if (stack_pop(node_stack, &traverse->current) == 0)
297 goto meta(context, StackClear); 290 goto meta(context, StackClear);
298 291
299 traverse->current = 0; 292 traverse->current = 0;
300 293
301 stack_pop(context->code_stack, &context->next);
302 goto meta(context, context->next); 294 goto meta(context, context->next);
303 } 295 }
304 296
305 __code stackClear_stub(struct Context* context) { 297 __code stackClear_stub(struct Context* context) {
306 goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse); 298 goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse);
312 traverse->current = tree->root; 304 traverse->current = tree->root;
313 305
314 goto meta(context, Search); 306 goto meta(context, Search);
315 } 307 }
316 308
317 goto meta(context, traverse->next); 309 goto meta(context, context->next);
318 } 310 }
319 311
320 __code get_stub(struct Context* context) { 312 __code get_stub(struct Context* context) {
321 goto get(context, &context->data[Tree]->tree, &context->data[Traverse]->traverse); 313 goto get(context, &context->data[Tree]->tree, &context->data[Traverse]->traverse);
322 } 314 }
335 } 327 }
336 328
337 if (traverse->current) 329 if (traverse->current)
338 goto meta(context, Search); 330 goto meta(context, Search);
339 331
340 stack_pop(context->code_stack, &context->next);
341 goto meta(context, context->next); 332 goto meta(context, context->next);
342 } 333 }
343 334
344 __code search_stub(struct Context* context) { 335 __code search_stub(struct Context* context) {
345 goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node); 336 goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node);