Mercurial > hg > Gears > GearsAgda
annotate src/parallel_execution/rb_tree.cbc @ 274:d14eb393023d
fix generate_stub
| author | mir3636 |
|---|---|
| date | Wed, 01 Feb 2017 18:13:47 +0900 |
| parents | 081607dcf893 |
| children |
| rev | line source |
|---|---|
| 86 | 1 #include <stdio.h> |
| 2 | |
| 3 #include "context.h" | |
| 4 #include "origin_cs.h" | |
| 5 | |
|
131
a4507906938c
Fix compile error but not work
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents:
130
diff
changeset
|
6 extern enum Relational compare(struct Node* node1, struct Node* node2); |
| 86 | 7 |
| 159 | 8 typedef struct Tree { |
| 194 | 9 union Data* tree; |
| 10 struct Node* node; | |
| 11 enum Code put; | |
| 12 enum Code get; | |
| 13 enum Code remove; | |
| 14 enum Code clear; | |
| 15 enum Code next; | |
| 159 | 16 } Tree; |
| 17 | |
| 194 | 18 typedef struct RedBlackTree { |
| 19 struct Node* root; | |
| 20 struct Node* current; // reading node of original tree | |
| 21 struct Node* previous; // parent of reading node of original tree | |
| 22 struct Node* newNode; // writing node of new tree | |
| 23 struct Node* parent; | |
| 24 struct Node* grandparent; | |
| 25 struct Stack* nodeStack; | |
| 26 int result; | |
| 27 } RedBlackTree; | |
| 159 | 28 |
| 29 typedef struct RotateTree { | |
| 194 | 30 enum Code next; |
| 31 struct RedBlackTree* traverse; | |
| 32 struct Tree* tree; | |
| 33 } rotateTree; | |
| 159 | 34 |
| 35 typedef struct Node { | |
| 194 | 36 int key; // comparable data segment |
| 37 union Data* value; | |
| 38 struct Node* left; | |
| 39 struct Node* right; | |
| 40 // need to balancing | |
| 41 enum Color { Red, Black, } color; | |
| 42 } node; | |
| 159 | 43 |
| 126 | 44 void printTree1(union Data* data) { |
| 132 | 45 struct Node* node = &data->node; |
| 126 | 46 if (node == NULL) { |
| 47 printf("NULL"); | |
| 48 } else { | |
| 49 printf("key = %d (", node->key); | |
| 133 | 50 printTree1((union Data*)(node->right)); |
| 126 | 51 printf("), ("); |
| 133 | 52 printTree1((union Data*)(node->left)); |
| 126 | 53 printf(")"); |
| 54 } | |
| 55 } | |
| 56 | |
| 57 void printTree(union Data* data) { | |
| 58 printTree1(data); | |
| 59 printf("\n"); | |
| 60 } | |
| 86 | 61 |
| 150 | 62 __code put(struct Stack* nodeStack, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, __code next(...)) { |
| 133 | 63 printTree((union Data*)(tree->root)); |
| 150 | 64 Node* newNode = new Node(); |
| 122 | 65 traverse->newNode = newNode; |
| 66 tree->root = newNode; // this should done at stackClear | |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
67 traverse->parent = NULL; |
| 86 | 68 if (root) { |
| 91 | 69 traverse->current = root; |
|
131
a4507906938c
Fix compile error but not work
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents:
130
diff
changeset
|
70 traverse->result = compare(traverse->current, node); |
| 150 | 71 goto replaceNode(traverse, traverse->current, newNode); |
| 86 | 72 } |
| 73 | |
| 150 | 74 goto insertNode(traverse, traverse->node, newNode); |
| 121 | 75 } |
| 76 | |
| 150 | 77 __code replaceNode(struct Traverse* traverse, struct Node* oldNode, struct Node* newNode) { |
| 78 Stack* nodeStack = new Stack(); | |
| 138 | 79 traverse->previous = newNode; |
| 121 | 80 *newNode = *oldNode; |
| 150 | 81 nodeStack->stack = traverse->nodeStack; |
| 82 nodeStack->data = newNode; | |
| 83 nodeStack->next = replaceNode1; | |
| 84 goto traverse->nodeStack->push(nodeStack); | |
| 85 // goto traverse->nodeStack->push(newNode, replaceNode1); | |
| 86 | 86 } |
| 87 | |
| 150 | 88 __code replaceNode1(struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, int result, __code next(...)) { |
| 89 Node* newnewNode = new Node(); | |
| 86 | 90 if (result == EQ) { |
| 121 | 91 newNode->value = node->value; |
| 117 | 92 // go to stack clear |
| 150 | 93 goto next(...); |
| 86 | 94 } else if (result == GT) { |
| 91 | 95 traverse->current = oldNode->right; |
| 121 | 96 newNode->right = newnewNode; |
| 86 | 97 } else { |
| 91 | 98 traverse->current = oldNode->left; |
| 121 | 99 newNode->left = newnewNode; |
| 86 | 100 } |
| 122 | 101 traverse->newNode = newnewNode; |
| 91 | 102 if (traverse->current) { |
|
131
a4507906938c
Fix compile error but not work
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents:
130
diff
changeset
|
103 traverse->result = compare(traverse->current, node); |
| 150 | 104 goto replaceNode(traverse, traverse->current, newNode); |
| 86 | 105 } |
| 150 | 106 goto insertNode(traverse, traverse->node, newNode); |
| 86 | 107 } |
| 108 | |
| 150 | 109 __code insertNode(struct Traverse* traverse, struct Node* node, struct Node* newNode) { |
| 86 | 110 *newNode = *node; |
| 122 | 111 newNode->color = Red; |
| 91 | 112 traverse->current = newNode; |
| 154 | 113 goto traverse->nodeStack->get2(traverse, tree, insertCase1); |
| 86 | 114 } |
| 115 | |
| 154 | 116 __code insertCase1(struct Node *parent, struct Node *grandparent, struct Traverse* traverse, struct Tree* tree) { |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
117 if (parent != NULL) { |
|
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
118 traverse->parent = parent; |
|
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
119 traverse->grandparent = grandparent; |
| 150 | 120 goto insertCase2(traverse); |
| 122 | 121 } |
| 127 | 122 tree->root->color = Black; |
| 150 | 123 goto stackClear(traverse); |
| 86 | 124 } |
| 125 | |
| 150 | 126 __code insertCase2(struct Traverse* traverse) { |
| 127 if (traverse->parent->color == Black) { | |
| 128 goto stackClear(traverse); | |
| 129 } | |
| 130 goto insertCase3(traverse); | |
| 86 | 131 } |
| 132 | |
| 150 | 133 __code insertCase3(struct Traverse* traverse) { |
| 134 Stack* nodeStack = new Stack(); | |
| 86 | 135 struct Node* uncle; |
| 136 | |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
137 if (traverse->grandparent->left == traverse->parent) |
|
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
138 uncle = traverse->grandparent->right; |
| 86 | 139 else |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
140 uncle = traverse->grandparent->left; |
| 86 | 141 |
| 142 if (uncle && (uncle->color == Red)) { | |
| 117 | 143 // do insertcase1 on grandparent, stack must be pop by two |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
144 traverse->parent->color = Black; |
| 86 | 145 uncle->color = Black; |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
146 traverse->grandparent->color = Red; |
|
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
147 traverse->current = traverse->grandparent; |
| 138 | 148 nodeStack->stack = (union Data*)traverse->nodeStack; |
| 150 | 149 nodeStack->next = insertCase1; |
| 157 | 150 goto traverse->nodeStack->pop2(nodeStack); |
| 86 | 151 } |
| 150 | 152 goto insertCase4(traverse, traverse->rotateTree); |
| 86 | 153 } |
| 154 | |
| 150 | 155 __code insertCase4(struct Traverse* traverse, struct RotateTree* rotateTree) { |
|
134
2eccf4564efe
fix stack call in rb_tree
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
133
diff
changeset
|
156 struct Stack* nodeStack = traverse->nodeStack; |
| 86 | 157 |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
158 if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) { |
|
134
2eccf4564efe
fix stack call in rb_tree
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
133
diff
changeset
|
159 traverse->current = traverse->current->left; |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
160 traverse->parent = traverse->grandparent; |
| 147 | 161 |
| 162 rotateTree->traverse = traverse; | |
| 150 | 163 rotateTree->next = insertCase5; |
| 147 | 164 |
| 138 | 165 nodeStack->stack = (union Data*)traverse->nodeStack; |
| 150 | 166 nodeStack->next = rotateLeft; |
| 157 | 167 goto nodeStack->pop(nodeStack); |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
168 } else if ((traverse->current == traverse->parent->left) && (traverse->parent == traverse->grandparent->right)) { |
| 147 | 169 traverse->parent = traverse->grandparent; |
|
134
2eccf4564efe
fix stack call in rb_tree
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
133
diff
changeset
|
170 traverse->current = traverse->current->right; |
| 147 | 171 |
| 172 rotateTree->traverse = traverse; | |
| 150 | 173 rotateTree->next = insertCase5; |
| 147 | 174 |
| 138 | 175 nodeStack->stack = (union Data*)traverse->nodeStack; |
| 150 | 176 nodeStack->next = rotateRight; |
| 157 | 177 goto nodeStack->pop(nodeStack); |
| 86 | 178 } |
| 179 | |
| 150 | 180 goto insertCase5(traverse); |
| 86 | 181 } |
| 182 | |
| 150 | 183 __code insertCase5(struct Traverse* traverse) { |
| 184 Stack* stack = new Stack; | |
| 185 nodeStack->stack = (union Data*)traverse->nodeStack; | |
| 186 nodeStack->next = insertCase51; | |
| 157 | 187 goto traverse->nodeStack->pop2(nodeStack); |
| 86 | 188 } |
| 189 | |
| 150 | 190 __code insertCase51(struct Traverse* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) { |
|
143
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
191 traverse->parent = parent; |
|
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
192 traverse->grandparent = grandparent; |
|
34a7a21edc36
recude stack get using traverse field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
141
diff
changeset
|
193 |
| 86 | 194 parent->color = Black; |
| 195 grandparent->color = Red; | |
| 196 | |
| 91 | 197 traverse->current = grandparent; |
| 147 | 198 |
| 199 rotateTree->traverse = traverse; | |
| 150 | 200 rotateTree->next = stackClear; |
| 147 | 201 |
| 86 | 202 if ((current == parent->left) && (parent == grandparent->left)) |
| 150 | 203 goto rotateRight(traverse); |
| 86 | 204 else |
| 150 | 205 goto rotateLeft(traverse); |
| 86 | 206 } |
| 207 | |
| 150 | 208 __code rotateLeft(struct Traverse* traverse) { |
| 209 Stack* nodeStack = new Stack(); | |
| 210 nodeStack->stack = (union Data*)traverse->nodeStack; | |
| 211 nodeStack->next = rotateLeft1; | |
| 157 | 212 goto traverse->nodeStack->get(nodeStack); |
| 86 | 213 } |
| 214 | |
| 150 | 215 __code rotateLeft1(struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node *parent,struct RotateTree *rotateTree) { |
| 86 | 216 struct Node* tmp = node->right; |
| 123 | 217 |
| 218 if (parent) { | |
| 146 | 219 if (node == parent->left) |
| 123 | 220 parent->left = tmp; |
| 221 else | |
| 222 parent->right = tmp; | |
| 223 } else { | |
| 224 tree->root = tmp; | |
| 225 } | |
| 117 | 226 |
| 123 | 227 node->right = tmp->left; |
| 228 tmp->left = node; | |
| 229 traverse->current = tmp; | |
| 230 | |
| 150 | 231 goto rotateTree->next(...); |
| 123 | 232 } |
| 233 | |
| 150 | 234 __code rotateRight(struct Traverse* traverse) { |
| 235 Stack* nodeStack = new Stack(); | |
| 236 nodeStack->stack = (union Data*)traverse->nodeStack; | |
| 237 nodeStack->next = rotateRight1; | |
| 157 | 238 goto traverse->nodeStack->get(nodeStack); |
| 123 | 239 } |
| 86 | 240 |
| 150 | 241 __code rotateRight1(struct Node* node, struct Tree* tree, struct Traverse* traverse,struct Node *parent,struct RotateTree *rotateTree) { |
| 123 | 242 struct Node* tmp = node->left; |
| 243 | |
| 86 | 244 if (parent) { |
| 146 | 245 if (node == parent->left) |
| 86 | 246 parent->left = tmp; |
| 247 else | |
| 248 parent->right = tmp; | |
| 249 } else { | |
| 250 tree->root = tmp; | |
| 251 } | |
| 252 | |
| 253 node->left = tmp->right; | |
| 254 tmp->right = node; | |
| 91 | 255 traverse->current = tmp; |
| 86 | 256 |
| 150 | 257 goto rotateTree->next(...); |
| 86 | 258 } |
| 259 | |
| 150 | 260 __code stackClear(struct Traverse* traverse) { |
| 261 Stack* nodeStack = new Stack(); | |
| 91 | 262 traverse->current = 0; |
|
145
cc071cf1ba85
add stack clear interface
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
144
diff
changeset
|
263 nodeStack->stack = (union Data*)traverse->nodeStack; |
|
cc071cf1ba85
add stack clear interface
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
144
diff
changeset
|
264 nodeStack->next = context->next; |
| 157 | 265 goto traverse->nodeStack->clear(nodeStack); |
| 86 | 266 } |
| 267 | |
| 150 | 268 __code get(struct Tree* tree, struct Traverse* traverse) { |
| 92 | 269 if (tree->root) { |
| 270 traverse->current = tree->root; | |
| 86 | 271 |
| 150 | 272 goto search(traverse, traverse->node); |
| 92 | 273 } |
| 86 | 274 |
| 150 | 275 goto traverse->next(...); |
| 92 | 276 } |
| 86 | 277 |
| 150 | 278 __code search(struct Traverse* traverse, struct Node* node) { |
|
131
a4507906938c
Fix compile error but not work
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents:
130
diff
changeset
|
279 // compare(context, traverse, traverse->current->key, node->key); |
|
a4507906938c
Fix compile error but not work
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents:
130
diff
changeset
|
280 traverse->result = compare(traverse->current, node); |
| 91 | 281 if (traverse->result == EQ) { |
| 282 *node = *traverse->current; | |
| 86 | 283 |
| 157 | 284 goto traverse->next(...); |
| 91 | 285 } else if (traverse->result == GT) { |
| 286 traverse->current = traverse->current->right; | |
| 287 } else { | |
| 288 traverse->current = traverse->current->left; | |
| 289 } | |
| 86 | 290 |
| 91 | 291 if (traverse->current) |
| 157 | 292 goto search(traverse, traverse->node); |
| 86 | 293 |
| 150 | 294 goto traverse->next(...); |
| 295 } |