Mercurial > hg > Members > Moririn

comparison src/parallel_execution/rb_tree.c @ 138:04a2f486a30d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
insert works but is not balanced
author kono
date Tue, 08 Nov 2016 19:39:40 +0900
parents 909d0548284f
children c13b07d15d86
comparison
equal deleted inserted replaced
137:909d0548284f 138:04a2f486a30d
1 #include <stdio.h> 1 #include <stdio.h>
2 2
3 #include "context.h" 3 #include "context.h"
4 #include "origin_cs.h" 4 #include "origin_cs.h"
5 5
6 extern union Data* allocator(struct Context* context);
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 void printTree1(union Data* data) { 8 void printTree1(union Data* data) {
10 struct Node* node = &data->node; 9 struct Node* node = &data->node;
11 if (node == NULL) { 10 if (node == NULL) {
29 traverse->newNode = newNode; 28 traverse->newNode = newNode;
30 tree->root = newNode; // this should done at stackClear 29 tree->root = newNode; // this should done at stackClear
31 if (root) { 30 if (root) {
32 traverse->current = root; 31 traverse->current = root;
33 traverse->result = compare(traverse->current, node); 32 traverse->result = compare(traverse->current, node);
34 nodeStack->data = (union Data*)(newNode); 33 goto meta(context, Replace);
35 nodeStack->next = Replace1;
36 goto meta(context, nodeStack->push);
37 } 34 }
38 35
39 goto meta(context, Insert); 36 goto meta(context, Insert);
40 } 37 }
41 38
42 __code put_stub(struct Context* context) { 39 __code put_stub(struct Context* context) {
43 struct Node* newNode = &ALLOCATE(context, Node)->node; 40 struct Node* newNode = &ALLOCATE(context, Node)->node;
44 goto put(context, 41 goto put(context,
45 context->data[Traverse]->traverse.nodeStack, 42 &context->data[Stack]->stack,
46 &context->data[Tree]->tree, 43 &context->data[Tree]->tree,
47 &context->data[Node]->node, 44 &context->data[Node]->node,
48 &context->data[Traverse]->traverse, 45 &context->data[Traverse]->traverse,
49 context->data[Tree]->tree.root, 46 context->data[Tree]->tree.root,
50 newNode 47 newNode
51 ); 48 );
52 } 49 }
53 50
54 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) { 51 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) {
52 traverse->previous = newNode;
55 *newNode = *oldNode; 53 *newNode = *oldNode;
54 nodeStack->stack = (union Data*)traverse->nodeStack;
56 nodeStack->data = (union Data*)(newNode); 55 nodeStack->data = (union Data*)(newNode);
57 nodeStack->next = Replace1; 56 nodeStack->next = Replace1;
58 goto meta(context, nodeStack->push); 57 goto meta(context, traverse->nodeStack->push);
59 } 58 }
60 59
61 __code replaceNode_stub(struct Context* context) { 60 __code replaceNode_stub(struct Context* context) {
62 goto replaceNode(context, 61 goto replaceNode(context,
63 &context->data[Traverse]->traverse, 62 &context->data[Traverse]->traverse,
64 context->data[Traverse]->traverse.current, 63 context->data[Traverse]->traverse.current,
65 context->data[Traverse]->traverse.newNode, 64 context->data[Traverse]->traverse.newNode,
66 context->data[Traverse]->traverse.nodeStack); 65 &context->data[Stack]->stack);
67 } 66 }
68 67
69 __code replaceNode1(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) { 68 __code replaceNode1(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) {
70 if (result == EQ) { 69 if (result == EQ) {
71 newNode->value = node->value; 70 newNode->value = node->value;
92 struct Node* newnewNode = &ALLOCATE(context, Node)->node; 91 struct Node* newnewNode = &ALLOCATE(context, Node)->node;
93 goto replaceNode1(context, 92 goto replaceNode1(context,
94 &context->data[Traverse]->traverse, 93 &context->data[Traverse]->traverse,
95 &context->data[Node]->node, 94 &context->data[Node]->node,
96 context->data[Traverse]->traverse.current, 95 context->data[Traverse]->traverse.current,
97 &context->data[Traverse]->traverse.nodeStack->data->node, 96 context->data[Traverse]->traverse.previous,
98 newnewNode, 97 newnewNode,
99 context->data[Traverse]->traverse.result); 98 context->data[Traverse]->traverse.result);
100 } 99 }
101 100
102 __code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) { 101 __code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) {
125 goto insertCase1(context, 124 goto insertCase1(context,
126 &context->data[Tree]->tree, 125 &context->data[Tree]->tree,
127 &context->data[Traverse]->traverse.nodeStack->stack->singleLinkedStack); 126 &context->data[Traverse]->traverse.nodeStack->stack->singleLinkedStack);
128 } 127 }
129 128
130 __code insertCase2(struct Context* context, struct Stack* nodeStack, struct Node* parent) { 129 __code insertCase2(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack, struct Node* parent) {
131 if (parent->color == Black) { 130 if (parent->color == Black) {
132 goto meta(context, StackClear); 131 goto meta(context, StackClear);
133 } 132 }
133 nodeStack->stack = (union Data*)traverse->nodeStack;
134 nodeStack->next = InsertCase3; 134 nodeStack->next = InsertCase3;
135 goto meta(context, nodeStack->get2); 135 goto meta(context, traverse->nodeStack->get2);
136 } 136 }
137 137
138 __code insert2_stub(struct Context* context) { 138 __code insert2_stub(struct Context* context) {
139 struct SingleLinkedStack *nodeStack = (struct SingleLinkedStack*)context->data[Traverse]->traverse.nodeStack->stack; 139 struct SingleLinkedStack *nodeStack = (struct SingleLinkedStack*)context->data[Traverse]->traverse.nodeStack->stack;
140 goto insertCase2(context, context->data[Traverse]->traverse.nodeStack, &nodeStack->top->data->node); 140 goto insertCase2(context, &context->data[Traverse]->traverse, &context->data[Stack]->stack, &nodeStack->top->data->node);
141 } 141 }
142 142
143 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* parent, struct Node* grandparent) { 143 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack, struct Node* parent, struct Node* grandparent) {
144 struct Stack* nodeStack = traverse->nodeStack;
145 struct Node* uncle; 144 struct Node* uncle;
146 145
147 if (grandparent->left == parent) 146 if (grandparent->left == parent)
148 uncle = grandparent->right; 147 uncle = grandparent->right;
149 else 148 else
153 // do insertcase1 on grandparent, stack must be pop by two 152 // do insertcase1 on grandparent, stack must be pop by two
154 parent->color = Black; 153 parent->color = Black;
155 uncle->color = Black; 154 uncle->color = Black;
156 grandparent->color = Red; 155 grandparent->color = Red;
157 traverse->current = grandparent; 156 traverse->current = grandparent;
157 nodeStack->stack = (union Data*)traverse->nodeStack;
158 nodeStack->next = InsertCase1; 158 nodeStack->next = InsertCase1;
159 goto meta(context, nodeStack->pop2); 159 goto meta(context, traverse->nodeStack->pop2);
160 } 160 }
161 nodeStack->stack = (union Data*)traverse->nodeStack;
161 nodeStack->next = InsertCase4; 162 nodeStack->next = InsertCase4;
162 goto meta(context, nodeStack->get2); 163 goto meta(context, traverse->nodeStack->get2);
163 } 164 }
164 165
165 __code insert3_stub(struct Context* context) { 166 __code insert3_stub(struct Context* context) {
166 goto insertCase3(context, &context->data[Traverse]->traverse, 167 goto insertCase3(context, &context->data[Traverse]->traverse,
168 &context->data[Stack]->stack,
167 &context->data[Traverse]->traverse.nodeStack->data->node, 169 &context->data[Traverse]->traverse.nodeStack->data->node,
168 &context->data[Traverse]->traverse.nodeStack->data1->node 170 &context->data[Traverse]->traverse.nodeStack->data1->node
169 ); 171 );
170 } 172 }
171 173
174 traverse->current = parent; 176 traverse->current = parent;
175 177
176 if ((current == parent->right) && (parent == grandparent->left)) { 178 if ((current == parent->right) && (parent == grandparent->left)) {
177 traverse->current = traverse->current->left; 179 traverse->current = traverse->current->left;
178 traverse->rotateNext = InsertCase5; 180 traverse->rotateNext = InsertCase5;
181 nodeStack->stack = (union Data*)traverse->nodeStack;
179 nodeStack->next = RotateL; 182 nodeStack->next = RotateL;
180 goto meta(context, nodeStack->get); 183 goto meta(context, nodeStack->get);
181 } else if ((current == parent->left) && (parent == grandparent->right)) { 184 } else if ((current == parent->left) && (parent == grandparent->right)) {
182 traverse->current = traverse->current->right; 185 traverse->current = traverse->current->right;
183 traverse->rotateNext = InsertCase5; 186 traverse->rotateNext = InsertCase5;
187 nodeStack->stack = (union Data*)traverse->nodeStack;
184 nodeStack->next = RotateR; 188 nodeStack->next = RotateR;
185 goto meta(context, nodeStack->get); 189 goto meta(context, nodeStack->get);
186 } 190 }
187 191
188 traverse->current = current; 192 traverse->current = current;
195 &context->data[Traverse]->traverse.nodeStack->data1->node); 199 &context->data[Traverse]->traverse.nodeStack->data1->node);
196 } 200 }
197 201
198 __code insertCase5(struct Context* context, struct Traverse* traverse) { 202 __code insertCase5(struct Context* context, struct Traverse* traverse) {
199 struct Stack* nodeStack = traverse->nodeStack; 203 struct Stack* nodeStack = traverse->nodeStack;
204 nodeStack->stack = (union Data*)traverse->nodeStack;
200 nodeStack->next = InsertCase51; 205 nodeStack->next = InsertCase51;
201 goto meta(context, nodeStack->pop2); 206 goto meta(context, nodeStack->pop2);
202 } 207 }
203 208
204 __code insert5_stub(struct Context* context) { 209 __code insert5_stub(struct Context* context) {
225 } 230 }
226 231
227 // put rotateLeft's continuation as argument 232 // put rotateLeft's continuation as argument
228 __code rotateLeft(struct Context* context, struct Traverse* traverse) { 233 __code rotateLeft(struct Context* context, struct Traverse* traverse) {
229 struct Stack* nodeStack = traverse->nodeStack; 234 struct Stack* nodeStack = traverse->nodeStack;
235 nodeStack->stack = (union Data*)traverse->nodeStack;
230 nodeStack->next = RotateL1; 236 nodeStack->next = RotateL1;
231 goto meta(context, nodeStack->get); 237 goto meta(context, nodeStack->get);
232 } 238 }
233 239
234 __code rotateLeft_stub(struct Context* context) { 240 __code rotateLeft_stub(struct Context* context) {