annotate src/llrb/llrb.c @ 69:368306e1bfed

llrb deletion(not work).
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 20 Oct 2015 16:22:42 +0900
parents 025fd6e90597
children 5c4b9d116eda
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 #include "stack.h"
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
6
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
7 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
8 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
9
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
10 extern int num;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
11 extern stack_ptr node_stack;
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
13 __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
14 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
15 allocator(context);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
16
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);
56
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);
56
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
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) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
32 stack_push(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) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
37 stack_pop(node_stack, &tree->current);
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
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
40 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
41 if (tree->current->right->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
42 goto meta(context, RotateL);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
43
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
44 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
45 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
46 if (tree->current->left->color == Red && tree->current->left->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
47 goto meta(context, RotateR);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
48
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
49 if (tree->current->right != 0 && tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
50 if (tree->current->right->color == Red && tree->current->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
51 goto meta(context, ColorFlip);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
52
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
53 goto meta(context, FixUp);
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
54 } else if (result == 1) {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
55 tree->current = oldNode->right;
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
56 newNode->right = context->heap;
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
57 } else {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
58 tree->current = oldNode->left;
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
59 newNode->left = context->heap;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
60 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
61
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
62 allocator(context);
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
63
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
64 if (tree->current == 0) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
65 stack_pop(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
66 goto meta(context, Insert);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
67 } else {
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
68 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
69
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
70 goto meta(context, Replace);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
71 }
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
74 __code replaceNode_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
75 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
76 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
77
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
78 __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
79 node->color = Red;
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
80 *newNode = *node;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
81
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
82 if (tree->root == 0) {
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
83 newNode->color = Black;
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
84 tree->root = newNode;
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
85 tree->current = 0;
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
86 goto meta(context, context->next);
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
87 }
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
88
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
89 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
90 if (tree->current->right->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
91 goto meta(context, RotateL);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
92
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
93
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
94 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
95 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
96 if (tree->current->left->color == Red && tree->current->left->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
97 goto meta(context, RotateR);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
98
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
99 if (tree->current->right != 0 && tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
100 if (tree->current->right->color == Red && tree->current->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
101 goto meta(context, ColorFlip);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
102
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
103 goto meta(context, FixUp);
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
104 }
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
105
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
106 __code insertNode_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
107 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
108 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
109
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
110 __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
111 struct Node* tmp = node->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
112 node->right = tmp->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
113 tmp->left = node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
114 tmp->color = node->color;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
115 node->color = Red;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
116 tree->current = tmp;
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
117
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
118 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
119 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
120 if (tree->current->left->color == Red && tree->current->left->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
121 goto meta(context, RotateR);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
122
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
123 if (tree->current->right != 0 && tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
124 if (tree->current->right->color == Red && tree->current->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
125 goto meta(context, ColorFlip);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
126
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
127 goto meta(context, FixUp);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
128 }
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
129
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
130 __code rotateLeft_stub(struct Context* context) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
131 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
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 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
135 struct Node* tmp = node->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
136 node->left = tmp->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
137 tmp->right = 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 context->data[Tree]->tree.current = tmp;
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
141
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
142 if (tree->current->right != 0 && tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
143 if (tree->current->right->color == Red && tree->current->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
144 goto meta(context, ColorFlip);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
145
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
146 goto meta(context, FixUp);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
147 }
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
148
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
149 __code rotateRight_stub(struct Context* context) {
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
150 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
151 }
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
152
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
153 __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
154 node->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
155 node->left->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
156 node->right->color ^= 1;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
157
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
158 goto meta(context, FixUp);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
159 }
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
160
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
161 __code colorFlip_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
162 goto colorFlip(context, context->data[Tree]->tree.current);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
163 }
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
164
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
165 __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
166 node->key = newNode->key;
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
167 tree->prev = newNode;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
168
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
169 if (stack_pop(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
170 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
171 goto meta(context, ChangeRef);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
172 }
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
173
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
174 newNode->color = Black;
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
175 tree->root = newNode;
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
176 tree->current = 0;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
177
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 60
diff changeset
178 goto meta(context, context->next);
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
179 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
180
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
181 __code fixUp_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
182 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
183 }
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
184
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
185 __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
186 if (result == 1) {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
187 node->right = tree->prev;
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
188 } else if (result == -1) {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
189 node->left = tree->prev;
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
190 } else {
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
191 perror("bad status");
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
192 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
193
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
194 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
195 if (tree->current->right->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
196 goto meta(context, RotateL);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
197
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
198 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
199 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
200 if (tree->current->left->color == Red && tree->current->left->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
201 goto meta(context, RotateR);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
202
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
203 if (tree->current->right != 0 && tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
204 if (tree->current->right->color == Red && tree->current->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
205 goto meta(context, ColorFlip);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
206
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
207 goto meta(context, FixUp);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
208 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
209
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
210 __code changeReference_stub(struct Context* context) {
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
211 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
212 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
213
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
214 __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
215 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
216
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
217 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
218
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
219 if (tree->result == 0) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
220 goto meta(context, context->next);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
221 } else if (tree->result == 1) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
222 tree->current = tree->current->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
223 } else {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
224 tree->current = tree->current->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
225 }
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->current == 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
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
230 goto meta(context, Get);
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 __code get_stub(struct Context* context) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
234 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
235 }
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
236
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
237 __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
238 allocate->size = sizeof(struct Node);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
239 allocator(context);
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 tree->current = tree->root;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
242 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
243 goto meta(context, Replace_d);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
244 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
245
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
246 __code delete_stub(struct Context* context) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
247 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
248 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
249
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
250 __code replaceNode_d(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
251 *newNode = *oldNode;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
252 tree->current = newNode;
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
253
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
254 if (tree->result == -1) {
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 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
257 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
258 if (tree->current->left->color != Red && tree->current->left->left->color != Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
259 goto meta(context, MoveRedL);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
260
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
261 stack_push(node_stack, &tree->current);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
262
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
263 tree->current->left = context->heap;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
264 tree->current = oldNode->left;
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
265
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
266 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
267 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
268
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
269 goto meta(context, Replace_d);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
270 } else {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
271 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
272 if (tree->current->left->color = Red) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
273 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
274 *context->data[context->dataNum]->node = *tree->current->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
275 tree->current->left = context->data[context->dataNum]->node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
276
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
277 // roatate right
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
278 struct Node* tmp = tree->current->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
279 tree->current->left = tmp->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
280 tmp->right = tree->current;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
281 tmp->color = tree->current->color;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
282 tree->current->color = Red;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
283 tree->current = tmp;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
284 }
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
285
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
286 if (tree->result == 0 && tree->current->right == 0) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
287 stack_pop(node_stack, &tree->current);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
288
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
289 compare(context, tree, tree->current->key, context->data[Node]->node.key);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
290
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
291 if (tree->result == 1) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
292 tree->current->right = 0;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
293 } else {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
294 tree->current->left = 0;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
295 }
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
296
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
297 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
298 if (tree->current->right->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
299 goto meta(context, RotateL);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
300
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
301 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
302 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
303 if (tree->current->left->color == Red && tree->current->left->left->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
304 goto meta(context, RotateR);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
305
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
306 goto meta(context, FixUp);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
307 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
308
60
4e5b425922ce fix llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
309
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
310 if (tree->current->right != 0) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
311 if (tree->right->left != 0) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
312 if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
313 goto meta(context, MoveRedR);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
314 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
315 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
316
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
317 stack_push(node_stack, &tree->current);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
318
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
319 tree->current->right = context->heap;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
320 tree->current = oldNode->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
321
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
322 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
323
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
324 goto(context, Replace_d);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
325
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
326 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
327
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
328 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
329 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
330 goto meta(context, Replace_d);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
331 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
332
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
333 __code replaceNode_d_stub(struct Context* context) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
334 goto replaceNode_d(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, &context->data[Node]->node);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
335 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
336
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
337 __code moveRedLeft(struct Context* context, struct Node* node) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
338 // color flip
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
339 node->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
340 node->left->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
341 node->right->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
342
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
343 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
344 if (tree->current->right->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
345 if (tree->current->right->left == Red) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
346 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
347 *context->data[context->dataNum]->node = *node->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
348 node->right = context->data[context->dataNum]->node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
349
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
350 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
351 *context->data[context->dataNum]->node = *node->right->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
352 node->right->left = context->data[context->dataNum]->node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
353
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
354 // rotate right
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
355 struct Node* tmp = node->right->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
356 node->right->left = tmp->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
357 tmp->right = node->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
358 tmp->color = node->right->color;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
359 node->right->color = Red;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
360 node->right = tmp;
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
361
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
362 // rotate left
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
363 tmp = node->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
364 node->right = tmp->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
365 tmp->left = node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
366 tmp->color = node->color;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
367 node->color = Red;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
368
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
369 // color flip
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
370 node->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
371 node->left->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
372 node->right->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
373
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
374 tree->current = tmp;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
375 }
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 stack_push(node_stack, &tree->current);
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 tree->current->left = context->heap;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
380 tree->current = oldNode->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
381
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
382 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
383 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
384
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
385 goto meta(context, Replace_d);
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
386 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
387
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
388 __code moveRedRight(struct Context* context, struct Node* node) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
389 // color flip
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
390 node->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
391 node->left->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
392 node->right->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
393
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
394 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
395 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
396 if (tree->current->left->left == Red) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
397 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
398 *context->data[context->dataNum]->node = *node->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
399 node->left = context->data[context->dataNum]->node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
400
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
401 // rotate right
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
402 struct Node* tmp = node->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
403 node->left = tmp->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
404 tmp->right = node;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
405 tmp->color = node->color;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
406 node->color = Red;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
407
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
408 // color flip
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
409 node->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
410 node->left->color ^= 1;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
411 node->right->color ^= 1;
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
412
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
413 tree->current = tmp;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
414 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
415
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
416 stack_push(node_stack, &tree->current);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
417
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
418 tree->current->right = context->heap;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
419 tree->prev = tree->current;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
420 tree->current = oldNode->right;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
421
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
422 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
423 if (tree->result = 0) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
424 goto meta(context, DeleteMin);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
425 } else {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
426 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
427
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
428 goto meta(context, Replace_d);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
429 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
430 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
431
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
432 __code colorFlip_stub(struct Context* context) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
433 goto colorFlip(context, context->data[Tree]->tree.current);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
434 }
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
435
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
436 __code deleteMin(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
437 stack_push(node_stack, &newNode);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
438
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
439 *newNode = *oldNode;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
440 tree->current = newNode;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
441
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
442 if (tree->current->left == 0) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
443 newNode->left = 0;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
444
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
445 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
446 if (tree->current->right->color == Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
447 goto meta(context, RotateL);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
448
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
449 goto meta(context, FixUp);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
450 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
451
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
452 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
453 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
454 if (tree->current->left->color != Red && tree->current->left->left->color != Red)
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
455 goto meta(context, MoveRedL);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
456
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
457 tree->current = oldNode->left;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
458 newNode->left = context->heap;
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
459
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
460 allocator(context);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
461 goto meta(context, DeleteMin);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
462 }
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
463
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
464 __code max_stub(struct Context* context) {
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
465 goto max(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
466 }