Mercurial > hg > Members > Moririn

comparison src/parallel_execution/rb_tree.c @ 172:661b0b0d0399

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
replace Tree to RedBlackTree
author ikkun
date Thu, 24 Nov 2016 20:22:17 +0900
parents 73c393f0dca3
children 8260b230dc2f
comparison
equal deleted inserted replaced
171:747067fe46bd 172:661b0b0d0399
33 void printTree(union Data* data) { 33 void printTree(union Data* data) {
34 printTree1(data); 34 printTree1(data);
35 printf("\n"); 35 printf("\n");
36 } 36 }
37 37
38 __code putRedBlackTree(struct Context* context, struct Stack* nodeStack, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) { 38 __code putRedBlackTree(struct Context* context, struct Stack* nodeStack, struct RedBlackTree* traverse, struct Node* node, struct Node* root, struct Node* newNode) {
39 printTree((union Data*)(tree->root)); 39 printTree((union Data*)(traverse->root));
40 traverse->newNode = newNode; 40 traverse->newNode = newNode;
41 tree->root = newNode; // this should done at stackClear 41 traverse->root = newNode; // this should done at stackClear
42 traverse->parent = NULL; 42 traverse->parent = NULL;
43 if (root) { 43 if (root) {
44 traverse->current = root; 44 traverse->current = root;
45 traverse->result = compare(traverse->current, node); 45 traverse->result = compare(traverse->current, node);
46 goto meta(context, C_replaceNode); 46 goto meta(context, C_replaceNode);
49 goto meta(context, C_insertNode); 49 goto meta(context, C_insertNode);
50 } 50 }
51 51
52 __code putRedBlackTree_stub(struct Context* context) { 52 __code putRedBlackTree_stub(struct Context* context) {
53 struct Node* newNode = &ALLOCATE(context, Node)->node; 53 struct Node* newNode = &ALLOCATE(context, Node)->node;
54 goto put(context, 54 goto putRedBlackTree(context,
55 &context->data[D_Stack]->stack, 55 &context->data[D_Stack]->stack,
56 &context->data[D_Tree]->tree, 56 &context->data[D_RedBlackTree]->RedBlackTree,
57 &context->data[D_Node]->node, 57 &context->data[D_Node]->node,
58 &context->data[D_Traverse]->Traverse, 58 context->data[D_RedBlackTree]->RedBlackTree.root,
59 context->data[D_Tree]->tree.root,
60 newNode 59 newNode
61 ); 60 );
62 } 61 }
63 62
64 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) { 63 __code replaceNode(struct Context* context, struct RedBlackTree* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) {
65 traverse->previous = newNode; 64 traverse->previous = newNode;
66 *newNode = *oldNode; 65 *newNode = *oldNode;
67 nodeStack->stack = (union Data*)traverse->nodeStack; 66 nodeStack->stack = (union Data*)traverse->nodeStack;
68 nodeStack->data = (union Data*)(newNode); 67 nodeStack->data = (union Data*)(newNode);
69 nodeStack->next = C_replaceNode1; 68 nodeStack->next = C_replaceNode1;
70 goto meta(context, traverse->nodeStack->push); 69 goto meta(context, traverse->nodeStack->push);
71 } 70 }
72 71
73 __code replaceNode_stub(struct Context* context) { 72 __code replaceNode_stub(struct Context* context) {
74 goto replaceNode(context, 73 goto replaceNode(context,
75 &context->data[D_Traverse]->Traverse, 74 &context->data[D_RedBlackTree]->RedBlackTree,
76 context->data[D_Traverse]->Traverse.current, 75 context->data[D_RedBlackTree]->RedBlackTree.current,
77 //context->data[D_Traverse]->Traverse.newNode, 76 //context->data[D_RedBlackTree]->RedBlackTree.newNode,
78 Gearef(context, Traverse)->newNode, 77 Gearef(context, RedBlackTree)->newNode,
79 &context->data[D_Stack]->stack); 78 &context->data[D_Stack]->stack);
80 } 79 }
81 80
82 __code replaceNode1(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) { 81 __code replaceNode1(struct Context* context, struct RedBlackTree* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) {
83 if (result == EQ) { 82 if (result == EQ) {
84 newNode->value = node->value; 83 newNode->value = node->value;
85 // go to stack clear 84 // go to stack clear
86 goto meta(context, context->next); 85 goto meta(context, context->next);
87 } else if (result == GT) { 86 } else if (result == GT) {
101 } 100 }
102 101
103 __code replaceNode1_stub(struct Context* context) { 102 __code replaceNode1_stub(struct Context* context) {
104 struct Node* newnewNode = &ALLOCATE(context, Node)->node; 103 struct Node* newnewNode = &ALLOCATE(context, Node)->node;
105 goto replaceNode1(context, 104 goto replaceNode1(context,
106 &context->data[D_Traverse]->Traverse, 105 &context->data[D_RedBlackTree]->RedBlackTree,
107 &context->data[D_Node]->node, 106 &context->data[D_Node]->node,
108 context->data[D_Traverse]->Traverse.current, 107 context->data[D_RedBlackTree]->RedBlackTree.current,
109 context->data[D_Traverse]->Traverse.previous, 108 context->data[D_RedBlackTree]->RedBlackTree.previous,
110 newnewNode, 109 newnewNode,
111 context->data[D_Traverse]->Traverse.result); 110 context->data[D_RedBlackTree]->RedBlackTree.result);
112 } 111 }
113 112
114 __code insertNode(struct Context* context, struct Traverse* traverse, struct Stack *nodeStack, struct Node* node, struct Node* newNode) { 113 __code insertNode(struct Context* context, struct RedBlackTree* traverse, struct Stack *nodeStack, struct Node* node, struct Node* newNode) {
115 *newNode = *node; 114 *newNode = *node;
116 newNode->color = Red; 115 newNode->color = Red;
117 traverse->current = newNode; 116 traverse->current = newNode;
118 nodeStack->stack = (union Data*)traverse->nodeStack; 117 nodeStack->stack = (union Data*)traverse->nodeStack;
119 nodeStack->next = C_insertCase1; 118 nodeStack->next = C_insertCase1;
120 goto meta(context, traverse->nodeStack->get2); 119 goto meta(context, traverse->nodeStack->get2);
121 } 120 }
122 121
123 __code insertNode_stub(struct Context* context) { 122 __code insertNode_stub(struct Context* context) {
124 goto insertNode(context, 123 goto insertNode(context,
125 &context->data[D_Traverse]->Traverse, 124 &context->data[D_RedBlackTree]->RedBlackTree,
126 &context->data[D_Stack]->stack, 125 &context->data[D_Stack]->stack,
127 &context->data[D_Node]->node, 126 &context->data[D_Node]->node,
128 context->data[D_Traverse]->Traverse.newNode); 127 context->data[D_RedBlackTree]->RedBlackTree.newNode);
129 } 128 }
130 129
131 __code insertCase1(struct Context* context,struct Traverse* traverse, struct Tree* tree,struct Node *parent, struct Node *grandparent) { 130 __code insertCase1(struct Context* context,struct RedBlackTree* traverse, struct RedBlackTree* tree,struct Node *parent, struct Node *grandparent) {
132 if (parent != NULL) { 131 if (parent != NULL) {
133 traverse->parent = parent; 132 traverse->parent = parent;
134 traverse->grandparent = grandparent; 133 traverse->grandparent = grandparent;
135 goto meta(context,C_insertCase2); 134 goto meta(context,C_insertCase2);
136 } 135 }
138 goto meta(context, C_stackClear); 137 goto meta(context, C_stackClear);
139 } 138 }
140 139
141 __code insertCase1_stub(struct Context* context) { 140 __code insertCase1_stub(struct Context* context) {
142 goto insertCase1(context, 141 goto insertCase1(context,
143 &context->data[D_Traverse]->Traverse, 142 &context->data[D_RedBlackTree]->RedBlackTree,
144 &context->data[D_Tree]->tree, 143 &context->data[D_Tree]->Tree,
145 &context->data[D_Stack]->stack.data->node, 144 &context->data[D_Stack]->stack.data->node,
146 &context->data[D_Stack]->stack.data1->node); 145 &context->data[D_Stack]->stack.data1->node);
147 } 146 }
148 147
149 __code insertCase2(struct Context* context, struct Traverse* traverse) { 148 __code insertCase2(struct Context* context, struct RedBlackTree* traverse) {
150 if (traverse->parent->color == Black) { 149 if (traverse->parent->color == Black) {
151 goto meta(context, C_stackClear); 150 goto meta(context, C_stackClear);
152 } 151 }
153 goto meta(context,C_insertCase3); 152 goto meta(context,C_insertCase3);
154 } 153 }
155 154
156 __code insertCase2_stub(struct Context* context) { 155 __code insertCase2_stub(struct Context* context) {
157 goto insertCase2(context, &context->data[D_Traverse]->Traverse); 156 goto insertCase2(context, &context->data[D_RedBlackTree]->RedBlackTree);
158 } 157 }
159 158
160 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack) { 159 __code insertCase3(struct Context* context, struct RedBlackTree* traverse, struct Stack* nodeStack) {
161 struct Node* uncle; 160 struct Node* uncle;
162 161
163 if (traverse->grandparent->left == traverse->parent) 162 if (traverse->grandparent->left == traverse->parent)
164 uncle = traverse->grandparent->right; 163 uncle = traverse->grandparent->right;
165 else 164 else
177 } 176 }
178 goto meta(context, C_insertCase4); 177 goto meta(context, C_insertCase4);
179 } 178 }
180 179
181 __code insertCase3_stub(struct Context* context) { 180 __code insertCase3_stub(struct Context* context) {
182 goto insertCase3(context, &context->data[D_Traverse]->Traverse, 181 goto insertCase3(context, &context->data[D_RedBlackTree]->RedBlackTree,
183 &context->data[D_Stack]->stack 182 &context->data[D_Stack]->stack
184 ); 183 );
185 } 184 }
186 185
187 __code insertCase4(struct Context* context, struct Traverse* traverse, struct RotateTree* rotateTree) { 186 __code insertCase4(struct Context* context, struct RedBlackTree* traverse, struct RotateTree* rotateTree) {
188 struct Stack* nodeStack = traverse->nodeStack; 187 struct Stack* nodeStack = traverse->nodeStack;
189 188
190 if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) { 189 if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) {
191 traverse->current = traverse->current->left; 190 traverse->current = traverse->current->left;
192 traverse->parent = traverse->grandparent; 191 traverse->parent = traverse->grandparent;
211 210
212 goto meta(context, C_insertCase5); 211 goto meta(context, C_insertCase5);
213 } 212 }
214 213
215 __code insertCase4_stub(struct Context* context) { 214 __code insertCase4_stub(struct Context* context) {
216 goto insertCase4(context, &context->data[D_Traverse]->Traverse, &context->data[D_RotateTree]->rotateTree); 215 goto insertCase4(context, &context->data[D_RedBlackTree]->RedBlackTree, &context->data[D_RotateTree]->rotateTree);
217 } 216 }
218 217
219 __code insertCase5(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) { 218 __code insertCase5(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack) {
220 nodeStack->stack = (union Data*)traverse->nodeStack; 219 nodeStack->stack = (union Data*)traverse->nodeStack;
221 nodeStack->next = C_insertCase51; 220 nodeStack->next = C_insertCase51;
222 goto meta(context, traverse->nodeStack->pop2); 221 goto meta(context, traverse->nodeStack->pop2);
223 } 222 }
224 223
225 __code insertCase5_stub(struct Context* context) { 224 __code insertCase5_stub(struct Context* context) {
226 goto insertCase5(context, &context->data[D_Traverse]->Traverse, &context->data[D_Stack]->stack); 225 goto insertCase5(context, &context->data[D_RedBlackTree]->RedBlackTree, &context->data[D_Stack]->stack);
227 } 226 }
228 227
229 __code insertCase51(struct Context* context, struct Traverse* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) { 228 __code insertCase51(struct Context* context, struct RedBlackTree* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) {
230 traverse->parent = parent; 229 traverse->parent = parent;
231 traverse->grandparent = grandparent; 230 traverse->grandparent = grandparent;
232 231
233 parent->color = Black; 232 parent->color = Black;
234 grandparent->color = Red; 233 grandparent->color = Red;
245 } 244 }
246 245
247 __code insertCase51_stub(struct Context* context) { 246 __code insertCase51_stub(struct Context* context) {
248 struct Node* parent = &context->data[D_Stack]->stack.data->node; 247 struct Node* parent = &context->data[D_Stack]->stack.data->node;
249 struct Node* grandparent = &context->data[D_Stack]->stack.data1->node; 248 struct Node* grandparent = &context->data[D_Stack]->stack.data1->node;
250 goto insertCase51(context, &context->data[D_Traverse]->Traverse,&context->data[D_RotateTree]->rotateTree, context->data[D_Traverse]->Traverse.current, parent, grandparent); 249 goto insertCase51(context, &context->data[D_RedBlackTree]->RedBlackTree,&context->data[D_RotateTree]->rotateTree, context->data[D_RedBlackTree]->RedBlackTree.current, parent, grandparent);
251 } 250 }
252 251
253 __code rotateLeft(struct Context* context, struct Traverse* traverse,struct Stack* nodeStack) { 252 __code rotateLeft(struct Context* context, struct RedBlackTree* traverse,struct Stack* nodeStack) {
254 nodeStack->stack = (union Data*)traverse->nodeStack; 253 nodeStack->stack = (union Data*)traverse->nodeStack;
255 nodeStack->next = C_rotateLeft1; 254 nodeStack->next = C_rotateLeft1;
256 goto meta(context, traverse->nodeStack->get); 255 goto meta(context, traverse->nodeStack->get);
257 } 256 }
258 257
259 __code rotateLeft_stub(struct Context* context) { 258 __code rotateLeft_stub(struct Context* context) {
260 struct Traverse* traverse = context->data[D_RotateTree]->rotateTree.traverse; 259 struct RedBlackTree* traverse = context->data[D_RotateTree]->rotateTree.traverse;
261 goto rotateLeft(context, traverse, &context->data[D_Stack]->stack); 260 goto rotateLeft(context, traverse, &context->data[D_Stack]->stack);
262 } 261 }
263 262
264 __code rotateLeft1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node *parent,struct RotateTree *rotateTree) { 263 __code rotateLeft1(struct Context* context, struct Node* node, struct RedBlackTree* traverse, struct Node *parent,struct RotateTree *rotateTree) {
265 struct Node* tmp = node->right; 264 struct Node* tmp = node->right;
266 265
267 if (parent) { 266 if (parent) {
268 if (node == parent->left) 267 if (node == parent->left)
269 parent->left = tmp; 268 parent->left = tmp;
270 else 269 else
271 parent->right = tmp; 270 parent->right = tmp;
272 } else { 271 } else {
273 tree->root = tmp; 272 traverse->root = tmp;
274 } 273 }
275 274
276 node->right = tmp->left; 275 node->right = tmp->left;
277 tmp->left = node; 276 tmp->left = node;
278 traverse->current = tmp; 277 traverse->current = tmp;
279 278
280 goto meta(context, rotateTree->next); 279 goto meta(context, rotateTree->next);
281 } 280 }
282 281
283 __code rotateLeft1_stub(struct Context* context) { 282 __code rotateLeft1_stub(struct Context* context) {
284 struct Traverse* traverse = context->data[D_RotateTree]->rotateTree.traverse; 283 struct RedBlackTree* traverse = context->data[D_RotateTree]->rotateTree.traverse;
285 struct Node* parent = &context->data[D_Stack]->stack.data->node; 284 struct Node* parent = &context->data[D_Stack]->stack.data->node;
286 goto rotateLeft1(context, 285 goto rotateLeft1(context,
287 traverse->current, 286 traverse->current,
288 &context->data[D_Tree]->tree, 287 &context->data[D_Tree]->Tree,
289 traverse, 288 traverse,
290 parent, 289 parent,
291 &context->data[D_RotateTree]->rotateTree); 290 &context->data[D_RotateTree]->rotateTree);
292 } 291 }
293 292
294 __code rotateRight(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) { 293 __code rotateRight(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack) {
295 nodeStack->stack = (union Data*)traverse->nodeStack; 294 nodeStack->stack = (union Data*)traverse->nodeStack;
296 nodeStack->next = C_rotateRight1; 295 nodeStack->next = C_rotateRight1;
297 goto meta(context, traverse->nodeStack->get); 296 goto meta(context, traverse->nodeStack->get);
298 } 297 }
299 298
300 __code rotateRight_stub(struct Context* context) { 299 __code rotateRight_stub(struct Context* context) {
301 struct Traverse* traverse = context->data[D_RotateTree]->rotateTree.traverse; 300 struct RedBlackTree* traverse = context->data[D_RotateTree]->rotateTree.traverse;
302 goto rotateLeft(context, traverse, &context->data[D_Stack]->stack); 301 goto rotateLeft(context, traverse, &context->data[D_Stack]->stack);
303 } 302 }
304 303
305 __code rotateRight1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse,struct Node *parent,struct RotateTree *rotateTree) { 304 __code rotateRight1(struct Context* context, struct Node* node, struct RedBlackTree* traverse,struct Node *parent,struct RotateTree *rotateTree) {
306 struct Node* tmp = node->left; 305 struct Node* tmp = node->left;
307 306
308 if (parent) { 307 if (parent) {
309 if (node == parent->left) 308 if (node == parent->left)
310 parent->left = tmp; 309 parent->left = tmp;
311 else 310 else
312 parent->right = tmp; 311 parent->right = tmp;
313 } else { 312 } else {
314 tree->root = tmp; 313 traverse->root = tmp;
315 } 314 }
316 315
317 node->left = tmp->right; 316 node->left = tmp->right;
318 tmp->right = node; 317 tmp->right = node;
319 traverse->current = tmp; 318 traverse->current = tmp;
320 319
321 goto meta(context, rotateTree->next); 320 goto meta(context, rotateTree->next);
322 } 321 }
323 322
324 __code rotateRight1_stub(struct Context* context) { 323 __code rotateRight1_stub(struct Context* context) {
325 struct Traverse* traverse = context->data[D_RotateTree]->rotateTree.traverse; 324 struct RedBlackTree* traverse = context->data[D_RotateTree]->rotateTree.traverse;
326 struct Node* parent = &context->data[D_Stack]->stack.data->node; 325 struct Node* parent = &context->data[D_Stack]->stack.data->node;
327 goto rotateRight1(context, 326 goto rotateRight1(context,
328 traverse->current, 327 traverse->current,
329 &context->data[D_Tree]->tree, 328 &context->data[D_Tree]->Tree,
330 traverse, 329 traverse,
331 parent, 330 parent,
332 &context->data[D_RotateTree]->rotateTree); 331 &context->data[D_RotateTree]->rotateTree);
333 } 332 }
334 333
335 __code stackClear(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) { 334 __code stackClear(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack) {
336 traverse->current = 0; 335 traverse->current = 0;
337 nodeStack->stack = (union Data*)traverse->nodeStack; 336 nodeStack->stack = (union Data*)traverse->nodeStack;
338 nodeStack->next = context->next; 337 nodeStack->next = context->next;
339 goto meta(context, traverse->nodeStack->clear); 338 goto meta(context, traverse->nodeStack->clear);
340 } 339 }
341 340
342 __code stackClear_stub(struct Context* context) { 341 __code stackClear_stub(struct Context* context) {
343 goto stackClear(context, &context->data[D_Traverse]->Traverse,&context->data[D_Stack]->stack); 342 goto stackClear(context, &context->data[D_RedBlackTree]->RedBlackTree,&context->data[D_Stack]->stack);
344 } 343 }
345 344
346 345
347 __code getRedBlackTree(struct Context* context, struct Tree* tree, struct Traverse* traverse) { 346 __code getRedBlackTree(struct Context* context, struct RedBlackTree* traverse) {
348 if (tree->root) { 347 if (tree->root) {
349 traverse->current = tree->root; 348 traverse->current = tree->root;
350 349
351 goto meta(context, C_search); 350 goto meta(context, C_search);
352 } 351 }
353 352
354 goto meta(context, traverse->next); 353 goto meta(context, traverse->next);
355 } 354 }
356 355
357 __code getRedBlackTree_stub(struct Context* context) { 356 __code getRedBlackTree_stub(struct Context* context) {
358 goto get(context, &context->data[D_Tree]->tree, &context->data[D_Traverse]->Traverse); 357 goto get(context, &context->data[D_Tree]->tree, &context->data[D_RedBlackTree]->RedBlackTree);
359 } 358 }
360 359
361 __code search(struct Context* context, struct Traverse* traverse, struct Node* node) { 360 __code search(struct Context* context, struct RedBlackTree* traverse, struct Node* node) {
362 // compare(context, traverse, traverse->current->key, node->key); 361 // compare(context, traverse, traverse->current->key, node->key);
363 traverse->result = compare(traverse->current, node); 362 traverse->result = compare(traverse->current, node);
364 if (traverse->result == EQ) { 363 if (traverse->result == EQ) {
365 *node = *traverse->current; 364 *node = *traverse->current;
366 365
376 375
377 goto meta(context, traverse->next); 376 goto meta(context, traverse->next);
378 } 377 }
379 378
380 __code search_stub(struct Context* context) { 379 __code search_stub(struct Context* context) {
381 goto search(context, &context->data[D_Traverse]->Traverse, &context->data[D_Node]->node); 380 goto search(context, &context->data[D_RedBlackTree]->RedBlackTree, &context->data[D_Node]->node);
382 } 381 }
383 382
384 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */ 383 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
385 /* /\* if (tree->root) { *\/ */ 384 /* /\* if (tree->root) { *\/ */
386 /* /\* stack_push(context->code_stack, &context->next); *\/ */ 385 /* /\* stack_push(context->code_stack, &context->next); *\/ */