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