changeset 452:1432d924c472

fix RedBlackTree.cbc Insert, debug now
author ryokka
date Fri, 08 Dec 2017 15:28:06 +0900
parents dcc42f3e7e97
children 40ea6277b91c
files src/parallel_execution/CMakeLists.txt src/parallel_execution/RedBlackTree.cbc src/parallel_execution/SingleLinkedStack.cbc src/parallel_execution/Stack.cbc src/parallel_execution/Tree.cbc src/parallel_execution/context.h
diffstat 6 files changed, 140 insertions(+), 145 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt	Tue Dec 05 06:33:40 2017 +0900
+++ b/src/parallel_execution/CMakeLists.txt	Fri Dec 08 15:28:06 2017 +0900
@@ -128,5 +128,5 @@
   TARGET
       rbtree
   SOURCES
-      RedBlackTree.cbc
+     SingleLinkedQueue.cbc test/rbTree_test.cbc RedBlackTree.cbc SingleLinkedStack.cbc
 )
--- a/src/parallel_execution/RedBlackTree.cbc	Tue Dec 05 06:33:40 2017 +0900
+++ b/src/parallel_execution/RedBlackTree.cbc	Fri Dec 08 15:28:06 2017 +0900
@@ -1,58 +1,81 @@
 #include <stdio.h>
 
 #include "../context.h"
-
-// extern enum Relational compare(struct Node* node1, struct Node* node2);
+#include "../compare.c"
 
 extern enum Relational compare(struct Node* node1, struct Node* node2);
 
+/* Tree* createRedBlackTree(struct Context* context)  */
+/*   struct Tree* tree = new Tree(); */
+/*   struct RedBlackTree* redBlackTree = new RedBlackTree(); */
+/*   tree->tree = (union Data*)redBlackTree; */
+/*   redBlackTree->root = NULL; */
+/*   redBlackTree->nodeStack = (union Data*)createSingleLinkedStack(context); */
+
+/*   tree->put = C_putRedBlackTree; */
+/*   // tree->get = C_getRedBlackTree; */
+/*   // tree->remove = C_removeRedBlackTree; */
+/*   // tree->clear = C_clearRedBlackTree; */
+/*   return tree; */
 
 Tree* createRedBlackTree(struct Context* context) {
     struct Tree* tree = new Tree();
-    struct RedBlackTree* redBlackTree = new RedBlackTree();
-    tree->tree = (union Data*)redBlackTree;
-    redBlackTree->root = NULL;
-    redBlackTree->nodeStack = (union Data*)createSingleLinkedStack(context);
+    struct RedBlackTree* rbtree = new RedBlackTree();
 
+    // struct RedBlackTree* tree = new RedBlackTree();
+    // struct RedBlackTree* tree = RedBlackTree(context);
+    tree->tree = (union Data*)rbtree;
+     rbtree->root = NULL;
+     rbtree->nodeStack = (union Data*)createSingleLinkedStack(context);
      tree->put = C_putRedBlackTree;
     // tree->get = C_getRedBlackTree;
     // tree->remove = C_removeRedBlackTree;
     // tree->clear = C_clearRedBlackTree;
-    return tree;
+     return tree;
 }
 
-__code printTree(struct RedBlackTree* tree) {
-    printTree1(tree);
-    printf("\n");
-}
-
-__code printTree1(struct RedBlackTree* tree) {
+// printTree use printNode
+void printNode(struct RedBlackTree* tree) {
   struct Node* node = tree->current;
   if (node == NULL) {
     printf("Leaf");
   } else {
     printf("key = %d (", node->key);
-    printTree1(node->right);
+    printNode(node->right);
     printf("), (");
-    printTree1(node->left);
+    printNode(node->left);
     printf(")");
   }
 }
 
-__code putRedBlackTree(struct Node* node, struct RedBlackTree* tree) {
-    struct Node* newNode = &ALLOCATE(context, Node)->Node;
-    struct Node* root = tree->root;
-    printTree((tree->root));
-    tree->newNode = newNode;
+void printTree(struct RedBlackTree* tree) {
+  printNode(tree);
+  printf("\n");
+}
+
+__code printRBTree(struct RedBlackTree* tree){
+  printTree(tree);
+  goto meta(context, C_exit_code);
+}
+
+__code putRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
+  printf("putRedBlackTree\n");
+  //struct Node* newNode = &ALLOCATE(context, Node)->Node;
+  struct Node* insertNode = node;
+  printf("value->%d,key->%d \n",node->value,node->key);
+    // struct Node* root = tree->root;
+    // printTree(tree);
+    tree->newNode = insertNode;
+    tree->newNode->color = Red;
     // tree->root = newNode; // this should done at stackClear
-    tree->parent = NULL;
-    if (root) {
-        tree->current = root;
+    // tree->parent = NULL;
+    // if (root) {
+    tree->current = tree->root;
         // tree->result = compare(tree->current, node);
-        goto insertRBTree(newNode, tree);
-    }
-    print("error : __code putRedBlackTree");
-    goto next(...);
+    goto insertRBTree(insertNode, tree);
+        // }
+    // printf("error : __code putRedBlackTree \n");
+    // goto meta(context, C_exit_code);
 }
 
 //__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
@@ -73,69 +96,104 @@
   // }
 
 __code insertRBTree(struct Node* node, struct RedBlackTree* tree) {
-  tree->current = node;
-  struct Stack* nodeStack = tree->nodeStack;
+  printf("insertRBTree\n");
+  printf("value->%d,key->%d\n",node->value,node->key);
+  // tree->current = node;
+  // struct Stack* stack = tree->nodeStack;
 
-  if (tree->root == null){
+  if (tree->root == NULL){
     tree->root = tree->current;
     tree->root->color = Black;
-    goto next(...);
-  }else{
-    goto searchInsertLocatetion(newNode, nodeStack, tree);
+    goto meta(context, C_printRBTree);
+  } else {
+    goto searchInsertLocation(newNode, nodeStack, tree);
   }
-
 }
 
 
-__code searchInsertLocation(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) {
-  struct Stack* nodeStack = tree->nodeStack;
+__code searchInsertLocation(struct Node* node, struct RedBlackTree* tree) {
+  printf("searchInsertLocation\n");
   struct Node* trace = tree->current;
+  struct Stack* stack = tree->nodeStack;
 
+  tree->result = compare(tree->current, tree->newNode);
 
 
   // i think faster  "compare tree->current, node" than  "switch case EQ, LT, RT"
-  if (tree->current > node || tree->current < node) {
-    goto nodestack->push(nodeStack,trace, searchInsertLocation);
-  } else if (tree->current == node) {
-    printf("alady member this node : __code searchInsertLocation()");
-    goto next(...);
-  } else if (tree->current == null){
-    tree->current = node;
-    goto nodeStack->pop(nodeStack,insertBalance);
-  }else{
-    printf("$insert value tree : __code searchInsertLocation()");
-    goto next(...);
+
+
+  if (tree->current == NULL){
+    // before CS(insertRBTree) remeve "root eq NULL Case"
+    goto stack->pop(insertLocationBackInsert);
+  } else if (tree->result == GT) {
+    tree->current = tree->current->right;
+    goto stack->push(trace, searchInsertLocation);
+  } else if (tree->result == LT){
+    tree->current = tree->current->left;
+    goto stack->push(trace, searchInsertLocation);
+  } else if (tree->result == EQ) {
+    printf("alady member this node : __code searchInsertLocation()\n");
+    goto meta(context, C_exit_code);
+  } else {
+    printf("$insert value tree : __code searchInsertLocation() \n");
+    goto meta(context, C_exit_code);
+  }
+}
+
+__code insertLocationBackInsert(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) {
+  printf("insertLocationBackInsert\n");
+  struct Node* traceNode = tree->nodeStack->data;
+  tree->current = traceNode;
+  // tree->current = nodeStack->data;
+  // this CS is ones only backTrace, and insert node
+  tree->result = compare(tree->current, tree->newNode);
+
+  if (tree->result == GT) {
+    tree->current->right = tree->newNode;
+    goto insertBalance();
+  } else if (tree->result == LT) {
+    tree->current->left = tree->newNode;
+    goto insertBalance();
+  } else {
+    printf("error : __code insertLocationBackTrace() \n");
+    goto meta(context, C_exit_code);
   }
 }
 
 __code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){
-  tree->current = nodeStack->data;
+  printf("insertBalance\n");
+  struct Node* traceNode = tree->nodeStack->data;
+  tree->current = traceNode;
+  struct Stack* stack = tree->nodeStack;
 
   // exit insertion code
   if (tree->current == tree->root) {
     tree->current->color = Black;
-    printTree(((union Data* ) (tree->root)));
+    printTree((union Data*)(tree->root));
     //printTree
-    goto next(...);
+    goto meta(context, C_exit_code);
   }
 
+
   //current color eq Red
-  if (current->color == Red)
-    goto nodeStack->pop(nodeStack, trace, insertBalance);
+  if (tree->current->color == Red)
+    goto stack->pop(insertBalance);
 
   // current color eq Black
-  if (current->left->left || current->left->right){
+  if (tree->current->left->left || tree->current->left->right){
     goto insertBalanceLeft(tree,nodeStack);
-  }else if (current->right->left || current->right->right){
+  } else if (tree->current->right->left || tree->current->right->right){
     goto insertBalanceRight(tree,nodeStack);
-  }else{
-    goto nodeStack->pop(nodeStack,insertBalance);
+  } else {
+    goto stack->pop(insertBalance);
   }
 }
 
 __code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){
+  printf("insertBalanceLeft\n");
+  struct Stack* stack = tree->nodeStack;
 
-  if (current->color == Black && current->left->color == Red && current->left->left->color == Red){
+  if (tree->current->color == Black && tree->current->left->color == Red && tree->current->left->left->color == Red){
     struct Node* tmpCurrent  = tree->current;
     struct Node* tmpLeft     = tree->current->left;
     struct Node* tmpLeftLeft = tree->current->left->left;
@@ -147,9 +205,9 @@
     tree->current->color = Red;
     tree->current->left->color = Black;
     tree->current->right->color = Black;
-    goto nodeStack->pop(nodeStack,insertBalance);
+    goto stack->pop(insertBalance);
 
-  } else if(current->color == Black && current->left->color == Red && current->left->right->color == Red){
+  } else if(tree->current->color == Black && tree->current->left->color == Red && tree->current->left->right->color == Red){
     struct Node* tmpCurrent   = tree->current;
     struct Node* tmpLeft      = tree->current->left;
     struct Node* tmpLeftRight = tree->current->left->right;
@@ -161,27 +219,30 @@
     tree->current->color = Red;
     tree->current->left->color = Black;
     tree->current->right->color = Black;
-    goto nodeStack->pop(nodeStack,insertBalance);
+    goto stack->pop(insertBalance);
 
   }
 }
 
 __code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){
-  if (current->color == Black && current->right->color == Red && current->right->right->color == Red){
+  printf("insertBalanceLeft\n");
+  struct Stack* stack = tree->nodeStack;
+
+  if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->right->color == Red){
     struct Node* tmpCurrent    = tree->current;
     struct Node* tmpRight      = tree->current->right;
     struct Node* tmpRightRight = tree->current->right->right;
 
     tree->current = tmpRight;
     tree->current->left = tmpCurrent;
-    tree->current->Right = tmpRightRight;
+    tree->current->right = tmpRightRight;
     tree->current->left->right = tmpRight->left;
     tree->current->color = Red;
     tree->current->left->color = Black;
     tree->current->right->color = Black;
-    goto nodeStack->pop(nodeStack,insertBalance);
+    goto stack->pop(insertBalance);
 
-  } else if (current->color == Black && current->right->color == Red && current->right->left->color == Red){
+  } else if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->left->color == Red){
 
     struct Node* tmpCurrent = tree->current;
     struct Node* tmpRight = tree->current->right;
@@ -194,81 +255,11 @@
     tree->current->color = Red;
     tree->current->left->color = Black;
     tree->current->right->color = Black;
-    goto nodeStack->pop(nodeStack,insertBalance);
+    goto stack->pop(insertBalance);
 
   } else {
-    printf("unkwon error : __code insertBalanceRight()");
-    goto next(...);
+    printf("unkwon error : __code insertBalanceRight() \n");
+    goto meta(context, C_exit_code);
   }
 }
-
-// insertion code end
-
-
-
-
-/* __code deleteRBTree(struct RedBlackTree newNode, struct RedBlackTree* tree) { */
-/*   tree->current = tree->root; */
-/*   goto deleteLocate; */
-/* } */
-
-/* __code deleteLocate(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { */
-/*   /\* check delete node locate and push route node *\/ */
-/*   struct Stack* nodeStack = tree->nodeStack; */
-/*   struct Node* trace = tree->current; */
-
-/*   if (tree->current > node) { */
-/*     goto nodeStack->push(nodeStack,trace,deleteLocate); */
-/*   } else if (tree->current < node) { */
-/*     goto nodeStack->push(trace,deleteLocate); */
-/*   } else if (tree->current == node) { */
-/*     // trace = tree->current; */
-/*     goto deleteNode(struct Stack* nodeStack, struct RedBlackTree* tree,struct Node* trace); */
-/*     // goto nodeStack->push(trace,deleteNode); */
-/*   } else if (tree->current == null){ */
-/*     printf("No member Delete node (__code deleteLocate)"); */
-/*     goto next(...); */
-/*   } else { */
-/*     printf("Error,__code deleteLocate"); */
-/*     goto next(...); */
-/*   } */
-/* } */
-
-/* __code deleteNode(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { */
-/*   struct Stack* nodeStack = tree->nodeStack; */
-/*   struct Node* replaceNode = nodeStack->data; */
-
-/*   if(replaceNode->right == null){ */
-/*     tree->current = replaceNode; */
-/*     tree->current = tree->current->left; */
-/*     goto deleteUnbalance(nodeStack,replaceNode); */
-/*   }else if(replaceNode->left == null){ */
-/*     tree->current = replaceNode; */
-/*     tree->current = tree->current->right; */
-/*     goto deleteUnbalance(nodeStack,replaceNode); */
-/*     //goto deleteNodeReplaceNull(); */
-/*   }else{ */
-/*     // goto nodeStack->push(nodeStack,replaceNode,deleteNodeReplace); */
-/*     goto deleteNodeReplace(nodeStack,replaceNode); */
-/*   } */
-/* } */
-
-
-/* __code deleteNodeReplace(){ */
-
-/*   if (replaceNode->left != null){ */
-/*     replaceNode = replaceNode->left; */
-/*     goto deleteNodeReplace(); */
-/*   }else if(){ */
-
-
-/*   } */
-
-/* } */
-
-
-/* __code deleteUnbalance() { */
-/*   if () { */
-/*   } */
-/* } */
-
+// insertCode end
--- a/src/parallel_execution/SingleLinkedStack.cbc	Tue Dec 05 06:33:40 2017 +0900
+++ b/src/parallel_execution/SingleLinkedStack.cbc	Fri Dec 08 15:28:06 2017 +0900
@@ -97,7 +97,7 @@
     }
     goto next(data, data1, ...);
 }
-    
+
 __code isEmptySingleLinkedStack(struct SingleLinkedStack* stack, __code next(...), __code whenEmpty(...)) {
     if (stack->top)
         goto next(...);
--- a/src/parallel_execution/Stack.cbc	Tue Dec 05 06:33:40 2017 +0900
+++ b/src/parallel_execution/Stack.cbc	Fri Dec 08 15:28:06 2017 +0900
@@ -1,7 +1,10 @@
 typedef struct Stack<Type, Impl>{
-        Type* stack;
-        Type* data;
-        Type* data1;
+        union Data* stack;
+        union Data* data;
+        union Data* data1;
+        /* Type* stack; */
+        /* Type* data; */
+        /* Type* data1; */
         __code whenEmpty(...);
         __code clear(Impl* stack,__code next(...));
         __code push(Impl* stack,Type* data, __code next(...));
--- a/src/parallel_execution/Tree.cbc	Tue Dec 05 06:33:40 2017 +0900
+++ b/src/parallel_execution/Tree.cbc	Fri Dec 08 15:28:06 2017 +0900
@@ -1,8 +1,8 @@
 typedef struct Tree<Type, Impl>{
     Type* tree;
     Type* node;
-    __code put(Impl* tree, Type* node, Type* root, Type* newNode);
-    __code get(Impl* tree, __code next(...));
+    __code put(Impl* tree,Type* node, __code next(...));
+    // __code get(Impl* tree, __code next(...));
     // __code removeRedBlackTree();
     // __code clearRedBlackTree();
     __code next(...);
--- a/src/parallel_execution/context.h	Tue Dec 05 06:33:40 2017 +0900
+++ b/src/parallel_execution/context.h	Fri Dec 08 15:28:06 2017 +0900
@@ -281,6 +281,7 @@
         struct Node* parent;
         struct Node* grandparent;
         struct Stack* nodeStack;
+        enum Code* put;
         int result;
     } RedBlackTree;
     struct RotateTree {