Mercurial > hg > GearsTemplate

comparison src/parallel_execution/rb_tree.c @ 91:1e074c3878c7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify tree
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 26 Jan 2016 07:46:26 +0900
parents 9e139a340bd1
children 851da1107223
comparison
equal deleted inserted replaced
90:4b5bf5b40970 91:1e074c3878c7
2 2
3 #include "context.h" 3 #include "context.h"
4 #include "origin_cs.h" 4 #include "origin_cs.h"
5 5
6 extern void allocator(struct Context* context); 6 extern void allocator(struct Context* context);
7 extern void compare(struct Context* context, struct Tree* tree, int key1, int key2); 7 extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2);
8 8
9 extern int num; 9 extern int num;
10 10
11 __code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) { 11 __code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Allocate* allocate) {
12 allocate->size = sizeof(struct Node); 12 allocate->size = sizeof(struct Node);
13 allocator(context); 13 allocator(context);
14 14
15 stack_push(context->code_stack, &context->next); 15 stack_push(context->code_stack, &context->next);
16 16
18 stack_push(context->code_stack, &context->next); 18 stack_push(context->code_stack, &context->next);
19 19
20 tree->root = &context->data[context->dataNum]->node; 20 tree->root = &context->data[context->dataNum]->node;
21 21
22 if (root) { 22 if (root) {
23 tree->current = root; 23 traverse->current = root;
24 compare(context, tree, tree->current->key, context->data[Node]->node.key); 24 compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
25 25
26 goto meta(context, Replace); 26 goto meta(context, Replace);
27 } 27 }
28 28
29 goto meta(context, Insert); 29 goto meta(context, Insert);
30 } 30 }
31 31
32 __code put_stub(struct Context* context) { 32 __code put_stub(struct Context* context) {
33 goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate); 33 goto put(context,
34 } 34 &context->data[Tree]->tree,
35 35 &context->data[Traverse]->traverse,
36 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { 36 context->data[Tree]->tree.root,
37 &context->data[Allocate]->allocate);
38 }
39
40 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, int result) {
37 *newNode = *oldNode; 41 *newNode = *oldNode;
38 stack_push(context->node_stack, &newNode); 42 stack_push(context->node_stack, &newNode);
39 43
40 if (result == EQ) { 44 if (result == EQ) {
41 newNode->value = context->data[Node]->node.value; 45 newNode->value = context->data[Node]->node.value;
42 46
43 stack_pop(context->code_stack, &context->next); 47 stack_pop(context->code_stack, &context->next);
44 goto meta(context, context->next); 48 goto meta(context, context->next);
45 } else if (result == GT) { 49 } else if (result == GT) {
46 tree->current = oldNode->right; 50 traverse->current = oldNode->right;
47 newNode->right = context->heap; 51 newNode->right = context->heap;
48 } else { 52 } else {
49 tree->current = oldNode->left; 53 traverse->current = oldNode->left;
50 newNode->left = context->heap; 54 newNode->left = context->heap;
51 } 55 }
52 56
53 allocator(context); 57 allocator(context);
54 58
55 if (tree->current) { 59 if (traverse->current) {
56 compare(context, tree, tree->current->key, context->data[Node]->node.key); 60 compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
57 goto meta(context, Replace); 61 goto meta(context, Replace);
58 } 62 }
59 63
60 goto meta(context, Insert); 64 goto meta(context, Insert);
61 } 65 }
62 66
63 __code replaceNode_stub(struct Context* context) { 67 __code replaceNode_stub(struct Context* context) {
64 goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); 68 goto replaceNode(context,
65 } 69 &context->data[Traverse]->traverse,
66 70 context->data[Traverse]->traverse.current,
67 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) { 71 &context->data[context->dataNum]->node,
72 context->data[Traverse]->traverse.result);
73 }
74
75 __code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) {
68 node->color = Red; 76 node->color = Red;
69 *newNode = *node; 77 *newNode = *node;
70 78
71 tree->current = newNode; 79 traverse->current = newNode;
72 80
73 goto meta(context, InsertCase1); 81 goto meta(context, InsertCase1);
74 } 82 }
75 83
76 __code insertNode_stub(struct Context* context) { 84 __code insertNode_stub(struct Context* context) {
77 goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node); 85 goto insertNode(context,
86 &context->data[Traverse]->traverse,
87 &context->data[Node]->node,
88 &context->data[context->dataNum]->node);
78 } 89 }
79 90
80 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) { 91 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
81 if (!isEmpty(context->node_stack)) 92 if (!isEmpty(context->node_stack))
82 goto meta(context, InsertCase2); 93 goto meta(context, InsertCase2);
86 stack_pop(context->code_stack, &context->next); 97 stack_pop(context->code_stack, &context->next);
87 goto meta(context, context->next); 98 goto meta(context, context->next);
88 } 99 }
89 100
90 __code insert1_stub(struct Context* context) { 101 __code insert1_stub(struct Context* context) {
91 goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 102 goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current);
92 } 103 }
93 104
94 __code insertCase2(struct Context* context, struct Node* current) { 105 __code insertCase2(struct Context* context, struct Node* current) {
95 struct Node* parent; 106 struct Node* parent;
96 stack_pop(context->node_stack, &parent); 107 stack_pop(context->node_stack, &parent);
103 stack_push(context->node_stack, &parent); 114 stack_push(context->node_stack, &parent);
104 goto meta(context, InsertCase3); 115 goto meta(context, InsertCase3);
105 } 116 }
106 117
107 __code insert2_stub(struct Context* context) { 118 __code insert2_stub(struct Context* context) {
108 goto insertCase2(context, context->data[Tree]->tree.current); 119 goto insertCase2(context, context->data[Traverse]->traverse.current);
109 } 120 }
110 121
111 __code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) { 122 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* current) {
112 struct Node* parent; 123 struct Node* parent;
113 struct Node* uncle; 124 struct Node* uncle;
114 struct Node* grandparent; 125 struct Node* grandparent;
115 126
116 stack_pop(context->node_stack, &parent); 127 stack_pop(context->node_stack, &parent);
123 134
124 if (uncle && (uncle->color == Red)) { 135 if (uncle && (uncle->color == Red)) {
125 parent->color = Black; 136 parent->color = Black;
126 uncle->color = Black; 137 uncle->color = Black;
127 grandparent->color = Red; 138 grandparent->color = Red;
128 tree->current = grandparent; 139 traverse->current = grandparent;
129 goto meta(context, InsertCase1); 140 goto meta(context, InsertCase1);
130 } 141 }
131 142
132 stack_push(context->node_stack, &grandparent); 143 stack_push(context->node_stack, &grandparent);
133 stack_push(context->node_stack, &parent); 144 stack_push(context->node_stack, &parent);
134 145
135 goto meta(context, InsertCase4); 146 goto meta(context, InsertCase4);
136 } 147 }
137 148
138 __code insert3_stub(struct Context* context) { 149 __code insert3_stub(struct Context* context) {
139 goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 150 goto insertCase3(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
140 } 151 }
141 152
142 __code insertCase4(struct Context* context, struct Tree* tree, struct Node* current) { 153 __code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current) {
143 struct Node* parent; 154 struct Node* parent;
144 struct Node* grandparent; 155 struct Node* grandparent;
145 156
146 stack_pop(context->node_stack, &parent); 157 stack_pop(context->node_stack, &parent);
147 stack_pop(context->node_stack, &grandparent); 158 stack_pop(context->node_stack, &grandparent);
148 159
149 stack_push(context->node_stack, &grandparent); 160 stack_push(context->node_stack, &grandparent);
150 161
151 tree->current = parent; 162 traverse->current = parent;
152 163
153 if ((current == parent->right) && (parent == grandparent->left)) { 164 if ((current == parent->right) && (parent == grandparent->left)) {
154 context->next = InsertCase4_1; 165 context->next = InsertCase4_1;
155 166
156 stack_push(context->code_stack, &context->next); 167 stack_push(context->code_stack, &context->next);
161 stack_push(context->code_stack, &context->next); 172 stack_push(context->code_stack, &context->next);
162 goto meta(context, RotateR); 173 goto meta(context, RotateR);
163 } 174 }
164 175
165 stack_push(context->node_stack, &parent); 176 stack_push(context->node_stack, &parent);
166 tree->current = current; 177 traverse->current = current;
167 goto meta(context, InsertCase5); 178 goto meta(context, InsertCase5);
168 } 179 }
169 180
170 __code insert4_stub(struct Context* context) { 181 __code insert4_stub(struct Context* context) {
171 goto insertCase4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 182 goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
172 } 183 }
173 184
174 __code insertCase4_1(struct Context* context, struct Tree* tree) { 185 __code insertCase4_1(struct Context* context, struct Traverse* traverse) {
175 stack_push(context->node_stack, &tree->current); 186 stack_push(context->node_stack, &traverse->current);
176 tree->current = tree->current->left; 187 traverse->current = traverse->current->left;
177 goto meta(context, InsertCase5); 188 goto meta(context, InsertCase5);
178 } 189 }
179 190
180 __code insert4_1_stub(struct Context* context) { 191 __code insert4_1_stub(struct Context* context) {
181 goto insertCase4_1(context, &context->data[Tree]->tree); 192 goto insertCase4_1(context, &context->data[Traverse]->traverse);
182 } 193 }
183 194
184 __code insertCase4_2(struct Context* context, struct Tree* tree) { 195 __code insertCase4_2(struct Context* context, struct Traverse* traverse) {
185 stack_push(context->node_stack, &tree->current); 196 stack_push(context->node_stack, &traverse->current);
186 tree->current = tree->current->right; 197 traverse->current = traverse->current->right;
187 goto meta(context, InsertCase5); 198 goto meta(context, InsertCase5);
188 } 199 }
189 200
190 __code insert4_2_stub(struct Context* context) { 201 __code insert4_2_stub(struct Context* context) {
191 goto insertCase4_2(context, &context->data[Tree]->tree); 202 goto insertCase4_2(context, &context->data[Traverse]->traverse);
192 } 203 }
193 204
194 __code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) { 205 __code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current) {
195 struct Node* parent; 206 struct Node* parent;
196 struct Node* grandparent; 207 struct Node* grandparent;
197 208
198 stack_pop(context->node_stack, &parent); 209 stack_pop(context->node_stack, &parent);
199 stack_pop(context->node_stack, &grandparent); 210 stack_pop(context->node_stack, &grandparent);
200 211
201 parent->color = Black; 212 parent->color = Black;
202 grandparent->color = Red; 213 grandparent->color = Red;
203 214
204 tree->current = grandparent; 215 traverse->current = grandparent;
205 216
206 if ((current == parent->left) && (parent == grandparent->left)) 217 if ((current == parent->left) && (parent == grandparent->left))
207 goto meta(context, RotateR); 218 goto meta(context, RotateR);
208 else 219 else
209 goto meta(context, RotateL); 220 goto meta(context, RotateL);
210 } 221 }
211 222
212 __code insert5_stub(struct Context* context) { 223 __code insert5_stub(struct Context* context) {
213 goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 224 goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
214 } 225 }
215 226
216 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) { 227 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
217 struct Node* tmp = node->right; 228 struct Node* tmp = node->right;
218 struct Node* parent = 0; 229 struct Node* parent = 0;
219 230
220 stack_pop(context->node_stack, &parent); 231 stack_pop(context->node_stack, &parent);
221 232
230 241
231 stack_push(context->node_stack, &parent); 242 stack_push(context->node_stack, &parent);
232 243
233 node->right = tmp->left; 244 node->right = tmp->left;
234 tmp->left = node; 245 tmp->left = node;
235 tree->current = tmp; 246 traverse->current = tmp;
236 247
237 stack_pop(context->code_stack, &context->next); 248 stack_pop(context->code_stack, &context->next);
238 goto meta(context, context->next); 249 goto meta(context, context->next);
239 } 250 }
240 251
241 __code rotateLeft_stub(struct Context* context) { 252 __code rotateLeft_stub(struct Context* context) {
242 goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree); 253 goto rotateLeft(context,
243 } 254 context->data[Traverse]->traverse.current,
244 255 &context->data[Tree]->tree,
245 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) { 256 &context->data[Traverse]->traverse);
257 }
258
259 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
246 struct Node* tmp = node->left; 260 struct Node* tmp = node->left;
247 struct Node* parent = 0; 261 struct Node* parent = 0;
248 262
249 stack_pop(context->node_stack, &parent); 263 stack_pop(context->node_stack, &parent);
250 264
259 273
260 stack_push(context->node_stack, &parent); 274 stack_push(context->node_stack, &parent);
261 275
262 node->left = tmp->right; 276 node->left = tmp->right;
263 tmp->right = node; 277 tmp->right = node;
264 tree->current = tmp; 278 traverse->current = tmp;
265 279
266 stack_pop(context->code_stack, &context->next); 280 stack_pop(context->code_stack, &context->next);
267 goto meta(context, context->next); 281 goto meta(context, context->next);
268 } 282 }
269 283
270 __code rotateRight_stub(struct Context* context) { 284 __code rotateRight_stub(struct Context* context) {
271 goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree); 285 goto rotateRight(context,
272 } 286 context->data[Traverse]->traverse.current,
273 287 &context->data[Tree]->tree,
274 __code stackClear(struct Context* context, stack_ptr node_stack, struct Tree* tree) { 288 &context->data[Traverse]->traverse);
275 if (stack_pop(node_stack, &tree->current) == 0) 289 }
290
291 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {
292 if (stack_pop(node_stack, &traverse->current) == 0)
276 goto meta(context, StackClear); 293 goto meta(context, StackClear);
277 294
278 tree->current = 0; 295 traverse->current = 0;
279 296
280 stack_pop(context->code_stack, &context->next); 297 stack_pop(context->code_stack, &context->next);
281 goto meta(context, context->next); 298 goto meta(context, context->next);
282 } 299 }
283 300
284 __code stackClear_stub(struct Context* context) { 301 __code stackClear_stub(struct Context* context) {
285 goto stackClear(context, context->node_stack, &context->data[Tree]->tree); 302 goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse);
286 } 303 }
287 304
288 305
289 /* /\* __code get(struct Context* context, struct Tree* tree) { *\/ */ 306 /* /\* __code get(struct Context* context, struct Tree* tree) { *\/ */
290 /* /\* if (tree->root) { *\/ */ 307 /* /\* if (tree->root) { *\/ */
299 316
300 /* /\* __code get_stub(struct Context* context) { *\/ */ 317 /* /\* __code get_stub(struct Context* context) { *\/ */
301 /* /\* goto get(context, &context->data[Tree]->tree); *\/ */ 318 /* /\* goto get(context, &context->data[Tree]->tree); *\/ */
302 /* /\* } *\/ */ 319 /* /\* } *\/ */
303 320
304 /* /\* __code search(struct Context* context, struct Tree* tree, struct Node* node) { *\/ */ 321 __code search(struct Context* context, struct Traverse* traverse, struct Node* node) {
305 /* /\* compare(context, tree, tree->current->key, node->key); *\/ */ 322 compare(context, traverse, traverse->current->key, node->key);
306 323
307 /* /\* if (tree->result == EQ) { *\/ */ 324 if (traverse->result == EQ) {
308 /* /\* *node = *tree->current; *\/ */ 325 *node = *traverse->current;
309 326
310 /* /\* goto meta(context, context->next); *\/ */ 327 goto meta(context, context->next);
311 /* /\* } else if (tree->result == GT) { *\/ */ 328 } else if (traverse->result == GT) {
312 /* /\* tree->current = tree->current->right; *\/ */ 329 traverse->current = traverse->current->right;
313 /* /\* } else { *\/ */ 330 } else {
314 /* /\* tree->current = tree->current->left; *\/ */ 331 traverse->current = traverse->current->left;
315 /* /\* } *\/ */ 332 }
316 333
317 /* /\* if (tree->current) *\/ */ 334 if (traverse->current)
318 /* /\* goto meta(context, Search); *\/ */ 335 goto meta(context, Search);
319 336
320 /* /\* stack_pop(context->code_stack, &context->next); *\/ */ 337 stack_pop(context->code_stack, &context->next);
321 /* /\* goto meta(context, context->next); *\/ */ 338 goto meta(context, context->next);
322 /* /\* } *\/ */ 339 }
323 340
324 /* /\* __code search_stub(struct Context* context) { *\/ */ 341 __code search_stub(struct Context* context) {
325 /* /\* goto search(context, &context->data[Tree]->tree, &context->data[Node]->node); *\/ */ 342 goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node);
326 /* /\* } *\/ */ 343 }
327 344
328 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */ 345 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
329 /* /\* if (tree->root) { *\/ */ 346 /* /\* if (tree->root) { *\/ */
330 /* /\* stack_push(context->code_stack, &context->next); *\/ */ 347 /* /\* stack_push(context->code_stack, &context->next); *\/ */
331 /* /\* context->next = Delete1; *\/ */ 348 /* /\* context->next = Delete1; *\/ */