Mercurial > hg > Gears > GearsAgda

annotate src/llrb/llrb.c @ 76:7ad6d1502a03

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
refactoring
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 17 Nov 2015 16:59:48 +0900
parents 97387904add9
children 618c03f25108
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdio.h>
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 #include "llrbContext.h"
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
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
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
11 __code put(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
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);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
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
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
17 if (tree->root) {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
18 tree->current = tree->root;
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
19 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
20
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
21 goto meta(context, Replace);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
22 }
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
23
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
24 goto meta(context, Insert);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
25 }
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
26
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
27 __code put_stub(struct Context* context) {
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
28 goto put(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
29 }
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
30
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
31 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
32 stack_push(context->node_stack, &newNode);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
33
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
34 *newNode = *oldNode;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
35
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
36 if (result == 0) {
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
37 stack_pop(context->node_stack, &tree->current);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
38 newNode->value = context->data[Node]->node.value;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
39
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
40 goto meta(context, Balance1);
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
41 } else if (result == 1) {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
42 tree->current = oldNode->right;
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
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
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
45 tree->current = oldNode->left;
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
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
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
51 if (tree->current) {
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
52 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
53 goto meta(context, Replace);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
54 }
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
55
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
56 stack_pop(context->node_stack, &tree->current);
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
57 goto meta(context, Insert);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
60 __code replaceNode_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
61 goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
62 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
63
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
64 __code balance1(struct Context* context, struct Node* current) {
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
65 if (current->right)
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
66 if (current->right->color == Red) {
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
67 context->next = Balance2;
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
68
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
69 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
70 goto meta(context, RotateL);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
71 }
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
73 goto meta(context, Balance2);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
74 }
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
75
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
76 __code balance1_stub(struct Context* context) {
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
77 goto balance1(context, context->data[Tree]->tree.current);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
78 }
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
79
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
80 __code balance2(struct Context* context, struct Node* current) {
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
81 if (current->left)
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
82 if (current->left->left)
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
83 if (current->left->color == Red && current->left->left->color == Red) {
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
84 context->next = Balance3;
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
85
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
86 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
87 goto meta(context, RotateR);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
88 }
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
89
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
90 goto meta(context, Balance3);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
91 }
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 __code balance2_stub(struct Context* context) {
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
94 goto balance2(context, context->data[Tree]->tree.current);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
95 }
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
96
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
97 __code balance3(struct Context* context, struct Node* current){
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
98 if (current->right && current->left)
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
99 if (current->right->color == Red && current->left->color == Red) {
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
100 context->next = FixUp;
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 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
103 goto meta(context, ColorFlip);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
104 }
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 goto meta(context, FixUp);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
107 }
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
108
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
109 __code balance3_stub(struct Context* context) {
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
110 goto balance3(context, context->data[Tree]->tree.current);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
111 }
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
112
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
113 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
114 node->color = Red;
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
115 *newNode = *node;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
116
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
117 if (tree->root)
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
118 goto meta(context, Balance1);
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
119
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
120 tree->current = newNode;
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
121 goto meta(context, SetRoot);
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
122 }
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
123
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
124 __code insertNode_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
125 goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
126 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
127
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
128 __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
129 struct Node* tmp = node->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
130 node->right = tmp->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
131 tmp->left = node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
132 tmp->color = node->color;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
133 node->color = Red;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
134 tree->current = tmp;
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
135
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
136 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
137 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
138 }
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
139
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
140 __code rotateLeft_stub(struct Context* context) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
141 goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
142 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
143
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
144 __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
145 struct Node* tmp = node->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
146 node->left = tmp->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
147 tmp->right = node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
148 tmp->color = node->color;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
149 node->color = Red;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
150 context->data[Tree]->tree.current = tmp;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
151
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
152 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
153 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
154 }
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
155
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
156 __code rotateRight_stub(struct Context* context) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
157 goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
158 }
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
159
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
160 __code colorFlip(struct Context* context, struct Node* node) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
161 node->color ^= 1;
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
162
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
163 if (node->left)
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
164 node->left->color ^= 1;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
165
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
166 if (node->right)
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
167 node->right->color ^= 1;
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
168
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
169 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
170 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
171 }
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
172
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
173 __code colorFlip_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
174 goto colorFlip(context, context->data[Tree]->tree.current);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
175 }
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
176
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
177 __code fixUp(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
178 node->key = newNode->key;
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
179 tree->prev = newNode;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
180
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
181 if (stack_pop(context->node_stack, &tree->current) == 0) {
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
182 compare(context, tree, tree->current->key, node->key);
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
183 goto meta(context, ChangeRef);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
184 }
75
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
185
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
186 goto meta(context, SetRoot);
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
187 }
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
188
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
189 __code fixUp_stub(struct Context* context) {
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
190 goto fixUp(context, &context->data[Tree]->tree, &context->data[Node]->node, context->data[Tree]->tree.current);
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
191 }
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
192
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
193 __code setRoot(struct Context* context, struct Tree* tree, struct Node* node) {
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
194 tree->root = node;
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
195 tree->root->color = Black;
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
196 tree->current = 0;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
197
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
198 stack_pop(context->code_stack, &context->next);
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
199 goto meta(context, context->next);
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
200 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
201
75
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
202 __code setRoot_stub(struct Context* context) {
97387904add9 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 74
diff changeset
203 goto setRoot(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
204 }
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
205
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
206 __code changeReference(struct Context* context, struct Tree* tree, struct Node* node, int result) {
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
207 if (result == 1) {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
208 node->right = tree->prev;
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
209 } else if (result == -1) {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
210 node->left = tree->prev;
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
211 } else {
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
212 perror("bad status");
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
213 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
214
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
215 goto meta(context, Balance1);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
216 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
217
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
218 __code changeReference_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
219 goto changeReference(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, context->data[Tree]->tree.result);
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
220 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
221
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
222 __code get(struct Context* context, struct Tree* tree, struct Node* node) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
223 tree->current = (tree->current == 0)? tree->root : tree->current;
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
224
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
225 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
226
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
227 if (tree->result == 0) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
228 goto meta(context, context->next);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
229 } else if (tree->result == 1) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
230 tree->current = tree->current->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
231 } else {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
232 tree->current = tree->current->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
233 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
234
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
235 if (tree->current)
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
236 goto meta(context, Get);
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
237
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
238 goto meta(context, context->next);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
239 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
240
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
241 __code get_stub(struct Context* context) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
242 goto get(context, &context->data[Tree]->tree, &context->data[Node]->node);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
243 }
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
244
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
245 __code delete(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
246 allocate->size = sizeof(struct Node);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
247 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
248
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
249 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
250
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
251 tree->current = tree->root;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
252 compare(context, tree, tree->current->key, context->data[Node]->node.key);
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
253 goto meta(context, Replace_d1);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
254 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
255
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
256 __code delete_stub(struct Context* context) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
257 goto delete(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
258 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
259
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
260 __code replaceNode_d1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
261 *newNode = *oldNode;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
262 tree->current = newNode;
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
263
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
264 if (tree->result == -1) {
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
265 if (tree->current->left) {
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
266
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
267 if (tree->current->left->left)
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
268 if (tree->current->left->color != Red && tree->current->left->left->color != Red) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
269 context->next = MoveRedL1;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
270
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
271 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
272 goto meta(context, ColorFlip);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
273 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
274
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
275 stack_push(context->node_stack, &tree->current);
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
276
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
277 tree->current->left = context->heap;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
278 tree->current = oldNode->left;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
279
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
280 allocator(context);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
281 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
282
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
283 goto meta(context, Replace_d1);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
284 }
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
285 } else {
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
286 if (tree->current->left)
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
287 if (tree->current->left->color == Red) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
288 allocator(context);
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
289 context->data[context->dataNum]->node = *tree->current->left;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
290 tree->current->left = &context->data[context->dataNum]->node;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
291
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
292 context->next = Replace_d2;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
293 stack_push(context->code_stack, &context->next);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
294
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
295 goto meta(context, RotateR);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
296 }
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
297
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
298 goto meta(context, Replace_d2);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
299 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
300 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
301
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
302 __code replaceNode_d1_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
303 goto replaceNode_d1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, &context->data[Node]->node);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
304 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
305
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
306 __code replaceNode_d2(struct Context* context, struct Tree* tree) {
74
724b65b1cfaf modify deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 73
diff changeset
307 compare(context, tree, tree->current->key, context->data[Node]->node.key);
724b65b1cfaf modify deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 73
diff changeset
308
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
309 if (tree->result == 0 && tree->current->right == 0) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
310 stack_pop(context->node_stack, &tree->current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
311
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
312 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
313
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
314 if (tree->result == 1) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
315 tree->current->right = 0;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
316 } else {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
317 tree->current->left = 0;
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
318 }
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
319
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
320 goto meta(context, Balance1);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
321 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
322
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
323 goto meta(context, Replace_d3);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
324 }
60
4e5b425922ce fix llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
325
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
326 __code replaceNode_d2_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
327 goto replaceNode_d2(context, &context->data[Tree]->tree);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
328 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
329
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
330 __code replaceNode_d3(struct Context* context, struct Tree* tree) {
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
331 if (tree->current->right) {
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
332 if (tree->current->right->left)
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
333 if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
334 context->next = MoveRedR1;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
335 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
336
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
337 goto meta(context, ColorFlip);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
338 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
339
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
340 goto meta(context, Replace_d4);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
341 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
342 }
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
343
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
344 __code replaceNode_d3_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
345 goto replaceNode_d3(context, &context->data[Tree]->tree);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
346 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
347
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
348 __code replaceNode_d4(struct Context* context, struct Tree* tree, struct Node* node) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
349 stack_push(context->node_stack, &tree->current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
350
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
351 if (tree->result == 0) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
352 tree->current = node->right;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
353 goto meta(context, FindMin);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
354 } else {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
355 struct Node* next = node->right;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
356 tree->current->right = context->heap;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
357 tree->current = next;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
358
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
359 allocator(context);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
360
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
361 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
362
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
363 goto meta(context, Replace_d1);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
364 }
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
365 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
366
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
367 __code replaceNode_d4_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
368 goto replaceNode_d4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
369 }
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
370
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
371 __code moveRedLeft1(struct Context* context, struct Tree* tree, struct Node* node) {
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
372 if (tree->current->right)
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
373 if (tree->current->right->left)
74
724b65b1cfaf modify deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 73
diff changeset
374 if (tree->current->right->left->color == Red) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
375 allocator(context);
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
376 context->data[context->dataNum]->node = *node->right;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
377 node->right = &context->data[context->dataNum]->node;
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
378
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
379 allocator(context);
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
380 context->data[context->dataNum]->node = *node->right->left;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
381 node->right->left = &context->data[context->dataNum]->node;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
382
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
383 stack_push(context->node_stack, &tree->current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
384 tree->current = node->right;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
385
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
386 context->next = MoveRedL2;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
387 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
388
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
389 goto meta(context, RotateR);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
390 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
391
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
392 stack_pop(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
393 if (context->next == DeleteMin2)
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
394 goto meta(context, context->next);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
395
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
396 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
397 stack_push(context->node_stack, &tree->current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
398
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
399 struct Node* next = node->left;
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
400 tree->current->left = context->heap;
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
401 tree->current = next;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
402
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
403 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
404 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
405
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
406 goto meta(context, Replace_d1);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
407 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
408
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
409 __code moveRedLeft1_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
410 goto moveRedLeft1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
411 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
412
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
413 __code moveRedLeft2(struct Context* context, struct Tree* tree) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
414 stack_pop(context->node_stack, &tree->current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
415
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
416 context->next = MoveRedL3;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
417 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
418
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
419 context->next = ColorFlip;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
420 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
421
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
422 goto meta(context, RotateL);
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
423 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
424
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
425 __code moveRedLeft2_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
426 goto moveRedLeft2(context, &context->data[Tree]->tree);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
427 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
428
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
429 __code moveRedLeft3(struct Context* context, struct Tree* tree) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
430 stack_pop(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
431 if (context->next == DeleteMin2)
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
432 goto meta(context, context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
433
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
434 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
435 stack_push(context->node_stack, &tree->current);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
436
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
437 tree->current = tree->current->left;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
438
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
439 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
440
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
441 goto meta(context, Replace_d1);
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
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
444 __code moveRedLeft3_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
445 goto moveRedLeft3(context, &context->data[Tree]->tree);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
446 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
447
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
448 __code moveRedRight1(struct Context* context, struct Tree* tree, struct Node* node) {
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
449 if (tree->current->left)
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
450 if (tree->current->left->left)
74
724b65b1cfaf modify deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 73
diff changeset
451 if (tree->current->left->left->color == Red) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
452 allocator(context);
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
453 context->data[context->dataNum]->node = *node->left;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
454 node->left = &context->data[context->dataNum]->node;
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
455
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
456 context->next = MoveRedR2;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
457 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
458
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
459 context->next = ColorFlip;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
460 stack_push(context->code_stack, &context->next);
74
724b65b1cfaf modify deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 73
diff changeset
461
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
462 goto meta(context, RotateR);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
463 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
464
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
465 goto meta(context, Replace_d4);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
466 }
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
467
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
468 __code moveRedRight1_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
469 goto moveRedRight1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
470 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
471
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
472 __code moveRedRight2(struct Context* context, struct Tree* tree) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
473 stack_push(context->node_stack, &tree->current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
474 tree->current = tree->current->right;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
475
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
476 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
477
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
478 goto meta(context, Replace_d1);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
479 }
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
480
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
481 __code moveRedRight2_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
482 goto moveRedRight2(context, &context->data[Tree]->tree);
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
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
485 __code findMin(struct Context* context, struct Tree* tree, struct Node* tmp) {
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
486 if (tree->current->left) {
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
487 tree->current = tree->current->left;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
488
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
489 goto meta(context, FindMin);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
490 }
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
491
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
492 tmp->key = tree->current->key;
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
493 tmp->value = tree->current->value;
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
494
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
495 stack_pop(context->node_stack, &tree->current);
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
496
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
497 tree->current->key = tmp->key;
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
498 tree->current->value = tmp->value;
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
499
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
500 stack_push(context->node_stack, &tree->current);
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
501
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
502 struct Node* next = tree->current->right;
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
503
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
504 tree->current->right = context->heap;
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
505 tree->current = next;
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
506
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
507 allocator(context);
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
508
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
509 goto meta(context, DeleteMin1);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
510 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
511
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
512 __code findMin_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
513 goto findMin(context, &context->data[Tree]->tree, &context->data[Node]->node);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
514 }
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
515
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
516 __code deleteMin1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
517 *newNode = *oldNode;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
518 tree->current = newNode;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
519
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
520 if (tree->current->left == 0) {
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
521 struct Node* node = tree->current;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
522
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
523 stack_pop(context->node_stack, &tree->current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
524
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
525 compare(context, tree, tree->current->key, node->key);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
526
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
527 if (tree->result == -1) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
528 tree->current->left = 0;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
529 } else {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
530 tree->current->right = 0;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
531 }
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
532
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
533 goto meta(context, Balance1);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
534 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
535
76
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
536 if (tree->current->left)
7ad6d1502a03 refactoring
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
537 if (tree->current->left->left)
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
538 if (tree->current->left->color != Red && tree->current->left->left->color != Red) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
539 context->next = DeleteMin2;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
540 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
541
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
542 context->next = MoveRedL1;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
543 stack_push(context->code_stack, &context->next);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
544
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
545 goto meta(context, ColorFlip);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
546 }
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
547
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
548 goto meta(context, DeleteMin2);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
549 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
550
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
551 __code deleteMin1_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
552 goto deleteMin1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
553 }
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
554
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
555 __code deleteMin2(struct Context* context, struct Tree* tree, struct Node* node) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
556 stack_push(context->node_stack, &tree->current);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
557 tree->current->left = context->heap;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
558 tree->current = node->left;
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
559
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
560 allocator(context);
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
561 goto meta(context, DeleteMin1);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
562 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
563
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
564 __code deleteMin2_stub(struct Context* context) {
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
565 goto deleteMin2(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
566 }