Mercurial > hg > GearsTemplate
annotate src/llrb/llrb.c @ 53:399ed10d1760
modify
| author | Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 11 Jun 2015 15:08:38 +0900 |
| parents | d191faf19961 |
| children | 0299b90256e5 |
| rev | line source |
|---|---|
| 19 | 1 #include <stdio.h> |
| 2 #include <stdlib.h> | |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
3 #include <sys/time.h> |
| 19 | 4 |
| 5 #include "llrbContext.h" | |
| 6 | |
| 7 #include "allocate.h" | |
| 8 #include "origin_cs.h" | |
| 9 | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
10 #include "stack.h" |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
11 |
| 19 | 12 #define NUM 100 |
| 13 | |
| 14 extern __code initLLRBContext(struct Context* context); | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
15 |
| 19 | 16 /* |
| 17 __code code1(Allocate allocate) { | |
| 18 allocate.size = sizeof(long); | |
| 19 allocate.next = Code2; | |
| 20 goto Allocate(allocate); | |
| 21 } | |
| 22 */ | |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
23 static double st_time; |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
24 static double ed_time; |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
25 static int num; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
26 static clock_t c1,c2; |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
27 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
28 static stack_ptr pstack; |
| 42 | 29 static struct Node* pre; |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
30 |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
31 static double getTime() { |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
32 struct timeval tv; |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
33 gettimeofday(&tv, NULL); |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
34 return tv.tv_sec + (double)tv.tv_usec*1e-6; |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
35 } |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
36 |
| 42 | 37 void print_tree(struct Node* node, int n) { |
| 38 if (node != 0) { | |
| 39 print_tree(node->left, n+1); | |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
40 for (int i=0;i<n;i++) |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
41 printf(" "); |
| 42 | 42 printf("key=%d depth=%d\t%p\n", node->key, n, node); |
| 43 print_tree(node->right, n+1); | |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
44 } |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
45 } |
| 19 | 46 |
| 53 | 47 __code code1(struct Context* context, struct Allocate *allocate) { |
| 48 allocate->size = sizeof(long); | |
| 49 allocate->next = Code2; | |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
50 goto meta(context, Allocator); |
| 19 | 51 } |
| 52 | |
| 53 | 53 /* __code code1(struct Context* context) { */ |
| 54 /* context->data[Allocate]->allocate.size = sizeof(long); */ | |
| 55 /* context->data[Allocate]->allocate.next = Code2; */ | |
| 56 /* goto meta(context, Allocator); */ | |
| 57 /* } */ | |
| 58 | |
| 19 | 59 __code meta(struct Context* context, enum Code next) { |
| 53 | 60 if (next == Code1) |
| 61 goto code1(context, &context->data[Allocate]->allocate); | |
| 62 | |
| 19 | 63 goto (context->code[next])(context); |
| 64 } | |
| 65 | |
| 66 __code put(struct Context* context) { | |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
67 struct Tree* tree = &context->data[Tree]->tree; |
| 42 | 68 context->data[Next]->next = context->data[Allocate]->allocate.next; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
69 |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
70 if (tree->root == 0) { |
| 44 | 71 context->data[Allocate]->allocate.next = Insert; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
72 goto meta(context, Allocator); |
| 19 | 73 } |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
74 |
| 44 | 75 context->data[Allocate]->allocate.next = Create; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
76 tree->current = tree->root; |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
77 |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
78 goto meta(context, Compare); |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
79 } |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
80 |
| 44 | 81 __code replaceNode(struct Context* context) { |
| 82 struct Node* newNode = &context->data[context->dataNum]->node; | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
83 struct Tree* tree = &context->data[Tree]->tree; |
| 42 | 84 struct Node* persistentNode = tree->current; |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
85 |
|
31
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
86 int result = context->data[Tree]->tree.result; |
|
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
87 |
| 44 | 88 *newNode = *persistentNode; |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
89 |
|
31
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
90 if (result == 0) { |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
91 stack_pop(pstack, &tree->current); |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
92 goto meta(context, RotateL); |
|
31
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
93 } else if (result == 1) { |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
94 tree->current = persistentNode->right; |
| 44 | 95 newNode->right = context->heap; |
|
31
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
96 } else { |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
97 tree->current = persistentNode->left; |
| 44 | 98 newNode->left = context->heap; |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
99 } |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
100 |
| 42 | 101 if (tree->current == 0) { |
| 102 stack_pop(pstack, &tree->current); | |
| 44 | 103 context->data[Allocate]->allocate.next = Insert; |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
104 goto meta(context, Allocator); |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
105 } |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
106 |
| 44 | 107 context->data[Allocate]->allocate.next = Create; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
108 goto meta(context, Compare); |
| 19 | 109 } |
| 110 | |
| 44 | 111 __code insertNode(struct Context* context) { |
| 112 struct Node* newNode = &context->data[context->dataNum]->node; | |
| 42 | 113 struct Node* temporalNode = &context->data[Node]->node; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
114 struct Tree* tree = &context->data[Tree]->tree; |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
115 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
116 temporalNode->color = Red; |
| 44 | 117 *newNode = *temporalNode; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
118 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
119 if (tree->root == 0) { |
| 44 | 120 newNode->color = Black; |
| 121 tree->root = newNode; | |
| 42 | 122 goto meta(context, context->data[Next]->next); |
| 20 | 123 } |
| 124 | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
125 goto meta(context, RotateL); |
| 21 | 126 } |
| 127 | |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
128 __code compare(struct Context* context) { |
| 42 | 129 int persistentKey = context->data[Tree]->tree.current->key; |
| 130 int temporalKey = context->data[Node]->node.key; | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
131 |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
132 struct Tree* tree = &context->data[Tree]->tree; |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
133 |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
134 if (persistentKey == temporalKey) { |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
135 tree->result = 0; |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
136 } else if (persistentKey < temporalKey) { |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
137 tree->result = 1; |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
138 } else { |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
139 tree->result = -1; |
| 20 | 140 } |
| 141 | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
142 goto meta(context, context->data[Allocate]->allocate.next); |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
143 } |
|
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
144 |
| 44 | 145 __code createNode(struct Context* context) { |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
146 stack_push(pstack, &context->heap); |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
147 |
| 44 | 148 context->data[Allocate]->allocate.next = Replace; |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
149 goto meta(context, Allocator); |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
150 } |
| 20 | 151 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
152 __code rotateLeft(struct Context* context) { |
| 42 | 153 struct Node* node = context->data[Tree]->tree.current; |
| 154 | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
155 if (node->right != 0) { |
| 42 | 156 if (node->right->color == Red) { |
| 157 struct Node* tmp = node->right; | |
| 158 node->right = tmp->left; | |
| 159 tmp->left = node; | |
| 160 tmp->color = tmp->left->color; | |
| 161 tmp->left->color = Red; | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
162 context->data[Tree]->tree.current = tmp; |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
163 } |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
164 } |
| 20 | 165 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
166 goto meta(context, RotateR); |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
167 } |
| 21 | 168 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
169 __code rotateRight(struct Context* context) { |
| 42 | 170 struct Node* node = context->data[Tree]->tree.current; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
171 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
172 if (node->left != 0) { |
| 42 | 173 if (node->left->left != 0) { |
| 174 if (node->left->color == Red && node->left->left->color == Red) { | |
| 175 struct Node* tmp = node->left; | |
| 176 node->left = tmp->right; | |
| 177 tmp->right = node; | |
| 178 tmp->color = tmp->right->color; | |
| 179 tmp->right->color = Red; | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
180 context->data[Tree]->tree.current = tmp; |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
181 } |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
182 } |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
183 } |
| 20 | 184 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
185 goto meta(context, ColorFlip); |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
186 } |
| 27 | 187 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
188 __code colorFlip(struct Context* context) { |
| 42 | 189 struct Node* node = context->data[Tree]->tree.current; |
| 27 | 190 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
191 if (node->right != 0 && node->left != 0) { |
| 42 | 192 if (node->right->color == Red && node->left->color == Red) { |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
193 node->color ^= 1; |
| 42 | 194 node->left->color ^= 1; |
| 195 node->right->color ^= 1; | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
196 } |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
197 } |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
198 |
| 27 | 199 goto meta(context, FixUp); |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
200 } |
| 20 | 201 |
| 27 | 202 __code fixUp(struct Context* context) { |
| 203 struct Allocate* allocate = &context->data[Allocate]->allocate; | |
| 42 | 204 struct Node* node = context->data[Tree]->tree.current; |
| 27 | 205 |
| 206 allocate->next = ChangeRef; | |
| 42 | 207 |
| 208 context->data[Node]->node.key = node->key; | |
| 209 context->data[Tree]->tree.prev = node; | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
210 |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
211 if (stack_pop(pstack, &context->data[Tree]->tree.current) == 0) { |
| 27 | 212 goto meta(context, Compare); |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
213 } |
| 27 | 214 |
| 42 | 215 context->data[Tree]->tree.root = node; |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
216 |
| 42 | 217 goto meta(context, context->data[Next]->next); |
| 27 | 218 } |
| 219 | |
| 220 __code changeReference(struct Context* context) { | |
| 42 | 221 struct Node* node = context->data[Tree]->tree.current; |
|
31
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
222 int result = context->data[Tree]->tree.result; |
| 27 | 223 |
|
31
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
224 if (result == 1) { |
|
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
225 node->right = context->data[Tree]->tree.prev; |
|
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
226 } else if (result == -1) { |
| 27 | 227 node->left = context->data[Tree]->tree.prev; |
|
31
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
228 } else { |
|
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
229 perror("bad status"); |
| 27 | 230 } |
| 231 | |
| 232 goto meta(context, RotateL); | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
233 } |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
234 |
| 46 | 235 __code get(struct Context* context) { |
| 236 context->data[Tree]->tree.current = context->data[Tree]->tree.root; | |
| 237 context->data[Next]->next = context->data[Allocate]->allocate.next; | |
| 238 context->data[Allocate]->allocate.next = Traverse; | |
| 239 | |
| 240 goto meta(context, Compare); | |
| 241 } | |
| 242 | |
| 243 __code traverse(struct Context* context) { | |
| 244 int result = context->data[Tree]->tree.result; | |
| 245 struct Tree* tree = &context->data[Tree]->tree; | |
| 246 | |
| 247 if (result == 0) { | |
| 248 goto meta(context, context->data[Next]->next); | |
| 249 } else if (result == 1) { | |
| 250 tree->current = tree->current->right; | |
| 251 } else { | |
| 252 tree->current = tree->current->left; | |
| 253 } | |
| 254 | |
| 255 if(tree->current == 0) { | |
| 256 goto meta(context, context->data[Next]->next); | |
| 257 } | |
| 258 | |
| 259 goto meta(context, Compare); | |
| 260 } | |
| 261 | |
| 50 | 262 __code delete(struct Context* context) { |
| 263 goto meta(context, Get); | |
| 264 } | |
| 265 | |
| 19 | 266 /* |
| 267 __code code2(Allocate allocate, Count count) { | |
| 268 count.count = 0; | |
| 269 goto code3(count); | |
| 270 } | |
| 271 */ | |
| 272 | |
| 273 __code code2(struct Context* context) { | |
| 42 | 274 context->data[4]->count = 1; |
| 21 | 275 goto meta(context, Code3); |
| 276 } | |
| 277 | |
| 278 __code code3(struct Context* context) { | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
279 struct Allocate* allocate = &context->data[Allocate]->allocate; |
| 42 | 280 struct Node* node = &context->data[Node]->node; |
| 281 long loop = context->data[4]->count; | |
| 282 | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
283 if (loop == num) { |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
284 goto meta(context, Code4); |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
285 } |
| 42 | 286 |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
287 allocate->size = sizeof(struct Node); |
| 42 | 288 allocate->next = Code3; |
| 289 | |
| 290 node->key = loop; | |
| 291 node->value = loop; | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
292 |
| 42 | 293 context->data[4]->count++; |
|
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
294 goto meta(context, Put); |
| 19 | 295 } |
| 296 | |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
297 __code code4(struct Context* context) { |
| 46 | 298 puts("---before---"); |
| 299 print_tree(context->data[Tree]->tree.root, 0); | |
| 42 | 300 |
| 301 struct Allocate* allocate = &context->data[Allocate]->allocate; | |
| 302 allocate->size = sizeof(struct Node); | |
| 303 allocate->next = Code5; | |
| 304 | |
| 305 struct Node* node = &context->data[Node]->node; | |
| 306 node->key = 0; | |
| 307 node->value = 0; | |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
308 |
|
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
309 goto meta(context, Put); |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
310 } |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
311 |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
312 __code code5(struct Context* context) { |
| 42 | 313 puts("---after---"); |
|
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
314 print_tree(context->data[Tree]->tree.root, 0); |
| 25 | 315 puts("--Number of Data--"); |
| 316 printf("%d\n", context->dataNum); | |
| 317 stack_free(pstack); | |
| 46 | 318 |
| 319 context->data[Allocate]->allocate.next = Code6; | |
| 320 context->data[Node]->node.key = 2; | |
| 321 | |
| 322 goto meta(context, Get); | |
| 323 } | |
| 324 | |
| 325 __code code6(struct Context* context) { | |
| 326 puts("---get---"); | |
| 327 print_tree(context->data[Tree]->tree.current, 0); | |
|
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
328 goto meta(context, Exit); |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
329 } |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
330 |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
331 int main(int argc, char** argv) { |
|
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
332 num = (int)atoi(argv[1]); |
| 26 | 333 pstack = stack_init(sizeof(union Data*), num); |
| 19 | 334 struct Context* context = (struct Context*)malloc(sizeof(struct Context)); |
| 335 initLLRBContext(context); | |
| 336 goto start_code(context, Code1); | |
| 337 } |