Mercurial > hg > CbC > old > akasha
changeset 9:e864ede359cc
Add iterator
author | Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 15 Mar 2016 16:47:41 +0900 |
parents | 46bc6ea5fa81 |
children | 48bcaf3f90ef |
files | README src/insert_verification/akashaCS.c src/insert_verification/akashaLLRBContext.c src/insert_verification/include/akashaLLRBContext.h src/insert_verification/main.c |
diffstat | 5 files changed, 56 insertions(+), 8 deletions(-) [+] |
line wrap: on
line diff
--- a/README Tue Mar 15 12:02:58 2016 +0900 +++ b/README Tue Mar 15 16:47:41 2016 +0900 @@ -15,7 +15,8 @@ # Coding Rules -variable naming rule: camelCase +variable naming rule: camelCase (e.g. hogeFugaPiyo) file naming rule: camelCase +separator of special prefix and suffix: under score (meta_, _stub) tab: soft tab (4 spaces)
--- a/src/insert_verification/akashaCS.c Tue Mar 15 12:02:58 2016 +0900 +++ b/src/insert_verification/akashaCS.c Tue Mar 15 16:47:41 2016 +0900 @@ -1,7 +1,7 @@ #include <stdlib.h> #include "akashaLLRBContext.h" -extern __code initLLRBContext(struct Context*); +extern __code initLLRBContext(struct Context*, enum Code); __code meta(struct Context* context, enum Code next) { goto (context->code[next])(context); @@ -9,9 +9,8 @@ __code startCode(enum Code next) { struct Context* context = (struct Context*)malloc(sizeof(struct Context)); - initLLRBContext(context); - goto meta(context, next); + goto initLLRBContext(context, next); } __code exitCode(struct Context* context) {
--- a/src/insert_verification/akashaLLRBContext.c Tue Mar 15 12:02:58 2016 +0900 +++ b/src/insert_verification/akashaLLRBContext.c Tue Mar 15 16:47:41 2016 +0900 @@ -6,7 +6,7 @@ extern __code showTree_stub(struct Context*); /* definitions from llrb */ -extern __code meta(struct Context*); +extern __code meta(struct Context*, enum Code next); extern __code put_stub(struct Context*); extern __code replaceNode_stub(struct Context*); extern __code insertNode_stub(struct Context*); @@ -41,7 +41,10 @@ extern __code deleteCase6_stub(struct Context*); extern __code exitCode(struct Context*); -__code initLLRBContext(struct Context* context) { +__code initIterator(struct Context*); +__code initFinishIterator(struct Context*, struct IterElem*); + +__code initLLRBContext(struct Context* context, enum Code next) { context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE; context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE); context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE); @@ -79,6 +82,9 @@ context->data[Node] = context->heap; context->heap += sizeof(struct Node); + context->data[Iter] = context->heap; + context->heap += sizeof(struct Iterator); + context->dataNum = Node; struct Tree* tree = &context->data[Tree]->tree; @@ -88,4 +94,34 @@ context->node_stack = stack_init(sizeof(struct Node*), 100); context->code_stack = stack_init(sizeof(enum Code), 100); + + context->next = next; + goto initIterator(context); } + +__code initIterator(struct Context* context) { + struct IterElem* ie = (struct IterElem*)malloc(sizeof(struct IterElem)); + struct Iterator* iter = &context->data[Iter]; + + ie->val = 0; + ie->next = NULL; + iter->head = ie; + + goto initIteratorElem(context, ie); +} + +__code initIteratorElem(struct Context* context, struct IterElem* prev) { + if (prev->val >= LIMIT_OF_VERIFICATION_SIZE) { goto initFinishIterator(context, prev); } + + struct IterElem* ie = (struct IterElem *)malloc(sizeof(struct IterElem)); + ie->val = prev->val + 1; + prev->next = ie; + goto initIteratorElem(context, ie); +} + +__code initFinishIterator(struct Context* context, struct IterElem* elem) { + struct Iterator* iter = &context->data[Iter]; + elem->next = iter->head; + iter->last = iter->head; + goto meta(context, context->next); +}
--- a/src/insert_verification/include/akashaLLRBContext.h Tue Mar 15 12:02:58 2016 +0900 +++ b/src/insert_verification/include/akashaLLRBContext.h Tue Mar 15 16:47:41 2016 +0900 @@ -2,6 +2,7 @@ #include "stack.h" #define ALLOCATE_SIZE 1000 +#define LIMIT_OF_VERIFICATION_SIZE 4 enum Code { InsertOnce, @@ -53,6 +54,7 @@ Allocate, Tree, Node, + Iter, }; struct Context { @@ -101,4 +103,16 @@ enum Code next; long size; } allocate; + + /* for verification */ + struct IterElem { + unsigned int val; + struct IterElem* next; + } iterElem; + struct Iterator { + struct Tree* tree; + struct Iterator* previousDepth; + struct IterElem* head; + struct IterElem* last; + } iterator; };
--- a/src/insert_verification/main.c Tue Mar 15 12:02:58 2016 +0900 +++ b/src/insert_verification/main.c Tue Mar 15 16:47:41 2016 +0900 @@ -3,7 +3,6 @@ #include "akashaLLRBContext.h" #include "akashaCS.h" - void printTree(struct Node* node, int n) { if (node != 0) { printTree(node->left, n+1); @@ -19,7 +18,6 @@ } __code insertOnce(struct Context* context, struct Node* node) { - node->key = rand()%100+1; node->value = 100;