Mercurial > hg > Members > innparusu > Gears

annotate src/parallel_execution/rb_tree.c @ 135:9ae7ce6c83f5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix segmentation falt
author innparusu
date Thu, 29 Sep 2016 17:18:15 +0900
parents 36ac17d37be4
children c7ac153f86dd
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdio.h>
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 #include "context.h"
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 #include "origin_cs.h"
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 extern void allocator(struct Context* context);
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
7 extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 extern int num;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
11 __code put(struct Context* context, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) {
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
12 traverse->newNode = newNode;
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
13 tree->root = newNode; // this should done at stackClear
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 if (root) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
15 traverse->current = root;
127
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
16 // traverse->result=compare(...)
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
17 compare(context, traverse, traverse->current->key, node->key);
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
18 // goto replaceNode(traverse->current, newNode, traverse->result);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 goto meta(context, Replace);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 goto meta(context, Insert);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 __code put_stub(struct Context* context) {
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
26 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
27 allocate->size = sizeof(struct Node);
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
28 allocator(context);
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
29
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
30 goto put(context,
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
31 &context->data[Tree]->tree,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
32 &context->data[Node]->node,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
33 &context->data[Traverse]->traverse,
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
34 context->data[Tree]->tree.root,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
35 &context->data[context->dataNum]->node
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
36 );
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
37 }
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
38
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
39 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Element* element) {
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
40 *newNode = *oldNode;
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
41 element->next = traverse->nodeStack;
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
42 element->data = (union Data* )newNode;
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
43 traverse->nodeStack = element;
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
44 // goto replaceNode1(struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, +struct Node* newnewNode, int result)
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
45 goto meta(context, Replace1);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
48 __code replaceNode_stub(struct Context* context) {
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
49 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
50 allocate->size = sizeof(struct Element);
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
51 allocator(context);
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
52 struct Element* element = &context->data[context->dataNum]->element;
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
53 goto replaceNode(context,
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
54 &context->data[Traverse]->traverse,
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
55 context->data[Traverse]->traverse.current,
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
56 context->data[Traverse]->traverse.newNode,
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
57 element);
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
58 }
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
59
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
60 __code replaceNode1(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 if (result == EQ) {
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
62 newNode->value = node->value;
127
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
63 // go to stack clear
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 goto meta(context, context->next);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 } else if (result == GT) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
66 traverse->current = oldNode->right;
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
67 newNode->right = newnewNode;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 } else {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
69 traverse->current = oldNode->left;
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
70 newNode->left = newnewNode;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 }
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
72 traverse->newNode = newnewNode;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
73 if (traverse->current) {
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
74 compare(context, traverse, traverse->current->key, node->key);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 goto meta(context, Replace);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 goto meta(context, Insert);
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
79
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81
131
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
82 __code replaceNode1_stub(struct Context* context) {
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
83 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
84 allocate->size = sizeof(struct Node);
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
85 allocator(context);
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
86 struct Node* newnewNode = &context->data[context->dataNum]->node;
f708b271a7b8 node stack rewrite
ikkun
parents: 130
diff changeset
87 goto replaceNode1(context,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
88 &context->data[Traverse]->traverse,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
89 &context->data[Node]->node,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
90 context->data[Traverse]->traverse.current,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
91 &context->data[Traverse]->traverse.nodeStack->data->node,
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
92 newnewNode,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
93 context->data[Traverse]->traverse.result);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
96 __code insertNode(struct Context* context, struct Traverse* traverse, struct Tree* tree, struct Node* node, struct Node* newNode) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 *newNode = *node;
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
98 newNode->color = Red;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
99 traverse->current = newNode;
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
100 tree->root->color = Black;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 goto meta(context, InsertCase1);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 __code insertNode_stub(struct Context* context) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
105 goto insertNode(context,
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
106 &context->data[Traverse]->traverse,
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
107 &context->data[Tree]->tree,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
108 &context->data[Node]->node,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
109 context->data[Traverse]->traverse.newNode);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
135
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
112 __code insertCase1(struct Context* context, struct Element* nodeStack) {
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
113 if (nodeStack!=NULL) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 goto meta(context, InsertCase2);
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
115 }
129
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 128
diff changeset
116 goto meta(context, StackClear);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 __code insert1_stub(struct Context* context) {
135
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
120 goto insertCase1(context, context->data[Traverse]->traverse.nodeStack);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
122
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
123 __code insertCase2(struct Context* context, struct Node* parent) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 if (parent->color == Black) {
129
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 128
diff changeset
125 goto meta(context, StackClear);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 goto meta(context, InsertCase3);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 __code insert2_stub(struct Context* context) {
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
131 goto insertCase2(context, (struct Node*)context->data[Traverse]->traverse.nodeStack->data);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
134 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* parent, struct Node* grandparent) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 struct Node* uncle;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
136
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 if (grandparent->left == parent)
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 uncle = grandparent->right;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 else
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 uncle = grandparent->left;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
141
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 if (uncle && (uncle->color == Red)) {
127
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
143 // do insertcase1 on grandparent, stack must be pop by two
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 parent->color = Black;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 uncle->color = Black;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 grandparent->color = Red;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
147 traverse->current = grandparent;
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
148 goto meta(context, InsertCase31);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 goto meta(context, InsertCase4);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
152
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 __code insert3_stub(struct Context* context) {
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
154 goto insertCase3(context, &context->data[Traverse]->traverse,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
155 (struct Node*)context->data[Traverse]->traverse.nodeStack->data,
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
156 (struct Node*)context->data[Traverse]->traverse.nodeStack->next->data
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
157 );
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 }
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
159 __code insertCase31(struct Context* context, struct Traverse* traverse) {
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
160 traverse->nodeStack = traverse->nodeStack->next->next;
130
2493f4226ca6 remove code stack, add stackPop2
ikkun
parents: 129
diff changeset
161 goto meta(context, InsertCase1);
2493f4226ca6 remove code stack, add stackPop2
ikkun
parents: 129
diff changeset
162 }
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
163 __code insert31_stub(struct Context* context) {
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
164 goto insertCase31(context, &context->data[Traverse]->traverse);
130
2493f4226ca6 remove code stack, add stackPop2
ikkun
parents: 129
diff changeset
165 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
166
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
167 __code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current,struct Node* parent, struct Node* grandparent) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
168 traverse->current = parent;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
169
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 if ((current == parent->right) && (parent == grandparent->left)) {
129
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 128
diff changeset
171 traverse->rotateNext = InsertCase4_1;
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
172 goto meta(context, InsertCase4_01);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 } else if ((current == parent->left) && (parent == grandparent->right)) {
129
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 128
diff changeset
174 traverse->rotateNext = InsertCase4_2;
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
175 goto meta(context, InsertCase4_02);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
177
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
178 traverse->current = current;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 goto meta(context, InsertCase5);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
180 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
181
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 __code insert4_stub(struct Context* context) {
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
183 goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current,
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
184 &context->data[Traverse]->traverse.nodeStack->data->node,
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
185 &context->data[Traverse]->traverse.nodeStack->next->data->node);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
187
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
188 __code insertCase4_01(struct Context* context, struct Traverse* traverse) {
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
189 context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next;
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
190 goto meta(context, RotateL);
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
191 }
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
192
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
193 __code insert4_01_stub(struct Context* context) {
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
194 goto insertCase4_01(context, &context->data[Traverse]->traverse);
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
195 }
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
196 __code insertCase4_1(struct Context* context, struct Traverse* traverse) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
197 traverse->current = traverse->current->left;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 goto meta(context, InsertCase5);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
199 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
200
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 __code insert4_1_stub(struct Context* context) {
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
202 struct Allocate* allocate = &context->data[Allocate]->allocate;
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
203 allocate->size = sizeof(struct Element);
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
204 allocator(context);
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
205 struct Element* element = &context->data[context->dataNum]->element;
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
206 struct Traverse* traverse = &context->data[Traverse]->traverse;
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
207 element->data = (union Data*)traverse->current;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
208 goto insertCase4_1(context, &context->data[Traverse]->traverse);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 }
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
210 __code insertCase4_02(struct Context* context, struct Traverse* traverse) {
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
211 context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next;
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
212 goto meta(context, RotateR);
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
213 }
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
214
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
215 __code insert4_02_stub(struct Context* context) {
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
216 goto insertCase4_02(context, &context->data[Traverse]->traverse);
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
217 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
218
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
219 __code insertCase4_2(struct Context* context, struct Traverse* traverse) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
220 traverse->current = traverse->current->right;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 goto meta(context, InsertCase5);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
223
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
224 __code insert4_2_stub(struct Context* context) {
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
225 struct Allocate* allocate = &context->data[Allocate]->allocate;
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
226 allocate->size = sizeof(struct Element);
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
227 allocator(context);
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
228 struct Element* element = &context->data[context->dataNum]->element;
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
229 struct Traverse* traverse = &context->data[Traverse]->traverse;
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
230 element->data = (union Data*)traverse->current;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
231 goto insertCase4_2(context, &context->data[Traverse]->traverse);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
233
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
234 __code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
235 parent->color = Black;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 grandparent->color = Red;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
237
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
238 traverse->current = grandparent;
129
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 128
diff changeset
239 traverse->rotateNext = StackClear;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
240 if ((current == parent->left) && (parent == grandparent->left))
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 goto meta(context, RotateR);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
242 else
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
243 goto meta(context, RotateL);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
244 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
245
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
246 __code insert5_stub(struct Context* context) {
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
247 struct Traverse* traverse = &context->data[Traverse]->traverse;
132
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
248 struct Node* parent = (struct Node*)traverse->nodeStack->data;
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
249 struct Node* grandparent = (struct Node*)traverse->nodeStack->next->data;
73a679a85c04 node stack rewrite
ikkun
parents: 131
diff changeset
250 traverse->nodeStack = traverse->nodeStack->next->next;
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
251 goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
252 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
253
127
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
254 // put rotateLeft's continuation as argument
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
255 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Element* element) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
256 struct Node* tmp = node->right;
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
257
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
258 if (parent) {
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
259 if (node == parent->left)
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
260 parent->left = tmp;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
261 else
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
262 parent->right = tmp;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
263 } else {
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
264 tree->root = tmp;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
265 }
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
266 element->data = (union Data*)parent;
127
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
267
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
268 node->right = tmp->left;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
269 tmp->left = node;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
270 traverse->current = tmp;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
271
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
272 goto meta(context, traverse->rotateNext);
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
273 }
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
274
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
275 __code rotateLeft_stub(struct Context* context) {
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
276 struct Traverse* traverse = &context->data[Traverse]->traverse;
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
277 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
278 traverse->nodeStack = traverse->nodeStack->next;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
279 struct Allocate* allocate = &context->data[Allocate]->allocate;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
280 allocate->size = sizeof(struct Element);
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
281 allocator(context);
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
282 struct Element* element = &context->data[context->dataNum]->element;
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
283 goto rotateLeft(context,
135
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
284 context->data[Traverse]->traverse.current,
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
285 &context->data[Tree]->tree,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
286 &context->data[Traverse]->traverse,
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
287 parent,
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
288 element);
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
289 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
290
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
291 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Element* element) {
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
292 struct Node* tmp = node->left;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
293
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
294 if (parent) {
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
295 if (node == parent->left)
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
296 parent->left = tmp;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
297 else
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
298 parent->right = tmp;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
299 } else {
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
300 tree->root = tmp;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
301 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
302
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
303 element->data = (union Data*)parent;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
304
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
305 node->left = tmp->right;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
306 tmp->right = node;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
307 traverse->current = tmp;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
308
129
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 128
diff changeset
309 goto meta(context, traverse->rotateNext);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
310 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
311
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
312 __code rotateRight_stub(struct Context* context) {
135
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
313 struct Traverse* traverse = &context->data[Traverse]->traverse;
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
314 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
315 traverse->nodeStack = traverse->nodeStack->next;
133
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
316 struct Allocate* allocate = &context->data[Allocate]->allocate;
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
317 allocate->size = sizeof(struct Element);
933c80f48d06 node stack rewrite
ikkun
parents: 132
diff changeset
318 allocator(context);
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
319 struct Element* element = &context->data[context->dataNum]->element;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
320 goto rotateRight(context,
135
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
321 context->data[Traverse]->traverse.current,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
322 &context->data[Tree]->tree,
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
323 &context->data[Traverse]->traverse,
135
9ae7ce6c83f5 Fix segmentation falt
innparusu
parents: 134
diff changeset
324 parent,
134
36ac17d37be4 Fix compile error but not work
one
parents: 133
diff changeset
325 element);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
326 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
327
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
328 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
329 traverse->current = 0;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
330
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
331 goto meta(context, context->next);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
332 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
333
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
334 __code stackClear_stub(struct Context* context) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
335 goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
336 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
337
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
338
92
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
339 __code get(struct Context* context, struct Tree* tree, struct Traverse* traverse) {
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
340 if (tree->root) {
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
341 traverse->current = tree->root;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
342
92
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
343 goto meta(context, Search);
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
344 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
345
129
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 128
diff changeset
346 goto meta(context, context->next);
92
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
347 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
348
92
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
349 __code get_stub(struct Context* context) {
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
350 goto get(context, &context->data[Tree]->tree, &context->data[Traverse]->traverse);
851da1107223 implement twice
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
351 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
352
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
353 __code search(struct Context* context, struct Traverse* traverse, struct Node* node) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
354 compare(context, traverse, traverse->current->key, node->key);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
355
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
356 if (traverse->result == EQ) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
357 *node = *traverse->current;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
358
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
359 goto meta(context, context->next);
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
360 } else if (traverse->result == GT) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
361 traverse->current = traverse->current->right;
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
362 } else {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
363 traverse->current = traverse->current->left;
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
364 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
365
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
366 if (traverse->current)
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
367 goto meta(context, Search);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
368
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
369 goto meta(context, context->next);
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
370 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
371
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
372 __code search_stub(struct Context* context) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
373 goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node);
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
374 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
375
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
376 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
377 /* /\* if (tree->root) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
378 /* /\* stack_push(context->code_stack, &context->next); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
379 /* /\* context->next = Delete1; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
380 /* /\* goto meta(context, Get); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
381 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
382
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
383 /* /\* goto meta(context, context->next); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
384 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
385
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
386 /* /\* __code delete_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
387 /* /\* goto delete(context, &context->data[Tree]->tree); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
388 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
389
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
390 /* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
391 /* /\* allocate->size = sizeof(struct Node); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
392 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
393
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
394 /* /\* struct Node* root = tree->root; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
395
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
396 /* /\* tree->root = &context->data[context->dataNum]->node; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
397 /* /\* tree->current = root; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
398
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
399 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
400
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
401 /* /\* goto meta(context, Replace_d1); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
402 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
403
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
404 /* /\* __code delete1_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
405 /* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
406 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
407
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
408 /* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
409 /* /\* if (current->color == Black) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
410 /* /\* struct Node* child = current->right == NULL ? current->left : current->right; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
411 /* /\* current->color = child == NULL ? Black : child->color; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
412
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
413 /* /\* goto meta(context, DeleteCase1); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
414 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
415
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
416 /* /\* goto meta(context, Delete3); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
417 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
418
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
419 /* /\* __code delete2_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
420 /* /\* goto delete2(context, context->data[Tree]->tree.current); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
421 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
422
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
423 /* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
424 /* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
425
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
426 /* /\* if (current->parent) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
427 /* /\* if (current == current->parent->left) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
428 /* /\* current->parent->left = tmp; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
429 /* /\* else *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
430 /* /\* current->parent->right = tmp; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
431 /* /\* } else { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
432 /* /\* tree->root = tmp; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
433 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
434
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
435 /* /\* if (tmp) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
436 /* /\* tmp->parent = current->parent; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
437
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
438 /* /\* if (current->parent == NULL && tmp) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
439 /* /\* tmp->color = Black; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
440
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
441 /* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
442
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
443 /* /\* stack_pop(context->code_stack, &context->next); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
444 /* /\* goto meta(context, context->next); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
445 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
446
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
447 /* /\* __code delete3_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
448 /* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
449 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
450
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
451 /* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
452 /* /\* *newNode = *oldNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
453
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
454 /* /\* if (result == EQ) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
455 /* /\* goto meta(context, Replace_d2); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
456 /* /\* else if (result == GT) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
457 /* /\* tree->current = newNode->right; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
458 /* /\* else *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
459 /* /\* tree->current = newNode->left; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
460
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
461 /* /\* tree->current->parent = newNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
462
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
463 /* /\* if (tree->current->left == NULL && tree->current->right == NULL) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
464 /* /\* goto meta(context, Delete2); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
465
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
466 /* /\* if (result == GT) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
467 /* /\* newNode->right = context->heap; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
468 /* /\* else if (result == LT) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
469 /* /\* newNode->left = context->heap; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
470
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
471 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
472
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
473 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
474
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
475 /* /\* goto meta(context, Replace_d1); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
476 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
477
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
478 /* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
479 /* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
480 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
481
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
482 /* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
483 /* /\* if (tree->current->left && tree->current->right) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
484 /* /\* newNode->left->parent = newNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
485 /* /\* tree->current = newNode->left; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
486 /* /\* newNode->left = context->heap; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
487 /* /\* tree->deleted = newNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
488
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
489 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
490 /* /\* tree->current->parent = newNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
491
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
492 /* /\* goto meta(context, FindMax1); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
493 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
494
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
495 /* /\* goto meta(context, Delete2); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
496 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
497
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
498 /* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
499 /* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
500 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
501
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
502 /* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
503 /* /\* *newNode = *oldNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
504
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
505 /* /\* if (newNode->right) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
506 /* /\* goto meta(context, FindMax2); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
507
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
508 /* /\* tree->deleted->key = newNode->key; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
509 /* /\* tree->deleted->value = newNode->value; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
510
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
511 /* /\* tree->current = newNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
512
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
513 /* /\* goto meta(context, Delete2); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
514 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
515
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
516 /* /\* __code findMax1_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
517 /* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
518 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
519
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
520
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
521 /* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
522 /* /\* *newNode = *oldNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
523
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
524 /* /\* if (newNode->right->right) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
525 /* /\* tree->current = newNode->right; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
526 /* /\* newNode->right = context->heap; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
527
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
528 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
529 /* /\* tree->current->parent = newNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
530
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
531 /* /\* goto meta(context, FindMax2); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
532 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
533
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
534 /* /\* tree->deleted->key = newNode->right->key; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
535 /* /\* tree->deleted->value = newNode->right->value; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
536
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
537 /* /\* tree->current = newNode; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
538
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
539 /* /\* goto meta(context, Delete2); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
540 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
541
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
542 /* /\* __code findMax2_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
543 /* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
544 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
545
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
546 /* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
547 /* /\* if (current->parent) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
548 /* /\* goto meta(context, DeleteCase2); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
549
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
550 /* /\* goto meta(context, Delete3); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
551 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
552
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
553 /* /\* __code deleteCase1_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
554 /* /\* goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
555 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
556
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
557 /* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
558 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
559
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
560 /* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
561 /* /\* current->parent->color = Red; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
562 /* /\* sibling->color = Black; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
563
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
564 /* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
565 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
566 /* /\* context->data[context->dataNum]->node = *sibling; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
567
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
568 /* /\* tree->current = current->parent; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
569
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
570 /* /\* context->next = DeleteCase3; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
571 /* /\* stack_push(context->code_stack, &context->next); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
572
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
573 /* /\* if (current == current->parent->left) *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
574 /* /\* goto meta(context, RotateL); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
575 /* /\* else *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
576 /* /\* goto meta(context, RotateR); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
577 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
578
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
579 /* /\* goto meta(context, DeleteCase3); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
580 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
581
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
582 /* /\* __code deleteCase2_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
583 /* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
584 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
585
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
586 /* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
587 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
588
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
589 /* /\* if (current->parent->color == Black && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
590 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
591 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
592 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
593 /* /\* sibling->color = Red; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
594
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
595 /* /\* tree->current = current->parent; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
596 /* /\* goto meta(context, DeleteCase1); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
597 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
598
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
599 /* /\* goto meta(context, DeleteCase4); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
600 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
601
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
602 /* /\* __code deleteCase3_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
603 /* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
604 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
605
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
606 /* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
607 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
608
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
609 /* /\* if (current->parent->color == Red && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
610 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
611 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
612 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
613 /* /\* sibling->color = Red; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
614 /* /\* current->parent->color = Black; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
615
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
616 /* /\* goto meta(context, Delete3); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
617 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
618
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
619 /* /\* goto meta(context, DeleteCase5); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
620 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
621
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
622 /* /\* __code deleteCase4_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
623 /* /\* goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
624 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
625
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
626 /* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
627 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
628 /* /\* sibling->parent = current->parent; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
629
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
630 /* /\* if (current == current->parent->left && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
631 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
632 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
633 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
634 /* /\* sibling->color = Red; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
635 /* /\* sibling->left->color = Black; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
636
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
637 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
638 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
639 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
640 /* /\* *tmp = *sibling; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
641 /* /\* tmp->parent = current; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
642
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
643 /* /\* tmp->left = context->heap; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
644 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
645 /* /\* context->data[context->dataNum]->node = *sibling->left; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
646 /* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
647
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
648 /* /\* tree->current = tmp; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
649
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
650 /* /\* context->next = DeleteCase6; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
651 /* /\* stack_push(context->code_stack, &context->next); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
652
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
653 /* /\* goto meta(context, RotateR); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
654 /* /\* } else if (current == current->parent->right && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
655 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
656 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
657 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
658 /* /\* sibling->color = Red; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
659 /* /\* sibling->right->color = Black; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
660
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
661 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
662 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
663 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
664 /* /\* *tmp = *sibling; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
665 /* /\* tmp->parent = current; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
666
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
667 /* /\* tmp->right = context->heap; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
668 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
669 /* /\* context->data[context->dataNum]->node = *sibling->right; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
670 /* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
671
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
672 /* /\* tree->current = tmp; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
673
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
674 /* /\* context->next = DeleteCase6; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
675 /* /\* stack_push(context->code_stack, &context->next); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
676 /* /\* goto meta(context, RotateL); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
677 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
678
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
679 /* /\* goto meta(context, DeleteCase6); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
680 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
681
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
682 /* /\* __code deleteCase5_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
683 /* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
684 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
685
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
686 /* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
687 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
688
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
689 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
690 /* /\* allocator(context); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
691 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
692 /* /\* *tmp = *sibling; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
693 /* /\* tmp->parent = current; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
694
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
695 /* /\* tmp->color = current->parent->color; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
696 /* /\* current->parent->color = Black; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
697
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
698 /* /\* context->next = Delete3; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
699 /* /\* stack_push(context->code_stack, &context->next); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
700
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
701 /* /\* if (current == current->parent->left) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
702 /* /\* tmp->right->color = Black; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
703 /* /\* tree->current = current->parent; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
704
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
705 /* /\* goto meta(context, RotateL); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
706 /* /\* } else { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
707 /* /\* tmp->left->color = Black; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
708 /* /\* tree->current = current->parent; *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
709
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
710 /* /\* goto meta(context, RotateR); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
711 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
712 /* /\* } *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
713
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
714 /* /\* __code deleteCase6_stub(struct Context* context) { *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
715 /* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
716 /* /\* } *\/ */