Mercurial > hg > Members > Moririn

changeset 458:3025d00eb87d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge
author Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date Thu, 14 Dec 2017 07:44:58 +0900
parents 2b36a1878c6f (current diff) a44dbeb08895 (diff)
children 57c715bd6283
files src/parallel_execution/generate_stub.pl
diffstat 7 files changed, 214 insertions(+), 161 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt	Thu Dec 14 07:44:21 2017 +0900
+++ b/src/parallel_execution/CMakeLists.txt	Thu Dec 14 07:44:58 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	Thu Dec 14 07:44:21 2017 +0900
+++ b/src/parallel_execution/RedBlackTree.cbc	Thu Dec 14 07:44:58 2017 +0900
@@ -1,58 +1,60 @@
 #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);
+    struct RedBlackTree* rbtree = new RedBlackTree();
 
+    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;
-}
-
-__code printTree(struct RedBlackTree* tree) {
-    printTree1(tree);
-    printf("\n");
+     return tree;
 }
 
-__code printTree1(struct RedBlackTree* tree) {
-  struct Node* node = tree->current;
+void printNode(struct Node* node) {
   if (node == NULL) {
-    printf("Leaf");
+    printf("leaf");
   } else {
-    printf("key = %d (", node->key);
-    printTree1(node->right);
-    printf("), (");
-    printTree1(node->left);
+    printf("((%d,%d (",node->color, node->key);
+    printNode(node->right);
+    printf(") (");
+    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) {
+  printf("\n");
+  tree->current = tree->root;
+  printNode(tree->current);
+  printf(")\n");
+}
+
+__code putRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
+    printf("C_putRedBlackTree\n");
+    //struct Node* newNode = &ALLOCATE(context, Node)->Node;
+    printf("value->%d,key->%d \n",node->value,node->key);
+    tree->previous = tree->newNode;
+    tree->newNode = node;
+    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(node, tree);
+        // }
+    // printf("error : __code putRedBlackTree \n");
+    // goto meta(context, C_exit_code);
 }
 
 //__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
@@ -72,70 +74,114 @@
   //   goto next(...);
   // }
 
-__code insertRBTree(struct Node* node, struct RedBlackTree* tree) {
-  tree->current = node;
-  struct Stack* nodeStack = tree->nodeStack;
+__code insertRBTree(struct Node* node, struct RedBlackTree* tree, struct Stack* stack, __code next(...)) {
+  // first case tree->current = root;
+  printf("C_insertRBTree\n");
+  //stack = tree->nodeStack;
+  printf("value->%d,key->%d\n",node->value,node->key);
+  printf("newNode value->%d,newNode key->%d\n",tree->newNode->value,tree->newNode->key);
 
-  if (tree->root == null){
-    tree->root = tree->current;
+  if (tree->root == NULL) {
+    printf("insertRBTree_root eq NULL\n");
+    tree->root = tree->newNode;
     tree->root->color = Black;
-    goto next(...);
-  }else{
-    goto searchInsertLocatetion(newNode, nodeStack, tree);
+    printf("tree->root->key = %d, tree->root->color = %d \n",tree->root->key,tree->root->color);
+    printTree(tree);
+    goto next(tree,...);
+  } else {
+    goto searchInsertLocation(node, tree, stack);
   }
-
 }
 
 
-__code searchInsertLocation(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) {
-  struct Stack* nodeStack = tree->nodeStack;
-  struct Node* trace = tree->current;
-
-
+__code searchInsertLocation(struct Node* node, struct RedBlackTree* tree) {
+  // first case tree->current = root; PreCase remove root=NULL case.don't exist firstCase tree->current=NULL
+  printf("C_searchInsertLocation\n");
+  printf("nownode->key %d , previous->key %d \n",tree->newNode->key,tree->previous->key);
 
-  // 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(...);
+  tree->result = compare(tree->current, node);
+  printf("tree->current->key = %d, node->key %d\n",tree->current->key,node->key);
+  printf("compare (%d,%d)\n",tree->current,node);
+  struct Stack* stack = tree->nodeStack;
+  if (tree->current == NULL) {
+    printf("goto insertLocationBackInsert stack->pop");
+    goto stack->pop(insertLocationBackInsert);
+  }
+  if (tree->result == GT) {
+    printf("GT searchInsertLocation");
+    tree->current = tree->current->right;
+    goto stack->push(tree->newNode,insertLocationBackInsert);
+  } else if (tree->result == LT) {
+    printf("LT searchInsertLocation");
+    tree->current = tree->current->left;
+    goto stack->push(tree->newNode, searchInsertLocation);
+  } else if (tree->result == EQ) {
+    printf("already 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 insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){
-  tree->current = nodeStack->data;
+__code insertLocationBackInsert(struct RedBlackTree* tree, struct Node* node, struct Stack* stack) {
+  printf("C_insertLocationBackInsert\n");
+  struct Node* hoge = stack->data;
+  printf("stackpopdata%d\n",stack->data);
+  tree->current = tree->previous;
+  // tree->current = nodeStack->data;
+  // this CS is ones only backTrace, and insert node
+  tree->result = compare(tree->previous,tree->newNode);
+  printf("back,compare\n");
+  if (tree->result == GT) {
+    printf("ok\n");
+    tree->current->right = tree->newNode;
+    printTree(tree);
+    goto insertBalance();
+  } else if (tree->result == LT) {
+    printf("LT\n");
+    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, __code next(...)) {
+  printf("C_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(tree);
     //printTree
-    goto next(...);
+    goto next(tree,...);
   }
 
+
   //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){
+__code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) {
+  printf("C_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 +193,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 +207,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){
+__code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) {
+  printf("C_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 +243,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/Stack.cbc	Thu Dec 14 07:44:21 2017 +0900
+++ b/src/parallel_execution/Stack.cbc	Thu Dec 14 07:44:58 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	Thu Dec 14 07:44:21 2017 +0900
+++ b/src/parallel_execution/Tree.cbc	Thu Dec 14 07:44:58 2017 +0900
@@ -1,8 +1,11 @@
 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(...));
+    /* future Code */
+    /* Type* tree; */
+    /* Type* node; */
+    union Data* tree;
+    struct Node* node;
+    __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	Thu Dec 14 07:44:21 2017 +0900
+++ b/src/parallel_execution/context.h	Thu Dec 14 07:44:58 2017 +0900
@@ -297,6 +297,7 @@
         enum Color {
             Red,
             Black,
+            // Red eq 0,Black eq 1. enum name convert intager.
         } color;
     } Node;
     struct Atomic {
--- a/src/parallel_execution/generate_stub.pl	Thu Dec 14 07:44:21 2017 +0900
+++ b/src/parallel_execution/generate_stub.pl	Thu Dec 14 07:44:58 2017 +0900
@@ -285,9 +285,9 @@
 
     while (<$in>) {
         if (! $inTypedef && ! $inStub && ! $inMain) {
-            if (/^typedef struct (\w+) {/) {
+            if (/^typedef struct (\w+) \{/) {
                 $inTypedef = 1;
-            } elsif (/^int main\((.*)\) {/) {
+            } elsif (/^int main\((.*)\) \{/) {
                 $inMain = 1;
             } elsif (/^\_\_code (\w+)\((.*)\)(.*)/) {
                 %localVarType = {};
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/test/rbTree_test.cbc	Thu Dec 14 07:44:58 2017 +0900
@@ -0,0 +1,67 @@
+#include "../../context.h"
+/* #include <assert.h> */
+
+__code rbTreeTest1(struct Tree* tree) {
+  printf("Test1\n");
+  Node* node = new Node();
+  node->value = 3;
+  node->key = 3;
+  printf("value->%d,key->%d\n",node->value,node->key);
+  goto tree->put(node, rbTreeTest2);
+}
+
+__code rbTreeTest1_stub(struct Context* context) {
+  printf("test1_stub\n");
+  Tree* tree = createRedBlackTree(context);
+  goto rbTreeTest1(context,tree);
+}
+
+
+__code rbTreeTest2(struct Tree* tree) {
+  printf("Test2\n");
+  Node* node = new Node();
+  node->value = 4;
+  node->key = 4;
+  goto tree->put(node, rbTreeTest3);
+}
+
+__code rbTreeTest2_stub(struct Context* context) {
+  printf("test2_stub\n");
+  Tree* tree = (struct Tree*)Gearef(context, Tree)->tree;
+  goto rbTreeTest2(context,tree);
+}
+
+
+__code rbTreeTest3(struct Tree* tree) {
+  printf("test3\n");
+  Node* node = new Node();
+  node->value = 2;
+  node->key = 2;
+  goto tree->put(node, rbTreeTest4);
+}
+
+
+__code rbTreeTest4(struct Tree* tree) {
+  printf("test4\n");
+  Node* node = new Node();
+  node->value = 8;
+  node->key = 8;
+  goto tree->put(node, rbTreeTest5);
+}
+
+
+__code rbTreeTest5(struct Tree* tree) {
+  printf("test5\n");
+  Node* node = new Node();
+  node->value = 7;
+  node->key = 7;
+  goto exit_code(context);
+}
+
+
+
+
+int main(int argc, char const* argv[]) {
+  printf("test_main\n");
+  goto rbTreeTest1();
+}