Mercurial > hg > GearsTemplate
annotate src/parallel_execution/RedBlackTree.cbc @ 458:3025d00eb87d
Merge
| author | Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 14 Dec 2017 07:44:58 +0900 |
| parents | a44dbeb08895 |
| children | 5fd0502a6c35 8d7e5d48cad3 |
| rev | line source |
|---|---|
| 273 | 1 #include <stdio.h> |
| 2 | |
| 3 #include "../context.h" | |
| 452 | 4 #include "../compare.c" |
| 445 | 5 |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
6 extern enum Relational compare(struct Node* node1, struct Node* node2); |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
7 |
| 273 | 8 |
| 9 Tree* createRedBlackTree(struct Context* context) { | |
| 10 struct Tree* tree = new Tree(); | |
| 452 | 11 struct RedBlackTree* rbtree = new RedBlackTree(); |
| 445 | 12 |
| 452 | 13 tree->tree = (union Data*)rbtree; |
| 14 rbtree->root = NULL; | |
| 15 rbtree->nodeStack = (union Data*)createSingleLinkedStack(context); | |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
16 tree->put = C_putRedBlackTree; |
| 445 | 17 // tree->get = C_getRedBlackTree; |
| 273 | 18 // tree->remove = C_removeRedBlackTree; |
| 19 // tree->clear = C_clearRedBlackTree; | |
| 452 | 20 return tree; |
| 273 | 21 } |
| 22 | |
| 454 | 23 void printNode(struct Node* node) { |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
24 if (node == NULL) { |
| 454 | 25 printf("leaf"); |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
26 } else { |
| 454 | 27 printf("((%d,%d (",node->color, node->key); |
| 452 | 28 printNode(node->right); |
| 454 | 29 printf(") ("); |
| 452 | 30 printNode(node->left); |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
31 printf(")"); |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
32 } |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
33 } |
| 273 | 34 |
| 452 | 35 void printTree(struct RedBlackTree* tree) { |
| 36 printf("\n"); | |
| 454 | 37 tree->current = tree->root; |
| 38 printNode(tree->current); | |
| 39 printf(")\n"); | |
| 452 | 40 } |
| 41 | |
| 42 __code putRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) { | |
| 454 | 43 printf("C_putRedBlackTree\n"); |
| 44 //struct Node* newNode = &ALLOCATE(context, Node)->Node; | |
| 45 printf("value->%d,key->%d \n",node->value,node->key); | |
| 46 tree->previous = tree->newNode; | |
| 47 tree->newNode = node; | |
| 452 | 48 tree->newNode->color = Red; |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
49 // tree->root = newNode; // this should done at stackClear |
| 452 | 50 // tree->parent = NULL; |
| 51 // if (root) { | |
| 52 tree->current = tree->root; | |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
53 // tree->result = compare(tree->current, node); |
| 454 | 54 goto insertRBTree(node, tree); |
| 452 | 55 // } |
| 56 // printf("error : __code putRedBlackTree \n"); | |
| 57 // goto meta(context, C_exit_code); | |
| 273 | 58 } |
| 59 | |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
60 //__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) { |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
61 // tree->current = 0; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
62 // nodeStack->stack = tree->nodeStack; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
63 // nodeStack->next = next; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
64 // goto meta(context, tree->nodeStack->clear); |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
65 //} |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
66 |
| 445 | 67 // __code getRedBlackTree(struct RedBlackTree* tree, __code next(...)) { |
| 68 // if (tree->root) { | |
| 69 // tree->current = tree->root; | |
| 70 // goto insertRBTree(); | |
| 71 // // goto deleteRBTree(); | |
| 72 // } | |
| 73 // | |
| 74 // goto next(...); | |
| 75 // } | |
| 273 | 76 |
| 454 | 77 __code insertRBTree(struct Node* node, struct RedBlackTree* tree, struct Stack* stack, __code next(...)) { |
| 78 // first case tree->current = root; | |
| 79 printf("C_insertRBTree\n"); | |
| 455 | 80 //stack = tree->nodeStack; |
| 452 | 81 printf("value->%d,key->%d\n",node->value,node->key); |
| 454 | 82 printf("newNode value->%d,newNode key->%d\n",tree->newNode->value,tree->newNode->key); |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
83 |
| 454 | 84 if (tree->root == NULL) { |
| 85 printf("insertRBTree_root eq NULL\n"); | |
| 86 tree->root = tree->newNode; | |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
87 tree->root->color = Black; |
| 454 | 88 printf("tree->root->key = %d, tree->root->color = %d \n",tree->root->key,tree->root->color); |
| 89 printTree(tree); | |
| 90 goto next(tree,...); | |
| 452 | 91 } else { |
| 454 | 92 goto searchInsertLocation(node, tree, stack); |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
93 } |
| 273 | 94 } |
| 95 | |
| 96 | |
| 455 | 97 __code searchInsertLocation(struct Node* node, struct RedBlackTree* tree) { |
| 454 | 98 // first case tree->current = root; PreCase remove root=NULL case.don't exist firstCase tree->current=NULL |
| 99 printf("C_searchInsertLocation\n"); | |
| 100 printf("nownode->key %d , previous->key %d \n",tree->newNode->key,tree->previous->key); | |
| 452 | 101 |
| 454 | 102 tree->result = compare(tree->current, node); |
| 103 printf("tree->current->key = %d, node->key %d\n",tree->current->key,node->key); | |
| 104 printf("compare (%d,%d)\n",tree->current,node); | |
| 455 | 105 struct Stack* stack = tree->nodeStack; |
| 454 | 106 if (tree->current == NULL) { |
| 107 printf("goto insertLocationBackInsert stack->pop"); | |
| 452 | 108 goto stack->pop(insertLocationBackInsert); |
| 454 | 109 } |
| 110 if (tree->result == GT) { | |
| 111 printf("GT searchInsertLocation"); | |
| 452 | 112 tree->current = tree->current->right; |
| 454 | 113 goto stack->push(tree->newNode,insertLocationBackInsert); |
| 114 } else if (tree->result == LT) { | |
| 115 printf("LT searchInsertLocation"); | |
| 452 | 116 tree->current = tree->current->left; |
| 454 | 117 goto stack->push(tree->newNode, searchInsertLocation); |
| 452 | 118 } else if (tree->result == EQ) { |
| 454 | 119 printf("already member this node : __code searchInsertLocation()\n"); |
| 452 | 120 goto meta(context, C_exit_code); |
| 121 } else { | |
| 122 printf("$insert value tree : __code searchInsertLocation() \n"); | |
| 123 goto meta(context, C_exit_code); | |
| 124 } | |
| 125 } | |
| 126 | |
| 454 | 127 __code insertLocationBackInsert(struct RedBlackTree* tree, struct Node* node, struct Stack* stack) { |
| 128 printf("C_insertLocationBackInsert\n"); | |
| 129 struct Node* hoge = stack->data; | |
| 130 printf("stackpopdata%d\n",stack->data); | |
| 131 tree->current = tree->previous; | |
| 452 | 132 // tree->current = nodeStack->data; |
| 133 // this CS is ones only backTrace, and insert node | |
| 454 | 134 tree->result = compare(tree->previous,tree->newNode); |
| 135 printf("back,compare\n"); | |
| 452 | 136 if (tree->result == GT) { |
| 454 | 137 printf("ok\n"); |
| 452 | 138 tree->current->right = tree->newNode; |
| 454 | 139 printTree(tree); |
| 452 | 140 goto insertBalance(); |
| 141 } else if (tree->result == LT) { | |
| 454 | 142 printf("LT\n"); |
| 452 | 143 tree->current->left = tree->newNode; |
| 144 goto insertBalance(); | |
| 145 } else { | |
| 146 printf("error : __code insertLocationBackTrace() \n"); | |
| 147 goto meta(context, C_exit_code); | |
| 445 | 148 } |
| 273 | 149 } |
| 150 | |
| 454 | 151 __code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node, __code next(...)) { |
| 152 printf("C_insertBalance\n"); | |
| 452 | 153 struct Node* traceNode = tree->nodeStack->data; |
| 154 tree->current = traceNode; | |
| 155 struct Stack* stack = tree->nodeStack; | |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
156 |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
157 // exit insertion code |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
158 if (tree->current == tree->root) { |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
159 tree->current->color = Black; |
| 454 | 160 printTree(tree); |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
161 //printTree |
| 454 | 162 goto next(tree,...); |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
163 } |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
164 |
| 452 | 165 |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
166 //current color eq Red |
| 452 | 167 if (tree->current->color == Red) |
| 168 goto stack->pop(insertBalance); | |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
169 |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
170 // current color eq Black |
| 454 | 171 if (tree->current->left->left || tree->current->left->right) { |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
172 goto insertBalanceLeft(tree,nodeStack); |
| 454 | 173 } else if (tree->current->right->left || tree->current->right->right) { |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
174 goto insertBalanceRight(tree,nodeStack); |
| 452 | 175 } else { |
| 176 goto stack->pop(insertBalance); | |
| 445 | 177 } |
| 273 | 178 } |
| 179 | |
| 454 | 180 __code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) { |
| 181 printf("C_insertBalanceLeft\n"); | |
| 452 | 182 struct Stack* stack = tree->nodeStack; |
| 273 | 183 |
| 454 | 184 if (tree->current->color == Black && tree->current->left->color == Red && tree->current->left->left->color == Red) { |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
185 struct Node* tmpCurrent = tree->current; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
186 struct Node* tmpLeft = tree->current->left; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
187 struct Node* tmpLeftLeft = tree->current->left->left; |
| 273 | 188 |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
189 tree->current = tmpLeft; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
190 tree->current->right = tmpCurrent; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
191 tree->current->left = tmpLeftLeft; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
192 tree->current->right->left = tmpLeft->right; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
193 tree->current->color = Red; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
194 tree->current->left->color = Black; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
195 tree->current->right->color = Black; |
| 452 | 196 goto stack->pop(insertBalance); |
| 273 | 197 |
| 454 | 198 } else if(tree->current->color == Black && tree->current->left->color == Red && tree->current->left->right->color == Red) { |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
199 struct Node* tmpCurrent = tree->current; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
200 struct Node* tmpLeft = tree->current->left; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
201 struct Node* tmpLeftRight = tree->current->left->right; |
| 273 | 202 |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
203 tree->current = tmpLeft; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
204 tree->current->right = tmpCurrent; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
205 tree->current->left = tmpLeftRight; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
206 tree->current->right->left = tmpLeft->left; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
207 tree->current->color = Red; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
208 tree->current->left->color = Black; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
209 tree->current->right->color = Black; |
| 452 | 210 goto stack->pop(insertBalance); |
| 273 | 211 |
| 445 | 212 } |
| 213 } | |
| 273 | 214 |
| 454 | 215 __code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) { |
| 216 printf("C_insertBalanceLeft\n"); | |
| 452 | 217 struct Stack* stack = tree->nodeStack; |
| 218 | |
| 454 | 219 if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->right->color == Red) { |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
220 struct Node* tmpCurrent = tree->current; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
221 struct Node* tmpRight = tree->current->right; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
222 struct Node* tmpRightRight = tree->current->right->right; |
| 273 | 223 |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
224 tree->current = tmpRight; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
225 tree->current->left = tmpCurrent; |
| 452 | 226 tree->current->right = tmpRightRight; |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
227 tree->current->left->right = tmpRight->left; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
228 tree->current->color = Red; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
229 tree->current->left->color = Black; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
230 tree->current->right->color = Black; |
| 452 | 231 goto stack->pop(insertBalance); |
| 273 | 232 |
| 454 | 233 } else if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->left->color == Red) { |
| 273 | 234 |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
235 struct Node* tmpCurrent = tree->current; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
236 struct Node* tmpRight = tree->current->right; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
237 struct Node* tmpRightLeft = tree->current->right->left; |
| 273 | 238 |
|
446
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
239 tree->current = tmpRight; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
240 tree->current->right = tmpCurrent; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
241 tree->current->left = tmpRightLeft; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
242 tree->current->left->right = tmpRight->right; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
243 tree->current->color = Red; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
244 tree->current->left->color = Black; |
|
41a6f8482374
fix RedBlackTree.cbc Insert, printTree. but occur error
ryokka
parents:
445
diff
changeset
|
245 tree->current->right->color = Black; |
| 452 | 246 goto stack->pop(insertBalance); |
| 273 | 247 |
| 445 | 248 } else { |
| 452 | 249 printf("unkwon error : __code insertBalanceRight() \n"); |
| 250 goto meta(context, C_exit_code); | |
| 445 | 251 } |
| 252 } | |
| 452 | 253 // insertCode end |