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;