# HG changeset patch # User Shohei KOKUBO # Date 1449814030 -32400 # Node ID 69d0637e52fd1cb5411ed0fa716d676fc9c38243 # Parent dc6f665bb753bd24f7ca120d5420c6b40244b218# Parent ed9d6438d2a57a65f1a3a187b6bde78a921b7dac merge diff -r ed9d6438d2a5 -r 69d0637e52fd src/llrb/CMakeLists.txt --- a/src/llrb/CMakeLists.txt Fri Dec 04 18:32:34 2015 +0900 +++ b/src/llrb/CMakeLists.txt Fri Dec 11 15:07:10 2015 +0900 @@ -1,5 +1,7 @@ cmake_minimum_required(VERSION 2.8) +add_definitions("-Wall -g -O0") + set(CMAKE_C_COMPILER $ENV{CbC_Clang}/clang) add_executable(llrb diff -r ed9d6438d2a5 -r 69d0637e52fd src/llrb/compare.c --- a/src/llrb/compare.c Fri Dec 04 18:32:34 2015 +0900 +++ b/src/llrb/compare.c Fri Dec 11 15:07:10 2015 +0900 @@ -2,10 +2,10 @@ void compare(struct Context* context, struct Tree* tree, int key1, int key2) { if (key1 == key2) { - tree->result = 0; + tree->result = EQ; } else if (key1 < key2) { - tree->result = 1; + tree->result = GT; } else { - tree->result = -1; + tree->result = LT; } } diff -r ed9d6438d2a5 -r 69d0637e52fd src/llrb/llrb.c --- a/src/llrb/llrb.c Fri Dec 04 18:32:34 2015 +0900 +++ b/src/llrb/llrb.c Fri Dec 11 15:07:10 2015 +0900 @@ -8,14 +8,16 @@ extern int num; -__code put(struct Context* context, struct Tree* tree, struct Allocate* allocate) { +__code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) { allocate->size = sizeof(struct Node); allocator(context); - + stack_push(context->code_stack, &context->next); - if (tree->root) { - tree->current = tree->root; + tree->root = &context->data[context->dataNum]->node; + + if (root) { + tree->current = root; compare(context, tree, tree->current->key, context->data[Node]->node.key); goto meta(context, Replace); @@ -25,17 +27,18 @@ } __code put_stub(struct Context* context) { - goto put(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); + goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate); } __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *newNode = *oldNode; - if (result == 0) { + if (result == EQ) { newNode->value = context->data[Node]->node.value; - goto meta(context, SetRoot); - } else if (result == 1) { + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); + } else if (result == GT) { tree->current = oldNode->right; newNode->right = context->heap; } else { @@ -59,114 +62,6 @@ goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); } -__code balance1(struct Context* context, struct Node* current) { - if (current->parent == 0) - goto meta(context, SetRoot); - else - goto meta(context, Balance2); -} - -__code balance1_stub(struct Context* context) { - goto balance1(context, context->data[Tree]->tree.current); -} - -__code balance2(struct Context* context, struct Node* current) { - if (current->parent->color == Black) - goto meta(context, SetRoot); - else - goto meta(context, Balance3); -} - -__code balance2_stub(struct Context* context) { - goto balance2(context, context->data[Tree]->tree.current); -} - -__code balance3(struct Context* context, struct Tree* tree, struct Node* current) { - struct Node* uncle; - struct Node* grandparent = current->parent->parent; - - if (grandparent == 0) - uncle = 0; - - if (grandparent->left == current->parent) - uncle = grandparent->right; - else - uncle = grandparent->left; - - if ((uncle != 0) && (uncle->color == Red)) { - current->parent->color = Black; - uncle->color = Black; - grandparent->color = Red; - tree->current = grandparent; - goto meta(context, Balance1); - } else { - goto meta(context, Balance4); - } -} - -__code balance3_stub(struct Context* context) { - goto balance3(context, context->data[Tree], context->data[Tree]->tree.current); -} - -__code balance4(struct Context* context, struct Node* current) { - struct Node* grandparent = current->parent->parent; - - if ((current == current->parent->right) && (current->parent == grandparent->left)) { - context->next = Balance4_1; - - stack_push(context->code_stack, &context->next); - goto meta(context, RotateL); - } else if ((current == current->parent->left) && (current->parent == grandparent->right)) { - context->next = Balance4_2; - - stack_push(context->code_stack, &context->next); - goto meta(context, RotateR); - } - - goto meta(context, Balance5); -} - -__code balance4_stub(struct Context* context) { - goto balance4(context, context->data[Tree]->tree.current); -} - -__code balance4_1(struct Context* context, struct Tree* tree) { - tree->current = tree->current->left; - goto meta(context, Balance5); -} - -__code balance4_1_stub(struct Context* context) { - goto balance4_1(context, context->data[Tree]); -} - -__code balance4_2(struct Context* context, struct Tree* tree) { - tree->current = tree->current->right; - goto meta(context, Balance5); -} - -__code balance4_2_stub(struct Context* context) { - goto balance4_2(context, context->data[Tree]); -} - -__code balance5(struct Context* context, struct Tree* tree, struct Node* current) { - current->parent->color = Black; - current->parent->parent->color = Red; - - context->next = SetRoot; - - stack_push(context->code_stack, &context->next); - tree->current = current->parent->parent; - - if ((current == current->parent->left) && (current->parent == current->parent->parent->left)) - goto meta(context, RotateR); - else - goto meta(context, RotateL); -} - -__code balance5_stub(struct Context* context) { - goto balance5(context, context->data[Tree], context->data[Tree]->tree.current); -} - __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) { node->color = Red; *newNode = *node; @@ -174,31 +69,153 @@ tree->current = newNode; - goto meta(context, Balance1); + goto meta(context, InsertCase1); } __code insertNode_stub(struct Context* context) { goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node); } +__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) { + if (current->parent) + goto meta(context, InsertCase2); + + tree->root->color = Black; + tree->current = 0; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code insert1_stub(struct Context* context) { + goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +} + +__code insertCase2(struct Context* context, struct Node* current) { + if (current->parent->color == Black) { + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); + } + + goto meta(context, InsertCase3); +} + +__code insert2_stub(struct Context* context) { + goto insertCase2(context, context->data[Tree]->tree.current); +} + +__code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) { + struct Node* uncle; + struct Node* grandparent = current->parent->parent; + + if (grandparent->left == current->parent) + uncle = grandparent->right; + else + uncle = grandparent->left; + + if (uncle && (uncle->color == Red)) { + current->parent->color = Black; + uncle->color = Black; + grandparent->color = Red; + tree->current = grandparent; + goto meta(context, InsertCase1); + } + + goto meta(context, InsertCase4); +} + +__code insert3_stub(struct Context* context) { + goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +} + +__code insertCase4(struct Context* context, struct Node* current) { + struct Node* grandparent = current->parent->parent; + + if ((current == current->parent->right) && (current->parent == grandparent->left)) { + context->next = InsertCase4_1; + + stack_push(context->code_stack, &context->next); + goto meta(context, RotateL); + } else if ((current == current->parent->left) && (current->parent == grandparent->right)) { + context->next = InsertCase4_2; + + stack_push(context->code_stack, &context->next); + goto meta(context, RotateR); + } + + goto meta(context, InsertCase5); +} + +__code insert4_stub(struct Context* context) { + goto insertCase4(context, context->data[Tree]->tree.current); +} + +__code insertCase4_1(struct Context* context, struct Tree* tree) { + tree->current = tree->current->left; + goto meta(context, InsertCase5); +} + +__code insert4_1_stub(struct Context* context) { + goto insertCase4_1(context, &context->data[Tree]->tree); +} + +__code insertCase4_2(struct Context* context, struct Tree* tree) { + tree->current = tree->current->right; + goto meta(context, InsertCase5); +} + +__code insert4_2_stub(struct Context* context) { + goto insertCase4_2(context, &context->data[Tree]->tree); +} + +__code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) { + current->parent->color = Black; + current->parent->parent->color = Red; + + tree->current = current->parent->parent; + + context->next = InsertCase5_1; + stack_push(context->code_stack, &context->next); + + if ((current == current->parent->left) && (current->parent == current->parent->parent->left)) + goto meta(context, RotateR); + else + goto meta(context, RotateL); +} + +__code insert5_stub(struct Context* context) { + goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +} + +__code insertCase5_1(struct Context* context, struct Tree* tree) { + tree->current = NULL; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code insert5_1_stub(struct Context* context) { + goto insertCase5_1(context, &context->data[context->dataNum]->tree); +} + __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) { struct Node* tmp = node->right; - if (node->parent == 0) { - tree->root = tmp; - } else { + if (node->parent) { if (node == node->parent->left) node->parent->left = tmp; else node->parent->right = tmp; + } else { + tree->root = tmp; } - if (tmp != 0) + if (tmp) tmp->parent = node->parent; node->right = tmp->left; - if (tmp->left != 0) + if (tmp->left) tmp->left->parent = node; tmp->left = node; @@ -216,21 +233,21 @@ __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) { struct Node* tmp = node->left; - if (node->parent == 0) { - tree->root = tmp; - } else { + if (node->parent) { if (node == node->parent->left) node->parent->left = tmp; else node->parent->right = tmp; + } else { + tree->root = tmp; } - if (tmp != 0) + if (tmp) tmp->parent = node->parent; node->left = tmp->right; - if (tmp->right != 0) + if (tmp->right) tmp->right->parent = node; tmp->right = node; @@ -245,415 +262,383 @@ goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree); } -__code colorFlip(struct Context* context, struct Node* node) { - node->color ^= 1; +__code get(struct Context* context, struct Tree* tree) { + if (tree->root) { + tree->current = tree->root; - if (node->left) - node->left->color ^= 1; - - if (node->right) - node->right->color ^= 1; + goto meta(context, Search); + } stack_pop(context->code_stack, &context->next); goto meta(context, context->next); } -__code colorFlip_stub(struct Context* context) { - goto colorFlip(context, context->data[Tree]->tree.current); -} - -__code fixUp(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) { - node->key = newNode->key; - tree->prev = newNode; - - if (stack_pop(context->node_stack, &tree->current) == 0) { - compare(context, tree, tree->current->key, node->key); - goto meta(context, ChangeRef); - } - - goto meta(context, SetRoot); -} - -__code fixUp_stub(struct Context* context) { - goto fixUp(context, &context->data[Tree]->tree, &context->data[Node]->node, context->data[Tree]->tree.current); +__code get_stub(struct Context* context) { + goto get(context, &context->data[Tree]->tree); } -__code setRoot(struct Context* context, struct Tree* tree, struct Node* node) { - if(node->parent) { - tree->current = tree->current->parent; - goto meta(context, SetRoot); - } - - tree->root = node; - tree->root->color = Black; - tree->current = 0; - - stack_pop(context->code_stack, &context->next); - goto meta(context, context->next); -} - -__code setRoot_stub(struct Context* context) { - goto setRoot(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); -} - -__code changeReference(struct Context* context, struct Tree* tree, struct Node* node, int result) { - if (result == 1) { - node->right = tree->prev; - } else if (result == -1) { - node->left = tree->prev; - } else { - perror("bad status"); - } - - goto meta(context, Balance1); -} - -__code changeReference_stub(struct Context* context) { - goto changeReference(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, context->data[Tree]->tree.result); -} - -__code get(struct Context* context, struct Tree* tree, struct Node* node) { - tree->current = (tree->current == 0)? tree->root : tree->current; - +__code search(struct Context* context, struct Tree* tree, struct Node* node) { compare(context, tree, tree->current->key, node->key); - if (tree->result == 0) { + if (tree->result == EQ) { + *node = *tree->current; + goto meta(context, context->next); - } else if (tree->result == 1) { + } else if (tree->result == GT) { tree->current = tree->current->right; } else { tree->current = tree->current->left; } if (tree->current) + goto meta(context, Search); + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code search_stub(struct Context* context) { + goto search(context, &context->data[Tree]->tree, &context->data[Node]->node); +} + +__code delete(struct Context* context, struct Tree* tree) { + if (tree->root) { + stack_push(context->code_stack, &context->next); + context->next = Delete1; goto meta(context, Get); + } goto meta(context, context->next); } -__code get_stub(struct Context* context) { - goto get(context, &context->data[Tree]->tree, &context->data[Node]->node); -} - -__code delete(struct Context* context, struct Tree* tree, struct Allocate* allocate) { - allocate->size = sizeof(struct Node); - allocator(context); - - stack_push(context->code_stack, &context->next); - - tree->current = tree->root; - compare(context, tree, tree->current->key, context->data[Node]->node.key); - goto meta(context, Replace_d1); -} - __code delete_stub(struct Context* context) { - goto delete(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); -} - -__code replaceNode_d1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) { - *newNode = *oldNode; - tree->current = newNode; - - if (tree->result == -1) { - if (tree->current->left) { - - if (tree->current->left->left) - if (tree->current->left->color != Red && tree->current->left->left->color != Red) { - context->next = MoveRedL1; - - stack_push(context->code_stack, &context->next); - goto meta(context, ColorFlip); - } - - stack_push(context->node_stack, &tree->current); - - tree->current->left = context->heap; - tree->current = oldNode->left; - - allocator(context); - compare(context, tree, tree->current->key, context->data[Node]->node.key); - - goto meta(context, Replace_d1); - } - } else { - if (tree->current->left) - if (tree->current->left->color == Red) { - allocator(context); - context->data[context->dataNum]->node = *tree->current->left; - tree->current->left = &context->data[context->dataNum]->node; - - context->next = Replace_d2; - stack_push(context->code_stack, &context->next); - - goto meta(context, RotateR); - } - - goto meta(context, Replace_d2); - } -} - -__code replaceNode_d1_stub(struct Context* context) { - goto replaceNode_d1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, &context->data[Node]->node); + goto delete(context, &context->data[Tree]->tree); } -__code replaceNode_d2(struct Context* context, struct Tree* tree) { - compare(context, tree, tree->current->key, context->data[Node]->node.key); +__code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { + allocate->size = sizeof(struct Node); + allocator(context); - if (tree->result == 0 && tree->current->right == 0) { - stack_pop(context->node_stack, &tree->current); - - compare(context, tree, tree->current->key, context->data[Node]->node.key); - - if (tree->result == 1) { - tree->current->right = 0; - } else { - tree->current->left = 0; - } - - goto meta(context, Balance1); - } - - goto meta(context, Replace_d3); -} - -__code replaceNode_d2_stub(struct Context* context) { - goto replaceNode_d2(context, &context->data[Tree]->tree); -} - -__code replaceNode_d3(struct Context* context, struct Tree* tree) { - if (tree->current->right) { - if (tree->current->right->left) - if (tree->current->right->color != Red && tree->current->right->left->color != Red) { - context->next = MoveRedR1; - stack_push(context->code_stack, &context->next); - - goto meta(context, ColorFlip); - } - - goto meta(context, Replace_d4); - } -} - -__code replaceNode_d3_stub(struct Context* context) { - goto replaceNode_d3(context, &context->data[Tree]->tree); -} - -__code replaceNode_d4(struct Context* context, struct Tree* tree, struct Node* node) { - stack_push(context->node_stack, &tree->current); + struct Node* root = tree->root; - if (tree->result == 0) { - tree->current = node->right; - goto meta(context, FindMin); - } else { - struct Node* next = node->right; - tree->current->right = context->heap; - tree->current = next; - - allocator(context); - - compare(context, tree, tree->current->key, context->data[Node]->node.key); - - goto meta(context, Replace_d1); - } -} - -__code replaceNode_d4_stub(struct Context* context) { - goto replaceNode_d4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); -} + tree->root = &context->data[context->dataNum]->node; + tree->current = root; -__code moveRedLeft1(struct Context* context, struct Tree* tree, struct Node* node) { - if (tree->current->right) - if (tree->current->right->left) - if (tree->current->right->left->color == Red) { - allocator(context); - context->data[context->dataNum]->node = *node->right; - node->right = &context->data[context->dataNum]->node; - - allocator(context); - context->data[context->dataNum]->node = *node->right->left; - node->right->left = &context->data[context->dataNum]->node; - - stack_push(context->node_stack, &tree->current); - tree->current = node->right; - - context->next = MoveRedL2; - stack_push(context->code_stack, &context->next); - - goto meta(context, RotateR); - } - - stack_pop(context->code_stack, &context->next); - if (context->next == DeleteMin2) - goto meta(context, context->next); - - stack_push(context->code_stack, &context->next); - stack_push(context->node_stack, &tree->current); - - struct Node* next = node->left; - tree->current->left = context->heap; - tree->current = next; - - allocator(context); compare(context, tree, tree->current->key, context->data[Node]->node.key); goto meta(context, Replace_d1); } -__code moveRedLeft1_stub(struct Context* context) { - goto moveRedLeft1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +__code delete1_stub(struct Context* context) { + goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); } - -__code moveRedLeft2(struct Context* context, struct Tree* tree) { - stack_pop(context->node_stack, &tree->current); + +__code delete2(struct Context* context, struct Node* current) { + if (current->color == Black) { + struct Node* child = current->right == NULL ? current->left : current->right; + current->color = child == NULL ? Black : child->color; - context->next = MoveRedL3; - stack_push(context->code_stack, &context->next); + goto meta(context, DeleteCase1); + } - context->next = ColorFlip; - stack_push(context->code_stack, &context->next); + goto meta(context, Delete3); +} - goto meta(context, RotateL); +__code delete2_stub(struct Context* context) { + goto delete2(context, context->data[Tree]->tree.current); } -__code moveRedLeft2_stub(struct Context* context) { - goto moveRedLeft2(context, &context->data[Tree]->tree); +__code delete3(struct Context* context, struct Tree* tree, struct Node* current) { + struct Node* tmp = current->right == NULL ? current->left : current->right; + + if (current->parent) { + if (current == current->parent->left) + current->parent->left = tmp; + else + current->parent->right = tmp; + } else { + tree->root = tmp; + } + + if (tmp) + tmp->parent = current->parent; + + if (current->parent == NULL && tmp) + tmp->color = Black; + + current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); } -__code moveRedLeft3(struct Context* context, struct Tree* tree) { - stack_pop(context->code_stack, &context->next); - if (context->next == DeleteMin2) - goto meta(context, context->next); +__code delete3_stub(struct Context* context) { + goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +} + +__code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { + *newNode = *oldNode; - stack_push(context->code_stack, &context->next); - stack_push(context->node_stack, &tree->current); + if (result == EQ) + goto meta(context, Replace_d2); + else if (result == GT) + tree->current = newNode->right; + else + tree->current = newNode->left; - tree->current = tree->current->left; + tree->current->parent = newNode; + + if (tree->current->left == NULL && tree->current->right == NULL) + goto meta(context, Delete2); + + if (result == GT) + newNode->right = context->heap; + else if (result == LT) + newNode->left = context->heap; + + allocator(context); compare(context, tree, tree->current->key, context->data[Node]->node.key); goto meta(context, Replace_d1); } -__code moveRedLeft3_stub(struct Context* context) { - goto moveRedLeft3(context, &context->data[Tree]->tree); +__code replaceNodeForDelete1_stub(struct Context* context) { + goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); +} + +__code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { + if (tree->current->left && tree->current->right) { + newNode->left->parent = newNode; + tree->current = newNode->left; + newNode->left = context->heap; + tree->deleted = newNode; + + allocator(context); + tree->current->parent = newNode; + + goto meta(context, FindMax1); + } + + goto meta(context, Delete2); +} + +__code replaceNodeForDelete2_stub(struct Context* context) { + goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); +} + +__code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { + *newNode = *oldNode; + + if (newNode->right) + goto meta(context, FindMax2); + + tree->deleted->key = newNode->key; + tree->deleted->value = newNode->value; + + tree->current = newNode; + + goto meta(context, Delete2); } -__code moveRedRight1(struct Context* context, struct Tree* tree, struct Node* node) { - if (tree->current->left) - if (tree->current->left->left) - if (tree->current->left->left->color == Red) { - allocator(context); - context->data[context->dataNum]->node = *node->left; - node->left = &context->data[context->dataNum]->node; - - context->next = MoveRedR2; - stack_push(context->code_stack, &context->next); +__code findMax1_stub(struct Context* context) { + goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); +} + + +__code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { + *newNode = *oldNode; + + if (newNode->right->right) { + tree->current = newNode->right; + newNode->right = context->heap; - context->next = ColorFlip; - stack_push(context->code_stack, &context->next); - - goto meta(context, RotateR); - } + allocator(context); + tree->current->parent = newNode; + + goto meta(context, FindMax2); + } - goto meta(context, Replace_d4); + tree->deleted->key = newNode->right->key; + tree->deleted->value = newNode->right->value; + + tree->current = newNode; + + goto meta(context, Delete2); +} + +__code findMax2_stub(struct Context* context) { + goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); } -__code moveRedRight1_stub(struct Context* context) { - goto moveRedRight1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +__code deleteCase1(struct Context* context, struct Node* current) { + if (current->parent) + goto meta(context, DeleteCase2); + + goto meta(context, Delete3); +} + +__code deleteCase1_stub(struct Context* context) { + goto deleteCase1(context, context->data[Tree]->tree.current); } -__code moveRedRight2(struct Context* context, struct Tree* tree) { - stack_push(context->node_stack, &tree->current); - tree->current = tree->current->right; +__code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { + struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; - compare(context, tree, tree->current->key, context->data[Node]->node.key); - - goto meta(context, Replace_d1); + if ((sibling == NULL ? Black : sibling->color) == Red) { + current->parent->color = Red; + sibling->color = Black; + + current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); + allocator(context); + context->data[context->dataNum]->node = *sibling; + + tree->current = current->parent; + + context->next = DeleteCase3; + stack_push(context->code_stack, &context->next); + + if (current == current->parent->left) + goto meta(context, RotateL); + else + goto meta(context, RotateR); + } + + goto meta(context, DeleteCase3); } -__code moveRedRight2_stub(struct Context* context) { - goto moveRedRight2(context, &context->data[Tree]->tree); +__code deleteCase2_stub(struct Context* context) { + goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); } -__code findMin(struct Context* context, struct Tree* tree, struct Node* tmp) { - if (tree->current->left) { - tree->current = tree->current->left; - - goto meta(context, FindMin); - } - - tmp->key = tree->current->key; - tmp->value = tree->current->value; - - stack_pop(context->node_stack, &tree->current); +__code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { + struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; - tree->current->key = tmp->key; - tree->current->value = tmp->value; - - stack_push(context->node_stack, &tree->current); - - struct Node* next = tree->current->right; - - tree->current->right = context->heap; - tree->current = next; - - allocator(context); - - goto meta(context, DeleteMin1); + if (current->parent->color == Black && + (sibling == NULL ? Black : sibling->color) == Black && + (sibling->left == NULL ? Black : sibling->left->color) == Black && + (sibling->right == NULL ? Black : sibling->right->color) == Black) { + sibling->color = Red; + + tree->current = current->parent; + goto meta(context, DeleteCase1); + } + + goto meta(context, DeleteCase4); } -__code findMin_stub(struct Context* context) { - goto findMin(context, &context->data[Tree]->tree, &context->data[Node]->node); +__code deleteCase3_stub(struct Context* context) { + goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +} + +__code deleteCase4(struct Context* context, struct Node* current) { + struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; + + if (current->parent->color == Red && + (sibling == NULL ? Black : sibling->color) == Black && + (sibling->left == NULL ? Black : sibling->left->color) == Black && + (sibling->right == NULL ? Black : sibling->right->color) == Black) { + sibling->color = Red; + current->parent->color = Black; + + goto meta(context, Delete3); + } + + goto meta(context, DeleteCase5); +} + +__code deleteCase4_stub(struct Context* context) { + goto deleteCase4(context, context->data[Tree]->tree.current); } -__code deleteMin1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { - *newNode = *oldNode; - tree->current = newNode; +__code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { + struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; + sibling->parent = current->parent; + + if (current == current->parent->left && + (sibling == NULL ? Black : sibling->color) == Black && + (sibling->left == NULL ? Black : sibling->left->color) == Red && + (sibling->right == NULL ? Black : sibling->right->color) == Black) { + sibling->color = Red; + sibling->left->color = Black; + + sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); + allocator(context); + struct Node* tmp = &context->data[context->dataNum]->node; + *tmp = *sibling; + tmp->parent = current; + + tmp->left = context->heap; + allocator(context); + context->data[context->dataNum]->node = *sibling->left; + context->data[context->dataNum]->node.parent = tmp; - if (tree->current->left == 0) { - struct Node* node = tree->current; - - stack_pop(context->node_stack, &tree->current); + tree->current = tmp; - compare(context, tree, tree->current->key, node->key); + context->next = DeleteCase6; + stack_push(context->code_stack, &context->next); + + goto meta(context, RotateR); + } else if (current == current->parent->right && + (sibling == NULL ? Black : sibling->color) == Black && + (sibling->left == NULL ? Black : sibling->left->color) == Black && + (sibling->right == NULL ? Black : sibling->right->color) == Red) { + sibling->color = Red; + sibling->right->color = Black; - if (tree->result == -1) { - tree->current->left = 0; - } else { - tree->current->right = 0; - } - - goto meta(context, Balance1); + sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); + allocator(context); + struct Node* tmp = &context->data[context->dataNum]->node; + *tmp = *sibling; + tmp->parent = current; + + tmp->right = context->heap; + allocator(context); + context->data[context->dataNum]->node = *sibling->right; + context->data[context->dataNum]->node.parent = tmp; + + tree->current = tmp; + + context->next = DeleteCase6; + stack_push(context->code_stack, &context->next); + goto meta(context, RotateL); } - if (tree->current->left) - if (tree->current->left->left) - if (tree->current->left->color != Red && tree->current->left->left->color != Red) { - context->next = DeleteMin2; - stack_push(context->code_stack, &context->next); + goto meta(context, DeleteCase6); +} - context->next = MoveRedL1; - stack_push(context->code_stack, &context->next); - - goto meta(context, ColorFlip); - } - - goto meta(context, DeleteMin2); +__code deleteCase5_stub(struct Context* context) { + goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); } -__code deleteMin1_stub(struct Context* context) { - goto deleteMin1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); +__code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { + struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; + + sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); + allocator(context); + struct Node* tmp = &context->data[context->dataNum]->node; + *tmp = *sibling; + tmp->parent = current; + + tmp->color = current->parent->color; + current->parent->color = Black; + + context->next = Delete3; + stack_push(context->code_stack, &context->next); + + if (current == current->parent->left) { + tmp->right->color = Black; + tree->current = current->parent; + + goto meta(context, RotateL); + } else { + tmp->left->color = Black; + tree->current = current->parent; + + goto meta(context, RotateR); + } } -__code deleteMin2(struct Context* context, struct Tree* tree, struct Node* node) { - stack_push(context->node_stack, &tree->current); - tree->current->left = context->heap; - tree->current = node->left; - - allocator(context); - goto meta(context, DeleteMin1); +__code deleteCase6_stub(struct Context* context) { + goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); } - -__code deleteMin2_stub(struct Context* context) { - goto deleteMin2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); -} diff -r ed9d6438d2a5 -r 69d0637e52fd src/llrb/llrbContext.c --- a/src/llrb/llrbContext.c Fri Dec 04 18:32:34 2015 +0900 +++ b/src/llrb/llrbContext.c Fri Dec 11 15:07:10 2015 +0900 @@ -19,28 +19,30 @@ extern __code colorFlip_stub(struct Context*); extern __code fixUp_stub(struct Context*); extern __code changeReference_stub(struct Context*); -extern __code balance1_stub(struct Context*); -extern __code balance2_stub(struct Context*); -extern __code balance3_stub(struct Context*); -extern __code balance4_stub(struct Context*); -extern __code balance4_1_stub(struct Context*); -extern __code balance4_2_stub(struct Context*); -extern __code balance5_stub(struct Context*); -extern __code setRoot_stub(struct Context*); +extern __code insert1_stub(struct Context*); +extern __code insert2_stub(struct Context*); +extern __code insert3_stub(struct Context*); +extern __code insert4_stub(struct Context*); +extern __code insert4_1_stub(struct Context*); +extern __code insert4_2_stub(struct Context*); +extern __code insert5_stub(struct Context*); +extern __code insert5_1_stub(struct Context*); extern __code get_stub(struct Context*); -extern __code findMin_stub(struct Context*); +extern __code search_stub(struct Context*); extern __code delete_stub(struct Context*); -extern __code replaceNode_d1_stub(struct Context*); -extern __code replaceNode_d2_stub(struct Context*); -extern __code replaceNode_d3_stub(struct Context*); -extern __code replaceNode_d4_stub(struct Context*); -extern __code moveRedLeft1_stub(struct Context*); -extern __code moveRedLeft2_stub(struct Context*); -extern __code moveRedLeft3_stub(struct Context*); -extern __code moveRedRight1_stub(struct Context*); -extern __code moveRedRight2_stub(struct Context*); -extern __code deleteMin1_stub(struct Context*); -extern __code deleteMin2_stub(struct Context*); +extern __code delete1_stub(struct Context*); +extern __code delete2_stub(struct Context*); +extern __code delete3_stub(struct Context*); +extern __code replaceNodeForDelete1_stub(struct Context*); +extern __code replaceNodeForDelete2_stub(struct Context*); +extern __code findMax1_stub(struct Context*); +extern __code findMax2_stub(struct Context*); +extern __code deleteCase1_stub(struct Context*); +extern __code deleteCase2_stub(struct Context*); +extern __code deleteCase3_stub(struct Context*); +extern __code deleteCase4_stub(struct Context*); +extern __code deleteCase5_stub(struct Context*); +extern __code deleteCase6_stub(struct Context*); extern __code exit_code(struct Context*); __code initLLRBContext(struct Context* context, int num) { @@ -64,31 +66,30 @@ context->code[Insert] = insertNode_stub; context->code[RotateL] = rotateLeft_stub; context->code[RotateR] = rotateRight_stub; - context->code[ColorFlip] = colorFlip_stub; - context->code[FixUp] = fixUp_stub; - context->code[ChangeRef] = changeReference_stub; - context->code[Balance1] = balance1_stub; - context->code[Balance2] = balance2_stub; - context->code[Balance3] = balance3_stub; - context->code[Balance4] = balance4_stub; - context->code[Balance4_1] = balance4_1_stub; - context->code[Balance4_2] = balance4_2_stub; - context->code[Balance5] = balance5_stub; - context->code[SetRoot] = setRoot_stub; + context->code[InsertCase1] = insert1_stub; + context->code[InsertCase2] = insert2_stub; + context->code[InsertCase3] = insert3_stub; + context->code[InsertCase4] = insert4_stub; + context->code[InsertCase4_1] = insert4_1_stub; + context->code[InsertCase4_2] = insert4_2_stub; + context->code[InsertCase5] = insert5_stub; + context->code[InsertCase5_1] = insert5_1_stub; context->code[Get] = get_stub; - context->code[Delete] = delete_stub; - context->code[FindMin] = findMin_stub; - context->code[Replace_d1] = replaceNode_d1_stub; - context->code[Replace_d2] = replaceNode_d2_stub; - context->code[Replace_d3] = replaceNode_d3_stub; - context->code[Replace_d4] = replaceNode_d4_stub; - context->code[MoveRedL1] = moveRedLeft1_stub; - context->code[MoveRedL2] = moveRedLeft2_stub; - context->code[MoveRedL3] = moveRedLeft3_stub; - context->code[MoveRedR1] = moveRedRight1_stub; - context->code[MoveRedR2] = moveRedRight2_stub; - context->code[DeleteMin1] = deleteMin1_stub; - context->code[DeleteMin2] = deleteMin2_stub; + context->code[Search] = search_stub; + context->code[Delete] = delete_stub; + context->code[Delete1] = delete1_stub; + context->code[Delete2] = delete2_stub; + context->code[Delete3] = delete3_stub; + context->code[Replace_d1] = replaceNodeForDelete1_stub; + context->code[Replace_d2] = replaceNodeForDelete2_stub; + context->code[FindMax1] = findMax1_stub; + context->code[FindMax2] = findMax2_stub; + context->code[DeleteCase1] = deleteCase1_stub; + context->code[DeleteCase2] = deleteCase2_stub; + context->code[DeleteCase3] = deleteCase3_stub; + context->code[DeleteCase4] = deleteCase4_stub; + context->code[DeleteCase5] = deleteCase5_stub; + context->code[DeleteCase6] = deleteCase6_stub; context->code[Exit] = exit_code; context->heap = context->heapStart; @@ -107,7 +108,7 @@ struct Tree* tree = &context->data[Tree]->tree; tree->root = 0; tree->current = 0; - tree->prev = 0; + tree->deleted = 0; context->node_stack = stack_init(sizeof(union Data*), num); context->code_stack = stack_init(sizeof(enum Code), 100); diff -r ed9d6438d2a5 -r 69d0637e52fd src/llrb/llrbContext.h --- a/src/llrb/llrbContext.h Fri Dec 04 18:32:34 2015 +0900 +++ b/src/llrb/llrbContext.h Fri Dec 11 15:07:10 2015 +0900 @@ -1,7 +1,7 @@ /* Context definition for llrb example */ #include "stack.h" -#define ALLOCATE_SIZE 100 +#define ALLOCATE_SIZE 1000 enum Code { Code1, @@ -17,37 +17,42 @@ Replace, Insert, Compare, - Create, RotateL, RotateR, - ColorFlip, - FixUp, - SetRoot, - ChangeRef, - Balance1, - Balance2, - Balance3, - Balance4, - Balance4_1, - Balance4_2, - Balance5, + SetTree, + InsertCase1, + InsertCase2, + InsertCase3, + InsertCase4, + InsertCase4_1, + InsertCase4_2, + InsertCase5, + InsertCase5_1, Get, - FindMin, + Search, Delete, + Delete1, + Delete2, + Delete3, Replace_d1, Replace_d2, - Replace_d3, - Replace_d4, - MoveRedL1, - MoveRedL2, - MoveRedL3, - MoveRedR1, - MoveRedR2, - DeleteMin1, - DeleteMin2, + FindMax1, + FindMax2, + DeleteCase1, + DeleteCase2, + DeleteCase3, + DeleteCase4, + DeleteCase5, + DeleteCase6, Exit, }; +enum Relational { + EQ, + GT, + LT, +}; + enum UniqueData { Allocate, Tree, @@ -80,7 +85,7 @@ enum Code next; struct Node* root; struct Node* current; - struct Node* prev; + struct Node* deleted;; int result; } tree; struct Node { diff -r ed9d6438d2a5 -r 69d0637e52fd src/llrb/main.c --- a/src/llrb/main.c Fri Dec 04 18:32:34 2015 +0900 +++ b/src/llrb/main.c Fri Dec 11 15:07:10 2015 +0900 @@ -88,11 +88,11 @@ print_tree(context->data[Tree]->tree.root, 0); struct Node* node = &context->data[Node]->node; - node->key = 5; + node->key = 4; context->next = Code5; - goto meta(context, Exit); + goto meta(context, Delete); } __code code5(struct Context* context) { @@ -101,7 +101,7 @@ puts("--Number of Data--"); printf("%d\n", context->dataNum); - goto meta(context, Find); + goto meta(context, Exit); } __code find(struct Context* context) { diff -r ed9d6438d2a5 -r 69d0637e52fd src/llrb/stack.c --- a/src/llrb/stack.c Fri Dec 04 18:32:34 2015 +0900 +++ b/src/llrb/stack.c Fri Dec 11 15:07:10 2015 +0900 @@ -55,7 +55,7 @@ stack_ptr->num--; memcpy(data, (char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, stack_ptr->size); - + return 0; }