Mercurial > hg > Members > innparusu > Gears

annotate src/llrb/llrb.c @ 74:724b65b1cfaf

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