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

annotate src/llrb/llrb.c @ 80:099d85f9d371

refactoring

author	Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date	Mon, 30 Nov 2015 21:40:50 +0900
parents	618c03f25108
children	dc6f665bb753

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

Mercurial > hg > Members > innparusu > Gears

annotate src/llrb/llrb.c @ 80:099d85f9d371