changeset 19:9302b1a48008

add llrb
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 21 Apr 2015 22:36:23 +0900
parents ec4e7a81bddf
children 324c44f2076f
files src/CMakeLists.txt src/llrb/CMakeLists.txt src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h
diffstat 5 files changed, 140 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/src/CMakeLists.txt	Tue Apr 21 13:33:23 2015 +0900
+++ b/src/CMakeLists.txt	Tue Apr 21 22:36:23 2015 +0900
@@ -13,3 +13,4 @@
 
 add_subdirectory(allocate)
 add_subdirectory(list)
+add_subdirectory(llrb)
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/CMakeLists.txt	Tue Apr 21 22:36:23 2015 +0900
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 2.8)
+
+add_executable(llrb
+               llrb.c
+               llrbContext.c
+)
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/llrb.c	Tue Apr 21 22:36:23 2015 +0900
@@ -0,0 +1,70 @@
+#include <stdio.h>
+#include <stdlib.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 1024
+
+extern __code initLLRBContext(struct Context* context);
+/* 
+__code code1(Allocate allocate) {
+    allocate.size = sizeof(long);
+    allocate.next = Code2;
+    goto Allocate(allocate);
+}
+*/
+
+__code code1(struct Context* context) {
+    context->data[0]->allocate.size = sizeof(struct Node);
+    context->data[0]->allocate.next = Put;
+    context->data[0]->allocate.after_put = 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 = Red;
+        goto meta(context, context->data[0]->allocate.after_put);
+    }
+    goto meta(context, Insert);
+}
+
+__code insert(struct Context* context) {
+    goto meta(context, context->data[0]->allocate.after_put);
+}
+
+/*
+__code code2(Allocate allocate, Count count) {
+    count.count = 0;
+    goto code3(count);
+}
+*/
+
+__code code2(struct Context* context) {
+    goto meta(context, Exit);
+}
+
+int main() {
+    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);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/llrbContext.c	Tue Apr 21 22:36:23 2015 +0900
@@ -0,0 +1,22 @@
+#include "llrbContext.h"
+extern __code code1(struct Context*);
+extern __code code2(struct Context*);
+extern __code meta(struct Context*);
+extern __code allocate(struct Context*);
+extern __code put(struct Context*);
+extern __code insert(struct Context*);
+extern __code exit_code(struct Context*);
+
+__code initLLRBContext(struct Context* context) {
+    context->codeSize = 3;
+    context->code[Code1]    = code1;
+    context->code[Code2]    = code2;
+    context->code[Allocate] = allocate;
+    context->code[Put]      = put;
+    context->code[Insert]   = insert;
+    context->code[Exit]     = exit_code;
+    
+    context->dataSize = 0;
+    context->data[context->dataSize] = context->heap;
+    context->heap += sizeof(struct Allocate);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/llrbContext.h	Tue Apr 21 22:36:23 2015 +0900
@@ -0,0 +1,41 @@
+/* Context definition for llrb example */
+
+enum Code {
+    Code1,
+    Code2,
+    Allocate,
+    Put,
+    Insert,
+    Exit,
+};
+
+enum Color {
+    Red,
+    Black,
+};
+
+struct Context {
+    int codeSize;
+    __code (**code) (struct Context *);
+    void* heap;
+    union Data* root;
+    int dataSize;
+    union Data **data;
+};
+
+union Data {
+    struct Node {
+        int key;
+        int value;
+        enum Color color;
+        union Data* left;
+        union Data* right;
+    } node;
+    struct Allocate {
+        long size;
+        enum Code next;
+        enum Code after_put;
+        int key;
+        int value;
+    } allocate;
+};