view src/llrb/llrb.c @ 23:868c2918b634

Non Destructive llrb
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Thu, 30 Apr 2015 19:07:23 +0900
parents 4c3c0ad4a75d
children 7494c0b87ec4
line wrap: on
line source

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#include "llrbContext.h"

#include "allocate.h"
#include "origin_cs.h"

#ifdef CLANG
#define _CbC_retrun __return
#define _CbC_environment __environment
#endif

#define NUM 100

extern __code initLLRBContext(struct Context* context);
void colorFlip(struct Context*);
void rotateLeft(struct Context*);
void rotateRight(struct Context*);
/* 
__code code1(Allocate allocate) {
    allocate.size = sizeof(long);
    allocate.next = Code2;
    goto Allocate(allocate);
}
*/
static double st_time;
static double ed_time;
static int num;
static clock_t c1,c2;

static double getTime() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

void print_tree(union Data* data, int n) {
    if (data != 0) {
        print_tree(data->node.left, n+1);
        for (int i=0;i<n;i++)
            printf("  ");
        printf("key=%d depth=%d\n", data->node.key, n);
        print_tree(data->node.right, n+1);
    }
}

__code code1(struct Context* context) {
    context->data[Allocate]->allocate.size = sizeof(long);
    context->data[Allocate]->allocate.next = Code2;
    goto meta(context, Allocator);
}

__code meta(struct Context* context, enum Code next) {
    goto (context->code[next])(context);
}

__code put(struct Context* context) {
    struct Tree* tree = &context->data[Tree]->tree;
    
    if (tree->root == 0) {
        struct Node* node = &context->data[Allocate]->allocate.node;
        node->color = Black;
        node->left = 0;
        node->right = 0;

        context->data[Allocate]->allocate.next = InitNode;
        goto meta(context, Allocator);
    }

    tree->current = tree->root;
    goto meta(context, Compare);
}

__code initNode(struct Context* context) {
    struct Node* persistentNode = &context->data[context->dataNum]->node;
    struct Node* temporalNode = &context->data[Allocate]->allocate.node;

    struct Tree* tree = &context->data[Tree]->tree;

    *persistentNode = *temporalNode;

    if (tree->root == 0 || tree->result == 0) {
        tree->root = context->data[context->dataNum];
        goto meta(context, context->data[Allocate]->allocate.after_put);
    }

}

__code compare(struct Context* context) {
    int persistentKey = context->data[Tree]->tree.current->node.key;
    int temporalKey = context->data[Allocate]->allocate.node.key;

    struct Tree* tree = &context->data[Tree]->tree;

    if (persistentKey == temporalKey) {
        tree->result = 0;
    } else if (persistentKey < temporalKey) {
        tree->result = 1;
    } else {
        tree->result = -1;
    }

    goto meta(context, Insert);
}
        
__code insert(struct Context* context) {
    struct Node* persistentNode = &context->data[Tree]->tree.current->node;
    struct Node* temporalNode = &context->data[Allocate]->allocate.node;

    struct Tree* tree = &context->data[Tree]->tree;

    switch (context->data[Tree]->tree.result) {
    case 0:
        temporalNode->right = persistentNode->right;
        temporalNode->left = persistentNode->left;
        temporalNode->color = persistentNode->color;

        context->data[Allocate]->allocate.next = InitNode;
        goto meta(context, Allocator);
    case 1:
        tree->current = persistentNode->right;
        goto meta(context, Compare);
    case -1:
        tree->current = persistentNode->left;
        goto meta(context, Compare);
    }
}
/* __code put(struct Context* context) { */
/*     context->data[context->dataNum]->node.key = context->data[0]->allocate.key; */
/*     context->data[context->dataNum]->node.value = context->data[0]->allocate.value; */
/*     if (context->root == 0) { */
/*         context->root = context->data[context->dataNum]; */
/*         context->root->node.color = Black; */
/*         context->root->node.parent = 0; */
/*         goto meta(context, context->data[0]->allocate.after_put); */
/*     } */
/*     context->data[context->dataNum]->node.color = Red; */
/*     context->current = context->root; */
/*     goto meta(context, InsertD); */
/* } */

/* __code insertDown(struct Context* context) { */
/*     int persistentKey = context->current->node.key; */
/*     int temporalKey = context->data[context->dataNum]->node.key; */
    
/*     if (context->current->node.right != 0 && context->current->node.left != 0) { */
/*         if (context->current->node.right->node.color == Red && context->current->node.left->node.color == Red) { */
/*             colorFlip(context); */
/*         } */
/*     } */
    
/*     if (persistentKey == temporalKey) { */
/*         context->current->node.value = context->data[context->dataNum]->node.value; */
/*         goto meta(context, context->data[0]->allocate.after_put); */
/*     } else if (temporalKey < persistentKey) { */
/*         if (context->current->node.left == 0) { */
/*             context->current->node.left = context->data[context->dataNum]; */
/*         } else { */
/*             context->current = context->current->node.left; */
/*             goto meta(context, InsertD); */
/*         } */
/*     } else { */
/*         if (context->current->node.right == 0) { */
/*             context->current->node.right = context->data[context->dataNum]; */
/*         } else { */
/*             context->current = context->current->node.right; */
/*             goto meta(context, InsertD); */
/*         } */
/*     } */

/*     context->data[context->dataNum]->node.parent = context->current; */
    
/*     goto meta(context, InsertU); */
/* } */

/* __code insertUp(struct Context* context) { */
/*     if (context->current->node.right != 0) { */
/*         if (context->current->node.right->node.color == Red) { */
/*             rotateLeft(context); */
/*         } */
/*     } */

/*     if (context->current->node.left != 0) { */
/*         if (context->current->node.left->node.left != 0) { */
/*             if (context->current->node.left->node.color == Red && context->current->node.left->node.left->node.color == Red) { */
/*                 rotateRight(context); */
/*             } */
/*         } */
/*     } */

/*     if (context->current->node.right != 0 && context->current->node.left != 0) { */
/*         if (context->current->node.right->node.color == Red && context->current->node.left->node.color == Red) { */
/*             colorFlip(context); */
/*         } */
/*     }     */
    
/*     if (context->current->node.parent == 0) { */
/*         context->root = context->current; */
/*         context->root->node.color = Black; */
/*         goto meta(context, context->data[0]->allocate.after_put); */
/*     } */
    
/*     if (context->current->node.parent != 0) { */
/*         if (context->current->node.parent->node.key < context->current->node.key) { */
/*             context->current->node.parent->node.right = context->current; */
/*         } else { */
/*             context->current->node.parent->node.left = context->current; */
/*         } */
/*     } */
    
/*     context->current = context->current->node.parent; */
/*     goto meta(context, InsertU); */
/* } */

/* void rotateLeft(struct Context* context) { */
/*     union Data* tmp = context->current->node.right; */
/*     context->current->node.right = tmp->node.left; */
/*     tmp->node.left = context->current; */
/*     tmp->node.color = tmp->node.left->node.color; */
/*     tmp->node.parent = tmp->node.left->node.parent; */
/*     tmp->node.left->node.color = Red; */
/*     tmp->node.left->node.parent = tmp; */
/*     context->current = tmp; */
/* } */

/* void rotateRight(struct Context* context) { */
/*     union Data* tmp = context->current->node.left; */
/*     context->current->node.left = tmp->node.right; */
/*     tmp->node.right = context->current; */
/*     tmp->node.color = tmp->node.right->node.color; */
/*     tmp->node.parent = tmp->node.right->node.parent; */
/*     tmp->node.right->node.color = Red; */
/*     tmp->node.right->node.parent = tmp; */
/*     context->current = tmp; */
/* } */

/* void colorFlip(struct Context* context) { */
/*     context->current->node.color ^= 1; */
/*     context->current->node.left->node.color ^= 1; */
/*     context->current->node.right->node.color ^= 1; */
/* } */

/*
__code code2(Allocate allocate, Count count) {
    count.count = 0;
    goto code3(count);
}
*/

__code code2(struct Context* context) {
    context->data[2]->count = 0;
    goto meta(context, Code3);
}

__code code3(struct Context* context) {
    if (context->data[2]->count == num) {
        goto meta(context, Code4);
    }
    context->data[Allocate]->allocate.size = sizeof(struct Node);
    context->data[Allocate]->allocate.after_put = Code3;
    context->data[Allocate]->allocate.node.key = context->data[2]->count;
    context->data[Allocate]->allocate.node.value = context->data[2]->count;
    context->data[2]->count++;
    goto meta(context, Put);
}

__code code4(struct Context* context) {
    c1 = clock();
    context->data[Allocate]->allocate.size = sizeof(struct Node);
    context->data[Allocate]->allocate.next = Put;
    context->data[Allocate]->allocate.after_put = Code5;
    context->data[Allocate]->allocate.node.key = num+1;
    context->data[Allocate]->allocate.node.value = num+1;

    goto meta(context, Allocator);
}

__code code5(struct Context* context) {
    c2 = clock();
    //printf("%ld %ld\n", context->data[1]->count-1, (long)c2-c1);
    print_tree(context->root, 0);
    goto meta(context, Exit);
}

int main(int argc, char** argv) {
    num = (int)atoi(argv[1]);
    struct Context* context = (struct Context*)malloc(sizeof(struct Context));
    initLLRBContext(context);
    goto start_code(context, Code1);
}