Mercurial > hg > CbC > old > akasha

changeset 25:38ba1606e62d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Refresh memory only between put and put
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Wed, 13 Apr 2016 16:30:47 +0900
parents 8ca38f736745
children cf7cbe70404f
files src/insert_verification/CMakeLists.txt src/insert_verification/akashaCS.c src/insert_verification/akashaLLRBContext.c src/insert_verification/allocate.c src/insert_verification/include/akashaLLRBContext.h
diffstat 5 files changed, 134 insertions(+), 139 deletions(-) [+]
line wrap: on
line diff
--- a/src/insert_verification/CMakeLists.txt	Wed Apr 13 16:19:05 2016 +0900
+++ b/src/insert_verification/CMakeLists.txt	Wed Apr 13 16:30:47 2016 +0900
@@ -11,8 +11,8 @@
                main.c
                akashaCS.c
                akashaLLRBContext.c
-               allocate.c
 
+               ${llrb_path}/allocate.c
                ${llrb_path}/llrb.c
                ${llrb_path}/compare.c
                ${llrb_path}/stack.c
--- a/src/insert_verification/akashaCS.c	Wed Apr 13 16:19:05 2016 +0900
+++ b/src/insert_verification/akashaCS.c	Wed Apr 13 16:30:47 2016 +0900
@@ -1,9 +1,135 @@
+#include <stdio.h>
 #include <stdlib.h>
+#include <string.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];
+}
+
+struct Node* nodeDeepCopy(struct Context* newContext, struct Node* oldNode) {
+    if (oldNode == NULL) return NULL;
+
+    struct Node* newNode = akashaMalloc(newContext, sizeof(struct Node));
+    newNode->next  = oldNode->next;
+    newNode->key   = oldNode->key;
+    newNode->value = oldNode->value;
+    newNode->color = oldNode->color;
+
+    if (oldNode->left != NULL)  {
+        newNode->left = nodeDeepCopy(newContext, oldNode->left);
+    } else {
+        newNode->left = NULL;
+    }
+
+    if (oldNode->right != NULL)  {
+        newNode->right = nodeDeepCopy(newContext, oldNode->right);
+    } else {
+        newNode->right = NULL;
+    }
+
+    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);
+}
+
+void iterElemDeepCopy(struct Context* newContext, struct Iterator* newIter, struct Iterator *oldIter) {
+    newIter->head = (struct IterElem*)akashaMalloc(newContext, sizeof(struct IterElem));
+
+    newIter->head->val = oldIter->head->val;
+    struct IterElem *oldElem = oldIter->head;
+    struct IterElem *newElem = newIter->head;
+    while (1) {
+        if (oldElem->next->val == oldIter->head->val) break;
+        newElem->next = akashaMalloc(newContext, sizeof(struct IterElem));
+
+        newElem->next->val = oldElem->next->val;
+        newElem = newElem->next;
+        oldElem = oldElem->next;
+    }
+    newElem->next = newIter->head;
+
+    while (newElem->val != oldIter->last->val) {
+        newElem = newElem->next;
+    }
+    newIter->last = newElem;
+}
+
+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->iteratedValue = oldIter->iteratedValue;
+
+    iterElemDeepCopy(newContext, newIter, oldIter);
+
+    if (oldIter->previousDepth != NULL) {
+        newIter->previousDepth = akashaMalloc(newContext, sizeof(struct Iterator));
+        iterDeepCopy(newContext, newIter->previousDepth, oldIter->previousDepth);
+    } else {
+        newIter->previousDepth = NULL;
+    }
+}
+
+void memoryRefresh(struct Context* oldContext) {
+    if (oldContext->node_stack->num != 0) { abort(); }
+    if (oldContext->code_stack->num != 0) { abort(); }
+
+    struct Context* newContext = (struct Context*)malloc(sizeof(struct Context));
+
+    newContext->dataLimit = oldContext->dataLimit*2;
+    newContext->heapLimit = oldContext->heapLimit*2;
+    newContext->code      = oldContext->code;
+    newContext->data      = malloc(newContext->dataLimit * sizeof(union Data*));
+    newContext->heapStart = malloc(newContext->heapLimit);
+    newContext->codeNum   = Exit;
+    newContext->heap      = newContext->heapStart;
+    memset(newContext->heapStart, newContext->heapLimit, 0);
+
+    printf("reallocation! : %lu\n", newContext->heapLimit);
+
+    newContext->data[Allocate] = newContext->heap;
+    newContext->heap += sizeof(struct Allocate);
+    newContext->data[Allocate]->allocate = oldContext->data[Allocate]->allocate;
+
+    newContext->data[Tree] = newContext->heap;
+    newContext->heap += sizeof(struct Tree);
+
+    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);
+    iterDeepCopy(newContext, &newContext->data[Iter]->iterator, &oldContext->data[Iter]->iterator);
+
+    newContext->node_stack = oldContext->node_stack;
+    newContext->code_stack = oldContext->code_stack;
+    newContext->next       = oldContext->next;
+    free(oldContext->data);
+    *oldContext = *newContext;
+}
+
 __code meta(struct Context* context, enum Code next) {
+    if ((next == Put) && (context->dataNum > (context->dataLimit * 0.9))) {
+        memoryRefresh(context);
+    }
     goto (context->code[next])(context);
 }
 
--- a/src/insert_verification/akashaLLRBContext.c	Wed Apr 13 16:19:05 2016 +0900
+++ b/src/insert_verification/akashaLLRBContext.c	Wed Apr 13 16:30:47 2016 +0900
@@ -59,9 +59,10 @@
 __code initLLRBContext(struct Context* context, enum Code next) {
     context->codeNum   = Exit;
 
-    context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE;
+    context->dataLimit = ALLOCATE_SIZE;
+    context->heapLimit = sizeof(union Data)*context->dataLimit;
     context->code      = malloc(sizeof(__code*)*context->codeNum);
-    context->data      = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
+    context->data      = malloc(sizeof(union Data*)*context->dataLimit);
     context->heapStart = malloc(context->heapLimit);
     memset(context->heapStart, context->heapLimit, 0);
 
--- a/src/insert_verification/allocate.c	Wed Apr 13 16:19:05 2016 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,133 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-
-#include "llrbContext.h"
-
-void* akashaMalloc(struct Context* context, size_t size) {
-    context->data[++context->dataNum] = context->heap;
-    context->heap += size;
-    return context->data[context->dataNum];
-}
-
-
-struct Node* nodeDeepCopy(struct Context* newContext, struct Node* oldNode) {
-    if (oldNode == NULL) return NULL;
-
-    struct Node* newNode = akashaMalloc(newContext, sizeof(struct Node));
-    newNode->next  = oldNode->next;
-    newNode->key   = oldNode->key;
-    newNode->value = oldNode->value;
-    newNode->color = oldNode->color;
-
-    if (oldNode->left != NULL)  {
-        newNode->left = nodeDeepCopy(newContext, oldNode->left);
-    } else {
-        newNode->left = NULL;
-    }
-
-    if (oldNode->right != NULL)  {
-        newNode->right = nodeDeepCopy(newContext, oldNode->right);
-    } else {
-        newNode->right = NULL;
-    }
-
-    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);
-}
-
-void iterElemDeepCopy(struct Context* newContext, struct Iterator* newIter, struct Iterator *oldIter) {
-    newIter->head = (struct IterElem*)akashaMalloc(newContext, sizeof(struct IterElem));
-
-    newIter->head->val = oldIter->head->val;
-    struct IterElem *oldElem = oldIter->head;
-    struct IterElem *newElem = newIter->head;
-    while (1) {
-        if (oldElem->next->val == oldIter->head->val) break;
-        newElem->next = akashaMalloc(newContext, sizeof(struct IterElem));
-
-        newElem->next->val = oldElem->next->val;
-        newElem = newElem->next;
-        oldElem = oldElem->next;
-    }
-    newElem->next = newIter->head;
-
-    while (newElem->val != oldIter->last->val) {
-        newElem = newElem->next;
-    }
-    newIter->last = newElem;
-}
-
-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->iteratedValue = oldIter->iteratedValue;
-
-    iterElemDeepCopy(newContext, newIter, oldIter);
-
-    if (oldIter->previousDepth != NULL) {
-        newIter->previousDepth = akashaMalloc(newContext, sizeof(struct Iterator));
-        iterDeepCopy(newContext, newIter->previousDepth, oldIter->previousDepth);
-    } else {
-        newIter->previousDepth = NULL;
-    }
-}
-
-void memoryRefresh(struct Context* oldContext) {
-    struct Context* newContext = (struct Context*)malloc(sizeof(struct Context));
-
-    newContext->heapLimit = oldContext->heapLimit*2;
-    newContext->code      = oldContext->code;
-    newContext->data      = malloc((newContext->heapLimit / sizeof(union Data)) * sizeof(union Data*));
-    newContext->heapStart = malloc(newContext->heapLimit);
-    newContext->codeNum   = Exit;
-    newContext->heap      = newContext->heapStart;
-    memset(newContext->heapStart, newContext->heapLimit, 0);
-
-    printf("reallocation! : %lu\n", newContext->heapLimit);
-
-    newContext->data[Allocate] = newContext->heap;
-    newContext->heap += sizeof(struct Allocate);
-    newContext->data[Allocate]->allocate = oldContext->data[Allocate]->allocate;
-
-    newContext->data[Tree] = newContext->heap;
-    newContext->heap += sizeof(struct Tree);
-
-    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);
-    iterDeepCopy(newContext, &newContext->data[Iter]->iterator, &oldContext->data[Iter]->iterator);
-
-    newContext->node_stack = oldContext->node_stack;
-    newContext->code_stack = oldContext->code_stack;
-    newContext->next       = oldContext->next;
-    free(oldContext->data);
-    *oldContext = *newContext;
-}
-
-void allocator(struct Context* context) {
-    struct Allocate* allocate = &context->data[Allocate]->allocate;
-
-    if ((((long)context->heap - (long)context->heapStart) > (context->heapLimit - allocate->size)) ||
-          (context->dataNum >= (context->heapLimit / sizeof(union Data)))) {
-        memoryRefresh(context);
-    }
-    context->data[++context->dataNum] = context->heap;
-    context->heap += allocate->size;
-    allocate->size = 0;
-}
--- a/src/insert_verification/include/akashaLLRBContext.h	Wed Apr 13 16:19:05 2016 +0900
+++ b/src/insert_verification/include/akashaLLRBContext.h	Wed Apr 13 16:30:47 2016 +0900
@@ -65,12 +65,13 @@
 
 struct Context {
     enum Code next;
-    int codeNum;
+    unsigned int codeNum;
     __code (**code) (struct Context*);
     void* heapStart;
     void* heap;
-    long heapLimit;
-    int dataNum;
+    unsigned long heapLimit;
+    unsigned long dataLimit;
+    unsigned long dataNum;
     stack_ptr code_stack;
     stack_ptr node_stack;
     union Data **data;