view src/insert_verification/main.c @ 15:d6d6e075b498

Show traces in all paths
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Sun, 20 Mar 2016 22:47:53 +0900
parents 1bbaafdafa47
children 3acaadc0a60c
line wrap: on
line source

#include <stdio.h>

#include "akashaLLRBContext.h"
#include "akashaCS.h"

extern void allocator(struct Context* context);
void showTrace(struct Iterator* iter); //FIXME

void printTree(struct Node* node, int n) {
    if (node != 0) {
        printTree(node->left, n+1);
        for (int i=0;i<n;i++)
            printf("  ");
        printf("key=%d value=%d color=%s\t%p\n", node->key, node->value,/* n, */node->color==0? "R":"B", node);
        printTree(node->right, n+1);
    }
}

__code showTree_stub(struct Context* context) {
    goto showTree(context, &context->data[Tree]->tree);
}

__code showTree(struct Context* context, struct Tree* tree) {
    printTree(tree->root, 0);
    puts("");

    goto meta(context, Exit);
}

__code verifySpecification(struct Context* context) {
}

__code iterateInsertion_stub(struct Context* context) {
    goto iterateInsertion(context, &context->data[Iter]->iterator, &context->data[Node]->node);
}

__code iterateInsertion(struct Context* context, struct Iterator* iter, struct Node* node) {
    // puts all elements in iterator into tree.
    node->key   = iter->head->val;
    node->value = iter->head->val;
    iter->head  = iter->head->next;

    if (iter->head == iter->last) {
        context->next = ShowTree;
    } else {
        context->next = IterateInsertion;
    }
    goto meta(context, Put);
}

__code putAndGoToNextDepth_stub(struct Context* context) {
    goto putAndGoToNextDepth(context, &context->data[Iter]->iterator, &context->data[Tree]->tree, &context->data[Node]->node);
}

__code putAndGoToNextDepth(struct Context* context, struct Iterator* iter, struct Tree* tree, struct Node* node) {
    node->key           = iter->head->val;
    node->value         = iter->head->val;
    iter->head          = iter->head->next;
    iter->iteratedValue = node->value;

    if (iter->head == iter->head->next) {
        context->next = GoToPreviousDepth;
    } else {
        context->next = DuplicateIterator;
    }
    goto meta(context, Put);
}

__code duplicateIterator_stub(struct Context* context) {
    goto duplicateIterator(context, &context->data[Allocate]->allocate, &context->data[Iter]->iterator);
}

__code duplicateIterator(struct Context* context, struct Allocate* allocate, struct Iterator* iter) {
    struct Iterator* newIter = context->heap;
    allocate->size = sizeof(struct Iterator);
    allocator(context);

    struct IterElem* dup = context->heap;
    allocate->size = sizeof(struct IterElem);
    allocator(context);

    dup->val  = iter->head->val;
    dup->next = NULL;

    newIter->previousDepth = iter;
    newIter->head          = dup;
    newIter->last          = NULL;
    context->data[Iter]    = (union Data*) newIter;

    goto duplicateIteratorElem_stub(context);
}

__code duplicateIteratorElem_stub(struct Context* context) {
    goto duplicateIteratorElem(context, &context->data[Allocate]->allocate, &context->data[Iter]->iterator);
}

__code duplicateIteratorElem(struct Context* context, struct Allocate* allocate, struct Iterator* iter) {
    // All elements in iterator must be unique.
    struct IterElem *oldElem = iter->previousDepth->head;
    struct IterElem *newElem = iter->head;


    while (newElem->next != NULL) {
        // FIXME: simple implementation O(n^2)
        oldElem = oldElem->next;
        newElem = newElem->next;
    }

    if (oldElem == iter->previousDepth->head) {
        newElem->next = iter->head;
        iter->last    = newElem;
        goto duplicateTree_stub(context); // meta
    } else {
        struct IterElem* dup = context->heap;
        allocate->size = sizeof(struct IterElem);
        allocator(context);

        dup->val         = oldElem->next->val;
        newElem->next    = dup;
        goto duplicateIteratorElem_stub(context); // meta
    }
}

__code duplicateTree_stub(struct Context* context) {
    goto duplicateTree(context, &context->data[Tree]->tree, &context->data[Iter]->iterator);
}

__code duplicateTree(struct Context* context, struct Tree* tree, struct Iterator* iter) {
    // Tree must be non destructive.
    // If you use destructive tree, you must copy tree.
    iter->previousDepth->tree = tree;
    goto meta(context, PutAndGoToNextDepth);
}

__code goToPreviousDepth(struct Context* context) {
    struct Iterator* finishedIter = &context->data[Iter]->iterator;

    showTrace(finishedIter); // FIXME: show trace

    while (finishedIter->head == finishedIter->last) {
        if (finishedIter->previousDepth == NULL) {
            goto meta(context, ShowTree); // all enumerations finished.
        }

        finishedIter = finishedIter->previousDepth;
        // TODO: cleanup memory
    }
    context->data[Iter] = (union Data*)finishedIter;
    context->data[Tree] = (union Data*)finishedIter->tree;

    goto meta(context, PutAndGoToNextDepth);
}

void showTrace(struct Iterator* iter) {
    printf("show trace(reversed):");

    for (; iter != NULL; iter = iter->previousDepth) {
        printf("%u ", iter->iteratedValue);
    }
    printf("\n");
}

int main(int argc, char const* argv[]) {
    goto startCode(PutAndGoToNextDepth);
}