Mercurial > hg > CbC > old > akasha

changeset 26:cf7cbe70404f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
WIP: Trying implement copying GC...
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Sat, 16 Apr 2016 09:44:48 +0900
parents 38ba1606e62d
children a416dd4093cf
files src/insert_verification/akashaCS.c src/insert_verification/include/akashaLLRBContext.h src/insert_verification/main.c
diffstat 3 files changed, 125 insertions(+), 41 deletions(-) [+]
line wrap: on
line diff
--- a/src/insert_verification/akashaCS.c	Wed Apr 13 16:30:47 2016 +0900
+++ b/src/insert_verification/akashaCS.c	Sat Apr 16 09:44:48 2016 +0900
@@ -1,21 +1,71 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <stdbool.h>
 
 #include "akashaLLRBContext.h"
 
 extern __code initLLRBContext(struct Context*, enum Code);
 
-void* akashaMalloc(struct Context* context, size_t size) {
-    context->data[++context->dataNum] = context->heap;
-    context->heap += size;
-    return context->data[context->dataNum];
+/* utils */
+
+void* akashaMalloc(struct Context* akashaContext, unsigned int size) {
+    akashaContext->data[++akashaContext->dataNum] = akashaContext->heap;
+    akashaContext->heap += size;
+    return akashaContext->data[akashaContext->dataNum];
+}
+
+bool eqNode(struct Node* n1, struct Node* n2) {
+    if ((n1 == NULL) && (n2 == NULL))  return true;
+    if (n1->key   != n2->key)          return false;
+    if (n1->value != n2->value)        return false;
+    if (n1->color != n2->color)        return false;
+    if (!eqNode(n1->left,  n2->left))  return false;
+    if (!eqNode(n1->right, n2->right)) return false;
+    return true;
 }
 
+bool eqTree(struct Tree* t1, struct Tree* t2) {
+    if ((t1 == NULL) && (t2 == NULL))      return true;
+    if (t1->next   != t2->next)            return false;
+    if (t2->result != t2->result)          return false;
+    if (!eqNode(t1->root,    t2->root))    return false;
+    if (!eqNode(t1->current, t2->current)) return false;
+    if (!eqNode(t1->deleted, t2->deleted)) return false;
+    return true;
+}
+
+
+bool eqIter(struct Iterator* iter1, struct Iterator* iter2) {
+    if (iter1->head->val != iter2->head->val)         return false;
+    if (iter1->last->val != iter2->last->val)         return false;
+    if (iter1->iteratedValue != iter2->iteratedValue) return false;
+    if (!eqTree(iter1->tree, iter2->tree))            return false;
+
+    struct IterElem *ie1 = iter1->head->next;
+    struct IterElem *ie2 = iter2->head->next;
+
+    while (ie1->val != iter1->head->val) {
+        if (ie1->val != ie2->val) return false;
+        ie1 = ie1->next;
+        ie2 = ie2->next;
+    }
+
+    if ((iter1->previousDepth == NULL) && (iter2->previousDepth == NULL)) return true;
+    return eqIter(iter1->previousDepth, iter2->previousDepth);
+}
+
+
+/* C function */
+
 struct Node* nodeDeepCopy(struct Context* newContext, struct Node* oldNode) {
     if (oldNode == NULL) return NULL;
 
-    struct Node* newNode = akashaMalloc(newContext, sizeof(struct Node));
+    struct Allocate* allocate = &newContext->data[Allocate]->allocate;
+    allocate->size = sizeof(Node);
+    allocator(newContext);
+
+    struct Node* newNode = (struct Node*)newContext->data[newContext->dataNum];
     newNode->next  = oldNode->next;
     newNode->key   = oldNode->key;
     newNode->value = oldNode->value;
@@ -36,13 +86,21 @@
     return newNode;
 }
 
-void treeDeepCopy(struct Context* newContext, struct Tree* newTree, struct Tree* oldTree) {
-    if (oldTree == NULL) return;
-    newTree->next    = oldTree->next;
-    newTree->result  = oldTree->result;
-    newTree->root    = nodeDeepCopy(newContext, oldTree->root);
-    newTree->current = nodeDeepCopy(newContext, oldTree->current);
-    newTree->deleted = nodeDeepCopy(newContext, oldTree->deleted);
+struct Tree* treeDeepCopy(struct Context* newContext, struct Tree* oldTree) {
+    if (oldTree == NULL) return NULL;
+
+    struct Allocate* allocate = &newContext->data[Allocate]->allocate;
+    allocate->size = sizeof(Node);
+    allocator(newContext);
+
+    struct Tree* newTree = (struct Tree*)newContext->data[newContext->dataNum];
+    newTree->next        = oldTree->next;
+    newTree->result      = oldTree->result;
+    newTree->root        = nodeDeepCopy(newContext, oldTree->root);
+    newTree->current     = nodeDeepCopy(newContext, oldTree->current);
+    newTree->deleted     = nodeDeepCopy(newContext, oldTree->deleted);
+
+    return newTree;
 }
 
 void iterElemDeepCopy(struct Context* newContext, struct Iterator* newIter, struct Iterator *oldIter) {
@@ -68,11 +126,9 @@
 }
 
 void iterDeepCopy(struct Context* newContext, struct Iterator* newIter, struct Iterator* oldIter) {
-    newIter->tree = akashaMalloc(newContext, sizeof(struct Tree));
-    treeDeepCopy(newContext, newIter->tree, oldIter->tree);
+    newIter->tree = treeDeepCopy(newContext, oldIter->tree);
 
     newIter->iteratedValue = oldIter->iteratedValue;
-
     iterElemDeepCopy(newContext, newIter, oldIter);
 
     if (oldIter->previousDepth != NULL) {
@@ -89,8 +145,8 @@
 
     struct Context* newContext = (struct Context*)malloc(sizeof(struct Context));
 
-    newContext->dataLimit = oldContext->dataLimit*2;
-    newContext->heapLimit = oldContext->heapLimit*2;
+    newContext->dataLimit = oldContext->dataLimit;
+    newContext->heapLimit = oldContext->heapLimit;
     newContext->code      = oldContext->code;
     newContext->data      = malloc(newContext->dataLimit * sizeof(union Data*));
     newContext->heapStart = malloc(newContext->heapLimit);
@@ -109,27 +165,54 @@
 
     newContext->data[Node] = newContext->heap;
     newContext->heap += sizeof(struct Node);
-    newContext->data[Node]->node = oldContext->data[Node]->node;
 
     newContext->data[Iter] = newContext->heap;
     newContext->heap += sizeof(struct Iterator);
 
     newContext->dataNum = Iter;
 
-    treeDeepCopy(newContext, &newContext->data[Tree]->tree,     &oldContext->data[Tree]->tree);
+    newContext->data[Node]->node = *nodeDeepCopy(newContext, &oldContext->data[Node]->node);
+    newContext->data[Tree]->tree = *treeDeepCopy(newContext, &oldContext->data[Tree]->tree);
+    if (!eqTree(&newContext->data[Tree]->tree,     &oldContext->data[Tree]->tree)) abort();
     iterDeepCopy(newContext, &newContext->data[Iter]->iterator, &oldContext->data[Iter]->iterator);
+    if (!eqIter(&newContext->data[Iter]->iterator, &oldContext->data[Iter]->iterator)) abort();
 
     newContext->node_stack = oldContext->node_stack;
     newContext->code_stack = oldContext->code_stack;
     newContext->next       = oldContext->next;
     free(oldContext->data);
+    free(oldContext->heapStart);
     *oldContext = *newContext;
 }
 
+void validateNodePointer(struct Node* node) {
+    if (node == NULL) return;
+    validateNodePointer(node->left);
+    validateNodePointer(node->right);
+}
+
+void validateTreePointer(struct Tree* tree) {
+    if (tree == NULL) return;
+    validateNodePointer(tree->root);
+    validateNodePointer(tree->current);
+    validateNodePointer(tree->deleted);
+}
+
+
+void findInvalidPointer(struct Context* context) {
+    validateNodePointer(&context->data[Node]->node);
+    validateTreePointer(&context->data[Tree]->tree);
+}
+
+/* Code Segments */
+
 __code meta(struct Context* context, enum Code next) {
-    if ((next == Put) && (context->dataNum > (context->dataLimit * 0.9))) {
-        memoryRefresh(context);
+    if (next == Put) {
+        findInvalidPointer(context);
+        if (context->dataNum > (context->dataLimit * 0.9)) memoryRefresh(context);
     }
+    findInvalidPointer(context);
+    context->prev = next;
     goto (context->code[next])(context);
 }
 
--- a/src/insert_verification/include/akashaLLRBContext.h	Wed Apr 13 16:30:47 2016 +0900
+++ b/src/insert_verification/include/akashaLLRBContext.h	Sat Apr 16 09:44:48 2016 +0900
@@ -1,8 +1,8 @@
 /* Context definition for llrb example */
 #include "stack.h"
 
-#define ALLOCATE_SIZE 100000
-#define LIMIT_OF_VERIFICATION_SIZE 11
+#define ALLOCATE_SIZE 20000000
+#define LIMIT_OF_VERIFICATION_SIZE 8
 
 enum Code {
     ShowTree,
@@ -65,6 +65,7 @@
 
 struct Context {
     enum Code next;
+    enum Code prev;
     unsigned int codeNum;
     __code (**code) (struct Context*);
     void* heapStart;
--- a/src/insert_verification/main.c	Wed Apr 13 16:30:47 2016 +0900
+++ b/src/insert_verification/main.c	Sat Apr 16 09:44:48 2016 +0900
@@ -1,8 +1,11 @@
+#include <stdbool.h>
 #include <stdio.h>
 
 #include "akashaLLRBContext.h"
 #include "akashaCS.h"
 
+extern struct Tree* treeDeepCopy(struct Context* newContext, struct Tree* oldTree); // FIXME
+extern bool eqTree(struct Tree*, struct Tree*);
 extern void allocator(struct Context* context);
 void showTrace(struct Iterator* iter); //FIXME
 
@@ -159,35 +162,32 @@
     struct IterElem *oldElem = iter->previousDepth->head->next;
     struct IterElem *newElem = iter->head;
 
-    while (newElem->next != NULL) {
-        // FIXME: simple implementation O(n^2)
-        oldElem = oldElem->next;
-        newElem = newElem->next;
-    }
-
-    if (oldElem->val == iter->previousDepth->iteratedValue) {
-        newElem->next = iter->head;
-        iter->last    = iter->head;
-        goto meta(context, DuplicateTree);
-    } else {
-        struct IterElem* dup = context->heap;
+    while (oldElem->val != iter->previousDepth->iteratedValue) {
         allocate->size = sizeof(struct IterElem);
         allocator(context);
 
-        dup->val         = oldElem->val;
-        newElem->next    = dup;
-        goto meta(context, DuplicateIteratorElem);
+        newElem->next      = (struct IterElem*)context->data[context->dataNum];
+        newElem->next->val = oldElem->val;
+
+        newElem = newElem->next;
+        oldElem = oldElem->next;
     }
+    newElem->next = iter->head;
+    iter->last    = iter->head;
+    goto meta(context, DuplicateTree);
 }
 
 __code duplicateTree_stub(struct Context* context) {
-    goto duplicateTree(context, &context->data[Tree]->tree, &context->data[Iter]->iterator);
+    goto duplicateTree(context, &context->data[Allocate]->allocate, &context->data[Tree]->tree, &context->data[Iter]->iterator);
 }
 
-__code duplicateTree(struct Context* context, struct Tree* tree, struct Iterator* iter) {
+__code duplicateTree(struct Context* context, struct Allocate* allocate, struct Tree* tree, struct Iterator* iter) {
     // Tree must be non destructive.
     // If you use destructive tree, you must copy tree.
-    iter->previousDepth->tree = tree;
+    allocate->size = sizeof(Tree);
+    allocator(context);
+    iter->previousDepth->tree = treeDeepCopy(context, tree);
+    if (!eqTree(iter->previousDepth->tree, tree)) abort();
     goto meta(context, PutAndGoToNextDepth);
 }