Mercurial > hg > CbC > old > akasha

annotate src/insert_verification/akashaCS.c @ 46:44cc739b8b56 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix assert condition
author atton
date Tue, 21 Jun 2016 07:41:55 +0000
parents 04283ef8f3ca
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
25
38ba1606e62d Refresh memory only between put and put
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
1 #include <stdio.h>
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 #include <stdlib.h>
25
38ba1606e62d Refresh memory only between put and put
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
3 #include <string.h>
26
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
4 #include <stdbool.h>
25
38ba1606e62d Refresh memory only between put and put
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
5
8
46bc6ea5fa81 Reduce Warnings
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
6 #include "akashaLLRBContext.h"
46bc6ea5fa81 Reduce Warnings
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
7
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
8 extern __code initLLRBContext(struct Context*, enum Code);
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
26
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
10 /* utils */
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
11
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
12 bool eqNode(struct Node* n1, struct Node* n2) {
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
13 if ((n1 == NULL) && (n2 == NULL)) return true;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
14 if (n1->key != n2->key) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
15 if (n1->value != n2->value) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
16 if (n1->color != n2->color) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
17 if (!eqNode(n1->left, n2->left)) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
18 if (!eqNode(n1->right, n2->right)) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
19 return true;
25
38ba1606e62d Refresh memory only between put and put
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
20 }
38ba1606e62d Refresh memory only between put and put
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
21
26
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
22 bool eqTree(struct Tree* t1, struct Tree* t2) {
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
23 if ((t1 == NULL) && (t2 == NULL)) return true;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
24 if (t1->next != t2->next) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
25 if (t2->result != t2->result) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
26 if (!eqNode(t1->root, t2->root)) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
27 if (!eqNode(t1->current, t2->current)) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
28 if (!eqNode(t1->deleted, t2->deleted)) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
29 return true;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
30 }
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
31
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
32
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
33 bool eqIter(struct Iterator* iter1, struct Iterator* iter2) {
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
34 if (iter1->head->val != iter2->head->val) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
35 if (iter1->last->val != iter2->last->val) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
36 if (iter1->iteratedValue != iter2->iteratedValue) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
37 if (!eqTree(iter1->tree, iter2->tree)) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
38
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
39 struct IterElem *ie1 = iter1->head->next;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
40 struct IterElem *ie2 = iter2->head->next;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
41
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
42 while (ie1->val != iter1->head->val) {
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
43 if (ie1->val != ie2->val) return false;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
44 ie1 = ie1->next;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
45 ie2 = ie2->next;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
46 }
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
47
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
48 if ((iter1->previousDepth == NULL) && (iter2->previousDepth == NULL)) return true;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
49 return eqIter(iter1->previousDepth, iter2->previousDepth);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
50 }
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
51
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
52
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
53 /* C function */
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
54
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
55 void validateNodePointer(struct Node* node) {
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
56 if (node == NULL) return;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
57 validateNodePointer(node->left);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
58 validateNodePointer(node->right);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
59 }
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
60
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
61 void validateTreePointer(struct Tree* tree) {
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
62 if (tree == NULL) return;
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
63 validateNodePointer(tree->root);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
64 validateNodePointer(tree->current);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
65 validateNodePointer(tree->deleted);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
66 }
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
67
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
68
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
69 void findInvalidPointer(struct Context* context) {
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
70 validateNodePointer(&context->data[Node]->node);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
71 validateTreePointer(&context->data[Tree]->tree);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
72 }
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
73
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
74 /* Code Segments */
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
75
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 __code meta(struct Context* context, enum Code next) {
28
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
77 struct Iterator* iter = &context->data[Iter]->iterator;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
78
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
79 switch (context->prev) {
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
80 case GoToPreviousDepth:
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
81 if (iter->iteratedPointDataNum == 0) break;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
82 if (iter->iteratedPointHeap == NULL) break;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
83
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
84 unsigned int diff =(unsigned long)context->heap - (unsigned long)iter->iteratedPointHeap;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
85 memset(iter->iteratedPointHeap, 0, diff);
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
86 context->dataNum = iter->iteratedPointDataNum;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
87 context->heap = iter->iteratedPointHeap;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
88 break;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
89 default:
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
90 break;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
91 }
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
92 switch (next) {
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
93 case PutAndGoToNextDepth:
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
94 if (context->prev == GoToPreviousDepth) break;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
95 if (iter->previousDepth == NULL) break;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
96 iter->previousDepth->iteratedPointDataNum = context->dataNum;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
97 iter->previousDepth->iteratedPointHeap = context->heap;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
98 break;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
99 default:
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
100 break;
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
101 }
04283ef8f3ca Free memory when backed previous depth
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
102
26
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
103 findInvalidPointer(context);
cf7cbe70404f WIP: Trying implement copying GC...
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
104 context->prev = next;
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 goto (context->code[next])(context);
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 }
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
108 __code startCode(enum Code next) {
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
109 struct Context* context = (struct Context*)malloc(sizeof(struct Context));
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
110
9
e864ede359cc Add iterator
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
111 goto initLLRBContext(context, next);
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 }
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113
6
3f00d95339a7 Use llrb in akasha
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
114 __code exitCode(struct Context* context) {
3
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 free(context->code);
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 free(context->data);
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 free(context->heapStart);
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 goto exit(0);
c80e44ac8f5e Import origin_cs and llrbContext
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 }