Mercurial > hg > Members > innparusu > Gears
view src/llrb/llrb.c @ 22:4c3c0ad4a75d
add benchmark method
author | Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 28 Apr 2015 17:39:44 +0900 |
parents | 737a900518be |
children | 868c2918b634 |
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 #define ALLOCATE_SIZE 1000000000 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 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\n", data->node.key); print_tree(data->node.right, n+1); } } __code code1(struct Context* context) { context->data[0]->allocate.size = sizeof(long); context->data[0]->allocate.next = Code2; goto meta(context, Allocate); } __code meta(struct Context* context, enum Code next) { goto (context->code[next])(context); } __code put(struct Context* context) { context->data[context->dataSize]->node.key = context->data[0]->allocate.key; context->data[context->dataSize]->node.value = context->data[0]->allocate.value; if (context->root == 0) { context->root = context->data[context->dataSize]; context->root->node.color = Black; context->root->node.parent = 0; goto meta(context, context->data[0]->allocate.after_put); } context->data[context->dataSize]->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->dataSize]->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->dataSize]->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->dataSize]; } 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->dataSize]; } else { context->current = context->current->node.right; goto meta(context, InsertD); } } context->data[context->dataSize]->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[1]->count = 0; goto meta(context, Code3); } __code code3(struct Context* context) { if (context->data[1]->count == num) { goto meta(context, Code4); } context->data[0]->allocate.size = sizeof(struct Node); context->data[0]->allocate.next = Put; context->data[0]->allocate.after_put = Code3; context->data[0]->allocate.key = context->data[1]->count; context->data[0]->allocate.value = context->data[1]->count; context->data[1]->count++; goto meta(context, Allocate); } __code code4(struct Context* context) { st_time = getTime(); context->data[0]->allocate.size = sizeof(struct Node); context->data[0]->allocate.next = Put; context->data[0]->allocate.after_put = Code5; context->data[0]->allocate.key = num+1; context->data[0]->allocate.value = num+1; goto meta(context, Allocate); } __code code5(struct Context* context) { ed_time = getTime(); // printf("%ld %0.12f\n", context->data[1]->count-1, ed_time-st_time); 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)); context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE); context->data = malloc(sizeof(union Data**)*ALLOCATE_SIZE); context->heap = malloc(sizeof(union Data*)*ALLOCATE_SIZE); initLLRBContext(context); goto start_code(context, Code1); }