| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| #include "adc.h" |
| #include "macrodef.h" |
| |
| int32 KeyComp( const uint32 *a, const uint32 *b, uint32 n ) { |
| uint32 i; |
| for ( i = 0; i < n; i++ ) { |
| if (a[i] < b[i]) return(-1); |
| else if (a[i] > b[i]) return(1); |
| } |
| return(0); |
| } |
| int32 TreeInsert(RBTree *tree, uint32 *attrs){ |
| uint32 sl = 1; |
| uint32 *attrsP; |
| int32 cmpres; |
| treeNode *xNd, *yNd, *tmp; |
| |
| tmp = &tree->root; |
| xNd = tmp->left; |
| |
| if (xNd == NULL){ |
| tree->count++; |
| NEW_TREE_NODE(tree->mp,tree->memPool, |
| tree->memaddr,tree->treeNodeSize, |
| tree->freeNodeCounter,tree->memoryIsFull) |
| xNd = tmp->left = tree->mp; |
| memcpy(&(xNd->nodeMemPool[0]), &attrs[0], tree->nodeDataSize); |
| xNd->left = xNd->right = NULL; |
| xNd->clr = BLACK; |
| return 0; |
| } |
| |
| tree->drcts[0] = 0; |
| tree->nodes[0] = &tree->root; |
| |
| while(1){ |
| attrsP = (uint32*) &(xNd->nodeMemPool[tree->nm]); |
| cmpres = KeyComp( &attrs[tree->nm<<1], attrsP, tree->nd ); |
| |
| if (cmpres < 0){ |
| tree->nodes[sl] = xNd; |
| tree->drcts[sl++] = 0; |
| yNd = xNd->left; |
| |
| if(yNd == NULL){ |
| NEW_TREE_NODE(tree->mp,tree->memPool, |
| tree->memaddr,tree->treeNodeSize, |
| tree->freeNodeCounter,tree->memoryIsFull) |
| xNd = xNd->left = tree->mp; |
| break; |
| } |
| }else if (cmpres > 0){ |
| tree->nodes[sl] = xNd; |
| tree->drcts[sl++] = 1; |
| yNd = xNd->right; |
| if(yNd == NULL){ |
| NEW_TREE_NODE(tree->mp,tree->memPool, |
| tree->memaddr,tree->treeNodeSize, |
| tree->freeNodeCounter,tree->memoryIsFull) |
| xNd = xNd->right = tree->mp; |
| break; |
| } |
| }else{ |
| uint64 ii; |
| int64 *mx; |
| mx = (int64*) &attrs[0]; |
| for ( ii = 0; ii < tree->nm; ii++ ) xNd->nodeMemPool[ii] += mx[ii]; |
| return 0; |
| } |
| xNd = yNd; |
| } |
| tree->count++; |
| memcpy(&(xNd->nodeMemPool[0]), &attrs[0], tree->nodeDataSize); |
| xNd->left = xNd->right = NULL; |
| xNd->clr = RED; |
| |
| while(1){ |
| if ( tree->nodes[sl-1]->clr != RED || sl<3 ) break; |
| |
| if (tree->drcts[sl-2] == 0){ |
| yNd = tree->nodes[sl-2]->right; |
| if (yNd != NULL && yNd->clr == RED){ |
| tree->nodes[sl-1]->clr = BLACK; |
| yNd->clr = BLACK; |
| tree->nodes[sl-2]->clr = RED; |
| sl -= 2; |
| }else{ |
| if (tree->drcts[sl-1] == 1){ |
| xNd = tree->nodes[sl-1]; |
| yNd = xNd->right; |
| xNd->right = yNd->left; |
| yNd->left = xNd; |
| tree->nodes[sl-2]->left = yNd; |
| }else |
| yNd = tree->nodes[sl-1]; |
| |
| xNd = tree->nodes[sl-2]; |
| xNd->clr = RED; |
| yNd->clr = BLACK; |
| |
| xNd->left = yNd->right; |
| yNd->right = xNd; |
| |
| if(tree->drcts[sl-3]) |
| tree->nodes[sl-3]->right = yNd; |
| else |
| tree->nodes[sl-3]->left = yNd; |
| break; |
| } |
| }else{ |
| yNd = tree->nodes[sl-2]->left; |
| if (yNd != NULL && yNd->clr == RED){ |
| tree->nodes[sl-1]->clr = BLACK; |
| yNd->clr = BLACK; |
| tree->nodes[sl-2]->clr = RED; |
| sl -= 2; |
| }else{ |
| if(tree->drcts[sl-1] == 0){ |
| xNd = tree->nodes[sl-1]; |
| yNd = xNd->left; |
| xNd->left = yNd->right; |
| yNd->right = xNd; |
| tree->nodes[sl-2]->right = yNd; |
| }else |
| yNd = tree->nodes[sl-1]; |
| |
| xNd = tree->nodes[sl-2]; |
| xNd->clr = RED; |
| yNd->clr = BLACK; |
| |
| xNd->right = yNd->left; |
| yNd->left = xNd; |
| |
| if (tree->drcts[sl-3]) |
| tree->nodes[sl-3]->right = yNd; |
| else |
| tree->nodes[sl-3]->left = yNd; |
| break; |
| } |
| } |
| } |
| tree->root.left->clr = BLACK; |
| return 0; |
| } |
| int32 WriteViewToDisk(ADC_VIEW_CNTL *avp, treeNode *t){ |
| uint32 i; |
| if(!t) return ADC_OK; |
| if(WriteViewToDisk( avp, t->left)) return ADC_WRITE_FAILED; |
| for(i=0;i<avp->nm;i++){ |
| avp->mSums[i] += t->nodeMemPool[i]; |
| } |
| WriteToFile(t->nodeMemPool,avp->outRecSize,1,avp->viewFile,avp->logf); |
| if(WriteViewToDisk( avp, t->right)) return ADC_WRITE_FAILED; |
| return ADC_OK; |
| } |
| int32 WriteViewToDiskCS(ADC_VIEW_CNTL *avp, treeNode *t,uint64 *ordern){ |
| uint32 i; |
| if(!t) return ADC_OK; |
| if(WriteViewToDiskCS( avp, t->left,ordern)) return ADC_WRITE_FAILED; |
| for(i=0;i<avp->nm;i++){ |
| avp->mSums[i] += t->nodeMemPool[i]; |
| avp->checksums[i] += (++(*ordern))*t->nodeMemPool[i]%measbound; |
| } |
| WriteToFile(t->nodeMemPool,avp->outRecSize,1,avp->viewFile,avp->logf); |
| if(WriteViewToDiskCS( avp, t->right,ordern)) return ADC_WRITE_FAILED; |
| return ADC_OK; |
| } |
| int32 computeChecksum(ADC_VIEW_CNTL *avp, treeNode *t,uint64 *ordern){ |
| uint32 i; |
| if(!t) return ADC_OK; |
| if(computeChecksum(avp,t->left,ordern)) return ADC_WRITE_FAILED; |
| for(i=0;i<avp->nm;i++){ |
| avp->checksums[i] += (++(*ordern))*t->nodeMemPool[i]%measbound; |
| } |
| if(computeChecksum(avp,t->right,ordern)) return ADC_WRITE_FAILED; |
| return ADC_OK; |
| } |
| int32 WriteChunkToDisk(uint32 recordSize,FILE *fileOfChunks, |
| treeNode *t, FILE *logFile){ |
| if(!t) return ADC_OK; |
| if(WriteChunkToDisk( recordSize, fileOfChunks, t->left, logFile)) |
| return ADC_WRITE_FAILED; |
| WriteToFile( t->nodeMemPool, recordSize, 1, fileOfChunks, logFile); |
| if(WriteChunkToDisk( recordSize, fileOfChunks, t->right, logFile)) |
| return ADC_WRITE_FAILED; |
| return ADC_OK; |
| } |
| RBTree * CreateEmptyTree(uint32 nd, uint32 nm, |
| uint32 memoryLimit, unsigned char * memPool){ |
| RBTree *tree = (RBTree*) malloc(sizeof(RBTree)); |
| if (!tree) return NULL; |
| |
| tree->root.left = NULL; |
| tree->root.right = NULL; |
| tree->count = 0; |
| tree->memaddr = 0; |
| tree->treeNodeSize = sizeof(struct treeNode) + DIM_FSZ*(nd-1)+MSR_FSZ*nm; |
| if (tree->treeNodeSize%8 != 0) tree->treeNodeSize += 4; |
| tree->memoryLimit = memoryLimit; |
| tree->memoryIsFull = 0; |
| tree->nodeDataSize = DIM_FSZ*nd + MSR_FSZ*nm; |
| tree->mp = NULL; |
| tree->nNodesLimit = tree->memoryLimit/tree->treeNodeSize; |
| tree->freeNodeCounter = tree->nNodesLimit; |
| tree->nd = nd; |
| tree->nm = nm; |
| tree->memPool = memPool; |
| tree->nodes = (treeNode**) malloc(sizeof(treeNode*)*MAX_TREE_HEIGHT); |
| if (!(tree->nodes)) return NULL; |
| tree->drcts = (uint32*) malloc( sizeof(uint32)*MAX_TREE_HEIGHT); |
| if (!(tree->drcts)) return NULL; |
| return tree; |
| } |
| void InitializeTree(RBTree *tree, uint32 nd, uint32 nm){ |
| tree->root.left = NULL; |
| tree->root.right = NULL; |
| tree->count = 0; |
| tree->memaddr = 0; |
| tree->treeNodeSize = sizeof(struct treeNode) + DIM_FSZ*(nd-1)+MSR_FSZ*nm; |
| if (tree->treeNodeSize%8 != 0) tree->treeNodeSize += 4; |
| tree->memoryIsFull = 0; |
| tree->nodeDataSize = DIM_FSZ*nd + MSR_FSZ*nm; |
| tree->mp = NULL; |
| tree->nNodesLimit = tree->memoryLimit/tree->treeNodeSize; |
| tree->freeNodeCounter = tree->nNodesLimit; |
| tree->nd = nd; |
| tree->nm = nm; |
| } |
| int32 DestroyTree(RBTree *tree) { |
| if (tree==NULL) return ADC_TREE_DESTROY_FAILURE; |
| if (tree->memPool!=NULL) free(tree->memPool); |
| if (tree->nodes) free(tree->nodes); |
| if (tree->drcts) free(tree->drcts); |
| free(tree); |
| return ADC_OK; |
| } |
| |
