Mercurial > hg > Members > innparusu > Gears

annotate src/llrb/llrb.c @ 47:348148d8fdb1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement get
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 19 May 2015 17:46:41 +0900
parents a0a58875c93f
children d191faf19961
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 #define NUM 100
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 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
15
19
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 __code code1(Allocate allocate) {
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 allocate.size = sizeof(long);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 allocate.next = Code2;
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 goto Allocate(allocate);
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 */
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
23 static double st_time;
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
24 static double ed_time;
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
25 static int num;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
26 static clock_t c1,c2;
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
27
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
28 static stack_ptr pstack;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
29 static struct Node* pre;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
30
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
31 static double getTime() {
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
32 struct timeval tv;
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
33 gettimeofday(&tv, NULL);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
34 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
35 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
36
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
37 void print_tree(struct Node* node, int n) {
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
38 if (node != 0) {
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
39 print_tree(node->left, n+1);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
40 for (int i=0;i<n;i++)
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
41 printf(" ");
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
42 printf("key=%d depth=%d\t%p\n", node->key, n, node);
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
43 print_tree(node->right, n+1);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
44 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
45 }
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 __code code1(struct Context* context) {
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
48 context->data[Allocate]->allocate.size = sizeof(long);
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
49 context->data[Allocate]->allocate.next = Code2;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
50 goto meta(context, Allocator);
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
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 __code meta(struct Context* context, enum Code next) {
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 goto (context->code[next])(context);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 }
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 __code put(struct Context* context) {
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
58 struct Tree* tree = &context->data[Tree]->tree;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
59 context->data[Next]->next = context->data[Allocate]->allocate.next;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
60
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
61 if (tree->root == 0) {
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
62 context->data[Allocate]->allocate.next = Insert;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
63 goto meta(context, Allocator);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
65
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
66 context->data[Allocate]->allocate.next = Create;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
67 tree->current = tree->root;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
68
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
69 goto meta(context, Compare);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
70 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
71
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
72 __code replaceNode(struct Context* context) {
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
73 struct Node* newNode = &context->data[context->dataNum]->node;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
74 struct Tree* tree = &context->data[Tree]->tree;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
75 struct Node* persistentNode = tree->current;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
76
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
77 int result = context->data[Tree]->tree.result;
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
78
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
79 *newNode = *persistentNode;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
80
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
81 if (result == 0) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
82 stack_pop(pstack, &tree->current);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
83 goto meta(context, RotateL);
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
84 } else if (result == 1) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
85 tree->current = persistentNode->right;
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
86 newNode->right = context->heap;
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
87 } else {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
88 tree->current = persistentNode->left;
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
89 newNode->left = context->heap;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
90 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
91
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
92 if (tree->current == 0) {
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
93 stack_pop(pstack, &tree->current);
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
94 context->data[Allocate]->allocate.next = Insert;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
95 goto meta(context, Allocator);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
96 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
97
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
98 context->data[Allocate]->allocate.next = Create;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
99 goto meta(context, Compare);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
102 __code insertNode(struct Context* context) {
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
103 struct Node* newNode = &context->data[context->dataNum]->node;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
104 struct Node* temporalNode = &context->data[Node]->node;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
105 struct Tree* tree = &context->data[Tree]->tree;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
106
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
107 temporalNode->color = Red;
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
108 *newNode = *temporalNode;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
109
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
110 if (tree->root == 0) {
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
111 newNode->color = Black;
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
112 tree->root = newNode;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
113 goto meta(context, context->data[Next]->next);
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
114 }
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
115
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
116 goto meta(context, RotateL);
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
117 }
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
118
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
119 __code compare(struct Context* context) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
120 int persistentKey = context->data[Tree]->tree.current->key;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
121 int temporalKey = context->data[Node]->node.key;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
122
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
123 struct Tree* tree = &context->data[Tree]->tree;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
124
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
125 if (persistentKey == temporalKey) {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
126 tree->result = 0;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
127 } else if (persistentKey < temporalKey) {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
128 tree->result = 1;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
129 } else {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
130 tree->result = -1;
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
131 }
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
132
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
133 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
134 }
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
135
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
136 __code createNode(struct Context* context) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
137 stack_push(pstack, &context->heap);
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
138
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
139 context->data[Allocate]->allocate.next = Replace;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
140 goto meta(context, Allocator);
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
141 }
20
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 __code rotateLeft(struct Context* context) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
144 struct Node* node = context->data[Tree]->tree.current;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
145
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
146 if (node->right != 0) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
147 if (node->right->color == Red) {
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
148 struct Node* tmp = node->right;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
149 node->right = tmp->left;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
150 tmp->left = node;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
151 tmp->color = tmp->left->color;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
152 tmp->left->color = Red;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
153 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
154 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
155 }
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 goto meta(context, RotateR);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
158 }
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
159
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
160 __code rotateRight(struct Context* context) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
161 struct Node* node = context->data[Tree]->tree.current;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
162
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
163 if (node->left != 0) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
164 if (node->left->left != 0) {
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
165 if (node->left->color == Red && node->left->left->color == Red) {
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
166 struct Node* tmp = node->left;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
167 node->left = tmp->right;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
168 tmp->right = node;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
169 tmp->color = tmp->right->color;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
170 tmp->right->color = Red;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
171 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
172 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
173 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
174 }
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
175
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
176 goto meta(context, ColorFlip);
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
177 }
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
178
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
179 __code colorFlip(struct Context* context) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
180 struct Node* node = context->data[Tree]->tree.current;
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
181
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
182 if (node->right != 0 && node->left != 0) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
183 if (node->right->color == Red && node->left->color == Red) {
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
184 node->color ^= 1;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
185 node->left->color ^= 1;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
186 node->right->color ^= 1;
24
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 }
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
189
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
190 goto meta(context, FixUp);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
191 }
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
192
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
193 __code fixUp(struct Context* context) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
194 struct Allocate* allocate = &context->data[Allocate]->allocate;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
195 struct Node* node = context->data[Tree]->tree.current;
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
196
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
197 allocate->next = ChangeRef;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
198
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
199 context->data[Node]->node.key = node->key;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
200 context->data[Tree]->tree.prev = node;
24
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 if (stack_pop(pstack, &context->data[Tree]->tree.current) == 0) {
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
203 goto meta(context, Compare);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
204 }
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
205
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
206 context->data[Tree]->tree.root = node;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
207
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
208 goto meta(context, context->data[Next]->next);
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
209 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
210
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
211 __code changeReference(struct Context* context) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
212 struct Node* node = context->data[Tree]->tree.current;
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
213 int result = context->data[Tree]->tree.result;
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
214
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
215 if (result == 1) {
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
216 node->right = context->data[Tree]->tree.prev;
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
217 } else if (result == -1) {
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
218 node->left = context->data[Tree]->tree.prev;
31
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
219 } else {
dbbafae822f8 modify Non-Destructive Red Black Tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
220 perror("bad status");
27
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
221 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
222
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
223 goto meta(context, RotateL);
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
224 }
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
225
47
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
226 __code get(struct Context* context) {
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
227 context->data[Tree]->tree.current = context->data[Tree]->tree.root;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
228 context->data[Next]->next = context->data[Allocate]->allocate.next;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
229 context->data[Allocate]->allocate.next = Traverse;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
230
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
231 goto meta(context, Compare);
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
232 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
233
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
234 __code traverse(struct Context* context) {
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
235 int result = context->data[Tree]->tree.result;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
236 struct Tree* tree = &context->data[Tree]->tree;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
237
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
238 if (result == 0) {
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
239 goto meta(context, context->data[Next]->next);
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
240 } else if (result == 1) {
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
241 tree->current = tree->current->right;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
242 } else {
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
243 tree->current = tree->current->left;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
244 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
245
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
246 if(tree->current == 0) {
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
247 goto meta(context, context->data[Next]->next);
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
248 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
249
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
250 goto meta(context, Compare);
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
251 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
252
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
253 /*
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
254 __code code2(Allocate allocate, Count count) {
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
255 count.count = 0;
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
256 goto code3(count);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
257 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
258 */
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
259
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
260 __code code2(struct Context* context) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
261 context->data[4]->count = 1;
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
262 goto meta(context, Code3);
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
263 }
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
264
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
265 __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
266 struct Allocate* allocate = &context->data[Allocate]->allocate;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
267 struct Node* node = &context->data[Node]->node;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
268 long loop = context->data[4]->count;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
269
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
270 if (loop == num) {
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
271 goto meta(context, Code4);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
272 }
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
273
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
274 allocate->size = sizeof(struct Node);
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
275 allocate->next = Code3;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
276
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
277 node->key = loop;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
278 node->value = loop;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
279
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
280 context->data[4]->count++;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
281 goto meta(context, Put);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
282 }
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
283
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
284 __code code4(struct Context* context) {
47
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
285 puts("---before---");
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
286 print_tree(context->data[Tree]->tree.root, 0);
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
287
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
288 struct Allocate* allocate = &context->data[Allocate]->allocate;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
289 allocate->size = sizeof(struct Node);
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
290 allocate->next = Code5;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
291
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
292 struct Node* node = &context->data[Node]->node;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
293 node->key = 0;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
294 node->value = 0;
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
295
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
296 goto meta(context, Put);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
297 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
298
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
299 __code code5(struct Context* context) {
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
300 puts("---after---");
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
301 print_tree(context->data[Tree]->tree.root, 0);
25
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
302 puts("--Number of Data--");
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
303 printf("%d\n", context->dataNum);
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
304 stack_free(pstack);
47
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
305
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
306 context->data[Allocate]->allocate.next = Code6;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
307 context->data[Node]->node.key = 2;
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
308
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
309 goto meta(context, Get);
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
310 }
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
311
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
312 __code code6(struct Context* context) {
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
313 puts("---get---");
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
314 print_tree(context->data[Tree]->tree.current, 0);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
315 goto meta(context, Exit);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
316 }
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
317
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
318 int main(int argc, char** argv) {
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
319 num = (int)atoi(argv[1]);
26
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
320 pstack = stack_init(sizeof(union Data*), num);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
321 struct Context* context = (struct Context*)malloc(sizeof(struct Context));
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
322 initLLRBContext(context);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
323 goto start_code(context, Code1);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
324 }