Mercurial > hg > Gears > GearsAgda

annotate src/llrb/llrbContext.h @ 83:c13575c3dbe9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
use stack
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Thu, 07 Jan 2016 08:20:03 +0900
parents dc6f665bb753
children
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 /* Context definition for llrb example */
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
2 #include "stack.h"
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
3
81
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
4 #define ALLOCATE_SIZE 1000
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
5
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 enum Code {
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 Code1,
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 Code2,
21
737a900518be implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
9 Code3,
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
10 Code4,
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
11 Code5,
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
12 Find,
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
13 Not_find,
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
14 Code6,
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
15 Allocator,
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 Put,
44
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
17 Replace,
a0a58875c93f refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
18 Insert,
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
19 Compare,
24
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
20 RotateL,
7494c0b87ec4 implement insert of Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
21 RotateR,
81
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
22 SetTree,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
23 InsertCase1,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
24 InsertCase2,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
25 InsertCase3,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
26 InsertCase4,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
27 InsertCase4_1,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
28 InsertCase4_2,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
29 InsertCase5,
83
c13575c3dbe9 use stack
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 81
diff changeset
30 StackClear,
46
348148d8fdb1 implement get
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
31 Get,
81
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
32 Search,
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
33 Delete,
81
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
34 Delete1,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
35 Delete2,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
36 Delete3,
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
37 Replace_d1,
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
38 Replace_d2,
81
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
39 FindMax1,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
40 FindMax2,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
41 DeleteCase1,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
42 DeleteCase2,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
43 DeleteCase3,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
44 DeleteCase4,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
45 DeleteCase5,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
46 DeleteCase6,
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 Exit,
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 };
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
81
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
50 enum Relational {
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
51 EQ,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
52 GT,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
53 LT,
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
54 };
dc6f665bb753 implement delete(tail call). do not work
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
55
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
56 enum UniqueData {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
57 Allocate,
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
58 Tree,
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
59 Node,
19
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 struct Context {
65
025fd6e90597 to the function call(allocate and compare)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
63 enum Code next;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
64 int codeNum;
53
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
65 __code (**code) (struct Context*);
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
66 void* heapStart;
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 void* heap;
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
68 long heapLimit;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
69 int dataNum;
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
70 stack_ptr code_stack;
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
71 stack_ptr node_stack;
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 union Data **data;
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 };
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 union Data {
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
76 struct Comparable { // inteface
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
77 enum Code compare;
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
78 union Data* data;
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
79 } compare;
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
80 struct Count {
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
81 enum Code next;
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 54
diff changeset
82 long i;
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
83 } count;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
84 struct Tree {
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
85 enum Code next;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
86 struct Node* root;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
87 struct Node* current;
83
c13575c3dbe9 use stack
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 81
diff changeset
88 struct Node* deleted;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
89 int result;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
90 } tree;
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 struct Node {
77
618c03f25108 implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
92 // need to tree
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
93 enum Code next;
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
94 int key; // comparable data segment
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 int value;
77
618c03f25108 implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
96 struct Node* left;
618c03f25108 implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
97 struct Node* right;
618c03f25108 implement insert(tail recursion)
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 75
diff changeset
98 // need to balancing
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
99 enum Color {
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
100 Red,
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
101 Black,
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
102 } color;
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 } node;
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 struct Allocate {
54
0299b90256e5 syntax suggest
kkb
parents: 53
diff changeset
105 enum Code next;
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 long size;
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 } allocate;
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 };