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

annotate src/llrb/llrb.c @ 81:dc6f665bb753

implement delete(tail call). do not work

author	Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date	Fri, 11 Dec 2015 15:06:20 +0900
parents	099d85f9d371
children	c13575c3dbe9

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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	11 __code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) {
57 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);
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	17 tree->root = &context->data[context->dataNum]->node;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	18
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	19 if (root) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	20 tree->current = root;
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	21 compare(context, tree, tree->current->key, context->data[Node]->node.key);
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	22
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	23 goto meta(context, Replace);
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	24 }
76 7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	25
7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	26 goto meta(context, Insert);
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	27 }
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	28
54 0299b90256e5 syntax suggest kkb parents: 53 diff changeset	29 __code put_stub(struct Context* context) {
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	30 goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate);
54 0299b90256e5 syntax suggest kkb parents: 53 diff changeset	31 }
0299b90256e5 syntax suggest kkb parents: 53 diff changeset	32
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	33 __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	34 newNode = oldNode;
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	35
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	36 if (result == EQ) {
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	37 newNode->value = context->data[Node]->node.value;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	38
80 099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	39 stack_pop(context->code_stack, &context->next);
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	40 goto meta(context, context->next);
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	41 } else if (result == GT) {
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	42 tree->current = oldNode->right;
44 a0a58875c93f refactoring llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 42 diff changeset	43 newNode->right = context->heap;
31 dbbafae822f8 modify Non-Destructive Red Black Tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 27 diff changeset	44 } else {
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	45 tree->current = oldNode->left;
44 a0a58875c93f refactoring llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 42 diff changeset	46 newNode->left = context->heap;
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	47 }
7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	48
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	49 allocator(context);
025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	50
76 7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	51 if (tree->current) {
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	52 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	53 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	54 goto meta(context, Replace);
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	55 }
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	56
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	57 tree->current = newNode;
76 7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	58 goto meta(context, Insert);
19 9302b1a48008 add llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	59 }
9302b1a48008 add llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	60
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	61 __code replaceNode_stub(struct Context* context) {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	62 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	63 }
23 868c2918b634 Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 22 diff changeset	64
80 099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	65 __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	66 node->color = Red;
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	67 newNode = node;
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	68 newNode->parent = tree->current;
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	69
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	70 tree->current = newNode;
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	71
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	72 goto meta(context, InsertCase1);
80 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
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	75 __code insertNode_stub(struct Context* context) {
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	76 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	77 }
099d85f9d371 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	78
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	79 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	80 if (current->parent)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	81 goto meta(context, InsertCase2);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	82
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	83 tree->root->color = Black;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	84 tree->current = 0;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	85
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	86 stack_pop(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	87 goto meta(context, context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	88 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	89
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	90 __code insert1_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	91 goto insertCase1(context, &context->data[Tree]->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	92 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	93
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	94 __code insertCase2(struct Context* context, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	95 if (current->parent->color == Black) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	96 stack_pop(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	97 goto meta(context, context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	98 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	99
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	100 goto meta(context, InsertCase3);
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	101 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	102
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	103 __code insert2_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	104 goto insertCase2(context, context->data[Tree]->tree.current);
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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	107 __code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) {
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	108 struct Node* uncle;
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	109 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	110
77 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;
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	115
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	116 if (uncle && (uncle->color == Red)) {
77 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;
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	121 goto meta(context, InsertCase1);
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	122 }
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	123
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	124 goto meta(context, InsertCase4);
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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	127 __code insert3_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	128 goto insertCase3(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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	131 __code insertCase4(struct Context* context, struct Node* current) {
77 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)) {
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	135 context->next = InsertCase4_1;
77 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)) {
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	140 context->next = InsertCase4_2;
77 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	146 goto meta(context, InsertCase5);
77 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	149 __code insert4_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	150 goto insertCase4(context, context->data[Tree]->tree.current);
77 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	153 __code insertCase4_1(struct Context* context, struct Tree* tree) {
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	154 tree->current = tree->current->left;
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	155 goto meta(context, InsertCase5);
77 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	158 __code insert4_1_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	159 goto insertCase4_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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	162 __code insertCase4_2(struct Context* context, struct Tree* tree) {
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	163 tree->current = tree->current->right;
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	164 goto meta(context, InsertCase5);
77 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	167 __code insert4_2_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	168 goto insertCase4_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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	171 __code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) {
77 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	177 context->next = InsertCase5_1;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	178 stack_push(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	179
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	180 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	181 goto meta(context, RotateR);
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	182 else
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	183 goto meta(context, RotateL);
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	184 }
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	185
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	186 __code insert5_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	187 goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	188 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	189
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	190 __code insertCase5_1(struct Context* context, struct Tree* tree) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	191 tree->current = NULL;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	192
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	193 stack_pop(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	194 goto meta(context, context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	195 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	196
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	197 __code insert5_1_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	198 goto insertCase5_1(context, &context->data[context->dataNum]->tree);
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	199 }
23 868c2918b634 Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 22 diff changeset	200
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	201 __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	202 struct Node* tmp = node->right;
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	203
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	204 if (node->parent) {
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	205 if (node == node->parent->left)
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	206 node->parent->left = tmp;
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	207 else
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	208 node->parent->right = tmp;
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	209 } else {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	210 tree->root = tmp;
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	211 }
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	212
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	213 if (tmp)
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	214 tmp->parent = node->parent;
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	215
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	216 node->right = tmp->left;
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	217
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	218 if (tmp->left)
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	219 tmp->left->parent = node;
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	220
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	221 tmp->left = node;
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	222 node->parent = tmp;
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	223 tree->current = tmp;
20 324c44f2076f implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 19 diff changeset	224
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	225 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	226 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	227 }
21 737a900518be implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 20 diff changeset	228
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	229 __code rotateLeft_stub(struct Context* context) {
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	230 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	231 }
23 868c2918b634 Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 22 diff changeset	232
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	233 __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	234 struct Node* tmp = node->left;
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	235
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	236 if (node->parent) {
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	237 if (node == node->parent->left)
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	238 node->parent->left = tmp;
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	239 else
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	240 node->parent->right = tmp;
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	241 } else {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	242 tree->root = tmp;
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	243 }
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	244
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	245 if (tmp)
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	246 tmp->parent = node->parent;
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	247
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	248 node->left = tmp->right;
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	249
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	250 if (tmp->right)
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	251 tmp->right->parent = node;
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	252
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	253 tmp->right = node;
77 618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	254 node->parent = tmp;
618c03f25108 implement insert(tail recursion) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 76 diff changeset	255 tree->current = tmp;
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	256
72 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 }
27 44879c87c2dc modify Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 26 diff changeset	260
57 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	261 __code rotateRight_stub(struct Context* context) {
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	262 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	263 }
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	264
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	265 __code get(struct Context* context, struct Tree* tree) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	266 if (tree->root) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	267 tree->current = tree->root;
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	268
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	269 goto meta(context, Search);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	270 }
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	271
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	272 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	273 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	274 }
20 324c44f2076f implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 19 diff changeset	275
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	276 __code get_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	277 goto get(context, &context->data[Tree]->tree);
75 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	280 __code search(struct Context* context, struct Tree* tree, struct Node* node) {
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	281 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	282
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	283 if (tree->result == EQ) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	284 node = tree->current;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	285
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	286 goto meta(context, context->next);
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	287 } else if (tree->result == GT) {
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	288 tree->current = tree->current->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	289 } else {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	290 tree->current = tree->current->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	291 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	292
76 7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	293 if (tree->current)
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	294 goto meta(context, Search);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	295
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	296 stack_pop(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	297 goto meta(context, context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	298 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	299
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	300 __code search_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	301 goto search(context, &context->data[Tree]->tree, &context->data[Node]->node);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	302 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	303
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	304 __code delete(struct Context* context, struct Tree* tree) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	305 if (tree->root) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	306 stack_push(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	307 context->next = Delete1;
76 7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	308 goto meta(context, Get);
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	309 }
76 7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	310
7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	311 goto meta(context, context->next);
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	312 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	313
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	314 __code delete_stub(struct Context* context) {
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	315 goto delete(context, &context->data[Tree]->tree);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	316 }
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	317
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	318 __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	319 allocate->size = sizeof(struct Node);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	320 allocator(context);
74 724b65b1cfaf modify deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 73 diff changeset	321
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	322 struct Node* root = tree->root;
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	323
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	324 tree->root = &context->data[context->dataNum]->node;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	325 tree->current = root;
69 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 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	328
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	329 goto meta(context, Replace_d1);
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	330 }
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	331
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	332 __code delete1_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	333 goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	334 }
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	335
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	336 __code delete2(struct Context* context, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	337 if (current->color == Black) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	338 struct Node* child = current->right == NULL ? current->left : current->right;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	339 current->color = child == NULL ? Black : child->color;
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	340
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	341 goto meta(context, DeleteCase1);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	342 }
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	343
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	344 goto meta(context, Delete3);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	345 }
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	346
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	347 __code delete2_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	348 goto delete2(context, context->data[Tree]->tree.current);
47 348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	349 }
348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	350
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	351 __code delete3(struct Context* context, struct Tree* tree, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	352 struct Node* tmp = current->right == NULL ? current->left : current->right;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	353
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	354 if (current->parent) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	355 if (current == current->parent->left)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	356 current->parent->left = tmp;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	357 else
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	358 current->parent->right = tmp;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	359 } else {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	360 tree->root = tmp;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	361 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	362
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	363 if (tmp)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	364 tmp->parent = current->parent;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	365
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	366 if (current->parent == NULL && tmp)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	367 tmp->color = Black;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	368
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	369 current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	370
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	371 stack_pop(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	372 goto meta(context, context->next);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	373 }
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	374
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	375 __code delete3_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	376 goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	377 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	378
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	379 __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	380 newNode = oldNode;
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	381
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	382 if (result == EQ)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	383 goto meta(context, Replace_d2);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	384 else if (result == GT)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	385 tree->current = newNode->right;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	386 else
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	387 tree->current = newNode->left;
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	388
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	389 tree->current->parent = newNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	390
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	391 if (tree->current->left == NULL && tree->current->right == NULL)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	392 goto meta(context, Delete2);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	393
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	394 if (result == GT)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	395 newNode->right = context->heap;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	396 else if (result == LT)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	397 newNode->left = context->heap;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	398
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	399 allocator(context);
73 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 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	402
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	403 goto meta(context, Replace_d1);
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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	406 __code replaceNodeForDelete1_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	407 goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	408 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	409
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	410 __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	411 if (tree->current->left && tree->current->right) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	412 newNode->left->parent = newNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	413 tree->current = newNode->left;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	414 newNode->left = context->heap;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	415 tree->deleted = newNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	416
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	417 allocator(context);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	418 tree->current->parent = newNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	419
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	420 goto meta(context, FindMax1);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	421 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	422
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	423 goto meta(context, Delete2);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	424 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	425
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	426 __code replaceNodeForDelete2_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	427 goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	428 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	429
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	430 __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	431 newNode = oldNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	432
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	433 if (newNode->right)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	434 goto meta(context, FindMax2);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	435
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	436 tree->deleted->key = newNode->key;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	437 tree->deleted->value = newNode->value;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	438
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	439 tree->current = newNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	440
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	441 goto meta(context, Delete2);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	442 }
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	443
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	444 __code findMax1_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	445 goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	446 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	447
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	448
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	449 __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	450 newNode = oldNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	451
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	452 if (newNode->right->right) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	453 tree->current = newNode->right;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	454 newNode->right = context->heap;
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	455
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	456 allocator(context);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	457 tree->current->parent = newNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	458
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	459 goto meta(context, FindMax2);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	460 }
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	461
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	462 tree->deleted->key = newNode->right->key;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	463 tree->deleted->value = newNode->right->value;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	464
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	465 tree->current = newNode;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	466
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	467 goto meta(context, Delete2);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	468 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	469
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	470 __code findMax2_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	471 goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	472 }
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	473
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	474 __code deleteCase1(struct Context* context, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	475 if (current->parent)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	476 goto meta(context, DeleteCase2);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	477
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	478 goto meta(context, Delete3);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	479 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	480
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	481 __code deleteCase1_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	482 goto deleteCase1(context, context->data[Tree]->tree.current);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	483 }
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	484
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	485 __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	486 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	487
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	488 if ((sibling == NULL ? Black : sibling->color) == Red) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	489 current->parent->color = Red;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	490 sibling->color = Black;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	491
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	492 current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	493 allocator(context);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	494 context->data[context->dataNum]->node = *sibling;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	495
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	496 tree->current = current->parent;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	497
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	498 context->next = DeleteCase3;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	499 stack_push(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	500
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	501 if (current == current->parent->left)
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	502 goto meta(context, RotateL);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	503 else
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	504 goto meta(context, RotateR);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	505 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	506
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	507 goto meta(context, DeleteCase3);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	508 }
22 4c3c0ad4a75d add benchmark method Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 21 diff changeset	509
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	510 __code deleteCase2_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	511 goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	512 }
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	513
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	514 __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	515 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
76 7ad6d1502a03 refactoring Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 75 diff changeset	516
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	517 if (current->parent->color == Black &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	518 (sibling == NULL ? Black : sibling->color) == Black &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	519 (sibling->left == NULL ? Black : sibling->left->color) == Black &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	520 (sibling->right == NULL ? Black : sibling->right->color) == Black) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	521 sibling->color = Red;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	522
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	523 tree->current = current->parent;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	524 goto meta(context, DeleteCase1);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	525 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	526
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	527 goto meta(context, DeleteCase4);
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	528 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	529
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	530 __code deleteCase3_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	531 goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	532 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	533
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	534 __code deleteCase4(struct Context* context, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	535 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	536
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	537 if (current->parent->color == Red &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	538 (sibling == NULL ? Black : sibling->color) == Black &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	539 (sibling->left == NULL ? Black : sibling->left->color) == Black &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	540 (sibling->right == NULL ? Black : sibling->right->color) == Black) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	541 sibling->color = Red;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	542 current->parent->color = Black;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	543
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	544 goto meta(context, Delete3);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	545 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	546
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	547 goto meta(context, DeleteCase5);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	548 }
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	549
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	550 __code deleteCase4_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	551 goto deleteCase4(context, context->data[Tree]->tree.current);
19 9302b1a48008 add llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	552 }
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	553
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	554 __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	555 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	556 sibling->parent = current->parent;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	557
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	558 if (current == current->parent->left &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	559 (sibling == NULL ? Black : sibling->color) == Black &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	560 (sibling->left == NULL ? Black : sibling->left->color) == Red &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	561 (sibling->right == NULL ? Black : sibling->right->color) == Black) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	562 sibling->color = Red;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	563 sibling->left->color = Black;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	564
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	565 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	566 allocator(context);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	567 struct Node* tmp = &context->data[context->dataNum]->node;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	568 tmp = sibling;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	569 tmp->parent = current;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	570
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	571 tmp->left = context->heap;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	572 allocator(context);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	573 context->data[context->dataNum]->node = *sibling->left;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	574 context->data[context->dataNum]->node.parent = tmp;
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	575
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	576 tree->current = tmp;
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	577
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	578 context->next = DeleteCase6;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	579 stack_push(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	580
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	581 goto meta(context, RotateR);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	582 } else if (current == current->parent->right &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	583 (sibling == NULL ? Black : sibling->color) == Black &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	584 (sibling->left == NULL ? Black : sibling->left->color) == Black &&
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	585 (sibling->right == NULL ? Black : sibling->right->color) == Red) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	586 sibling->color = Red;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	587 sibling->right->color = Black;
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	588
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	589 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	590 allocator(context);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	591 struct Node* tmp = &context->data[context->dataNum]->node;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	592 tmp = sibling;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	593 tmp->parent = current;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	594
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	595 tmp->right = context->heap;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	596 allocator(context);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	597 context->data[context->dataNum]->node = *sibling->right;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	598 context->data[context->dataNum]->node.parent = tmp;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	599
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	600 tree->current = tmp;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	601
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	602 context->next = DeleteCase6;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	603 stack_push(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	604 goto meta(context, RotateL);
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	605 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	606
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	607 goto meta(context, DeleteCase6);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	608 }
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	609
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	610 __code deleteCase5_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	611 goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
73 2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	612 }
2667c3251a00 implement llrb deletion Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 72 diff changeset	613
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	614 __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	615 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	616
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	617 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	618 allocator(context);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	619 struct Node* tmp = &context->data[context->dataNum]->node;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	620 tmp = sibling;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	621 tmp->parent = current;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	622
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	623 tmp->color = current->parent->color;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	624 current->parent->color = Black;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	625
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	626 context->next = Delete3;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	627 stack_push(context->code_stack, &context->next);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	628
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	629 if (current == current->parent->left) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	630 tmp->right->color = Black;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	631 tree->current = current->parent;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	632
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	633 goto meta(context, RotateL);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	634 } else {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	635 tmp->left->color = Black;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	636 tree->current = current->parent;
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	637
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	638 goto meta(context, RotateR);
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	639 }
73 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
81 dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	642 __code deleteCase6_stub(struct Context* context) {
dc6f665bb753 implement delete(tail call). do not work Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 80 diff changeset	643 goto deleteCase6(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	644 }

Mercurial > hg > Members > innparusu > Gears

annotate src/llrb/llrb.c @ 81:dc6f665bb753