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

diff -r 324c44f2076f -r 737a900518be src/llrb/llrb.c
--- a/src/llrb/llrb.c	Tue Apr 28 04:31:19 2015 +0900
+++ b/src/llrb/llrb.c	Tue Apr 28 14:34:59 2015 +0900
@@ -27,11 +27,8 @@
 */
 
 __code code1(struct Context* context) {
-    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;
+    context->data[0]->allocate.size = sizeof(long);
+    context->data[0]->allocate.next = Code2;
     goto meta(context, Allocate);
 }
 
@@ -45,14 +42,15 @@
     if (context->root == 0) {
         context->root = context->data[context->dataSize];
         context->root->node.color = Black;
+        context->root->node.parent = 0;
         goto meta(context, context->data[0]->allocate.after_put);
     }
     context->data[context->dataSize]->node.color = Red;
     context->current = context->root;
-    goto meta(context, Insert);
+    goto meta(context, InsertD);
 }
 
-__code insert(struct Context* context) {
+__code insertDown(struct Context* context) {
     int persistentKey = context->current->node.key;
     int temporalKey = context->data[context->dataSize]->node.key;
     
@@ -65,22 +63,28 @@
     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) {
+    } else if (temporalKey < persistentKey) {
         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);
+            goto meta(context, InsertD);
         }
     } 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);
+            goto meta(context, InsertD);
         }
     }
 
+    context->data[context->dataSize]->node.parent = context->current;
+    
+    goto meta(context, InsertU);
+}
+
+__code insertUp(struct Context* context) {
     if (context->current->node.right != 0) {
         if (context->current->node.right->node.color == Red) {
             rotateLeft(context);
@@ -101,9 +105,22 @@
         }
     }    
     
-    context->root->node.color = Black;
+    if (context->current->node.parent == 0) {
+        context->root = context->current;
+        context->root->node.color = Black;
+        goto meta(context, context->data[0]->allocate.after_put);
+    }
     
-    goto meta(context, context->data[0]->allocate.after_put);
+    if (context->current->node.parent != 0) {
+        if (context->current->node.parent->node.key < context->current->node.key) {
+            context->current->node.parent->node.right = context->current;
+        } else {
+            context->current->node.parent->node.left = context->current;
+        }
+    }
+    
+    context->current = context->current->node.parent;
+    goto meta(context, InsertU);
 }
 
 void rotateLeft(struct Context* context) {
@@ -111,7 +128,9 @@
     context->current->node.right = tmp->node.left;
     tmp->node.left = context->current;
     tmp->node.color = tmp->node.left->node.color;
+    tmp->node.parent = tmp->node.left->node.parent;
     tmp->node.left->node.color = Red;
+    tmp->node.left->node.parent = tmp;
     context->current = tmp;
 }
 
@@ -120,7 +139,9 @@
     context->current->node.left = tmp->node.right;
     tmp->node.right = context->current;
     tmp->node.color = tmp->node.right->node.color;
+    tmp->node.parent = tmp->node.right->node.parent;
     tmp->node.right->node.color = Red;
+    tmp->node.right->node.parent = tmp;
     context->current = tmp;
 }
 
@@ -138,7 +159,20 @@
 */
 
 __code code2(struct Context* context) {
-    goto meta(context, Exit);
+    context->data[1]->count = 0;
+    goto meta(context, Code3);
+}
+
+__code code3(struct Context* context) {
+    if (context->data[1]->count == NUM)
+        goto meta(context, Exit);
+    context->data[0]->allocate.size = sizeof(struct Node);
+    context->data[0]->allocate.next = Put;
+    context->data[0]->allocate.after_put = Code3;
+    context->data[0]->allocate.key = context->data[1]->count;
+    context->data[0]->allocate.value = context->data[1]->count;
+    context->data[1]->count++;
+    goto meta(context, Allocate);
 }
 
 int main() {
diff -r 324c44f2076f -r 737a900518be src/llrb/llrbContext.c
--- a/src/llrb/llrbContext.c	Tue Apr 28 04:31:19 2015 +0900
+++ b/src/llrb/llrbContext.c	Tue Apr 28 14:34:59 2015 +0900
@@ -1,19 +1,23 @@
 #include "llrbContext.h"
 extern __code code1(struct Context*);
 extern __code code2(struct Context*);
+extern __code code3(struct Context*);
 extern __code meta(struct Context*);
 extern __code allocate(struct Context*);
 extern __code put(struct Context*);
-extern __code insert(struct Context*);
+extern __code insertDown(struct Context*);
+extern __code insertUp(struct Context*);
 extern __code exit_code(struct Context*);
 
 __code initLLRBContext(struct Context* context) {
     context->codeSize = 3;
     context->code[Code1]    = code1;
     context->code[Code2]    = code2;
+    context->code[Code3]    = code3;
     context->code[Allocate] = allocate;
     context->code[Put]      = put;
-    context->code[Insert]   = insert;
+    context->code[InsertD]  = insertDown;
+    context->code[InsertU]  = insertUp;
     context->code[Exit]     = exit_code;
     
     context->dataSize = 0;
diff -r 324c44f2076f -r 737a900518be src/llrb/llrbContext.h
--- a/src/llrb/llrbContext.h	Tue Apr 28 04:31:19 2015 +0900
+++ b/src/llrb/llrbContext.h	Tue Apr 28 14:34:59 2015 +0900
@@ -3,9 +3,11 @@
 enum Code {
     Code1,
     Code2,
+    Code3,
     Allocate,
     Put,
-    Insert,
+    InsertD,
+    InsertU,
     Exit,
 };
 
@@ -25,10 +27,12 @@
 };
 
 union Data {
+    long count;
     struct Node {
         int key;
         int value;
         enum Color color;
+        union Data* parent;
         union Data* left;
         union Data* right;
     } node;