Members/innparusu/Gears: src/llrb/llrb.c annotate

annotate src/llrb/llrb.c @ 77:618c03f25108

implement insert(tail recursion)

author	Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date	Fri, 27 Nov 2015 02:14:25 +0900
parents	7ad6d1502a03
children	099d85f9d371

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

Mercurial > hg > Members > innparusu > Gears

annotate src/llrb/llrb.c @ 77:618c03f25108