Mercurial > hg > Members > innparusu > Gears

annotate src/llrb/llrb.c @ 25:390cf0523ea7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add file
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Fri, 01 May 2015 05:35:10 +0900
parents 7494c0b87ec4
children 06fcbe45e85c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdio.h>
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 #include <stdlib.h>
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
3 #include <sys/time.h>
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 #include "llrbContext.h"
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 #include "allocate.h"
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 #include "origin_cs.h"
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
10 #include "stack.h"
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
11
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 #ifdef CLANG
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 #define _CbC_retrun __return
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 #define _CbC_environment __environment
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 #endif
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 #define NUM 100
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 extern __code initLLRBContext(struct Context* context);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
20
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 /*
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 __code code1(Allocate allocate) {
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 allocate.size = sizeof(long);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 allocate.next = Code2;
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 goto Allocate(allocate);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 */
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
28 static double st_time;
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
29 static double ed_time;
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
30 static int num;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
31 static clock_t c1,c2;
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
32
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
33 static stack_ptr pstack;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
34 static union Data* pre;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
35
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
36 static double getTime() {
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
37 struct timeval tv;
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
38 gettimeofday(&tv, NULL);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
39 return tv.tv_sec + (double)tv.tv_usec*1e-6;
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
40 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
41
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
42 void print_tree(union Data* data, int n) {
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
43 if (data != 0) {
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
44 print_tree(data->node.left, n+1);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
45 for (int i=0;i<n;i++)
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
46 printf(" ");
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
47 printf("key=%d depth=%d\t%p\n", data->node.key, n, data);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
48 print_tree(data->node.right, n+1);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
49 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
50 }
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 __code code1(struct Context* context) {
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
53 context->data[Allocate]->allocate.size = sizeof(long);
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
54 context->data[Allocate]->allocate.next = Code2;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
55 goto meta(context, Allocator);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 __code meta(struct Context* context, enum Code next) {
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 goto (context->code[next])(context);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 __code put(struct Context* context) {
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
63 struct Tree* tree = &context->data[Tree]->tree;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
64
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
65 if (tree->root == 0) {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
66 struct Node* node = &context->data[Allocate]->allocate.node;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
67 node->color = Black;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
68 node->left = 0;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
69 node->right = 0;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
70
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
71 context->data[Allocate]->allocate.next = InitNode;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
72 goto meta(context, Allocator);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
74
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
75 context->data[Allocate]->allocate.next = Insert;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
76 tree->current = tree->root;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
77
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
78 goto meta(context, Compare);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
79 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
80
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
81 __code clone(struct Context* context) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
82 struct Node* node = &context->data[context->dataNum]->node;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
83 struct Node* persistentNode = &context->data[Tree]->tree.current->node;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
84 struct Tree* tree = &context->data[Tree]->tree;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
85
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
86 *node = *persistentNode;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
87
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
88 switch (context->data[Tree]->tree.result) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
89 case 0:
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
90 stack_pop(pstack, &tree->current);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
91 goto meta(context, RotateL);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
92 case 1:
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
93 tree->current = persistentNode->right;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
94 node->right = context->heap;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
95 break;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
96 default:
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
97 tree->current = persistentNode->left;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
98 node->left = context->heap;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
99 break;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
100 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
101
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
102 if (context->data[Tree]->tree.current == 0) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
103 stack_pop(pstack, &context->data[Tree]->tree.current);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
104 context->data[Allocate]->allocate.next = InitNode;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
105 goto meta(context, Allocator);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
106 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
107
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
108 context->data[Allocate]->allocate.next = Insert;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
109 goto meta(context, Compare);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
112 __code initNode(struct Context* context) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
113 struct Node* node = &context->data[context->dataNum]->node;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
114 struct Node* temporalNode = &context->data[Allocate]->allocate.node;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
115 struct Tree* tree = &context->data[Tree]->tree;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
116
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
117 temporalNode->color = Red;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
118 *node = *temporalNode;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
119
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
120 if (tree->root == 0) {
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
121 tree->root = context->data[context->dataNum];
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
122 goto meta(context, context->data[Allocate]->allocate.after_put);
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
123 }
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
124
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
125 context->data[Allocate]->allocate.next = Insert;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
126 goto meta(context, RotateL);
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
127 }
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
128
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
129 __code compare(struct Context* context) {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
130 int persistentKey = context->data[Tree]->tree.current->node.key;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
131 int temporalKey = context->data[Allocate]->allocate.node.key;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
132
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
133 struct Tree* tree = &context->data[Tree]->tree;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
134
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
135 if (persistentKey == temporalKey) {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
136 tree->result = 0;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
137 } else if (persistentKey < temporalKey) {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
138 tree->result = 1;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
139 } else {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
140 tree->result = -1;
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
141 }
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
142
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
143 goto meta(context, context->data[Allocate]->allocate.next);
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
144 }
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
145
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
146 __code insert(struct Context* context) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
147 stack_push(pstack, &context->heap);
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
148
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
149 context->data[Allocate]->allocate.next = Clone;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
150 goto meta(context, Allocator);
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
151 }
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
152
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
153 __code rotateLeft(struct Context* context) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
154 struct Node* node = &context->data[Tree]->tree.current->node;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
155 struct Allocate* allocate = &context->data[Allocate]->allocate;
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
156
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
157 allocate->next = ChangeRef;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
158 allocate->node.key = node->key;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
159 allocate->node.key = node->key;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
160
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
161 if (node->right != 0) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
162 if (node->right->node.color == Red) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
163 union Data* tmp = context->data[Tree]->tree.current->node.right;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
164 context->data[Tree]->tree.current->node.right = tmp->node.left;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
165 tmp->node.left = context->data[Tree]->tree.current;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
166 tmp->node.color = tmp->node.left->node.color;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
167 tmp->node.left->node.color = Red;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
168 context->data[Tree]->tree.current = tmp;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
169 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
170 }
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
171
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
172 goto meta(context, RotateR);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
173 }
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
174
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
175 __code rotateRight(struct Context* context) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
176 struct Node* node = &context->data[Tree]->tree.current->node;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
177
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
178 if (node->left != 0) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
179 if (node->left->node.left != 0) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
180 if (node->left->node.color == Red && node->left->node.left->node.color == Red) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
181 union Data* tmp = context->data[Tree]->tree.current->node.left;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
182 context->data[Tree]->tree.current->node.left = tmp->node.right;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
183 tmp->node.right = context->data[Tree]->tree.current;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
184 tmp->node.color = tmp->node.right->node.color;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
185 tmp->node.right->node.color = Red;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
186 context->data[Tree]->tree.current = tmp;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
187 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
188 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
189 }
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
190
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
191 goto meta(context, ColorFlip);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
192 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
193 __code colorFlip(struct Context* context) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
194 struct Node* node = &context->data[Tree]->tree.current->node;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
195
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
196 if (node->right != 0 && node->left != 0) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
197 if (node->right->node.color == Red && node->left->node.color == Red) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
198 node->color ^= 1;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
199 node->left->node.color ^= 1;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
200 node->right->node.color ^= 1;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
201 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
202 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
203
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
204 goto meta(context, Compare);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
205 }
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
206
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
207 __code changeReference(struct Context* context) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
208 union Data* data = context->data[Tree]->tree.current;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
209
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
210 if (stack_pop(pstack, &context->data[Tree]->tree.current) == 0) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
211 struct Node* node = &context->data[Tree]->tree.current->node;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
212
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
213 switch (context->data[Tree]->tree.result) {
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
214 case 1:
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
215 node->left = data;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
216 break;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
217 default:
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
218 node->right = data;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
219 break;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
220 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
221
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
222 goto meta(context, RotateL);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
223 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
224
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
225 context->data[Tree]->tree.root = context->data[Tree]->tree.current;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
226
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
227 goto meta(context, context->data[Allocate]->allocate.after_put);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
228 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
229
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
230
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
231 /*
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 __code code2(Allocate allocate, Count count) {
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
233 count.count = 0;
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
234 goto code3(count);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
235 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 */
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
237
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
238 __code code2(struct Context* context) {
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
239 context->data[2]->count = 0;
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
240 goto meta(context, Code3);
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
241 }
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
242
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
243 __code code3(struct Context* context) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
244 struct Allocate* allocate = &context->data[Allocate]->allocate;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
245 long loop = context->data[2]->count;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
246 if (loop == num) {
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
247 goto meta(context, Code4);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
248 }
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
249 allocate->size = sizeof(struct Node);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
250 allocate->after_put = Code3;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
251 allocate->node.key = loop;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
252 allocate->node.value = loop;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
253
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
254 context->data[2]->count++;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
255 goto meta(context, Put);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
256 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
257
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
258 __code code4(struct Context* context) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
259 pre = context->data[Tree]->tree.root;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
260 context->data[Allocate]->allocate.size = sizeof(struct Node);
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
261 context->data[Allocate]->allocate.after_put = Code5;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
262 context->data[Allocate]->allocate.node.key = num;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
263 context->data[Allocate]->allocate.node.value = num;
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
264
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
265 goto meta(context, Put);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
266 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
267
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
268 __code code5(struct Context* context) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
269 puts("---prev---");
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
270 print_tree(pre, 0);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
271 puts("---follow---");
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
272 print_tree(context->data[Tree]->tree.root, 0);
25
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
273 puts("--Number of Data--");
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
274 printf("%d\n", context->dataNum);
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
275 stack_free(pstack);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
276 goto meta(context, Exit);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
277 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
278
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
279 int main(int argc, char** argv) {
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
280 num = (int)atoi(argv[1]);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
281 pstack = stack_init(sizeof(union Data*), num/2);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
282 struct Context* context = (struct Context*)malloc(sizeof(struct Context));
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
283 initLLRBContext(context);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
284 goto start_code(context, Code1);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
285 }