19
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 #include <stdio.h>
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 #include <stdlib.h>
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 #include "llrbContext.h"
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 #include "allocate.h"
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 #include "origin_cs.h"
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 #ifdef CLANG
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 #define _CbC_retrun __return
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 #define _CbC_environment __environment
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 #endif
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 #define NUM 100
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 #define ALLOCATE_SIZE 1024
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 extern __code initLLRBContext(struct Context* context);
|
|
20
|
18 void colorFlip(struct Context*);
|
|
|
19 void rotateLeft(struct Context*);
|
|
|
20 void rotateRight(struct Context*);
|
19
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21 /*
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 __code code1(Allocate allocate) {
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 allocate.size = sizeof(long);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 allocate.next = Code2;
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 goto Allocate(allocate);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 */
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 __code code1(struct Context* context) {
|
|
21
|
30 context->data[0]->allocate.size = sizeof(long);
|
|
|
31 context->data[0]->allocate.next = Code2;
|
19
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 goto meta(context, Allocate);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 __code meta(struct Context* context, enum Code next) {
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 goto (context->code[next])(context);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 __code put(struct Context* context) {
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 context->data[context->dataSize]->node.key = context->data[0]->allocate.key;
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 context->data[context->dataSize]->node.value = context->data[0]->allocate.value;
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 if (context->root == 0) {
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 context->root = context->data[context->dataSize];
|
|
20
|
44 context->root->node.color = Black;
|
|
21
|
45 context->root->node.parent = 0;
|
19
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 goto meta(context, context->data[0]->allocate.after_put);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 }
|
|
20
|
48 context->data[context->dataSize]->node.color = Red;
|
|
|
49 context->current = context->root;
|
|
21
|
50 goto meta(context, InsertD);
|
19
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52
|
|
21
|
53 __code insertDown(struct Context* context) {
|
|
20
|
54 int persistentKey = context->current->node.key;
|
|
|
55 int temporalKey = context->data[context->dataSize]->node.key;
|
|
|
56
|
|
|
57 if (context->current->node.right != 0 && context->current->node.left != 0) {
|
|
|
58 if (context->current->node.right->node.color == Red && context->current->node.left->node.color == Red) {
|
|
|
59 colorFlip(context);
|
|
|
60 }
|
|
|
61 }
|
|
|
62
|
|
|
63 if (persistentKey == temporalKey) {
|
|
|
64 context->current->node.value = context->data[context->dataSize]->node.value;
|
|
|
65 goto meta(context, context->data[0]->allocate.after_put);
|
|
21
|
66 } else if (temporalKey < persistentKey) {
|
|
20
|
67 if (context->current->node.left == 0) {
|
|
|
68 context->current->node.left = context->data[context->dataSize];
|
|
|
69 } else {
|
|
|
70 context->current = context->current->node.left;
|
|
21
|
71 goto meta(context, InsertD);
|
|
20
|
72 }
|
|
|
73 } else {
|
|
|
74 if (context->current->node.right == 0) {
|
|
|
75 context->current->node.right = context->data[context->dataSize];
|
|
|
76 } else {
|
|
|
77 context->current = context->current->node.right;
|
|
21
|
78 goto meta(context, InsertD);
|
|
20
|
79 }
|
|
|
80 }
|
|
|
81
|
|
21
|
82 context->data[context->dataSize]->node.parent = context->current;
|
|
|
83
|
|
|
84 goto meta(context, InsertU);
|
|
|
85 }
|
|
|
86
|
|
|
87 __code insertUp(struct Context* context) {
|
|
20
|
88 if (context->current->node.right != 0) {
|
|
|
89 if (context->current->node.right->node.color == Red) {
|
|
|
90 rotateLeft(context);
|
|
|
91 }
|
|
|
92 }
|
|
|
93
|
|
|
94 if (context->current->node.left != 0) {
|
|
|
95 if (context->current->node.left->node.left != 0) {
|
|
|
96 if (context->current->node.left->node.color == Red && context->current->node.left->node.left->node.color == Red) {
|
|
|
97 rotateRight(context);
|
|
|
98 }
|
|
|
99 }
|
|
|
100 }
|
|
|
101
|
|
|
102 if (context->current->node.right != 0 && context->current->node.left != 0) {
|
|
|
103 if (context->current->node.right->node.color == Red && context->current->node.left->node.color == Red) {
|
|
|
104 colorFlip(context);
|
|
|
105 }
|
|
|
106 }
|
|
|
107
|
|
21
|
108 if (context->current->node.parent == 0) {
|
|
|
109 context->root = context->current;
|
|
|
110 context->root->node.color = Black;
|
|
|
111 goto meta(context, context->data[0]->allocate.after_put);
|
|
|
112 }
|
|
20
|
113
|
|
21
|
114 if (context->current->node.parent != 0) {
|
|
|
115 if (context->current->node.parent->node.key < context->current->node.key) {
|
|
|
116 context->current->node.parent->node.right = context->current;
|
|
|
117 } else {
|
|
|
118 context->current->node.parent->node.left = context->current;
|
|
|
119 }
|
|
|
120 }
|
|
|
121
|
|
|
122 context->current = context->current->node.parent;
|
|
|
123 goto meta(context, InsertU);
|
19
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
125
|
|
20
|
126 void rotateLeft(struct Context* context) {
|
|
|
127 union Data* tmp = context->current->node.right;
|
|
|
128 context->current->node.right = tmp->node.left;
|
|
|
129 tmp->node.left = context->current;
|
|
|
130 tmp->node.color = tmp->node.left->node.color;
|
|
21
|
131 tmp->node.parent = tmp->node.left->node.parent;
|
|
20
|
132 tmp->node.left->node.color = Red;
|
|
21
|
133 tmp->node.left->node.parent = tmp;
|
|
20
|
134 context->current = tmp;
|
|
|
135 }
|
|
|
136
|
|
|
137 void rotateRight(struct Context* context) {
|
|
|
138 union Data* tmp = context->current->node.left;
|
|
|
139 context->current->node.left = tmp->node.right;
|
|
|
140 tmp->node.right = context->current;
|
|
|
141 tmp->node.color = tmp->node.right->node.color;
|
|
21
|
142 tmp->node.parent = tmp->node.right->node.parent;
|
|
20
|
143 tmp->node.right->node.color = Red;
|
|
21
|
144 tmp->node.right->node.parent = tmp;
|
|
20
|
145 context->current = tmp;
|
|
|
146 }
|
|
|
147
|
|
|
148 void colorFlip(struct Context* context) {
|
|
|
149 context->current->node.color ^= 1;
|
|
|
150 context->current->node.left->node.color ^= 1;
|
|
|
151 context->current->node.right->node.color ^= 1;
|
|
|
152 }
|
|
|
153
|
19
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154 /*
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155 __code code2(Allocate allocate, Count count) {
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156 count.count = 0;
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
157 goto code3(count);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
158 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
159 */
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
160
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
161 __code code2(struct Context* context) {
|
|
21
|
162 context->data[1]->count = 0;
|
|
|
163 goto meta(context, Code3);
|
|
|
164 }
|
|
|
165
|
|
|
166 __code code3(struct Context* context) {
|
|
|
167 if (context->data[1]->count == NUM)
|
|
|
168 goto meta(context, Exit);
|
|
|
169 context->data[0]->allocate.size = sizeof(struct Node);
|
|
|
170 context->data[0]->allocate.next = Put;
|
|
|
171 context->data[0]->allocate.after_put = Code3;
|
|
|
172 context->data[0]->allocate.key = context->data[1]->count;
|
|
|
173 context->data[0]->allocate.value = context->data[1]->count;
|
|
|
174 context->data[1]->count++;
|
|
|
175 goto meta(context, Allocate);
|
19
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
178 int main() {
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
179 struct Context* context = (struct Context*)malloc(sizeof(struct Context));
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181 context->data = malloc(sizeof(union Data**)*ALLOCATE_SIZE);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 context->heap = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
183 initLLRBContext(context);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184 goto start_code(context, Code1);
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185 }
|
