Mercurial > hg > Members > Moririn

annotate src/tmp/rb_tree.c @ 86:e06e1a9e569e parallel_execution

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