Mercurial > hg > Gears > GearsAgda

comparison src/parallel_execution/rb_tree.c @ 134:2eccf4564efe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix stack call in rb_tree
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Tue, 08 Nov 2016 10:44:39 +0900
parents 568730b1239e
children 909d0548284f
comparison
equal deleted inserted replaced
133:568730b1239e 134:2eccf4564efe
38 38
39 goto meta(context, Insert); 39 goto meta(context, Insert);
40 } 40 }
41 41
42 __code put_stub(struct Context* context) { 42 __code put_stub(struct Context* context) {
43 struct Allocate* allocate = &context->data[Allocate]->allocate; 43 struct Node* newNode = &ALLOCATE(context, Node)->node;
44 allocate->size = sizeof(struct Node);
45 allocator(context);
46 goto put(context, 44 goto put(context,
47 context->data[Traverse]->traverse.nodeStack, 45 context->data[Traverse]->traverse.nodeStack,
48 &context->data[Tree]->tree, 46 &context->data[Tree]->tree,
49 &context->data[Node]->node, 47 &context->data[Node]->node,
50 &context->data[Traverse]->traverse, 48 &context->data[Traverse]->traverse,
51 context->data[Tree]->tree.root, 49 context->data[Tree]->tree.root,
52 &context->data[context->dataNum]->node 50 newNode
53 ); 51 );
54 } 52 }
55 53
56 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) { 54 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) {
57 *newNode = *oldNode; 55 *newNode = *oldNode;
127 goto insertCase1(context, 125 goto insertCase1(context,
128 &context->data[Tree]->tree, 126 &context->data[Tree]->tree,
129 context->data[Traverse]->traverse.nodeStack); 127 context->data[Traverse]->traverse.nodeStack);
130 } 128 }
131 129
132 __code insertCase2(struct Context* context, struct Node* parent) { 130 __code insertCase2(struct Context* context, struct Stack* nodeStack, struct Node* parent) {
133 if (parent->color == Black) { 131 if (parent->color == Black) {
134 goto meta(context, StackClear); 132 goto meta(context, StackClear);
135 } 133 }
136 goto meta(context, InsertCase3); 134 nodeStack->next = InsertCase3;
135 goto meta(context, nodeStack->get2);
137 } 136 }
138 137
139 __code insert2_stub(struct Context* context) { 138 __code insert2_stub(struct Context* context) {
140 goto insertCase2(context, (struct Node*)context->data[Traverse]->traverse.nodeStack->data); 139 goto insertCase2(context, context->data[Traverse]->traverse.nodeStack, (struct Node*)context->data[Traverse]->traverse.nodeStack->data);
141 } 140 }
142 141
143 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* parent, struct Node* grandparent) { 142 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* parent, struct Node* grandparent) {
143 struct Stack* nodeStack = traverse->nodeStack;
144 struct Node* uncle; 144 struct Node* uncle;
145 145
146 if (grandparent->left == parent) 146 if (grandparent->left == parent)
147 uncle = grandparent->right; 147 uncle = grandparent->right;
148 else 148 else
152 // do insertcase1 on grandparent, stack must be pop by two 152 // do insertcase1 on grandparent, stack must be pop by two
153 parent->color = Black; 153 parent->color = Black;
154 uncle->color = Black; 154 uncle->color = Black;
155 grandparent->color = Red; 155 grandparent->color = Red;
156 traverse->current = grandparent; 156 traverse->current = grandparent;
157 goto meta(context, InsertCase31); 157 nodeStack->next = InsertCase1;
158 } 158 goto meta(context, nodeStack->pop2);
159 goto meta(context, InsertCase4); 159 }
160 nodeStack->next = InsertCase4;
161 goto meta(context, nodeStack->get2);
160 } 162 }
161 163
162 __code insert3_stub(struct Context* context) { 164 __code insert3_stub(struct Context* context) {
163 goto insertCase3(context, &context->data[Traverse]->traverse, 165 goto insertCase3(context, &context->data[Traverse]->traverse,
164 (struct Node*)context->data[Traverse]->traverse.nodeStack->data, 166 &context->data[Traverse]->traverse.nodeStack->data->node,
165 (struct Node*)context->data[Traverse]->traverse.nodeStack->next->data 167 &context->data[Traverse]->traverse.nodeStack->data1->node
166 ); 168 );
167 } 169 }
168 __code insertCase31(struct Context* context, struct Traverse* traverse) {
169 traverse->nodeStack = traverse->nodeStack->next->next;
170 goto meta(context, InsertCase1);
171 }
172 __code insert31_stub(struct Context* context) {
173 goto insertCase31(context, &context->data[Traverse]->traverse);
174 }
175 170
176 __code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current,struct Node* parent, struct Node* grandparent) { 171 __code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current,struct Node* parent, struct Node* grandparent) {
172 struct Stack* nodeStack = traverse->nodeStack;
177 traverse->current = parent; 173 traverse->current = parent;
178 174
179 if ((current == parent->right) && (parent == grandparent->left)) { 175 if ((current == parent->right) && (parent == grandparent->left)) {
180 traverse->rotateNext = InsertCase4_1; 176 traverse->current = traverse->current->left;
181 goto meta(context, InsertCase4_01); 177 traverse->rotateNext = InsertCase5;
178 nodeStack->next = RotateL;
179 goto meta(context, nodeStack->get);
182 } else if ((current == parent->left) && (parent == grandparent->right)) { 180 } else if ((current == parent->left) && (parent == grandparent->right)) {
183 traverse->rotateNext = InsertCase4_2; 181 traverse->current = traverse->current->right;
184 goto meta(context, InsertCase4_02); 182 traverse->rotateNext = InsertCase5;
183 nodeStack->next = RotateR;
184 goto meta(context, nodeStack->get);
185 } 185 }
186 186
187 traverse->current = current; 187 traverse->current = current;
188 goto meta(context, InsertCase5); 188 goto meta(context, InsertCase5);
189 } 189 }
190 190
191 __code insert4_stub(struct Context* context) { 191 __code insert4_stub(struct Context* context) {
192 goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, 192 goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current,
193 &context->data[Traverse]->traverse.nodeStack->data->node, 193 &context->data[Traverse]->traverse.nodeStack->data->node,
194 &context->data[Traverse]->traverse.nodeStack->next->data->node); 194 &context->data[Traverse]->traverse.nodeStack->data1->node);
195 } 195 }
196 196
197 __code insertCase4_01(struct Context* context, struct Traverse* traverse) { 197 __code insertCase5(struct Context* context, struct Traverse* traverse) {
198 traverse->nodeStack = traverse->nodeStack -> next; 198 struct Stack* nodeStack = traverse->nodeStack;
199 traverse->rotateNext = InsertCase5; 199 nodeStack->next = InsertCase51;
200 goto meta(context, RotateL); 200 goto meta(context, nodeStack->pop2);
201 } 201 }
202 202
203 __code insert4_01_stub(struct Context* context) { 203 __code insert5_stub(struct Context* context) {
204 goto insertCase4_01(context, &context->data[Traverse]->traverse); 204 goto insertCase5(context, &context->data[Traverse]->traverse);
205 } 205 }
206 __code insertCase4_1(struct Context* context, struct Traverse* traverse) { 206
207 traverse->current = traverse->current->left; 207 __code insertCase51(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) {
208 goto meta(context, InsertCase5);
209 }
210
211 __code insert4_1_stub(struct Context* context) {
212 struct Allocate* allocate = &context->data[Allocate]->allocate;
213 allocate->size = sizeof(struct Element);
214 allocator(context);
215 struct Element* element = &context->data[context->dataNum]->element;
216 struct Traverse* traverse = &context->data[Traverse]->traverse;
217 element->data = (union Data*)traverse->current;
218 goto insertCase4_1(context, &context->data[Traverse]->traverse);
219 }
220 __code insertCase4_02(struct Context* context, struct Traverse* traverse) {
221 traverse->nodeStack = traverse->nodeStack -> next;
222 traverse->rotateNext = InsertCase5;
223 goto meta(context, RotateR);
224 }
225
226 __code insert4_02_stub(struct Context* context) {
227 goto insertCase4_02(context, &context->data[Traverse]->traverse);
228 }
229
230 __code insertCase4_2(struct Context* context, struct Traverse* traverse) {
231 traverse->current = traverse->current->right;
232 goto meta(context, InsertCase5);
233 }
234
235 __code insert4_2_stub(struct Context* context) {
236 struct Allocate* allocate = &context->data[Allocate]->allocate;
237 allocate->size = sizeof(struct Element);
238 allocator(context);
239 struct Element* element = &context->data[context->dataNum]->element;
240 struct Traverse* traverse = &context->data[Traverse]->traverse;
241 element->data = (union Data*)traverse->current;
242 goto insertCase4_2(context, &context->data[Traverse]->traverse);
243 }
244
245 __code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) {
246 parent->color = Black; 208 parent->color = Black;
247 grandparent->color = Red; 209 grandparent->color = Red;
248 210
249 traverse->current = grandparent; 211 traverse->current = grandparent;
250 traverse->rotateNext = StackClear; 212 traverse->rotateNext = StackClear;
252 goto meta(context, RotateR); 214 goto meta(context, RotateR);
253 else 215 else
254 goto meta(context, RotateL); 216 goto meta(context, RotateL);
255 } 217 }
256 218
257 __code insert5_stub(struct Context* context) { 219 __code insert51_stub(struct Context* context) {
258 struct Traverse* traverse = &context->data[Traverse]->traverse; 220 struct Traverse* traverse = &context->data[Traverse]->traverse;
259 struct Node* parent = (struct Node*)traverse->nodeStack->data; 221 struct Node* parent = &traverse->nodeStack->data->node;
260 struct Node* grandparent = (struct Node*)traverse->nodeStack->next->data; 222 struct Node* grandparent = &traverse->nodeStack->data1->node;
261 traverse->nodeStack = traverse->nodeStack->next->next; 223 goto insertCase51(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent);
262 goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent);
263 } 224 }
264 225
265 // put rotateLeft's continuation as argument 226 // put rotateLeft's continuation as argument
266 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) { 227 __code rotateLeft(struct Context* context, struct Traverse* traverse) {
228 struct Stack* nodeStack = traverse->nodeStack;
229 nodeStack->next = RotateL1;
230 goto meta(context, nodeStack->get);
231 }
232
233 __code rotateLeft_stub(struct Context* context) {
234 goto rotateLeft(context, &context->data[Traverse]->traverse);
235 }
236
237 __code rotateLeft1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
267 struct Node* tmp = node->right; 238 struct Node* tmp = node->right;
268 239
269 if (parent) { 240 if (parent) {
270 if (node == parent->left) 241 if (node == parent->left)
271 parent->left = tmp; 242 parent->left = tmp;
280 traverse->current = tmp; 251 traverse->current = tmp;
281 252
282 goto meta(context, traverse->rotateNext); 253 goto meta(context, traverse->rotateNext);
283 } 254 }
284 255
285 __code rotateLeft_stub(struct Context* context) { 256 __code rotateLeft1_stub(struct Context* context) {
286 struct Traverse* traverse = &context->data[Traverse]->traverse; 257 struct Traverse* traverse = &context->data[Traverse]->traverse;
287 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL; 258 struct Node* parent = &traverse->nodeStack->data->node;
288 goto rotateLeft(context, 259 goto rotateLeft1(context,
289 context->data[Traverse]->traverse.current, 260 context->data[Traverse]->traverse.current,
290 &context->data[Tree]->tree, 261 &context->data[Tree]->tree,
291 &context->data[Traverse]->traverse, 262 &context->data[Traverse]->traverse,
292 parent); 263 parent);
293 } 264 }
294 265
295 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) { 266 __code rotateRight(struct Context* context, struct Traverse* traverse) {
267 struct Stack* nodeStack = traverse->nodeStack;
268 nodeStack->next = RotateR1;
269 goto meta(context, nodeStack->get);
270 }
271
272 __code rotateRight_stub(struct Context* context) {
273 goto rotateRight(context, &context->data[Traverse]->traverse);
274 }
275
276 __code rotateRight1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
296 struct Node* tmp = node->left; 277 struct Node* tmp = node->left;
297 278
298 if (parent) { 279 if (parent) {
299 if (node == parent->left) 280 if (node == parent->left)
300 parent->left = tmp; 281 parent->left = tmp;
309 traverse->current = tmp; 290 traverse->current = tmp;
310 291
311 goto meta(context, traverse->rotateNext); 292 goto meta(context, traverse->rotateNext);
312 } 293 }
313 294
314 __code rotateRight_stub(struct Context* context) { 295 __code rotateRight1_stub(struct Context* context) {
315 struct Traverse* traverse = &context->data[Traverse]->traverse; 296 struct Traverse* traverse = &context->data[Traverse]->traverse;
316 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL; 297 struct Node* parent = &traverse->nodeStack->data->node;
317 goto rotateRight(context, 298 goto rotateRight1(context,
318 context->data[Traverse]->traverse.current, 299 context->data[Traverse]->traverse.current,
319 &context->data[Tree]->tree, 300 &context->data[Tree]->tree,
320 &context->data[Traverse]->traverse, 301 &context->data[Traverse]->traverse,
321 parent); 302 parent);
322 } 303 }