source: CIVL/examples/omp/nas-dc/DC/rbt.c@ 1aaefd4

main test-branch
Last change on this file since 1aaefd4 was ea777aa, checked in by Alex Wilton <awilton@…>, 3 years ago

Moved examples, include, build_default.properties, common.xml, and README out from dev.civl.com into the root of the repo.

git-svn-id: ​svn://vsl.cis.udel.edu/civl/trunk@5704 fb995dde-84ed-4084-dfe6-e5aef3e2452c
  • Property mode set to 100644
File size: 6.9 KB
Line 
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include "adc.h"
5#include "macrodef.h"
6
7int32 KeyComp( const uint32 *a, const uint32 *b, uint32 n ) {
8 uint32 i;
9 for ( i = 0; i < n; i++ ) {
10 if (a[i] < b[i]) return(-1);
11 else if (a[i] > b[i]) return(1);
12 }
13 return(0);
14}
15int32 TreeInsert(RBTree *tree, uint32 *attrs){
16 uint32 sl = 1;
17 uint32 *attrsP;
18 int32 cmpres;
19 treeNode *xNd, *yNd, *tmp;
20
21 tmp = &tree->root;
22 xNd = tmp->left;
23
24 if (xNd == NULL){
25 tree->count++;
26 NEW_TREE_NODE(tree->mp,tree->memPool,
27 tree->memaddr,tree->treeNodeSize,
28 tree->freeNodeCounter,tree->memoryIsFull)
29 xNd = tmp->left = tree->mp;
30 memcpy(&(xNd->nodeMemPool[0]), &attrs[0], tree->nodeDataSize);
31 xNd->left = xNd->right = NULL;
32 xNd->clr = BLACK;
33 return 0;
34 }
35
36 tree->drcts[0] = 0;
37 tree->nodes[0] = &tree->root;
38
39 while(1){
40 attrsP = (uint32*) &(xNd->nodeMemPool[tree->nm]);
41 cmpres = KeyComp( &attrs[tree->nm<<1], attrsP, tree->nd );
42
43 if (cmpres < 0){
44 tree->nodes[sl] = xNd;
45 tree->drcts[sl++] = 0;
46 yNd = xNd->left;
47
48 if(yNd == NULL){
49 NEW_TREE_NODE(tree->mp,tree->memPool,
50 tree->memaddr,tree->treeNodeSize,
51 tree->freeNodeCounter,tree->memoryIsFull)
52 xNd = xNd->left = tree->mp;
53 break;
54 }
55 }else if (cmpres > 0){
56 tree->nodes[sl] = xNd;
57 tree->drcts[sl++] = 1;
58 yNd = xNd->right;
59 if(yNd == NULL){
60 NEW_TREE_NODE(tree->mp,tree->memPool,
61 tree->memaddr,tree->treeNodeSize,
62 tree->freeNodeCounter,tree->memoryIsFull)
63 xNd = xNd->right = tree->mp;
64 break;
65 }
66 }else{
67 uint64 ii;
68 int64 *mx;
69 mx = (int64*) &attrs[0];
70 for ( ii = 0; ii < tree->nm; ii++ ) xNd->nodeMemPool[ii] += mx[ii];
71 return 0;
72 }
73 xNd = yNd;
74 }
75 tree->count++;
76 memcpy(&(xNd->nodeMemPool[0]), &attrs[0], tree->nodeDataSize);
77 xNd->left = xNd->right = NULL;
78 xNd->clr = RED;
79
80 while(1){
81 if ( tree->nodes[sl-1]->clr != RED || sl<3 ) break;
82
83 if (tree->drcts[sl-2] == 0){
84 yNd = tree->nodes[sl-2]->right;
85 if (yNd != NULL && yNd->clr == RED){
86 tree->nodes[sl-1]->clr = BLACK;
87 yNd->clr = BLACK;
88 tree->nodes[sl-2]->clr = RED;
89 sl -= 2;
90 }else{
91 if (tree->drcts[sl-1] == 1){
92 xNd = tree->nodes[sl-1];
93 yNd = xNd->right;
94 xNd->right = yNd->left;
95 yNd->left = xNd;
96 tree->nodes[sl-2]->left = yNd;
97 }else
98 yNd = tree->nodes[sl-1];
99
100 xNd = tree->nodes[sl-2];
101 xNd->clr = RED;
102 yNd->clr = BLACK;
103
104 xNd->left = yNd->right;
105 yNd->right = xNd;
106
107 if(tree->drcts[sl-3])
108 tree->nodes[sl-3]->right = yNd;
109 else
110 tree->nodes[sl-3]->left = yNd;
111 break;
112 }
113 }else{
114 yNd = tree->nodes[sl-2]->left;
115 if (yNd != NULL && yNd->clr == RED){
116 tree->nodes[sl-1]->clr = BLACK;
117 yNd->clr = BLACK;
118 tree->nodes[sl-2]->clr = RED;
119 sl -= 2;
120 }else{
121 if(tree->drcts[sl-1] == 0){
122 xNd = tree->nodes[sl-1];
123 yNd = xNd->left;
124 xNd->left = yNd->right;
125 yNd->right = xNd;
126 tree->nodes[sl-2]->right = yNd;
127 }else
128 yNd = tree->nodes[sl-1];
129
130 xNd = tree->nodes[sl-2];
131 xNd->clr = RED;
132 yNd->clr = BLACK;
133
134 xNd->right = yNd->left;
135 yNd->left = xNd;
136
137 if (tree->drcts[sl-3])
138 tree->nodes[sl-3]->right = yNd;
139 else
140 tree->nodes[sl-3]->left = yNd;
141 break;
142 }
143 }
144 }
145 tree->root.left->clr = BLACK;
146 return 0;
147}
148int32 WriteViewToDisk(ADC_VIEW_CNTL *avp, treeNode *t){
149 uint32 i;
150 if(!t) return ADC_OK;
151 if(WriteViewToDisk( avp, t->left)) return ADC_WRITE_FAILED;
152 for(i=0;i<avp->nm;i++){
153 avp->mSums[i] += t->nodeMemPool[i];
154 }
155 WriteToFile(t->nodeMemPool,avp->outRecSize,1,avp->viewFile,avp->logf);
156 if(WriteViewToDisk( avp, t->right)) return ADC_WRITE_FAILED;
157 return ADC_OK;
158}
159int32 WriteViewToDiskCS(ADC_VIEW_CNTL *avp, treeNode *t,uint64 *ordern){
160 uint32 i;
161 if(!t) return ADC_OK;
162 if(WriteViewToDiskCS( avp, t->left,ordern)) return ADC_WRITE_FAILED;
163 for(i=0;i<avp->nm;i++){
164 avp->mSums[i] += t->nodeMemPool[i];
165 avp->checksums[i] += (++(*ordern))*t->nodeMemPool[i]%measbound;
166 }
167 WriteToFile(t->nodeMemPool,avp->outRecSize,1,avp->viewFile,avp->logf);
168 if(WriteViewToDiskCS( avp, t->right,ordern)) return ADC_WRITE_FAILED;
169 return ADC_OK;
170}
171int32 computeChecksum(ADC_VIEW_CNTL *avp, treeNode *t,uint64 *ordern){
172 uint32 i;
173 if(!t) return ADC_OK;
174 if(computeChecksum(avp,t->left,ordern)) return ADC_WRITE_FAILED;
175 for(i=0;i<avp->nm;i++){
176 avp->checksums[i] += (++(*ordern))*t->nodeMemPool[i]%measbound;
177 }
178 if(computeChecksum(avp,t->right,ordern)) return ADC_WRITE_FAILED;
179 return ADC_OK;
180}
181int32 WriteChunkToDisk(uint32 recordSize,FILE *fileOfChunks,
182 treeNode *t, FILE *logFile){
183 if(!t) return ADC_OK;
184 if(WriteChunkToDisk( recordSize, fileOfChunks, t->left, logFile))
185 return ADC_WRITE_FAILED;
186 WriteToFile( t->nodeMemPool, recordSize, 1, fileOfChunks, logFile);
187 if(WriteChunkToDisk( recordSize, fileOfChunks, t->right, logFile))
188 return ADC_WRITE_FAILED;
189 return ADC_OK;
190}
191RBTree * CreateEmptyTree(uint32 nd, uint32 nm,
192 uint32 memoryLimit, unsigned char * memPool){
193 RBTree *tree = (RBTree*) malloc(sizeof(RBTree));
194 if (!tree) return NULL;
195
196 tree->root.left = NULL;
197 tree->root.right = NULL;
198 tree->count = 0;
199 tree->memaddr = 0;
200 tree->treeNodeSize = sizeof(struct treeNode) + DIM_FSZ*(nd-1)+MSR_FSZ*nm;
201 if (tree->treeNodeSize%8 != 0) tree->treeNodeSize += 4;
202 tree->memoryLimit = memoryLimit;
203 tree->memoryIsFull = 0;
204 tree->nodeDataSize = DIM_FSZ*nd + MSR_FSZ*nm;
205 tree->mp = NULL;
206 tree->nNodesLimit = tree->memoryLimit/tree->treeNodeSize;
207 tree->freeNodeCounter = tree->nNodesLimit;
208 tree->nd = nd;
209 tree->nm = nm;
210 tree->memPool = memPool;
211 tree->nodes = (treeNode**) malloc(sizeof(treeNode*)*MAX_TREE_HEIGHT);
212 if (!(tree->nodes)) return NULL;
213 tree->drcts = (uint32*) malloc( sizeof(uint32)*MAX_TREE_HEIGHT);
214 if (!(tree->drcts)) return NULL;
215 return tree;
216}
217void InitializeTree(RBTree *tree, uint32 nd, uint32 nm){
218 tree->root.left = NULL;
219 tree->root.right = NULL;
220 tree->count = 0;
221 tree->memaddr = 0;
222 tree->treeNodeSize = sizeof(struct treeNode) + DIM_FSZ*(nd-1)+MSR_FSZ*nm;
223 if (tree->treeNodeSize%8 != 0) tree->treeNodeSize += 4;
224 tree->memoryIsFull = 0;
225 tree->nodeDataSize = DIM_FSZ*nd + MSR_FSZ*nm;
226 tree->mp = NULL;
227 tree->nNodesLimit = tree->memoryLimit/tree->treeNodeSize;
228 tree->freeNodeCounter = tree->nNodesLimit;
229 tree->nd = nd;
230 tree->nm = nm;
231}
232int32 DestroyTree(RBTree *tree) {
233 if (tree==NULL) return ADC_TREE_DESTROY_FAILURE;
234 if (tree->memPool!=NULL) free(tree->memPool);
235 if (tree->nodes) free(tree->nodes);
236 if (tree->drcts) free(tree->drcts);
237 free(tree);
238 return ADC_OK;
239}
240
Note: See TracBrowser for help on using the repository browser.