Mercurial > hg > Gears > GearsAgda

comparison src/parallel_execution/RedBlackTree.cbc @ 338:0d720487291f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove stub from RedBlackTree.cbc
author mir3636
date Tue, 09 May 2017 12:08:29 +0900
parents 5bca0ff563e6
children eec6553a2aa6
comparison
equal deleted inserted replaced
337:5bca0ff563e6 338:0d720487291f
91 *newNode = *node; 91 *newNode = *node;
92 newNode->color = Red; 92 newNode->color = Red;
93 tree->current = newNode; 93 tree->current = newNode;
94 nodeStack->stack = (union Data*)tree->nodeStack; 94 nodeStack->stack = (union Data*)tree->nodeStack;
95 nodeStack->next = C_insertCase1; 95 nodeStack->next = C_insertCase1;
96 goto meta(context, traverse->nodeStack->get2); 96 goto meta(context, tree->nodeStack->get2);
97 } 97 }
98 98
99 __code insertCase1(struct RedBlackTree* tree, struct Node *parent, struct Node *grandparent) { 99 __code insertCase1(struct RedBlackTree* tree, struct Node *parent, struct Node *grandparent) {
100 if (parent != NULL) { 100 if (parent != NULL) {
101 tree->parent = parent; 101 tree->parent = parent;
146 146
147 if ((tree->current == tree->parent->right) && (tree->parent == tree->grandparent->left)) { 147 if ((tree->current == tree->parent->right) && (tree->parent == tree->grandparent->left)) {
148 tree->current = tree->current->left; 148 tree->current = tree->current->left;
149 tree->parent = tree->grandparent; 149 tree->parent = tree->grandparent;
150 150
151 rotateTree->tree = tree; 151 rotateTree->traverse = tree;
152 rotateTree->next = C_insertCase5; 152 rotateTree->next = C_insertCase5;
153 153
154 nodeStack->stack = (union Data*)tree->nodeStack; 154 nodeStack->stack = (union Data*)tree->nodeStack;
155 nodeStack->next = C_rotateLeft; 155 nodeStack->next = C_rotateLeft;
156 goto meta(context, nodeStack->pop); 156 goto meta(context, nodeStack->pop);
157 } else if ((tree->current == tree->parent->left) && (tree->parent == tree->grandparent->right)) { 157 } else if ((tree->current == tree->parent->left) && (tree->parent == tree->grandparent->right)) {
158 tree->parent = tree->grandparent; 158 tree->parent = tree->grandparent;
159 tree->current = tree->current->right; 159 tree->current = tree->current->right;
160 160
161 rotateTree->tree = tree; 161 rotateTree->traverse = tree;
162 rotateTree->next = C_insertCase5; 162 rotateTree->next = C_insertCase5;
163 163
164 nodeStack->stack = (union Data*)tree->nodeStack; 164 nodeStack->stack = (union Data*)tree->nodeStack;
165 nodeStack->next = C_rotateRight; 165 nodeStack->next = C_rotateRight;
166 goto meta(context, nodeStack->pop); 166 goto meta(context, nodeStack->pop);
167 } 167 }
168 168
169 goto meta(context, C_insertCase5); 169 goto meta(context, C_insertCase5);
170 } 170 }
171 171
172 __code insertCase5(struct RedBlackTree* traverse,struct Stack *nodeStack) { 172 __code insertCase5(struct RedBlackTree* tree, struct Stack* nodeStack) {
173 nodeStack->stack = (union Data*)traverse->nodeStack; 173 nodeStack->stack = (union Data*)tree->nodeStack;
174 nodeStack->next = C_insertCase51; 174 nodeStack->next = C_insertCase51;
175 goto meta(context, traverse->nodeStack->pop2); 175 goto meta(context, tree->nodeStack->pop2);
176 } 176 }
177 177
178 __code insertCase5_stub(struct Context* context) { 178 __code insertCase51(struct RedBlackTree* tree, struct RotateTree* rotateTree, struct Node* parent, struct Node* grandparent) {
179 goto insertCase5(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Stack)); 179 struct Node* current = tree->current;
180 } 180 tree->parent = parent;
181 181 tree->grandparent = grandparent;
182 __code insertCase51(struct RedBlackTree* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) {
183 traverse->parent = parent;
184 traverse->grandparent = grandparent;
185 182
186 parent->color = Black; 183 parent->color = Black;
187 grandparent->color = Red; 184 grandparent->color = Red;
188 185
189 traverse->current = grandparent; 186 tree->current = grandparent;
190 187
191 rotateTree->traverse = traverse; 188 rotateTree->traverse = tree;
192 rotateTree->next = C_stackClear; 189 rotateTree->next = C_stackClear;
193 190
194 if ((current == parent->left) && (parent == grandparent->left)) 191 if ((current == parent->left) && (parent == grandparent->left))
195 goto meta(context, C_rotateRight); 192 goto meta(context, C_rotateRight);
196 else 193 else
201 struct Node* parent = &context->data[D_Stack]->Stack.data->Node; 198 struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
202 struct Node* grandparent = &context->data[D_Stack]->Stack.data1->Node; 199 struct Node* grandparent = &context->data[D_Stack]->Stack.data1->Node;
203 goto insertCase51(context, 200 goto insertCase51(context,
204 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, 201 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
205 Gearef(context, RotateTree), 202 Gearef(context, RotateTree),
206 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.current,
207 parent, 203 parent,
208 grandparent); 204 grandparent);
209 } 205 }
210 206
211 __code rotateLeft(struct RedBlackTree* traverse,struct Stack* nodeStack) { 207 __code rotateLeft(struct RedBlackTree* tree, struct Stack* nodeStack) {
212 nodeStack->stack = (union Data*)traverse->nodeStack; 208 nodeStack->stack = (union Data*)tree->nodeStack;
213 nodeStack->next = C_rotateLeft1; 209 nodeStack->next = C_rotateLeft1;
214 goto meta(context, traverse->nodeStack->get); 210 goto meta(context, tree->nodeStack->get);
215 } 211 }
216 212
217 __code rotateLeft_stub(struct Context* context) { 213 __code rotateLeft_stub(struct Context* context) {
218 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; 214 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
219 goto rotateLeft(context, traverse, Gearef(context, Stack)); 215 goto rotateLeft(context, traverse, Gearef(context, Stack));
220 } 216 }
221 217
222 __code rotateLeft1(struct Node* node, struct RedBlackTree* traverse, struct Node *parent,struct RotateTree *rotateTree) { 218 __code rotateLeft1(struct Node* node, struct RedBlackTree* tree, struct Node* parent, struct RotateTree* rotateTree) {
223 struct Node* tmp = node->right; 219 struct Node* tmp = node->right;
224 220
225 if (parent) { 221 if (parent) {
226 if (node == parent->left) 222 if (node == parent->left)
227 parent->left = tmp; 223 parent->left = tmp;
228 else 224 else
229 parent->right = tmp; 225 parent->right = tmp;
230 } else { 226 } else {
231 traverse->root = tmp; 227 tree->root = tmp;
232 } 228 }
233 229
234 node->right = tmp->left; 230 node->right = tmp->left;
235 tmp->left = node; 231 tmp->left = node;
236 traverse->current = tmp; 232 tree->current = tmp;
237 233
238 goto meta(context, rotateTree->next); 234 goto meta(context, rotateTree->next);
239 } 235 }
240 236
241 __code rotateLeft1_stub(struct Context* context) { 237 __code rotateLeft1_stub(struct Context* context) {
242 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; 238 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
243 struct Node* parent = &context->data[D_Stack]->Stack.data->Node; 239 struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
244 goto rotateLeft1(context, 240 goto rotateLeft1(context,
245 traverse->current, 241 traverse->current,
246 traverse, 242 traverse,
247 parent, 243 parent,
248 Gearef(context, RotateTree)); 244 Gearef(context, RotateTree));
249 } 245 }
250 246
251 __code rotateRight(struct RedBlackTree* traverse,struct Stack *nodeStack) { 247 __code rotateRight(struct RedBlackTree* tree, struct Stack* nodeStack) {
252 nodeStack->stack = (union Data*)traverse->nodeStack; 248 nodeStack->stack = (union Data*)tree->nodeStack;
253 nodeStack->next = C_rotateRight1; 249 nodeStack->next = C_rotateRight1;
254 goto meta(context, traverse->nodeStack->get); 250 goto meta(context, tree->nodeStack->get);
255 } 251 }
256 252
257 __code rotateRight_stub(struct Context* context) { 253 __code rotateRight_stub(struct Context* context) {
258 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; 254 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
259 goto rotateLeft(context, traverse, Gearef(context, Stack)); 255 goto rotateLeft(context, traverse, Gearef(context, Stack));
286 traverse, 282 traverse,
287 parent, 283 parent,
288 Gearef(context, RotateTree)); 284 Gearef(context, RotateTree));
289 } 285 }
290 286
291 __code stackClear(struct RedBlackTree* traverse,struct Stack *nodeStack, __code next(...)) { 287 __code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
292 traverse->current = 0; 288 tree->current = 0;
293 nodeStack->stack = (union Data*)traverse->nodeStack; 289 nodeStack->stack = (union Data*)tree->nodeStack;
294 nodeStack->next = next; 290 nodeStack->next = next;
295 goto meta(context, traverse->nodeStack->clear); 291 goto meta(context, tree->nodeStack->clear);
296 } 292 }
297 293
298 __code stackClear_stub(struct Context* context) { 294 __code getRedBlackTree(struct RedBlackTree* tree, __code next(...)) {
299 goto stackClear(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Stack), 295 if (tree->root) {
300 Gearef(context, Tree)->next); 296 tree->current = tree->root;
301 }
302
303
304 __code getRedBlackTree(struct RedBlackTree* traverse, __code next(...)) {
305 if (traverse->root) {
306 traverse->current = traverse->root;
307 297
308 goto meta(context, C_search); 298 goto meta(context, C_search);
309 } 299 }
310 300
311 goto next(...); 301 goto next(...);
312 } 302 }
313 303
314 __code getRedBlackTree_stub(struct Context* context) { 304 __code search(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
315 goto getRedBlackTree(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Tree)->next);
316 }
317
318 __code search(struct RedBlackTree* traverse, struct Node* node, __code next(...)) {
319 // compare(context, traverse, traverse->current->key, node->key); 305 // compare(context, traverse, traverse->current->key, node->key);
320 traverse->result = compare(traverse->current, node); 306 tree->result = compare(tree->current, node);
321 if (traverse->result == EQ) { 307 if (tree->result == EQ) {
322 *node = *traverse->current; 308 *node = *tree->current;
323 309
324 goto meta(context, next); 310 goto meta(context, next);
325 } else if (traverse->result == GT) { 311 } else if (tree->result == GT) {
326 traverse->current = traverse->current->right; 312 tree->current = tree->current->right;
327 } else { 313 } else {
328 traverse->current = traverse->current->left; 314 tree->current = tree->current->left;
329 } 315 }
330 316
331 if (traverse->current) 317 if (tree->current)
332 goto meta(context, C_search); 318 goto meta(context, C_search);
333 319
334 goto next(...); 320 goto next(...);
335 }
336
337 __code search_stub(struct Context* context) {
338 goto search(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Node), Gearef(context, Tree)->next);
339 } 321 }
340 322
341 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */ 323 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
342 /* /\* if (tree->root) { *\/ */ 324 /* /\* if (tree->root) { *\/ */
343 /* /\* stack_push(context->code_stack, &context->next); *\/ */ 325 /* /\* stack_push(context->code_stack, &context->next); *\/ */