Mercurial > hg > CbC > old > akasha

annotate src/insert_verification/akashaLLRBContext.c @ 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
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdlib.h>
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 #include "akashaLLRBContext.h"
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
5 extern __code insertOnce_stub(struct Context*);
7
24ae2641fec5 Show tree in llrb
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
6 extern __code showTree_stub(struct Context*);
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
7
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
8 /* definitions from llrb */
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
9 extern __code meta(struct Context*, enum Code next);
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 extern __code put_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 extern __code replaceNode_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 extern __code insertNode_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 extern __code rotateLeft_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 extern __code rotateRight_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 extern __code colorFlip_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 extern __code fixUp_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 extern __code changeReference_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 extern __code insert1_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 extern __code insert2_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 extern __code insert3_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 extern __code insert4_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 extern __code insert4_1_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 extern __code insert4_2_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 extern __code insert5_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 extern __code stackClear_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 extern __code get_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 extern __code search_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 extern __code delete_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 extern __code delete1_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 extern __code delete2_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 extern __code delete3_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 extern __code replaceNodeForDelete1_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 extern __code replaceNodeForDelete2_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 extern __code findMax1_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 extern __code findMax2_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 extern __code deleteCase1_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 extern __code deleteCase2_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 extern __code deleteCase3_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 extern __code deleteCase4_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 extern __code deleteCase5_stub(struct Context*);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 extern __code deleteCase6_stub(struct Context*);
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
42 extern __code exitCode(struct Context*);
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
44 __code initIterator(struct Context*);
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
45 __code initFinishIterator(struct Context*, struct IterElem*);
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
46
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
47 __code initLLRBContext(struct Context* context, enum Code next) {
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE;
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
49 context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE);
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
50 context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 context->heapStart = malloc(context->heapLimit);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 context->codeNum = Exit;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
55 context->code[InsertOnce] = insertOnce_stub;
7
24ae2641fec5 Show tree in llrb
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
56 context->code[ShowTree] = showTree_stub;
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
57
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
58 /* definitions from llrb */
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 context->code[Put] = put_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 context->code[Replace] = replaceNode_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 context->code[Insert] = insertNode_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 context->code[RotateL] = rotateLeft_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 context->code[RotateR] = rotateRight_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 context->code[InsertCase1] = insert1_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 context->code[InsertCase2] = insert2_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 context->code[InsertCase3] = insert3_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 context->code[InsertCase4] = insert4_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 context->code[InsertCase4_1] = insert4_1_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 context->code[InsertCase4_2] = insert4_2_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 context->code[InsertCase5] = insert5_stub;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 context->code[StackClear] = stackClear_stub;
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
72 context->code[Exit] = exitCode;
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 context->heap = context->heapStart;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 context->data[Allocate] = context->heap;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 context->heap += sizeof(struct Allocate);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 context->data[Tree] = context->heap;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 context->heap += sizeof(struct Tree);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 context->data[Node] = context->heap;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 context->heap += sizeof(struct Node);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
85 context->data[Iter] = context->heap;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
86 context->heap += sizeof(struct Iterator);
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
87
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 context->dataNum = Node;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 struct Tree* tree = &context->data[Tree]->tree;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 tree->root = 0;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 tree->current = 0;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 tree->deleted = 0;
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 context->node_stack = stack_init(sizeof(struct Node*), 100);
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 context->code_stack = stack_init(sizeof(enum Code), 100);
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
97
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
98 context->next = next;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
99 goto initIterator(context);
4
d41e349d6e22 Fix filename
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 }
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
101
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
102 __code initIterator(struct Context* context) {
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
103 struct IterElem* ie = (struct IterElem*)malloc(sizeof(struct IterElem));
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
104 struct Iterator* iter = &context->data[Iter];
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
105
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
106 ie->val = 0;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
107 ie->next = NULL;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
108 iter->head = ie;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
109
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
110 goto initIteratorElem(context, ie);
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
111 }
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
112
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
113 __code initIteratorElem(struct Context* context, struct IterElem* prev) {
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
114 if (prev->val >= LIMIT_OF_VERIFICATION_SIZE) { goto initFinishIterator(context, prev); }
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
115
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
116 struct IterElem* ie = (struct IterElem *)malloc(sizeof(struct IterElem));
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
117 ie->val = prev->val + 1;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
118 prev->next = ie;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
119 goto initIteratorElem(context, ie);
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
120 }
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
121
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
122 __code initFinishIterator(struct Context* context, struct IterElem* elem) {
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
123 struct Iterator* iter = &context->data[Iter];
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
124 elem->next = iter->head;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
125 iter->last = iter->head;
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
126 goto meta(context, context->next);
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
127 }