Mercurial > hg > Members > innparusu > Gears

comparison src/parallel_execution/rb_tree.c @ 136:c7ac153f86dd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix rotate cs stack
author one
date Thu, 29 Sep 2016 19:02:49 +0900
parents 9ae7ce6c83f5
children fe1fbfec7d01
comparison
equal deleted inserted replaced
135:9ae7ce6c83f5 136:c7ac153f86dd
4 #include "origin_cs.h" 4 #include "origin_cs.h"
5 5
6 extern void allocator(struct Context* context); 6 extern void allocator(struct Context* context);
7 extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2); 7 extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2);
8 8
9 extern int num; 9 void printTree1(union Data* data) {
10 struct Node* node = (struct Node*)data;
11 if (node == NULL) {
12 printf("NULL");
13 } else {
14 printf("key = %d (", node->key);
15 printTree1((union Data*)node->right);
16 printf("), (");
17 printTree1((union Data*)node->left);
18 printf(")");
19 }
20 }
21
22 void printTree(union Data* data) {
23 printTree1(data);
24 printf("\n");
25 }
10 26
11 __code put(struct Context* context, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) { 27 __code put(struct Context* context, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) {
28 printTree((union Data*)tree->root);
12 traverse->newNode = newNode; 29 traverse->newNode = newNode;
13 tree->root = newNode; // this should done at stackClear 30 tree->root = newNode; // this should done at stackClear
14 if (root) { 31 if (root) {
15 traverse->current = root; 32 traverse->current = root;
16 // traverse->result=compare(...) 33 // traverse->result=compare(...)
184 &context->data[Traverse]->traverse.nodeStack->data->node, 201 &context->data[Traverse]->traverse.nodeStack->data->node,
185 &context->data[Traverse]->traverse.nodeStack->next->data->node); 202 &context->data[Traverse]->traverse.nodeStack->next->data->node);
186 } 203 }
187 204
188 __code insertCase4_01(struct Context* context, struct Traverse* traverse) { 205 __code insertCase4_01(struct Context* context, struct Traverse* traverse) {
189 context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next; 206 traverse->nodeStack = traverse->nodeStack -> next;
207 traverse->rotateNext = InsertCase5;
190 goto meta(context, RotateL); 208 goto meta(context, RotateL);
191 } 209 }
192 210
193 __code insert4_01_stub(struct Context* context) { 211 __code insert4_01_stub(struct Context* context) {
194 goto insertCase4_01(context, &context->data[Traverse]->traverse); 212 goto insertCase4_01(context, &context->data[Traverse]->traverse);
206 struct Traverse* traverse = &context->data[Traverse]->traverse; 224 struct Traverse* traverse = &context->data[Traverse]->traverse;
207 element->data = (union Data*)traverse->current; 225 element->data = (union Data*)traverse->current;
208 goto insertCase4_1(context, &context->data[Traverse]->traverse); 226 goto insertCase4_1(context, &context->data[Traverse]->traverse);
209 } 227 }
210 __code insertCase4_02(struct Context* context, struct Traverse* traverse) { 228 __code insertCase4_02(struct Context* context, struct Traverse* traverse) {
211 context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next; 229 traverse->nodeStack = traverse->nodeStack -> next;
230 traverse->rotateNext = InsertCase5;
212 goto meta(context, RotateR); 231 goto meta(context, RotateR);
213 } 232 }
214 233
215 __code insert4_02_stub(struct Context* context) { 234 __code insert4_02_stub(struct Context* context) {
216 goto insertCase4_02(context, &context->data[Traverse]->traverse); 235 goto insertCase4_02(context, &context->data[Traverse]->traverse);
250 traverse->nodeStack = traverse->nodeStack->next->next; 269 traverse->nodeStack = traverse->nodeStack->next->next;
251 goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent); 270 goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent);
252 } 271 }
253 272
254 // put rotateLeft's continuation as argument 273 // put rotateLeft's continuation as argument
255 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Element* element) { 274 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
256 struct Node* tmp = node->right; 275 struct Node* tmp = node->right;
257 276
258 if (parent) { 277 if (parent) {
259 if (node == parent->left) 278 if (node == parent->left)
260 parent->left = tmp; 279 parent->left = tmp;
261 else 280 else
262 parent->right = tmp; 281 parent->right = tmp;
263 } else { 282 } else {
264 tree->root = tmp; 283 tree->root = tmp;
265 } 284 }
266 element->data = (union Data*)parent;
267 285
268 node->right = tmp->left; 286 node->right = tmp->left;
269 tmp->left = node; 287 tmp->left = node;
270 traverse->current = tmp; 288 traverse->current = tmp;
271 289
273 } 291 }
274 292
275 __code rotateLeft_stub(struct Context* context) { 293 __code rotateLeft_stub(struct Context* context) {
276 struct Traverse* traverse = &context->data[Traverse]->traverse; 294 struct Traverse* traverse = &context->data[Traverse]->traverse;
277 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL; 295 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
278 traverse->nodeStack = traverse->nodeStack->next;
279 struct Allocate* allocate = &context->data[Allocate]->allocate;
280 allocate->size = sizeof(struct Element);
281 allocator(context);
282 struct Element* element = &context->data[context->dataNum]->element;
283 goto rotateLeft(context, 296 goto rotateLeft(context,
284 context->data[Traverse]->traverse.current, 297 context->data[Traverse]->traverse.current,
285 &context->data[Tree]->tree, 298 &context->data[Tree]->tree,
286 &context->data[Traverse]->traverse, 299 &context->data[Traverse]->traverse,
287 parent, 300 parent);
288 element); 301 }
289 } 302
290 303 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
291 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Element* element) {
292 struct Node* tmp = node->left; 304 struct Node* tmp = node->left;
293 305
294 if (parent) { 306 if (parent) {
295 if (node == parent->left) 307 if (node == parent->left)
296 parent->left = tmp; 308 parent->left = tmp;
298 parent->right = tmp; 310 parent->right = tmp;
299 } else { 311 } else {
300 tree->root = tmp; 312 tree->root = tmp;
301 } 313 }
302 314
303 element->data = (union Data*)parent;
304
305 node->left = tmp->right; 315 node->left = tmp->right;
306 tmp->right = node; 316 tmp->right = node;
307 traverse->current = tmp; 317 traverse->current = tmp;
308 318
309 goto meta(context, traverse->rotateNext); 319 goto meta(context, traverse->rotateNext);
310 } 320 }
311 321
312 __code rotateRight_stub(struct Context* context) { 322 __code rotateRight_stub(struct Context* context) {
313 struct Traverse* traverse = &context->data[Traverse]->traverse; 323 struct Traverse* traverse = &context->data[Traverse]->traverse;
314 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL; 324 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
315 traverse->nodeStack = traverse->nodeStack->next;
316 struct Allocate* allocate = &context->data[Allocate]->allocate;
317 allocate->size = sizeof(struct Element);
318 allocator(context);
319 struct Element* element = &context->data[context->dataNum]->element;
320 goto rotateRight(context, 325 goto rotateRight(context,
321 context->data[Traverse]->traverse.current, 326 context->data[Traverse]->traverse.current,
322 &context->data[Tree]->tree, 327 &context->data[Tree]->tree,
323 &context->data[Traverse]->traverse, 328 &context->data[Traverse]->traverse,
324 parent, 329 parent);
325 element);
326 } 330 }
327 331
328 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) { 332 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {
329 traverse->current = 0; 333 traverse->current = 0;
330 334