Mercurial > hg > GearsTemplate

comparison src/parallel_execution/RedBlackTree.cbc @ 458:3025d00eb87d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
457:2b36a1878c6f 458:3025d00eb87d
1 #include <stdio.h> 1 #include <stdio.h>
2 2
3 #include "../context.h" 3 #include "../context.h"
4 4 #include "../compare.c"
5 // extern enum Relational compare(struct Node* node1, struct Node* node2);
6 5
7 extern enum Relational compare(struct Node* node1, struct Node* node2); 6 extern enum Relational compare(struct Node* node1, struct Node* node2);
8 7
9 8
10 Tree* createRedBlackTree(struct Context* context) { 9 Tree* createRedBlackTree(struct Context* context) {
11 struct Tree* tree = new Tree(); 10 struct Tree* tree = new Tree();
12 struct RedBlackTree* redBlackTree = new RedBlackTree(); 11 struct RedBlackTree* rbtree = new RedBlackTree();
13 tree->tree = (union Data*)redBlackTree; 12
14 redBlackTree->root = NULL; 13 tree->tree = (union Data*)rbtree;
15 redBlackTree->nodeStack = (union Data*)createSingleLinkedStack(context); 14 rbtree->root = NULL;
16 15 rbtree->nodeStack = (union Data*)createSingleLinkedStack(context);
17 tree->put = C_putRedBlackTree; 16 tree->put = C_putRedBlackTree;
18 // tree->get = C_getRedBlackTree; 17 // tree->get = C_getRedBlackTree;
19 // tree->remove = C_removeRedBlackTree; 18 // tree->remove = C_removeRedBlackTree;
20 // tree->clear = C_clearRedBlackTree; 19 // tree->clear = C_clearRedBlackTree;
21 return tree; 20 return tree;
22 } 21 }
23 22
24 __code printTree(struct RedBlackTree* tree) { 23 void printNode(struct Node* node) {
25 printTree1(tree);
26 printf("\n");
27 }
28
29 __code printTree1(struct RedBlackTree* tree) {
30 struct Node* node = tree->current;
31 if (node == NULL) { 24 if (node == NULL) {
32 printf("Leaf"); 25 printf("leaf");
33 } else { 26 } else {
34 printf("key = %d (", node->key); 27 printf("((%d,%d (",node->color, node->key);
35 printTree1(node->right); 28 printNode(node->right);
36 printf("), ("); 29 printf(") (");
37 printTree1(node->left); 30 printNode(node->left);
38 printf(")"); 31 printf(")");
39 } 32 }
40 } 33 }
41 34
42 __code putRedBlackTree(struct Node* node, struct RedBlackTree* tree) { 35 void printTree(struct RedBlackTree* tree) {
43 struct Node* newNode = &ALLOCATE(context, Node)->Node; 36 printf("\n");
44 struct Node* root = tree->root; 37 tree->current = tree->root;
45 printTree((tree->root)); 38 printNode(tree->current);
46 tree->newNode = newNode; 39 printf(")\n");
40 }
41
42 __code putRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
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;
48 tree->newNode->color = Red;
47 // tree->root = newNode; // this should done at stackClear 49 // tree->root = newNode; // this should done at stackClear
48 tree->parent = NULL; 50 // tree->parent = NULL;
49 if (root) { 51 // if (root) {
50 tree->current = root; 52 tree->current = tree->root;
51 // tree->result = compare(tree->current, node); 53 // tree->result = compare(tree->current, node);
52 goto insertRBTree(newNode, tree); 54 goto insertRBTree(node, tree);
53 } 55 // }
54 print("error : __code putRedBlackTree"); 56 // printf("error : __code putRedBlackTree \n");
55 goto next(...); 57 // goto meta(context, C_exit_code);
56 } 58 }
57 59
58 //__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) { 60 //__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
59 // tree->current = 0; 61 // tree->current = 0;
60 // nodeStack->stack = tree->nodeStack; 62 // nodeStack->stack = tree->nodeStack;
70 // } 72 // }
71 // 73 //
72 // goto next(...); 74 // goto next(...);
73 // } 75 // }
74 76
75 __code insertRBTree(struct Node* node, struct RedBlackTree* tree) { 77 __code insertRBTree(struct Node* node, struct RedBlackTree* tree, struct Stack* stack, __code next(...)) {
76 tree->current = node; 78 // first case tree->current = root;
77 struct Stack* nodeStack = tree->nodeStack; 79 printf("C_insertRBTree\n");
78 80 //stack = tree->nodeStack;
79 if (tree->root == null){ 81 printf("value->%d,key->%d\n",node->value,node->key);
80 tree->root = tree->current; 82 printf("newNode value->%d,newNode key->%d\n",tree->newNode->value,tree->newNode->key);
83
84 if (tree->root == NULL) {
85 printf("insertRBTree_root eq NULL\n");
86 tree->root = tree->newNode;
81 tree->root->color = Black; 87 tree->root->color = Black;
82 goto next(...); 88 printf("tree->root->key = %d, tree->root->color = %d \n",tree->root->key,tree->root->color);
83 }else{ 89 printTree(tree);
84 goto searchInsertLocatetion(newNode, nodeStack, tree); 90 goto next(tree,...);
85 } 91 } else {
86 92 goto searchInsertLocation(node, tree, stack);
87 } 93 }
88 94 }
89 95
90 __code searchInsertLocation(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { 96
91 struct Stack* nodeStack = tree->nodeStack; 97 __code searchInsertLocation(struct Node* node, struct RedBlackTree* tree) {
92 struct Node* trace = tree->current; 98 // first case tree->current = root; PreCase remove root=NULL case.don't exist firstCase tree->current=NULL
93 99 printf("C_searchInsertLocation\n");
94 100 printf("nownode->key %d , previous->key %d \n",tree->newNode->key,tree->previous->key);
95 101
96 // i think faster "compare tree->current, node" than "switch case EQ, LT, RT" 102 tree->result = compare(tree->current, node);
97 if (tree->current > node || tree->current < node) { 103 printf("tree->current->key = %d, node->key %d\n",tree->current->key,node->key);
98 goto nodestack->push(nodeStack,trace, searchInsertLocation); 104 printf("compare (%d,%d)\n",tree->current,node);
99 } else if (tree->current == node) { 105 struct Stack* stack = tree->nodeStack;
100 printf("alady member this node : __code searchInsertLocation()"); 106 if (tree->current == NULL) {
101 goto next(...); 107 printf("goto insertLocationBackInsert stack->pop");
102 } else if (tree->current == null){ 108 goto stack->pop(insertLocationBackInsert);
103 tree->current = node; 109 }
104 goto nodeStack->pop(nodeStack,insertBalance); 110 if (tree->result == GT) {
105 }else{ 111 printf("GT searchInsertLocation");
106 printf("$insert value tree : __code searchInsertLocation()"); 112 tree->current = tree->current->right;
107 goto next(...); 113 goto stack->push(tree->newNode,insertLocationBackInsert);
108 } 114 } else if (tree->result == LT) {
109 } 115 printf("LT searchInsertLocation");
110 116 tree->current = tree->current->left;
111 __code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ 117 goto stack->push(tree->newNode, searchInsertLocation);
112 tree->current = nodeStack->data; 118 } else if (tree->result == EQ) {
119 printf("already member this node : __code searchInsertLocation()\n");
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
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;
132 // tree->current = nodeStack->data;
133 // this CS is ones only backTrace, and insert node
134 tree->result = compare(tree->previous,tree->newNode);
135 printf("back,compare\n");
136 if (tree->result == GT) {
137 printf("ok\n");
138 tree->current->right = tree->newNode;
139 printTree(tree);
140 goto insertBalance();
141 } else if (tree->result == LT) {
142 printf("LT\n");
143 tree->current->left = tree->newNode;
144 goto insertBalance();
145 } else {
146 printf("error : __code insertLocationBackTrace() \n");
147 goto meta(context, C_exit_code);
148 }
149 }
150
151 __code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node, __code next(...)) {
152 printf("C_insertBalance\n");
153 struct Node* traceNode = tree->nodeStack->data;
154 tree->current = traceNode;
155 struct Stack* stack = tree->nodeStack;
113 156
114 // exit insertion code 157 // exit insertion code
115 if (tree->current == tree->root) { 158 if (tree->current == tree->root) {
116 tree->current->color = Black; 159 tree->current->color = Black;
117 printTree(((union Data* ) (tree->root))); 160 printTree(tree);
118 //printTree 161 //printTree
119 goto next(...); 162 goto next(tree,...);
120 } 163 }
164
121 165
122 //current color eq Red 166 //current color eq Red
123 if (current->color == Red) 167 if (tree->current->color == Red)
124 goto nodeStack->pop(nodeStack, trace, insertBalance); 168 goto stack->pop(insertBalance);
125 169
126 // current color eq Black 170 // current color eq Black
127 if (current->left->left || current->left->right){ 171 if (tree->current->left->left || tree->current->left->right) {
128 goto insertBalanceLeft(tree,nodeStack); 172 goto insertBalanceLeft(tree,nodeStack);
129 }else if (current->right->left || current->right->right){ 173 } else if (tree->current->right->left || tree->current->right->right) {
130 goto insertBalanceRight(tree,nodeStack); 174 goto insertBalanceRight(tree,nodeStack);
131 }else{ 175 } else {
132 goto nodeStack->pop(nodeStack,insertBalance); 176 goto stack->pop(insertBalance);
133 } 177 }
134 } 178 }
135 179
136 __code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ 180 __code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) {
137 181 printf("C_insertBalanceLeft\n");
138 if (current->color == Black && current->left->color == Red && current->left->left->color == Red){ 182 struct Stack* stack = tree->nodeStack;
183
184 if (tree->current->color == Black && tree->current->left->color == Red && tree->current->left->left->color == Red) {
139 struct Node* tmpCurrent = tree->current; 185 struct Node* tmpCurrent = tree->current;
140 struct Node* tmpLeft = tree->current->left; 186 struct Node* tmpLeft = tree->current->left;
141 struct Node* tmpLeftLeft = tree->current->left->left; 187 struct Node* tmpLeftLeft = tree->current->left->left;
142 188
143 tree->current = tmpLeft; 189 tree->current = tmpLeft;
145 tree->current->left = tmpLeftLeft; 191 tree->current->left = tmpLeftLeft;
146 tree->current->right->left = tmpLeft->right; 192 tree->current->right->left = tmpLeft->right;
147 tree->current->color = Red; 193 tree->current->color = Red;
148 tree->current->left->color = Black; 194 tree->current->left->color = Black;
149 tree->current->right->color = Black; 195 tree->current->right->color = Black;
150 goto nodeStack->pop(nodeStack,insertBalance); 196 goto stack->pop(insertBalance);
151 197
152 } else if(current->color == Black && current->left->color == Red && current->left->right->color == Red){ 198 } else if(tree->current->color == Black && tree->current->left->color == Red && tree->current->left->right->color == Red) {
153 struct Node* tmpCurrent = tree->current; 199 struct Node* tmpCurrent = tree->current;
154 struct Node* tmpLeft = tree->current->left; 200 struct Node* tmpLeft = tree->current->left;
155 struct Node* tmpLeftRight = tree->current->left->right; 201 struct Node* tmpLeftRight = tree->current->left->right;
156 202
157 tree->current = tmpLeft; 203 tree->current = tmpLeft;
159 tree->current->left = tmpLeftRight; 205 tree->current->left = tmpLeftRight;
160 tree->current->right->left = tmpLeft->left; 206 tree->current->right->left = tmpLeft->left;
161 tree->current->color = Red; 207 tree->current->color = Red;
162 tree->current->left->color = Black; 208 tree->current->left->color = Black;
163 tree->current->right->color = Black; 209 tree->current->right->color = Black;
164 goto nodeStack->pop(nodeStack,insertBalance); 210 goto stack->pop(insertBalance);
165 211
166 } 212 }
167 } 213 }
168 214
169 __code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ 215 __code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) {
170 if (current->color == Black && current->right->color == Red && current->right->right->color == Red){ 216 printf("C_insertBalanceLeft\n");
217 struct Stack* stack = tree->nodeStack;
218
219 if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->right->color == Red) {
171 struct Node* tmpCurrent = tree->current; 220 struct Node* tmpCurrent = tree->current;
172 struct Node* tmpRight = tree->current->right; 221 struct Node* tmpRight = tree->current->right;
173 struct Node* tmpRightRight = tree->current->right->right; 222 struct Node* tmpRightRight = tree->current->right->right;
174 223
175 tree->current = tmpRight; 224 tree->current = tmpRight;
176 tree->current->left = tmpCurrent; 225 tree->current->left = tmpCurrent;
177 tree->current->Right = tmpRightRight; 226 tree->current->right = tmpRightRight;
178 tree->current->left->right = tmpRight->left; 227 tree->current->left->right = tmpRight->left;
179 tree->current->color = Red; 228 tree->current->color = Red;
180 tree->current->left->color = Black; 229 tree->current->left->color = Black;
181 tree->current->right->color = Black; 230 tree->current->right->color = Black;
182 goto nodeStack->pop(nodeStack,insertBalance); 231 goto stack->pop(insertBalance);
183 232
184 } else if (current->color == Black && current->right->color == Red && current->right->left->color == Red){ 233 } else if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->left->color == Red) {
185 234
186 struct Node* tmpCurrent = tree->current; 235 struct Node* tmpCurrent = tree->current;
187 struct Node* tmpRight = tree->current->right; 236 struct Node* tmpRight = tree->current->right;
188 struct Node* tmpRightLeft = tree->current->right->left; 237 struct Node* tmpRightLeft = tree->current->right->left;
189 238
192 tree->current->left = tmpRightLeft; 241 tree->current->left = tmpRightLeft;
193 tree->current->left->right = tmpRight->right; 242 tree->current->left->right = tmpRight->right;
194 tree->current->color = Red; 243 tree->current->color = Red;
195 tree->current->left->color = Black; 244 tree->current->left->color = Black;
196 tree->current->right->color = Black; 245 tree->current->right->color = Black;
197 goto nodeStack->pop(nodeStack,insertBalance); 246 goto stack->pop(insertBalance);
198 247
199 } else { 248 } else {
200 printf("unkwon error : __code insertBalanceRight()"); 249 printf("unkwon error : __code insertBalanceRight() \n");
201 goto next(...); 250 goto meta(context, C_exit_code);
202 } 251 }
203 } 252 }
204 253 // insertCode end
205 // insertion code end
206
207
208
209
210 /* __code deleteRBTree(struct RedBlackTree newNode, struct RedBlackTree* tree) { */
211 /* tree->current = tree->root; */
212 /* goto deleteLocate; */
213 /* } */
214
215 /* __code deleteLocate(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { */
216 /* /\* check delete node locate and push route node *\/ */
217 /* struct Stack* nodeStack = tree->nodeStack; */
218 /* struct Node* trace = tree->current; */
219
220 /* if (tree->current > node) { */
221 /* goto nodeStack->push(nodeStack,trace,deleteLocate); */
222 /* } else if (tree->current < node) { */
223 /* goto nodeStack->push(trace,deleteLocate); */
224 /* } else if (tree->current == node) { */
225 /* // trace = tree->current; */
226 /* goto deleteNode(struct Stack* nodeStack, struct RedBlackTree* tree,struct Node* trace); */
227 /* // goto nodeStack->push(trace,deleteNode); */
228 /* } else if (tree->current == null){ */
229 /* printf("No member Delete node (__code deleteLocate)"); */
230 /* goto next(...); */
231 /* } else { */
232 /* printf("Error,__code deleteLocate"); */
233 /* goto next(...); */
234 /* } */
235 /* } */
236
237 /* __code deleteNode(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { */
238 /* struct Stack* nodeStack = tree->nodeStack; */
239 /* struct Node* replaceNode = nodeStack->data; */
240
241 /* if(replaceNode->right == null){ */
242 /* tree->current = replaceNode; */
243 /* tree->current = tree->current->left; */
244 /* goto deleteUnbalance(nodeStack,replaceNode); */
245 /* }else if(replaceNode->left == null){ */
246 /* tree->current = replaceNode; */
247 /* tree->current = tree->current->right; */
248 /* goto deleteUnbalance(nodeStack,replaceNode); */
249 /* //goto deleteNodeReplaceNull(); */
250 /* }else{ */
251 /* // goto nodeStack->push(nodeStack,replaceNode,deleteNodeReplace); */
252 /* goto deleteNodeReplace(nodeStack,replaceNode); */
253 /* } */
254 /* } */
255
256
257 /* __code deleteNodeReplace(){ */
258
259 /* if (replaceNode->left != null){ */
260 /* replaceNode = replaceNode->left; */
261 /* goto deleteNodeReplace(); */
262 /* }else if(){ */
263
264
265 /* } */
266
267 /* } */
268
269
270 /* __code deleteUnbalance() { */
271 /* if () { */
272 /* } */
273 /* } */
274