Gears/GearsAgda: src/llrb/llrb.c annotate

annotate src/llrb/llrb.c @ 72:5c4b9d116eda

use stack for code segment

author	Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date	Tue, 10 Nov 2015 01:59:04 +0900
parents	368306e1bfed
children	2667c3251a00

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
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	11 __code put(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	12 allocate->size = sizeof(struct Node);
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	13 allocator(context);
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	14
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	15 stack_push(context->code_stack, &context->next);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	16
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	17 if (tree->root == 0) {
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	18 goto meta(context, Insert);
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	19 } else {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	20 tree->current = tree->root;
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	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);
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	24 }
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	25 }
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	26
54 0299b90256e5 syntax suggest kkb parents: 53 diff changeset	27 __code put_stub(struct Context* context) {
0299b90256e5 syntax suggest kkb parents: 53 diff changeset	28 goto put(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
0299b90256e5 syntax suggest kkb parents: 53 diff changeset	29 }
0299b90256e5 syntax suggest kkb parents: 53 diff changeset	30
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	31 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	32 stack_push(context->node_stack, &newNode);
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	33
56 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
31 dbbafae822f8 modify Non-Destructive Red Black Tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 27 diff changeset	36 if (result == 0) {
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	37 stack_pop(context->node_stack, &tree->current);
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	38 newNode->value = context->data[Node]->node.value;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	39
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	40 goto meta(context, Balance1);
31 dbbafae822f8 modify Non-Destructive Red Black Tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 27 diff changeset	41 } else if (result == 1) {
56 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 {
56 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
42 44914699ee9b refactoring llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 31 diff changeset	51 if (tree->current == 0) {
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	52 stack_pop(context->node_stack, &tree->current);
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	53 goto meta(context, Insert);
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	54 } else {
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	55 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	56
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	57 goto meta(context, Replace);
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	58 }
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
56 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
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	65 __code balance1(struct Context* context, struct Node* current) {
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	66 if (current->right != 0)
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	67 if (current->right->color == Red) {
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	68 context->next = Balance2;
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	69
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	70 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	71 goto meta(context, RotateL);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	72 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	73
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	74 goto meta(context, Balance2);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	75 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	76
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	77 __code balance1_stub(struct Context* context) {
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	78 goto balance1(context, context->data[Tree]->tree.current);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	79 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	80
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	81 __code balance2(struct Context* context, struct Node* current) {
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	82 if (current->left != 0)
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	83 if (current->left->left != 0)
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	84 if (current->left->color == Red && current->left->left->color == Red) {
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	85 context->next = Balance3;
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	86
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	87 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	88 goto meta(context, RotateR);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	89 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	90
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	91 goto meta(context, Balance3);
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
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	94 __code balance2_stub(struct Context* context) {
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	95 goto balance2(context, context->data[Tree]->tree.current);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	96 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	97
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	98 __code balance3(struct Context* context, struct Node* current){
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	99 if (current->right != 0 && current->left != 0)
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	100 if (current->right->color == Red && current->left->color == Red) {
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	101 context->next = FixUp;
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	102
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	103 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	104 goto meta(context, ColorFlip);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	105 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	106
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	107 goto meta(context, FixUp);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	108 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	109
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	110 __code balance3_stub(struct Context* context) {
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	111 goto balance3(context, context->data[Tree]->tree.current);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	112 }
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	113
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	114 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	115 node->color = Red;
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	116 newNode = node;
23 868c2918b634 Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 22 diff changeset	117
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	118 if (tree->root == 0) {
44 a0a58875c93f refactoring llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 42 diff changeset	119 newNode->color = Black;
a0a58875c93f refactoring llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 42 diff changeset	120 tree->root = newNode;
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	121 tree->current = 0;
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	122
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	123 stack_pop(context->code_stack, &context->next);
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	124 goto meta(context, context->next);
20 324c44f2076f implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 19 diff changeset	125 }
324c44f2076f implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 19 diff changeset	126
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	127 goto meta(context, Balance1);
21 737a900518be implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 20 diff changeset	128 }
737a900518be implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 20 diff changeset	129
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	130 __code insertNode_stub(struct Context* context) {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	131 goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	132 }
23 868c2918b634 Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 22 diff changeset	133
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	134 __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	135 struct Node* tmp = node->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	136 node->right = tmp->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	137 tmp->left = node;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	138 tmp->color = node->color;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	139 node->color = Red;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	140 tree->current = tmp;
20 324c44f2076f implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 19 diff changeset	141
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	142 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	143 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	144 }
21 737a900518be implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 20 diff changeset	145
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	146 __code rotateLeft_stub(struct Context* context) {
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	147 goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	148 }
23 868c2918b634 Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 22 diff changeset	149
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	150 __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	151 struct Node* tmp = node->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	152 node->left = tmp->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	153 tmp->right = node;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	154 tmp->color = node->color;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	155 node->color = Red;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	156 context->data[Tree]->tree.current = tmp;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	157
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	158 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	159 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	160 }
27 44879c87c2dc modify Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 26 diff changeset	161
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	162 __code rotateRight_stub(struct Context* context) {
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	163 goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	164 }
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	165
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	166 __code colorFlip(struct Context* context, struct Node* node) {
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	167 node->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	168 node->left->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	169 node->right->color ^= 1;
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	170
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	171 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	172 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	173 }
20 324c44f2076f implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 19 diff changeset	174
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	175 __code colorFlip_stub(struct Context* context) {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	176 goto colorFlip(context, context->data[Tree]->tree.current);
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	177 }
27 44879c87c2dc modify Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 26 diff changeset	178
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	179 __code fixUp(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	180 node->key = newNode->key;
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	181 tree->prev = newNode;
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	182
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	183 if (stack_pop(context->node_stack, &tree->current) == 0) {
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	184 compare(context, tree, tree->current->key, node->key);
025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	185 goto meta(context, ChangeRef);
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	186 }
27 44879c87c2dc modify Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 26 diff changeset	187
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	188 newNode->color = Black;
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	189 tree->root = newNode;
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	190 tree->current = 0;
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	191
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	192 stack_pop(context->code_stack, &context->next);
65 025fd6e90597 to the function call(allocate and compare) Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 60 diff changeset	193 goto meta(context, context->next);
27 44879c87c2dc modify Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 26 diff changeset	194 }
44879c87c2dc modify Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 26 diff changeset	195
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	196 __code fixUp_stub(struct Context* context) {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	197 goto fixUp(context, &context->data[Tree]->tree, &context->data[Node]->node, context->data[Tree]->tree.current);
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	198 }
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	199
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	200 __code changeReference(struct Context* context, struct Tree* tree, struct Node* node, int result) {
31 dbbafae822f8 modify Non-Destructive Red Black Tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 27 diff changeset	201 if (result == 1) {
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	202 node->right = tree->prev;
31 dbbafae822f8 modify Non-Destructive Red Black Tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 27 diff changeset	203 } else if (result == -1) {
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	204 node->left = tree->prev;
31 dbbafae822f8 modify Non-Destructive Red Black Tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 27 diff changeset	205 } else {
dbbafae822f8 modify Non-Destructive Red Black Tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 27 diff changeset	206 perror("bad status");
27 44879c87c2dc modify Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 26 diff changeset	207 }
44879c87c2dc modify Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 26 diff changeset	208
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	209 goto meta(context, Balance1);
24 7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	210 }
7494c0b87ec4 implement insert of Non Destructive llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 23 diff changeset	211
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	212 __code changeReference_stub(struct Context* context) {
c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	213 goto changeReference(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, context->data[Tree]->tree.result);
46 348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	214 }
348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	215
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	216 __code get(struct Context* context, struct Tree* tree, struct Node* node) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	217 tree->current = (tree->current == 0)? tree->root : tree->current;
46 348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	218
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	219 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	220
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	221 if (tree->result == 0) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	222 goto meta(context, context->next);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	223 } else if (tree->result == 1) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	224 tree->current = tree->current->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	225 } else {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	226 tree->current = tree->current->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	227 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	228
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	229 if (tree->current == 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	230 goto meta(context, context->next);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	231
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	232 goto meta(context, Get);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	233 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	234
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	235 __code get_stub(struct Context* context) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	236 goto get(context, &context->data[Tree]->tree, &context->data[Node]->node);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	237 }
46 348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	238
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	239 __code delete(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	240 allocate->size = sizeof(struct Node);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	241 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	242
72 5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	243 stack_push(context->code_stack, &context->next);
5c4b9d116eda use stack for code segment Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 69 diff changeset	244
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	245 tree->current = tree->root;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	246 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	247 goto meta(context, Replace_d);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	248 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	249
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	250 __code delete_stub(struct Context* context) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	251 goto delete(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	252 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	253
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	254 __code replaceNode_d(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	255 newNode = oldNode;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	256 tree->current = newNode;
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	257
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	258 if (tree->result == -1) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	259
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	260 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	261 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	262 if (tree->current->left->color != Red && tree->current->left->left->color != Red)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	263 goto meta(context, MoveRedL);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	264
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	265 stack_push(node_stack, &tree->current);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	266
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	267 tree->current->left = context->heap;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	268 tree->current = oldNode->left;
21 737a900518be implement insert Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 20 diff changeset	269
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	270 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	271 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	272
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	273 goto meta(context, Replace_d);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	274 } else {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	275 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	276 if (tree->current->left->color = Red) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	277 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	278 context->data[context->dataNum]->node = tree->current->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	279 tree->current->left = context->data[context->dataNum]->node;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	280
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	281 // roatate right
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	282 struct Node* tmp = tree->current->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	283 tree->current->left = tmp->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	284 tmp->right = tree->current;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	285 tmp->color = tree->current->color;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	286 tree->current->color = Red;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	287 tree->current = tmp;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	288 }
42 44914699ee9b refactoring llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 31 diff changeset	289
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	290 if (tree->result == 0 && tree->current->right == 0) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	291 stack_pop(node_stack, &tree->current);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	292
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	293 compare(context, tree, tree->current->key, context->data[Node]->node.key);
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	294
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	295 if (tree->result == 1) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	296 tree->current->right = 0;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	297 } else {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	298 tree->current->left = 0;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	299 }
56 c469c5ed5b4d modify syntax Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 54 diff changeset	300
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	301 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	302 if (tree->current->right->color == Red)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	303 goto meta(context, RotateL);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	304
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	305 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	306 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	307 if (tree->current->left->color == Red && tree->current->left->left->color == Red)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	308 goto meta(context, RotateR);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	309
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	310 goto meta(context, FixUp);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	311 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	312
60 4e5b425922ce fix llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 56 diff changeset	313
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	314 if (tree->current->right != 0) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	315 if (tree->right->left != 0) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	316 if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	317 goto meta(context, MoveRedR);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	318 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	319 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	320
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	321 stack_push(node_stack, &tree->current);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	322
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	323 tree->current->right = context->heap;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	324 tree->current = oldNode->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	325
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	326 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	327
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	328 goto(context, Replace_d);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	329
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	330 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	331
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	332 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	333 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	334 goto meta(context, Replace_d);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	335 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	336
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	337 __code replaceNode_d_stub(struct Context* context) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	338 goto replaceNode_d(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, &context->data[Node]->node);
22 4c3c0ad4a75d add benchmark method Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 21 diff changeset	339 }
4c3c0ad4a75d add benchmark method Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 21 diff changeset	340
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	341 __code moveRedLeft(struct Context* context, struct Node* node) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	342 // color flip
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	343 node->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	344 node->left->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	345 node->right->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	346
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	347 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	348 if (tree->current->right->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	349 if (tree->current->right->left == Red) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	350 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	351 context->data[context->dataNum]->node = node->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	352 node->right = context->data[context->dataNum]->node;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	353
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	354 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	355 context->data[context->dataNum]->node = node->right->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	356 node->right->left = context->data[context->dataNum]->node;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	357
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	358 // rotate right
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	359 struct Node* tmp = node->right->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	360 node->right->left = tmp->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	361 tmp->right = node->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	362 tmp->color = node->right->color;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	363 node->right->color = Red;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	364 node->right = tmp;
46 348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	365
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	366 // rotate left
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	367 tmp = node->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	368 node->right = tmp->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	369 tmp->left = node;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	370 tmp->color = node->color;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	371 node->color = Red;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	372
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	373 // color flip
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	374 node->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	375 node->left->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	376 node->right->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	377
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	378 tree->current = tmp;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	379 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	380
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	381 stack_push(node_stack, &tree->current);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	382
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	383 tree->current->left = context->heap;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	384 tree->current = oldNode->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	385
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	386 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	387 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	388
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	389 goto meta(context, Replace_d);
46 348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	390 }
348148d8fdb1 implement get Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 44 diff changeset	391
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	392 __code moveRedRight(struct Context* context, struct Node* node) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	393 // color flip
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	394 node->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	395 node->left->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	396 node->right->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	397
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	398 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	399 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	400 if (tree->current->left->left == Red) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	401 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	402 context->data[context->dataNum]->node = node->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	403 node->left = context->data[context->dataNum]->node;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	404
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	405 // rotate right
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	406 struct Node* tmp = node->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	407 node->left = tmp->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	408 tmp->right = node;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	409 tmp->color = node->color;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	410 node->color = Red;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	411
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	412 // color flip
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	413 node->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	414 node->left->color ^= 1;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	415 node->right->color ^= 1;
22 4c3c0ad4a75d add benchmark method Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 21 diff changeset	416
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	417 tree->current = tmp;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	418 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	419
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	420 stack_push(node_stack, &tree->current);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	421
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	422 tree->current->right = context->heap;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	423 tree->prev = tree->current;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	424 tree->current = oldNode->right;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	425
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	426 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	427 if (tree->result = 0) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	428 goto meta(context, DeleteMin);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	429 } else {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	430 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	431
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	432 goto meta(context, Replace_d);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	433 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	434 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	435
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	436 __code colorFlip_stub(struct Context* context) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	437 goto colorFlip(context, context->data[Tree]->tree.current);
19 9302b1a48008 add llrb Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	438 }
69 368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	439
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	440 __code deleteMin(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	441 stack_push(node_stack, &newNode);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	442
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	443 newNode = oldNode;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	444 tree->current = newNode;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	445
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	446 if (tree->current->left == 0) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	447 newNode->left = 0;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	448
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	449 if (tree->current->right != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	450 if (tree->current->right->color == Red)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	451 goto meta(context, RotateL);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	452
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	453 goto meta(context, FixUp);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	454 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	455
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	456 if (tree->current->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	457 if (tree->current->left->left != 0)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	458 if (tree->current->left->color != Red && tree->current->left->left->color != Red)
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	459 goto meta(context, MoveRedL);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	460
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	461 tree->current = oldNode->left;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	462 newNode->left = context->heap;
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	463
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	464 allocator(context);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	465 goto meta(context, DeleteMin);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	466 }
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	467
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	468 __code max_stub(struct Context* context) {
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	469 goto max(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
368306e1bfed llrb deletion(not work). Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 65 diff changeset	470 }

Mercurial > hg > Gears > GearsAgda

annotate src/llrb/llrb.c @ 72:5c4b9d116eda