Mercurial > hg > CbC > old > akasha

annotate src/insert_verification/include/akashaLLRBContext.h @ 9:e864ede359cc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add iterator
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Tue, 15 Mar 2016 16:47:41 +0900
parents 24ae2641fec5
children b13d2c8d4b47
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Context definition for llrb example */
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 #include "stack.h"
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 #define ALLOCATE_SIZE 1000
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
5 #define LIMIT_OF_VERIFICATION_SIZE 4
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 enum Code {
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
8 InsertOnce,
7
24ae2641fec5 Show tree in llrb
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
9 ShowTree,
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
10
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
11 /* definitions from llrb */
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 Allocator,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 Put,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 Replace,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 Insert,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 Compare,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 RotateL,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 RotateR,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 SetTree,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 InsertCase1,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 InsertCase2,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 InsertCase3,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 InsertCase4,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 InsertCase4_1,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 InsertCase4_2,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 InsertCase5,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 StackClear,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 Get,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 Search,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 Delete,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 Delete1,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 Delete2,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 Delete3,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 Replace_d1,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 Replace_d2,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 FindMax1,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 FindMax2,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 DeleteCase1,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 DeleteCase2,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 DeleteCase3,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 DeleteCase4,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 DeleteCase5,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 DeleteCase6,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 Exit,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 };
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 enum Relational {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 EQ,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 GT,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 LT,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 };
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 enum UniqueData {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 Allocate,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 Tree,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 Node,
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
57 Iter,
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 };
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 struct Context {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 enum Code next;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 int codeNum;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 __code (**code) (struct Context*);
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 void* heapStart;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 void* heap;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 long heapLimit;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 int dataNum;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 stack_ptr code_stack;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 stack_ptr node_stack;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 union Data **data;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 };
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 union Data {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 struct Comparable { // inteface
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 enum Code compare;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 union Data* data;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 } compare;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 struct Count {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 enum Code next;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 long i;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 } count;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 struct Tree {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 enum Code next;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 struct Node* root;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 struct Node* current;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 struct Node* deleted;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 int result;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 } tree;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 struct Node {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 // need to tree
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 enum Code next;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 int key; // comparable data segment
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 int value;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 struct Node* left;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 struct Node* right;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 // need to balancing
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 enum Color {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 Red,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 Black,
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 } color;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 } node;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 struct Allocate {
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 enum Code next;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 long size;
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 } allocate;
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
106
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
107 /* for verification */
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
108 struct IterElem {
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
109 unsigned int val;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
110 struct IterElem* next;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
111 } iterElem;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
112 struct Iterator {
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
113 struct Tree* tree;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
114 struct Iterator* previousDepth;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
115 struct IterElem* head;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
116 struct IterElem* last;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
117 } iterator;
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 };