Mercurial > hg > Members > innparusu > Gears

comparison src/parallel_execution/rb_tree.c @ 133:933c80f48d06

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
node stack rewrite
author ikkun
date Wed, 28 Sep 2016 19:02:25 +0900
parents 73a679a85c04
children 36ac17d37be4
comparison
equal deleted inserted replaced
132:73a679a85c04 133:933c80f48d06
215 __code insertCase4_2(struct Context* context, struct Traverse* traverse) { 215 __code insertCase4_2(struct Context* context, struct Traverse* traverse) {
216 traverse->current = traverse->current->right; 216 traverse->current = traverse->current->right;
217 goto meta(context, InsertCase5); 217 goto meta(context, InsertCase5);
218 } 218 }
219 219
220 __code insert4_2_stub(struct Context* context) { 220 __code insert4_2_stub(struct Context* context) {
221 struct Allocate* allocate = &context->data[Allocate]->allocate; 221 struct Allocate* allocate = &context->data[Allocate]->allocate;
222 allocate->size = sizeof(struct Element); 222 allocate->size = sizeof(struct Element);
223 allocator(context); 223 allocator(context);
224 struct Element* element = &context->data[context->dataNum]->node; 224 struct Element* element = &context->data[context->dataNum]->node;
225 element->data = (struct Data*)traverse->current; 225 element->data = (struct Data*)traverse->current;
247 } 247 }
248 248
249 // put rotateLeft's continuation as argument 249 // put rotateLeft's continuation as argument
250 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) { 250 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
251 struct Node* tmp = node->right; 251 struct Node* tmp = node->right;
252 struct Node* parent = 0;
253
254 // if you have a pararent as an argument , we don't need stack operation
255 stack_pop(context->node_stack, &parent);
256 252
257 if (parent) { 253 if (parent) {
258 if (node == parent->left) 254 if (node == parent->left)
259 parent->left = tmp; 255 parent->left = tmp;
260 else 256 else
261 parent->right = tmp; 257 parent->right = tmp;
262 } else { 258 } else {
263 tree->root = tmp; 259 tree->root = tmp;
264 } 260 }
265 261 element->data = (struct Data*)parent;
266 stack_push(context->node_stack, &parent); 262
267
268 node->right = tmp->left; 263 node->right = tmp->left;
269 tmp->left = node; 264 tmp->left = node;
270 traverse->current = tmp; 265 traverse->current = tmp;
271 266
272 goto meta(context, traverse->rotateNext); 267 goto meta(context, traverse->rotateNext);
273 } 268 }
274 269
275 __code rotateLeft_stub(struct Context* context) { 270 __code rotateLeft_stub(struct Context* context) {
271 struct Traverse* traverse = context->data[Traverse]->traverse;
272 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
273 traverse->nodeStack = traverse->nodeStack->next;
274 struct Allocate* allocate = &context->data[Allocate]->allocate;
275 allocate->size = sizeof(struct Element);
276 allocator(context);
277 struct Element* element = &context->data[context->dataNum]->node;
276 goto rotateLeft(context, 278 goto rotateLeft(context,
277 context->data[Traverse]->traverse.current, 279 context->data[Traverse]->traverse.current,
278 &context->data[Tree]->tree, 280 &context->data[Tree]->tree,
279 &context->data[Traverse]->traverse); 281 &context->data[Traverse]->traverse);
280 } 282 }
281 283
282 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) { 284 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Node* element) {
283 struct Node* tmp = node->left; 285 struct Node* tmp = node->left;
284 struct Node* parent = 0; 286
285
286 stack_pop(context->node_stack, &parent);
287
288 if (parent) { 287 if (parent) {
289 if (node == parent->left) 288 if (node == parent->left)
290 parent->left = tmp; 289 parent->left = tmp;
291 else 290 else
292 parent->right = tmp; 291 parent->right = tmp;
293 } else { 292 } else {
294 tree->root = tmp; 293 tree->root = tmp;
295 } 294 }
296 295
297 stack_push(context->node_stack, &parent); 296 element->data = (struct Data*)parent;
298 297
299 node->left = tmp->right; 298 node->left = tmp->right;
300 tmp->right = node; 299 tmp->right = node;
301 traverse->current = tmp; 300 traverse->current = tmp;
302 301
303 goto meta(context, traverse->rotateNext); 302 goto meta(context, traverse->rotateNext);
304 } 303 }
305 304
306 __code rotateRight_stub(struct Context* context) { 305 __code rotateRight_stub(struct Context* context) {
306 struct Allocate* allocate = &context->data[Allocate]->allocate;
307 allocate->size = sizeof(struct Element);
308 allocator(context);
309 struct Element* element = &context->data[context->dataNum]->node;
307 goto rotateRight(context, 310 goto rotateRight(context,
308 context->data[Traverse]->traverse.current, 311 context->data[Traverse]->traverse.current,
309 &context->data[Tree]->tree, 312 &context->data[Tree]->tree,
310 &context->data[Traverse]->traverse); 313 &context->data[Traverse]->traverse);
311 } 314 }
312 315
313 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) { 316 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {
314 if (stack_pop(node_stack, &traverse->current) == 0)
315 goto meta(context, StackClear);
316
317 traverse->current = 0; 317 traverse->current = 0;
318 318
319 goto meta(context, context->next); 319 goto meta(context, context->next);
320 } 320 }
321 321