Mercurial > hg > CbC > old > akasha
changeset 25:38ba1606e62d
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 (2016-04-13) |
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;