GearsTemplate: src/parallel_execution/rb

annotate src/parallel_execution/rb_tree.c @ 119:b224aa7b80a0

remove code stack, stack clear is directly called

author	ikkun
date	Mon, 26 Sep 2016 20:20:16 +0900
parents	32773f506410
children	2493f4226ca6

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);
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	7 extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2);
86 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
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	11 __code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Allocate* allocate) {
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	12 // tree->root=allocator(context,struct Node);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	13 allocate->size = sizeof(struct Node);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	14 allocator(context);
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	15
a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	16 // we don't need this push
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	17 stack_push(context->code_stack, &context->next);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	18
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	19 tree->root = &context->data[context->dataNum]->node;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	20
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	21 if (root) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	22 traverse->current = root;
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	23 // traverse->result=compare(...)
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	24 compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
86 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) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	33 goto put(context,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	34 &context->data[Tree]->tree,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	35 &context->data[Traverse]->traverse,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	36 context->data[Tree]->tree.root,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	37 &context->data[Allocate]->allocate);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	38 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	39
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	40 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, int result) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	41 newNode = oldNode;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	42 stack_push(context->node_stack, &newNode);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	43
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	44 if (result == EQ) {
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	45 newNode->value = context->data[Node]->node.value;
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	46
a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	47 // go to stack clear
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	48 stack_pop(context->code_stack, &context->next);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	49 goto meta(context, context->next);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	50 } else if (result == GT) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	51 traverse->current = oldNode->right;
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	52 newNode->right = context->heap; // allocator(context,struct Node)
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	53 } else {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	54 traverse->current = oldNode->left;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	55 newNode->left = context->heap;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	56 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	57
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	58 allocator(context);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	59
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	60 if (traverse->current) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	61 compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	62 goto meta(context, Replace);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	63 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	64
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	65 goto meta(context, Insert);
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	68 __code replaceNode_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	69 goto replaceNode(context,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	70 &context->data[Traverse]->traverse,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	71 context->data[Traverse]->traverse.current,
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	72 &context->data[context->dataNum]->node, // new Node
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	73 context->data[Traverse]->traverse.result);
86 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
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	76 __code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	77 node->color = Red;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	78 newNode = node;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	79
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	80 traverse->current = newNode;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	81
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	82 goto meta(context, InsertCase1);
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	85 __code insertNode_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	86 goto insertNode(context,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	87 &context->data[Traverse]->traverse,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	88 &context->data[Node]->node,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	89 &context->data[context->dataNum]->node);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	90 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	91
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	92 // parent, grandparent and Node stack are input data segments
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	93 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	94 if (!isEmpty(context->node_stack)) // parent!=null
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	95 goto meta(context, InsertCase2);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	96
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	97 tree->root->color = Black;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	98
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	99 goto meta(context, StackClear);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	100 }
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 __code insert1_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	103 goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	104 }
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 __code insertCase2(struct Context* context, struct Node* current) {
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	107 struct Node* parent;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	108 stack_pop(context->node_stack, &parent);
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 if (parent->color == Black) {
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	111 goto meta(context, StackClear);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	112 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	113
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	114 stack_push(context->node_stack, &parent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	115 goto meta(context, InsertCase3);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	116 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	117
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	118 __code insert2_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	119 goto insertCase2(context, context->data[Traverse]->traverse.current);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	120 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	121
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	122 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* current) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	123 struct Node* parent;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	124 struct Node* uncle;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	125 struct Node* grandparent;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	126
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	127 stack_pop(context->node_stack, &parent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	128 stack_pop(context->node_stack, &grandparent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	129
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	130 if (grandparent->left == parent)
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	131 uncle = grandparent->right;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	132 else
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	133 uncle = grandparent->left;
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 if (uncle && (uncle->color == Red)) {
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	136 // do insertcase1 on grandparent, stack must be pop by two
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	137 parent->color = Black;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	138 uncle->color = Black;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	139 grandparent->color = Red;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	140 traverse->current = grandparent;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	141 goto meta(context, InsertCase1);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	142 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	143
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	144 stack_push(context->node_stack, &grandparent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	145 stack_push(context->node_stack, &parent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	146
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	147 goto meta(context, InsertCase4);
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	150 __code insert3_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	151 goto insertCase3(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
86 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
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	154 __code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	155 struct Node* parent;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	156 struct Node* grandparent;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	157
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	158 stack_pop(context->node_stack, &parent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	159 stack_pop(context->node_stack, &grandparent);
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->node_stack, &grandparent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	162
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	163 traverse->current = parent;
86 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 if ((current == parent->right) && (parent == grandparent->left)) {
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	166 traverse->rotateNext = InsertCase4_1;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	167 goto meta(context, RotateL);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	168 } else if ((current == parent->left) && (parent == grandparent->right)) {
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	169 traverse->rotateNext = InsertCase4_2;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	170 goto meta(context, RotateR);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	171 }
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 stack_push(context->node_stack, &parent);
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	174 traverse->current = current;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	175 goto meta(context, InsertCase5);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	176 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	177
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	178 __code insert4_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	179 goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	180 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	181
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	182 __code insertCase4_1(struct Context* context, struct Traverse* traverse) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	183 stack_push(context->node_stack, &traverse->current);
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	184 traverse->current = traverse->current->left;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	185 goto meta(context, InsertCase5);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	186 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	187
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	188 __code insert4_1_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	189 goto insertCase4_1(context, &context->data[Traverse]->traverse);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	190 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	191
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	192 __code insertCase4_2(struct Context* context, struct Traverse* traverse) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	193 stack_push(context->node_stack, &traverse->current);
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	194 traverse->current = traverse->current->right;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	195 goto meta(context, InsertCase5);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	196 }
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 __code insert4_2_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	199 goto insertCase4_2(context, &context->data[Traverse]->traverse);
86 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
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	202 __code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	203 struct Node* parent;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	204 struct Node* 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 stack_pop(context->node_stack, &parent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	207 stack_pop(context->node_stack, &grandparent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	208
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	209 parent->color = Black;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	210 grandparent->color = Red;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	211
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	212 traverse->current = grandparent;
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	213 traverse->rotateNext = StackClear;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	214 if ((current == parent->left) && (parent == grandparent->left))
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	215 goto meta(context, RotateR);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	216 else
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	217 goto meta(context, RotateL);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	218 }
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 __code insert5_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	221 goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	222 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	223
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	224 // put rotateLeft's continuation as argument
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	225 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	226 struct Node* tmp = node->right;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	227 struct Node* parent = 0;
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	228
a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	229 // if you have a pararent as an argument , we don't need stack operation
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	230 stack_pop(context->node_stack, &parent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	231
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	232 if (parent) {
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	233 if (node == parent->left)
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	234 parent->left = tmp;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	235 else
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	236 parent->right = tmp;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	237 } else {
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	238 tree->root = tmp;
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 stack_push(context->node_stack, &parent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	242
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	243 node->right = tmp->left;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	244 tmp->left = node;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	245 traverse->current = tmp;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	246
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	247 goto meta(context, traverse->rotateNext);
86 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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	250 __code rotateLeft_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	251 goto rotateLeft(context,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	252 context->data[Traverse]->traverse.current,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	253 &context->data[Tree]->tree,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	254 &context->data[Traverse]->traverse);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	255 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	256
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	257 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	258 struct Node* tmp = node->left;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	259 struct Node* parent = 0;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	260
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	261 stack_pop(context->node_stack, &parent);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	262
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	263 if (parent) {
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	264 if (node == parent->left)
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	265 parent->left = tmp;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	266 else
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	267 parent->right = tmp;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	268 } else {
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	269 tree->root = tmp;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	270 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	271
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	272 stack_push(context->node_stack, &parent);
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 node->left = tmp->right;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	275 tmp->right = node;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	276 traverse->current = tmp;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	277
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	278 goto meta(context, traverse->rotateNext);
86 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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	281 __code rotateRight_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	282 goto rotateRight(context,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	283 context->data[Traverse]->traverse.current,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	284 &context->data[Tree]->tree,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	285 &context->data[Traverse]->traverse);
86 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
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	288 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	289 if (stack_pop(node_stack, &traverse->current) == 0)
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	290 goto meta(context, StackClear);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	291
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	292 traverse->current = 0;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	293
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	294 goto meta(context, context->next);
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	297 __code stackClear_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	298 goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse);
86 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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	301
92 851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	302 __code get(struct Context* context, struct Tree* tree, struct Traverse* traverse) {
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	303 if (tree->root) {
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	304 traverse->current = tree->root;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	305
92 851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	306 goto meta(context, Search);
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	307 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	308
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	309 goto meta(context, context->next);
92 851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	310 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	311
92 851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	312 __code get_stub(struct Context* context) {
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	313 goto get(context, &context->data[Tree]->tree, &context->data[Traverse]->traverse);
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	314 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	315
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	316 __code search(struct Context* context, struct Traverse* traverse, struct Node* node) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	317 compare(context, traverse, traverse->current->key, node->key);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	318
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	319 if (traverse->result == EQ) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	320 node = traverse->current;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	321
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	322 goto meta(context, context->next);
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	323 } else if (traverse->result == GT) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	324 traverse->current = traverse->current->right;
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	325 } else {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	326 traverse->current = traverse->current->left;
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	327 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	328
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	329 if (traverse->current)
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	330 goto meta(context, Search);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	331
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	332 goto meta(context, context->next);
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	333 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	334
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	335 __code search_stub(struct Context* context) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	336 goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node);
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	337 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	338
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	339 /* /\* __code delete(struct Context* context, struct Tree* tree) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	340 /* /\* if (tree->root) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	341 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	342 /* /\* context->next = Delete1; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	343 /* /\* goto meta(context, Get); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	344 /* /\* } \/ /
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 /* /\* goto meta(context, context->next); \/ /
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	349 /* /\* __code delete_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	350 /* /\* goto delete(context, &context->data[Tree]->tree); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	351 /* /\* } \/ /
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 /* /\* __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	354 /* /\* allocate->size = sizeof(struct Node); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	355 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	356
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	357 /* /\* struct Node* root = tree->root; \/ /
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 /* /\* tree->root = &context->data[context->dataNum]->node; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	360 /* /\* tree->current = root; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	361
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	362 /* /\* 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	363
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	364 /* /\* goto meta(context, Replace_d1); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	365 /* /\* } \/ /
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 /* /\* __code delete1_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	368 /* /\* 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	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(struct Context* context, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	372 /* /\* if (current->color == Black) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	373 /* /\* struct Node* child = current->right == NULL ? current->left : current->right; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	374 /* /\* current->color = child == NULL ? Black : child->color; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	375
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	376 /* /\* goto meta(context, DeleteCase1); \/ /
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	379 /* /\* goto meta(context, Delete3); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	380 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	381
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	382 /* /\* __code delete2_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	383 /* /\* goto delete2(context, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	384 /* /\* } \/ /
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 /* /\* __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	387 /* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	388
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	389 /* /\* if (current->parent) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	390 /* /\* if (current == current->parent->left) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	391 /* /\* current->parent->left = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	392 /* /\* else \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	393 /* /\* current->parent->right = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	394 /* /\* } else { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	395 /* /\* tree->root = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	396 /* /\* } \/ /
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 /* /\* if (tmp) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	399 /* /\* tmp->parent = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	400
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	401 /* /\* if (current->parent == NULL && tmp) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	402 /* /\* tmp->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	403
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	404 /* /\* 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	405
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	406 /* /\* stack_pop(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	407 /* /\* goto meta(context, context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	408 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	409
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	410 /* /\* __code delete3_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	411 /* /\* 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	412 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	413
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	414 /* /\* __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	415 /* /\* newNode = oldNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	416
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	417 /* /\* if (result == EQ) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	418 /* /\* goto meta(context, Replace_d2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	419 /* /\* else if (result == GT) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	420 /* /\* tree->current = newNode->right; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	421 /* /\* else \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	422 /* /\* tree->current = newNode->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	423
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	424 /* /\* tree->current->parent = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	425
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	426 /* /\* if (tree->current->left == NULL && tree->current->right == NULL) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	427 /* /\* goto meta(context, Delete2); \/ /
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 /* /\* if (result == GT) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	430 /* /\* newNode->right = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	431 /* /\* else if (result == LT) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	432 /* /\* newNode->left = context->heap; \/ /
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 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	435
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	436 /* /\* 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	437
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	438 /* /\* goto meta(context, Replace_d1); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	439 /* /\* } \/ /
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 /* /\* __code replaceNodeForDelete1_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	442 /* /\* 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	443 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	444
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	445 /* /\* __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	446 /* /\* if (tree->current->left && tree->current->right) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	447 /* /\* newNode->left->parent = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	448 /* /\* tree->current = newNode->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	449 /* /\* newNode->left = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	450 /* /\* tree->deleted = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	451
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	452 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	453 /* /\* tree->current->parent = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	454
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	455 /* /\* goto meta(context, FindMax1); \/ /
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	458 /* /\* goto meta(context, Delete2); \/ /
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	461 /* /\* __code replaceNodeForDelete2_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	462 /* /\* 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	463 /* /\* } \/ /
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 /* /\* __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	466 /* /\* newNode = oldNode; \/ /
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 /* /\* if (newNode->right) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	469 /* /\* goto meta(context, FindMax2); \/ /
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 /* /\* tree->deleted->key = newNode->key; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	472 /* /\* tree->deleted->value = newNode->value; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	473
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	474 /* /\* tree->current = newNode; \/ /
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 /* /\* goto meta(context, Delete2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	477 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	478
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	479 /* /\* __code findMax1_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	480 /* /\* 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	481 /* /\* } \/ /
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	484 /* /\* __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	485 /* /\* newNode = oldNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	486
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	487 /* /\* if (newNode->right->right) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	488 /* /\* tree->current = newNode->right; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	489 /* /\* newNode->right = context->heap; \/ /
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 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	492 /* /\* tree->current->parent = newNode; \/ /
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 /* /\* goto meta(context, FindMax2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	495 /* /\* } \/ /
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 /* /\* tree->deleted->key = newNode->right->key; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	498 /* /\* tree->deleted->value = newNode->right->value; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	499
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	500 /* /\* tree->current = newNode; \/ /
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, Delete2); \/ /
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 findMax2_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	506 /* /\* 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	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 deleteCase1(struct Context* context, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	510 /* /\* if (current->parent) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	511 /* /\* goto meta(context, DeleteCase2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	512
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	513 /* /\* goto meta(context, Delete3); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	514 /* /\* } \/ /
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 /* /\* __code deleteCase1_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	517 /* /\* goto deleteCase1(context, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	518 /* /\* } \/ /
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 /* /\* __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	521 /* /\* 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	522
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	523 /* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	524 /* /\* current->parent->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	525 /* /\* sibling->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	526
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	527 /* /\* 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	528 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	529 /* /\* context->data[context->dataNum]->node = sibling; \/ */
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 /* /\* tree->current = current->parent; \/ /
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 /* /\* context->next = DeleteCase3; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	534 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	535
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	536 /* /\* if (current == current->parent->left) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	537 /* /\* goto meta(context, RotateL); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	538 /* /\* else \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	539 /* /\* goto meta(context, RotateR); \/ /
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	542 /* /\* goto meta(context, DeleteCase3); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	543 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	544
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	545 /* /\* __code deleteCase2_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	546 /* /\* 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	547 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	548
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	549 /* /\* __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	550 /* /\* 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	551
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	552 /* /\* if (current->parent->color == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	553 /* /\* (sibling == NULL ? Black : sibling->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	554 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	555 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	556 /* /\* sibling->color = Red; \/ /
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 /* /\* tree->current = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	559 /* /\* goto meta(context, DeleteCase1); \/ /
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	562 /* /\* goto meta(context, DeleteCase4); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	563 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	564
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	565 /* /\* __code deleteCase3_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	566 /* /\* 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	567 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	568
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	569 /* /\* __code deleteCase4(struct Context* context, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	570 /* /\* 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	571
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	572 /* /\* if (current->parent->color == Red && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	573 /* /\* (sibling == NULL ? Black : sibling->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	574 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	575 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	576 /* /\* sibling->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	577 /* /\* current->parent->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	578
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	579 /* /\* goto meta(context, Delete3); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	580 /* /\* } \/ /
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 /* /\* goto meta(context, DeleteCase5); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	583 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	584
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	585 /* /\* __code deleteCase4_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	586 /* /\* goto deleteCase4(context, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	587 /* /\* } \/ /
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 /* /\* __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	590 /* /\* 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	591 /* /\* sibling->parent = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	592
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	593 /* /\* if (current == current->parent->left && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	594 /* /\* (sibling == NULL ? Black : sibling->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	595 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	596 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	597 /* /\* sibling->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	598 /* /\* sibling->left->color = Black; \/ /
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 /* /\* 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	601 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	602 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	603 /* /\* tmp = sibling; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	604 /* /\* tmp->parent = current; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	605
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	606 /* /\* tmp->left = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	607 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	608 /* /\* context->data[context->dataNum]->node = sibling->left; \/ */
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	609 /* /\* context->data[context->dataNum]->node.parent = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	610
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	611 /* /\* tree->current = tmp; \/ /
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 /* /\* context->next = DeleteCase6; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	614 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	615
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	616 /* /\* goto meta(context, RotateR); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	617 /* /\* } else if (current == current->parent->right && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	618 /* /\* (sibling == NULL ? Black : sibling->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	619 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	620 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	621 /* /\* sibling->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	622 /* /\* sibling->right->color = Black; \/ /
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 /* /\* 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	625 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	626 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	627 /* /\* tmp = sibling; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	628 /* /\* tmp->parent = current; \/ /
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 /* /\* tmp->right = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	631 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	632 /* /\* context->data[context->dataNum]->node = sibling->right; \/ */
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	633 /* /\* context->data[context->dataNum]->node.parent = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	634
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	635 /* /\* tree->current = tmp; \/ /
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 /* /\* context->next = DeleteCase6; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	638 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	639 /* /\* goto meta(context, RotateL); \/ /
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
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	642 /* /\* goto meta(context, DeleteCase6); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	643 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	644
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	645 /* /\* __code deleteCase5_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	646 /* /\* 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	647 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	648
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	649 /* /\* __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	650 /* /\* 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	651
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	652 /* /\* 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	653 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	654 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	655 /* /\* tmp = sibling; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	656 /* /\* tmp->parent = current; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	657
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	658 /* /\* tmp->color = current->parent->color; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	659 /* /\* current->parent->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	660
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	661 /* /\* context->next = Delete3; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	662 /* /\* stack_push(context->code_stack, &context->next); \/ /
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 /* /\* if (current == current->parent->left) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	665 /* /\* tmp->right->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	666 /* /\* tree->current = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	667
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	668 /* /\* goto meta(context, RotateL); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	669 /* /\* } else { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	670 /* /\* tmp->left->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	671 /* /\* tree->current = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	672
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	673 /* /\* goto meta(context, RotateR); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	674 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	675 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	676
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	677 /* /\* __code deleteCase6_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	678 /* /\* 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	679 /* /\* } \/ /

Mercurial > hg > GearsTemplate

annotate src/parallel_execution/rb_tree.c @ 119:b224aa7b80a0