Mercurial > hg > Gears > GearsAgda
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); }