#include #include #include #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;inm;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;inm;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;inm;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; }