# HG changeset patch
# User Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
# Date 1430163079 -32400
# Node ID 324c44f2076f98c4aba3835c359044a4a538f3fd
# Parent  9302b1a48008f39564e0037e51b27fa08dd51526
implement insert

diff -r 9302b1a48008 -r 324c44f2076f src/llrb/llrb.c
--- a/src/llrb/llrb.c	Tue Apr 21 22:36:23 2015 +0900
+++ b/src/llrb/llrb.c	Tue Apr 28 04:31:19 2015 +0900
@@ -15,6 +15,9 @@
 #define ALLOCATE_SIZE 1024
 
 extern __code initLLRBContext(struct Context* context);
+void colorFlip(struct Context*);
+void rotateLeft(struct Context*);
+void rotateRight(struct Context*);
 /* 
 __code code1(Allocate allocate) {
     allocate.size = sizeof(long);
@@ -27,6 +30,8 @@
     context->data[0]->allocate.size = sizeof(struct Node);
     context->data[0]->allocate.next = Put;
     context->data[0]->allocate.after_put = Code2;
+    context->data[0]->allocate.key = 0;
+    context->data[0]->allocate.value = 0;
     goto meta(context, Allocate);
 }
 
@@ -39,16 +44,92 @@
     context->data[context->dataSize]->node.value = context->data[0]->allocate.value;
     if (context->root == 0) {
         context->root = context->data[context->dataSize];
-        context->root->node.color = Red;
+        context->root->node.color = Black;
         goto meta(context, context->data[0]->allocate.after_put);
     }
+    context->data[context->dataSize]->node.color = Red;
+    context->current = context->root;
     goto meta(context, Insert);
 }
 
 __code insert(struct Context* context) {
+    int persistentKey = context->current->node.key;
+    int temporalKey = context->data[context->dataSize]->node.key;
+    
+    if (context->current->node.right != 0 && context->current->node.left != 0) {
+        if (context->current->node.right->node.color == Red && context->current->node.left->node.color == Red) {
+            colorFlip(context);
+        }
+    }
+    
+    if (persistentKey == temporalKey) {
+        context->current->node.value = context->data[context->dataSize]->node.value;
+        goto meta(context, context->data[0]->allocate.after_put);
+    } else if (persistentKey < temporalKey) {
+        if (context->current->node.left == 0) {
+            context->current->node.left = context->data[context->dataSize];
+        } else {
+            context->current = context->current->node.left;
+            goto meta(context, Insert);
+        }
+    } else {
+        if (context->current->node.right == 0) {
+            context->current->node.right = context->data[context->dataSize];
+        } else {
+            context->current = context->current->node.right;
+            goto meta(context, Insert);
+        }
+    }
+
+    if (context->current->node.right != 0) {
+        if (context->current->node.right->node.color == Red) {
+            rotateLeft(context);
+        }
+    }
+
+    if (context->current->node.left != 0) {
+        if (context->current->node.left->node.left != 0) {
+            if (context->current->node.left->node.color == Red && context->current->node.left->node.left->node.color == Red) {
+                rotateRight(context);
+            }
+        }
+    }
+
+    if (context->current->node.right != 0 && context->current->node.left != 0) {
+        if (context->current->node.right->node.color == Red && context->current->node.left->node.color == Red) {
+            colorFlip(context);
+        }
+    }    
+    
+    context->root->node.color = Black;
+    
     goto meta(context, context->data[0]->allocate.after_put);
 }
 
+void rotateLeft(struct Context* context) {
+    union Data* tmp = context->current->node.right;
+    context->current->node.right = tmp->node.left;
+    tmp->node.left = context->current;
+    tmp->node.color = tmp->node.left->node.color;
+    tmp->node.left->node.color = Red;
+    context->current = tmp;
+}
+
+void rotateRight(struct Context* context) {
+    union Data* tmp = context->current->node.left;
+    context->current->node.left = tmp->node.right;
+    tmp->node.right = context->current;
+    tmp->node.color = tmp->node.right->node.color;
+    tmp->node.right->node.color = Red;
+    context->current = tmp;
+}
+
+void colorFlip(struct Context* context) {
+    context->current->node.color ^= 1;
+    context->current->node.left->node.color ^= 1;
+    context->current->node.right->node.color ^= 1;
+}
+
 /*
 __code code2(Allocate allocate, Count count) {
     count.count = 0;
diff -r 9302b1a48008 -r 324c44f2076f src/llrb/llrbContext.c
--- a/src/llrb/llrbContext.c	Tue Apr 21 22:36:23 2015 +0900
+++ b/src/llrb/llrbContext.c	Tue Apr 28 04:31:19 2015 +0900
@@ -19,4 +19,7 @@
     context->dataSize = 0;
     context->data[context->dataSize] = context->heap;
     context->heap += sizeof(struct Allocate);
+
+    context->root = 0;
+    context->current = 0;
 }
diff -r 9302b1a48008 -r 324c44f2076f src/llrb/llrbContext.h
--- a/src/llrb/llrbContext.h	Tue Apr 21 22:36:23 2015 +0900
+++ b/src/llrb/llrbContext.h	Tue Apr 28 04:31:19 2015 +0900
@@ -19,6 +19,7 @@
     __code (**code) (struct Context *);
     void* heap;
     union Data* root;
+    union Data* current;
     int dataSize;
     union Data **data;
 };