Mercurial > hg > Gears > GearsAgda
annotate src/llrb/llrb.c @ 81:dc6f665bb753
implement delete(tail call). do not work
author | Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 11 Dec 2015 15:06:20 +0900 |
parents | 099d85f9d371 |
children | c13575c3dbe9 |
rev | line source |
---|---|
19 | 1 #include <stdio.h> |
2 | |
3 #include "llrbContext.h" | |
4 #include "origin_cs.h" | |
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
5 |
65
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
6 extern void allocator(struct Context* context); |
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
7 extern void compare(struct Context* context, struct Tree* tree, int key1, int key2); |
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
8 |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
9 extern int num; |
19 | 10 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
11 __code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) { |
56 | 12 allocate->size = sizeof(struct Node); |
65
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
13 allocator(context); |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
14 |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
15 stack_push(context->code_stack, &context->next); |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
16 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
17 tree->root = &context->data[context->dataNum]->node; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
18 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
19 if (root) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
20 tree->current = root; |
65
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
21 compare(context, tree, tree->current->key, context->data[Node]->node.key); |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
22 |
65
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
23 goto meta(context, Replace); |
56 | 24 } |
76 | 25 |
26 goto meta(context, Insert); | |
56 | 27 } |
28 | |
54 | 29 __code put_stub(struct Context* context) { |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
30 goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate); |
54 | 31 } |
32 | |
56 | 33 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { |
34 *newNode = *oldNode; | |
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
35 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
36 if (result == EQ) { |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
37 newNode->value = context->data[Node]->node.value; |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
38 |
80 | 39 stack_pop(context->code_stack, &context->next); |
40 goto meta(context, context->next); | |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
41 } else if (result == GT) { |
56 | 42 tree->current = oldNode->right; |
44 | 43 newNode->right = context->heap; |
31
dbbafae822f8
modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
27
diff
changeset
|
44 } else { |
56 | 45 tree->current = oldNode->left; |
44 | 46 newNode->left = context->heap; |
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
47 } |
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
48 |
65
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
49 allocator(context); |
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
50 |
76 | 51 if (tree->current) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
52 tree->current->parent = newNode; |
65
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
53 compare(context, tree, tree->current->key, context->data[Node]->node.key); |
025fd6e90597
to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
54 goto meta(context, Replace); |
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
55 } |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
56 |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
57 tree->current = newNode; |
76 | 58 goto meta(context, Insert); |
19 | 59 } |
60 | |
56 | 61 __code replaceNode_stub(struct Context* context) { |
62 goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); | |
63 } | |
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
64 |
80 | 65 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) { |
66 node->color = Red; | |
67 *newNode = *node; | |
68 newNode->parent = tree->current; | |
69 | |
70 tree->current = newNode; | |
71 | |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
72 goto meta(context, InsertCase1); |
80 | 73 } |
74 | |
75 __code insertNode_stub(struct Context* context) { | |
76 goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node); | |
77 } | |
78 | |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
79 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
80 if (current->parent) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
81 goto meta(context, InsertCase2); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
82 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
83 tree->root->color = Black; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
84 tree->current = 0; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
85 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
86 stack_pop(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
87 goto meta(context, context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
88 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
89 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
90 __code insert1_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
91 goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
92 } |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
93 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
94 __code insertCase2(struct Context* context, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
95 if (current->parent->color == Black) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
96 stack_pop(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
97 goto meta(context, context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
98 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
99 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
100 goto meta(context, InsertCase3); |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
101 } |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
102 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
103 __code insert2_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
104 goto insertCase2(context, context->data[Tree]->tree.current); |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
105 } |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
106 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
107 __code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
108 struct Node* uncle; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
109 struct Node* grandparent = current->parent->parent; |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
110 |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
111 if (grandparent->left == current->parent) |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
112 uncle = grandparent->right; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
113 else |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
114 uncle = grandparent->left; |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
115 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
116 if (uncle && (uncle->color == Red)) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
117 current->parent->color = Black; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
118 uncle->color = Black; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
119 grandparent->color = Red; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
120 tree->current = grandparent; |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
121 goto meta(context, InsertCase1); |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
122 } |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
123 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
124 goto meta(context, InsertCase4); |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
125 } |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
126 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
127 __code insert3_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
128 goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
129 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
130 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
131 __code insertCase4(struct Context* context, struct Node* current) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
132 struct Node* grandparent = current->parent->parent; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
133 |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
134 if ((current == current->parent->right) && (current->parent == grandparent->left)) { |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
135 context->next = InsertCase4_1; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
136 |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
137 stack_push(context->code_stack, &context->next); |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
138 goto meta(context, RotateL); |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
139 } else if ((current == current->parent->left) && (current->parent == grandparent->right)) { |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
140 context->next = InsertCase4_2; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
141 |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
142 stack_push(context->code_stack, &context->next); |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
143 goto meta(context, RotateR); |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
144 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
145 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
146 goto meta(context, InsertCase5); |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
147 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
148 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
149 __code insert4_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
150 goto insertCase4(context, context->data[Tree]->tree.current); |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
151 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
152 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
153 __code insertCase4_1(struct Context* context, struct Tree* tree) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
154 tree->current = tree->current->left; |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
155 goto meta(context, InsertCase5); |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
156 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
157 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
158 __code insert4_1_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
159 goto insertCase4_1(context, &context->data[Tree]->tree); |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
160 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
161 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
162 __code insertCase4_2(struct Context* context, struct Tree* tree) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
163 tree->current = tree->current->right; |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
164 goto meta(context, InsertCase5); |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
165 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
166 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
167 __code insert4_2_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
168 goto insertCase4_2(context, &context->data[Tree]->tree); |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
169 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
170 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
171 __code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
172 current->parent->color = Black; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
173 current->parent->parent->color = Red; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
174 |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
175 tree->current = current->parent->parent; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
176 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
177 context->next = InsertCase5_1; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
178 stack_push(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
179 |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
180 if ((current == current->parent->left) && (current->parent == current->parent->parent->left)) |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
181 goto meta(context, RotateR); |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
182 else |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
183 goto meta(context, RotateL); |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
184 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
185 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
186 __code insert5_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
187 goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
188 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
189 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
190 __code insertCase5_1(struct Context* context, struct Tree* tree) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
191 tree->current = NULL; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
192 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
193 stack_pop(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
194 goto meta(context, context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
195 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
196 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
197 __code insert5_1_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
198 goto insertCase5_1(context, &context->data[context->dataNum]->tree); |
56 | 199 } |
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
200 |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
201 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) { |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
202 struct Node* tmp = node->right; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
203 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
204 if (node->parent) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
205 if (node == node->parent->left) |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
206 node->parent->left = tmp; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
207 else |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
208 node->parent->right = tmp; |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
209 } else { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
210 tree->root = tmp; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
211 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
212 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
213 if (tmp) |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
214 tmp->parent = node->parent; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
215 |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
216 node->right = tmp->left; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
217 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
218 if (tmp->left) |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
219 tmp->left->parent = node; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
220 |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
221 tmp->left = node; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
222 node->parent = tmp; |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
223 tree->current = tmp; |
20 | 224 |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
225 stack_pop(context->code_stack, &context->next); |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
226 goto meta(context, context->next); |
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
227 } |
21 | 228 |
56 | 229 __code rotateLeft_stub(struct Context* context) { |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
230 goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree); |
56 | 231 } |
23
868c2918b634
Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
22
diff
changeset
|
232 |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
233 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) { |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
234 struct Node* tmp = node->left; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
235 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
236 if (node->parent) { |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
237 if (node == node->parent->left) |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
238 node->parent->left = tmp; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
239 else |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
240 node->parent->right = tmp; |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
241 } else { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
242 tree->root = tmp; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
243 } |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
244 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
245 if (tmp) |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
246 tmp->parent = node->parent; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
247 |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
248 node->left = tmp->right; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
249 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
250 if (tmp->right) |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
251 tmp->right->parent = node; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
252 |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
253 tmp->right = node; |
77
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
254 node->parent = tmp; |
618c03f25108
implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
255 tree->current = tmp; |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
256 |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
257 stack_pop(context->code_stack, &context->next); |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
258 goto meta(context, context->next); |
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
259 } |
27 | 260 |
56 | 261 __code rotateRight_stub(struct Context* context) { |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
262 goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree); |
56 | 263 } |
264 | |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
265 __code get(struct Context* context, struct Tree* tree) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
266 if (tree->root) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
267 tree->current = tree->root; |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
268 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
269 goto meta(context, Search); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
270 } |
72
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
271 |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
272 stack_pop(context->code_stack, &context->next); |
5c4b9d116eda
use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
69
diff
changeset
|
273 goto meta(context, context->next); |
24
7494c0b87ec4
implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
23
diff
changeset
|
274 } |
20 | 275 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
276 __code get_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
277 goto get(context, &context->data[Tree]->tree); |
75 | 278 } |
279 | |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
280 __code search(struct Context* context, struct Tree* tree, struct Node* node) { |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
281 compare(context, tree, tree->current->key, node->key); |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
282 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
283 if (tree->result == EQ) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
284 *node = *tree->current; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
285 |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
286 goto meta(context, context->next); |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
287 } else if (tree->result == GT) { |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
288 tree->current = tree->current->right; |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
289 } else { |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
290 tree->current = tree->current->left; |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
291 } |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
292 |
76 | 293 if (tree->current) |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
294 goto meta(context, Search); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
295 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
296 stack_pop(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
297 goto meta(context, context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
298 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
299 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
300 __code search_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
301 goto search(context, &context->data[Tree]->tree, &context->data[Node]->node); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
302 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
303 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
304 __code delete(struct Context* context, struct Tree* tree) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
305 if (tree->root) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
306 stack_push(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
307 context->next = Delete1; |
76 | 308 goto meta(context, Get); |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
309 } |
76 | 310 |
311 goto meta(context, context->next); | |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
312 } |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
313 |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
314 __code delete_stub(struct Context* context) { |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
315 goto delete(context, &context->data[Tree]->tree); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
316 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
317 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
318 __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
319 allocate->size = sizeof(struct Node); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
320 allocator(context); |
74 | 321 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
322 struct Node* root = tree->root; |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
323 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
324 tree->root = &context->data[context->dataNum]->node; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
325 tree->current = root; |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
326 |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
327 compare(context, tree, tree->current->key, context->data[Node]->node.key); |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
328 |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
329 goto meta(context, Replace_d1); |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
330 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
331 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
332 __code delete1_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
333 goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
334 } |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
335 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
336 __code delete2(struct Context* context, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
337 if (current->color == Black) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
338 struct Node* child = current->right == NULL ? current->left : current->right; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
339 current->color = child == NULL ? Black : child->color; |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
340 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
341 goto meta(context, DeleteCase1); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
342 } |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
343 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
344 goto meta(context, Delete3); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
345 } |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
346 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
347 __code delete2_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
348 goto delete2(context, context->data[Tree]->tree.current); |
46 | 349 } |
350 | |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
351 __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
352 struct Node* tmp = current->right == NULL ? current->left : current->right; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
353 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
354 if (current->parent) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
355 if (current == current->parent->left) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
356 current->parent->left = tmp; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
357 else |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
358 current->parent->right = tmp; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
359 } else { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
360 tree->root = tmp; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
361 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
362 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
363 if (tmp) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
364 tmp->parent = current->parent; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
365 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
366 if (current->parent == NULL && tmp) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
367 tmp->color = Black; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
368 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
369 current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
370 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
371 stack_pop(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
372 goto meta(context, context->next); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
373 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
374 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
375 __code delete3_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
376 goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
377 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
378 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
379 __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
380 *newNode = *oldNode; |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
381 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
382 if (result == EQ) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
383 goto meta(context, Replace_d2); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
384 else if (result == GT) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
385 tree->current = newNode->right; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
386 else |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
387 tree->current = newNode->left; |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
388 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
389 tree->current->parent = newNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
390 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
391 if (tree->current->left == NULL && tree->current->right == NULL) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
392 goto meta(context, Delete2); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
393 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
394 if (result == GT) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
395 newNode->right = context->heap; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
396 else if (result == LT) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
397 newNode->left = context->heap; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
398 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
399 allocator(context); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
400 |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
401 compare(context, tree, tree->current->key, context->data[Node]->node.key); |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
402 |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
403 goto meta(context, Replace_d1); |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
404 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
405 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
406 __code replaceNodeForDelete1_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
407 goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
408 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
409 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
410 __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
411 if (tree->current->left && tree->current->right) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
412 newNode->left->parent = newNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
413 tree->current = newNode->left; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
414 newNode->left = context->heap; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
415 tree->deleted = newNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
416 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
417 allocator(context); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
418 tree->current->parent = newNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
419 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
420 goto meta(context, FindMax1); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
421 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
422 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
423 goto meta(context, Delete2); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
424 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
425 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
426 __code replaceNodeForDelete2_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
427 goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
428 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
429 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
430 __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
431 *newNode = *oldNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
432 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
433 if (newNode->right) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
434 goto meta(context, FindMax2); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
435 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
436 tree->deleted->key = newNode->key; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
437 tree->deleted->value = newNode->value; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
438 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
439 tree->current = newNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
440 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
441 goto meta(context, Delete2); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
442 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
443 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
444 __code findMax1_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
445 goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
446 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
447 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
448 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
449 __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
450 *newNode = *oldNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
451 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
452 if (newNode->right->right) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
453 tree->current = newNode->right; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
454 newNode->right = context->heap; |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
455 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
456 allocator(context); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
457 tree->current->parent = newNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
458 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
459 goto meta(context, FindMax2); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
460 } |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
461 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
462 tree->deleted->key = newNode->right->key; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
463 tree->deleted->value = newNode->right->value; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
464 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
465 tree->current = newNode; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
466 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
467 goto meta(context, Delete2); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
468 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
469 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
470 __code findMax2_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
471 goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
472 } |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
473 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
474 __code deleteCase1(struct Context* context, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
475 if (current->parent) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
476 goto meta(context, DeleteCase2); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
477 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
478 goto meta(context, Delete3); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
479 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
480 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
481 __code deleteCase1_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
482 goto deleteCase1(context, context->data[Tree]->tree.current); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
483 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
484 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
485 __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
486 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
487 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
488 if ((sibling == NULL ? Black : sibling->color) == Red) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
489 current->parent->color = Red; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
490 sibling->color = Black; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
491 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
492 current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
493 allocator(context); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
494 context->data[context->dataNum]->node = *sibling; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
495 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
496 tree->current = current->parent; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
497 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
498 context->next = DeleteCase3; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
499 stack_push(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
500 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
501 if (current == current->parent->left) |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
502 goto meta(context, RotateL); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
503 else |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
504 goto meta(context, RotateR); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
505 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
506 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
507 goto meta(context, DeleteCase3); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
508 } |
22
4c3c0ad4a75d
add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
509 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
510 __code deleteCase2_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
511 goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
512 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
513 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
514 __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
515 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; |
76 | 516 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
517 if (current->parent->color == Black && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
518 (sibling == NULL ? Black : sibling->color) == Black && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
519 (sibling->left == NULL ? Black : sibling->left->color) == Black && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
520 (sibling->right == NULL ? Black : sibling->right->color) == Black) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
521 sibling->color = Red; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
522 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
523 tree->current = current->parent; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
524 goto meta(context, DeleteCase1); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
525 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
526 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
527 goto meta(context, DeleteCase4); |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
528 } |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
529 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
530 __code deleteCase3_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
531 goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
532 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
533 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
534 __code deleteCase4(struct Context* context, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
535 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
536 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
537 if (current->parent->color == Red && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
538 (sibling == NULL ? Black : sibling->color) == Black && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
539 (sibling->left == NULL ? Black : sibling->left->color) == Black && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
540 (sibling->right == NULL ? Black : sibling->right->color) == Black) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
541 sibling->color = Red; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
542 current->parent->color = Black; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
543 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
544 goto meta(context, Delete3); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
545 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
546 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
547 goto meta(context, DeleteCase5); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
548 } |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
549 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
550 __code deleteCase4_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
551 goto deleteCase4(context, context->data[Tree]->tree.current); |
19 | 552 } |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
553 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
554 __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
555 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
556 sibling->parent = current->parent; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
557 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
558 if (current == current->parent->left && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
559 (sibling == NULL ? Black : sibling->color) == Black && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
560 (sibling->left == NULL ? Black : sibling->left->color) == Red && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
561 (sibling->right == NULL ? Black : sibling->right->color) == Black) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
562 sibling->color = Red; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
563 sibling->left->color = Black; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
564 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
565 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
566 allocator(context); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
567 struct Node* tmp = &context->data[context->dataNum]->node; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
568 *tmp = *sibling; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
569 tmp->parent = current; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
570 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
571 tmp->left = context->heap; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
572 allocator(context); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
573 context->data[context->dataNum]->node = *sibling->left; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
574 context->data[context->dataNum]->node.parent = tmp; |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
575 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
576 tree->current = tmp; |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
577 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
578 context->next = DeleteCase6; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
579 stack_push(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
580 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
581 goto meta(context, RotateR); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
582 } else if (current == current->parent->right && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
583 (sibling == NULL ? Black : sibling->color) == Black && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
584 (sibling->left == NULL ? Black : sibling->left->color) == Black && |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
585 (sibling->right == NULL ? Black : sibling->right->color) == Red) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
586 sibling->color = Red; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
587 sibling->right->color = Black; |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
588 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
589 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
590 allocator(context); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
591 struct Node* tmp = &context->data[context->dataNum]->node; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
592 *tmp = *sibling; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
593 tmp->parent = current; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
594 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
595 tmp->right = context->heap; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
596 allocator(context); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
597 context->data[context->dataNum]->node = *sibling->right; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
598 context->data[context->dataNum]->node.parent = tmp; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
599 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
600 tree->current = tmp; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
601 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
602 context->next = DeleteCase6; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
603 stack_push(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
604 goto meta(context, RotateL); |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
605 } |
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
606 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
607 goto meta(context, DeleteCase6); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
608 } |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
609 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
610 __code deleteCase5_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
611 goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
612 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
613 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
614 __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
615 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
616 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
617 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
618 allocator(context); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
619 struct Node* tmp = &context->data[context->dataNum]->node; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
620 *tmp = *sibling; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
621 tmp->parent = current; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
622 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
623 tmp->color = current->parent->color; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
624 current->parent->color = Black; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
625 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
626 context->next = Delete3; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
627 stack_push(context->code_stack, &context->next); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
628 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
629 if (current == current->parent->left) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
630 tmp->right->color = Black; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
631 tree->current = current->parent; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
632 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
633 goto meta(context, RotateL); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
634 } else { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
635 tmp->left->color = Black; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
636 tree->current = current->parent; |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
637 |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
638 goto meta(context, RotateR); |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
639 } |
73
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
640 } |
2667c3251a00
implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
72
diff
changeset
|
641 |
81
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
642 __code deleteCase6_stub(struct Context* context) { |
dc6f665bb753
implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
80
diff
changeset
|
643 goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); |
69
368306e1bfed
llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
65
diff
changeset
|
644 } |