btree.cpp
stdlib.h
string.h
stdio.h
unistd.h
iostream
assert.h
btree.h
ubixfs.h
btree.h
stdlib.h
ubixfs.h
ubixos/types.h
sys/_types.h
string.h
btreeheader.h
file.h
sys/types.h
fsAbstract.h
types.h
unistd.h
device.h
assert.h
iostream
src/sys/ubixfsv2/btree.cpp
stdio.h
dirent.h
std
VERIFY
x
y
z
n
if ((x) != (y)) { cout << "verify " << z << " failed" << endl; PrintWholeTree(); }

    //http://www.cs.msstate.edu/~cs2314/global/BTreeAnimation/algorithm.html
    #include<stdlib.h>
    #include<string.h>
    #include<stdio.h>
    #include<unistd.h>
    #include<iostream>
    #include<assert.h>
    #include"btree.h"
    #include"ubixfs.h"

    usingnamespacestd;
    #defineVERIFY(x,y,z,n)if((x)!=(y)){cout<<"verify"<<z<<"failed"<<endl;PrintWholeTree();}

    bTree::bTree(UbixFS*filesystem,fileDescriptor*myfd){
    size_tresult=0;

    root=NULL;
    tag=0;
    fs=filesystem;
    fd=myfd;
    header=newbTreeHeader;
    assert(header);
    memset(header,0,sizeof(bTreeHeader));
    assert(fs);
    result=fs->vfs_read(fd,header,0,sizeof(bTreeHeader));
    assert(result==sizeof(bTreeHeader));

    //Ifthereareanyfilesinthisdir,loadthefirstnodeoftheb+tree
    if(header->treeLeafCount!=0){
    assert(header->firstNodeOffset!=0);
    root=newbNode;
    assert(root);
    result=fs->vfs_read(fd,root,header->firstNodeOffset,sizeof(bNode));
    assert(result==sizeof(bNode));
    }//if

    }//bTree::bTree

    bTree::bTree(constchar*key,ubixfsInode*inode){
    /*oncetheFSandthebTreeareinterfaced,thisshouldgoaway*/
    root=NULL;
    tag=0;
    header=newbTreeHeader;
    assert(header);
    memset(header,0,sizeof(bTreeHeader));
    header->treeDepth=1;
    header->treeWidth=0;
    header->treeLeafCount=0;
    header->firstDeleted=-1;
    header->firstNodeOffset=sizeof(bTreeHeader);

    if(inode==NULL)return;
    root=allocEmptyNode();
    if(root==NULL)return;
    root->used=1;
    root->parent.bPtr=NULL;
    root->leaf=true;
    root->childCount[1]=1;

    //cout<<"---Creating"<<inode->name<<"@"<<inode<<endl;
    strncpy(root->keys[0],key,B_MAX_NAME_LENGTH);
    //insertpointertodatapagetotherightofthedata
    root->head[1].iPtr=inode;
    root->tail[1].iPtr=inode;

    root->present[1]=true;
    if(inode!=NULL){
    inode->next.bPtr=inode->prev.bPtr=NULL;
    }//if
    return;
    }//bTree:bTree

    bool
    bTree::Insert(constchar*key,ubixfsInode*inode){
    bNode*bnode=root;
    ubixfsInode*tmpInode=NULL;
    unsignedintcurSlot=0;

    if(inode==NULL)returnfalse;

    //note:thiscodeisrightoutoftheconstructor
    if(root==NULL){
    if(header==NULL)header=newbTreeHeader;
    assert(header);
    memset(header,0,sizeof(bTreeHeader));
    header->treeDepth=1;
    header->treeWidth=0;
    header->treeLeafCount=0;
    header->firstDeleted=-1;
    header->firstNodeOffset=sizeof(bTreeHeader);

    root=allocEmptyNode();
    assert(root);
    if(root==NULL)returnfalse;

    root->used=1;
    root->parent.bPtr=NULL;
    root->leaf=true;
    root->childCount[1]=1;

    strncpy(root->keys[0],key,B_MAX_NAME_LENGTH);
    //insertpointertodatapagetotherightofthedata
    root->head[1].iPtr=inode;
    root->tail[1].iPtr=inode;

    root->present[1]=true;
    inode->next.iPtr=inode->prev.iPtr=NULL;
    returntrue;
    }//if

    tmpInode=Find(key);
    if(tmpInode!=NULL)returnfalse;
    //PrintWholeTree();
    //cout<<"Insert("<<key<<")"<<endl;
    //Info(bnode);
    ++header->treeLeafCount;
    /*
    *Findtheleafnodetheinodegoesinto
    */
    assert(bnode->used);
    //cout<<"---Inserting"<<inode->name<<"@"<<inode<<endl;
    while(bnode!=NULL&&!bnode->leaf){
    if(strcmp(key,bnode->keys[0])<0){
    bnode=bnode->head[0].bPtr;
    }else{
    if(strcmp(key,bnode->keys[bnode->used-1])>=0){
    bnode=bnode->head[bnode->used].bPtr;
    }else{
    for(unsignedinti=1;i<bnode->used;i++){
    if(strcmp(key,bnode->keys[i])<0){
    bnode=bnode->head[i].bPtr;
    break;
    }//if
    }//fori
    }//else
    }
    }//while

    /*
    *
    */

    assert(bnode);
    if(bnode->leaf!=true)cout<<"leafnode!=true"<<endl;
    assert(inode);

    if(strcmp(key,bnode->keys[curSlot=0])<0)
    tmpInode=bnode->head[curSlot].iPtr;
    else
    if(strcmp(key,bnode->keys[(curSlot=bnode->used)-1])>=0)
    tmpInode=bnode->head[bnode->used].iPtr;
    else{
    for(curSlot=1;curSlot<bnode->used;curSlot++){
    if(strcmp(key,bnode->keys[curSlot])<0){
    tmpInode=bnode->head[curSlot].iPtr;
    break;
    }//if
    }//forcurSlot
    tmpInode=bnode->head[curSlot].iPtr;
    }//else

    if(tmpInode==NULL){
    /*
    *Thisisthefirstnodeinthisleaf
    */
    bnode->head[curSlot].iPtr=bnode->tail[curSlot].iPtr=inode;
    bnode->present[curSlot]=true;

    if(curSlot==0){

    if(bnode->head[1].iPtr!=NULL){
    ubixfsInode*iptr=bnode->head[1].iPtr;
    inode->prev.iPtr=iptr->prev.iPtr;
    inode->next.iPtr=iptr;
    iptr->prev.iPtr=inode;
    if(inode->prev.iPtr!=NULL)
    inode->prev.iPtr->next.iPtr=inode;
    }else{
    inode->next.iPtr=inode->prev.iPtr=NULL;
    }//else

    }else{
    ++bnode->used;
    }//else

    }else{
    /*
    *Addnodetoleafpage.Scanthroughtofindwhereitgoes.
    */
    if(strcmp(key,bnode->head[curSlot].iPtr->name)<0)
    {

    inode->next.iPtr=bnode->head[curSlot].iPtr;
    inode->prev.iPtr=inode->next.iPtr->prev.iPtr;
    inode->next.iPtr->prev.iPtr=inode;
    if(inode->prev.iPtr!=NULL)inode->prev.iPtr->next.iPtr=inode;
    bnode->head[curSlot].iPtr=inode;

    }else{

    if(strcmp(key,bnode->tail[curSlot].iPtr->name)>0){

    inode->prev.iPtr=bnode->tail[curSlot].iPtr;
    inode->next.iPtr=inode->prev.iPtr->next.iPtr;
    inode->prev.iPtr->next.iPtr=inode;

    if(inode->next.iPtr!=NULL)inode->next.iPtr->prev.iPtr=inode;
    bnode->tail[curSlot].iPtr=inode;

    }else{

    ubixfsInode*tmpInode=bnode->head[curSlot].iPtr;
    for(unsignedinti=0;i<bnode->childCount[curSlot];i++){
    if(strcmp(key,tmpInode->name)<0){
    inode->next.iPtr=tmpInode;
    inode->prev.iPtr=tmpInode->prev.iPtr;
    inode->next.iPtr->prev.iPtr=inode;
    inode->prev.iPtr->next.iPtr=inode;
    break;
    }//if
    tmpInode=tmpInode->next.iPtr;
    }//fori

    }//else

    }//else

    }//else

    if(++bnode->childCount[curSlot]==B_MAX_CHILD_COUNT){

    //cout<<"----beforesplit----"<<endl;
    //Info(bnode);

    if(curSlot!=bnode->used){
    intshift=bnode->used-curSlot+1;

    memmove(&bnode->head[curSlot+1],
    &bnode->head[curSlot],
    sizeof(bnode->head[0])*shift);
    memmove(&bnode->tail[curSlot+1],
    &bnode->tail[curSlot],
    sizeof(bnode->tail[0])*shift);
    memmove(&bnode->present[curSlot+1],
    &bnode->present[curSlot],
    sizeof(bnode->present[0])*shift);
    memmove(&bnode->childCount[curSlot+1],
    &bnode->childCount[curSlot],
    sizeof(bnode->childCount[0])*shift);

    memmove(&bnode->keys[curSlot+1],
    &bnode->keys[curSlot],
    sizeof(bnode->keys[0])*(shift-1));
    memset(bnode->keys[curSlot],0,B_MAX_NAME_LENGTH);
    }else{
    bnode->head[curSlot+1]=bnode->head[curSlot];
    bnode->tail[curSlot+1]=bnode->tail[curSlot];
    bnode->childCount[curSlot+1]=bnode->childCount[curSlot];
    bnode->present[curSlot+1]=bnode->present[curSlot];
    }//else

    ubixfsInode*tmpInode=bnode->head[curSlot].iPtr;

    for(unsignedinti=0;i<(B_MAX_CHILD_COUNT+1)>>1;i++){
    assert(tmpInode);
    tmpInode=tmpInode->next.iPtr;
    }//fori

    strncpy(bnode->keys[curSlot],tmpInode->name,B_MAX_NAME_LENGTH);
    bnode->head[curSlot+1].iPtr=tmpInode;
    bnode->tail[curSlot].iPtr=tmpInode->prev.iPtr;
    bnode->childCount[curSlot]=(B_MAX_CHILD_COUNT+1)>>1;
    bnode->childCount[curSlot+1]-=bnode->childCount[curSlot];
    bnode->present[curSlot]=true;
    ++header->treeWidth;
    if(++bnode->used==B_MAX_KEYS)splitNode(bnode);

    }//ifleafisfull
    //Info(bnode);
    returntrue;
    }//bTree::Insert

    void
    bTree::splitNode(bNode*oldNode){
    ubixfsInode*tmpInode=NULL;
    assert(oldNode);
    if(oldNode==NULL)return;
    if(oldNode->used!=B_MAX_KEYS)return;

    bNode*newNode=allocEmptyNode();
    if(newNode==NULL)return;

    unsignedintshift=B_MAX_KEYS>>1;
    unsignedintsplitLoc=B_MAX_KEYS-shift;
    ++shift;
    //cout<<"oldNodebeforesplit:"<<endl;
    //Info(oldNode);
    //cout<<"splitLoc:"<<splitLoc<<endl;
    //cout<<"shift:"<<shift<<endl;

    newNode->used=oldNode->used=B_MAX_KEYS>>1;
    newNode->parent.bPtr=oldNode->parent.bPtr;
    newNode->leaf=oldNode->leaf;

    //cout<<"newNode->used:"<<newNode->used<<endl;
    //cout<<"oldNode->used:"<<oldNode->used<<endl;

    memcpy(&newNode->keys[0],
    &oldNode->keys[splitLoc],
    sizeof(newNode->keys[0])*(shift-1));

    memset(&oldNode->keys[splitLoc],0,sizeof(newNode->keys[0])*(shift-1));

    memcpy(&newNode->present[0],
    &oldNode->present[splitLoc],
    sizeof(newNode->present[0])*shift);

    memset(&oldNode->present[splitLoc],0,sizeof(newNode->present[0])*shift);

    memcpy(&newNode->head[0],
    &oldNode->head[splitLoc],
    sizeof(newNode->head[0])*shift);

    memset(&oldNode->head[splitLoc],0,
    sizeof(newNode->head[0])*shift);

    memcpy(&newNode->tail[0],
    &oldNode->tail[splitLoc],
    sizeof(newNode->tail[0])*shift);

    memset(&oldNode->tail[splitLoc],0,
    sizeof(newNode->tail[0])*shift);

    memcpy(&newNode->childCount[0],
    &oldNode->childCount[splitLoc],
    sizeof(newNode->childCount[0])*shift);

    memset(&oldNode->childCount[splitLoc],0,
    sizeof(newNode->childCount[0])*shift);

    if(!newNode->leaf){
    for(unsignedinti=0;i<=newNode->used;i++){
    newNode->head[i].bPtr->parent.bPtr=newNode;
    }//fori
    }//ifnewNodeisn'taleaf

    tmpInode=GetFirstNode(newNode);
    assert(tmpInode);

    if(oldNode==root){
    //allocateanewrootnode
    ++header->treeDepth;
    root=allocEmptyNode();
    oldNode->parent.bPtr=root;
    newNode->parent.bPtr=root;
    //strncpy(root->keys[0],newNode->keys[0],B_MAX_NAME_LENGTH);
    strncpy(root->keys[0],tmpInode->name,B_MAX_NAME_LENGTH);
    root->head[0].bPtr=oldNode;
    root->tail[0].bPtr=root->tail[1].bPtr=NULL;
    root->head[1].bPtr=newNode;
    root->used=1;
    root->leaf=false;
    root->present[0]=root->present[1]=true;
    root->childCount[0]=root->childCount[1]=0;
    //root->childCount[0]=oldNode->used;
    //root->childCount[1]=newNode->used;

    //cout<<"parent"<<endl;
    //Info(newNode->parent);
    //cout<<"oldNode"<<endl;
    //Info(oldNode);
    //cout<<"-----"<<endl;
    //cout<<"newNode"<<endl;
    //Info(newNode);
    //cout<<"-----"<<endl;

    }else{
    insertNode(newNode->parent.bPtr,tmpInode->name,newNode);
    //if(oldNode->parent->used==B_MAX_KEYS)splitNode(oldNode->parent);
    }//else
    return;
    }//bTree::splitNode

    void
    bTree::insertNode(bNode*node,constchar*key,bNode*headPtr){
    unsignedintcurSlot=0;
    if(node==NULL||key==NULL)return;

    if(strcmp(key,node->keys[node->used-1])>=0){
    curSlot=node->used;
    memset(node->keys[curSlot],0,B_MAX_NAME_LENGTH);
    strncpy(node->keys[curSlot],key,B_MAX_NAME_LENGTH);
    node->head[curSlot+1].bPtr=headPtr;
    node->tail[curSlot+1].bPtr=NULL;
    node->present[curSlot+1]=true;
    node->childCount[node->used]=0;//maybe?

    }else{

    for(curSlot=0;curSlot<node->used;curSlot++){
    if(strcmp(key,node->keys[curSlot])<0)break;
    }//for

    /*
    *notethatthereisonemoreitemforeverythingbutkeys
    *So,maketheshiftcount+1andjustsubtractitfromthekeyshift
    *later
    */
    intshift=node->used-curSlot+1;

    memmove(&node->head[curSlot+1],
    &node->head[curSlot],
    sizeof(node->head[0])*shift);
    memmove(&node->tail[curSlot+1],
    &node->tail[curSlot],
    sizeof(node->tail[0])*shift);
    memmove(&node->present[curSlot+1],
    &node->present[curSlot],
    sizeof(node->present[0])*shift);
    memmove(&node->childCount[curSlot+1],
    &node->childCount[curSlot],
    sizeof(node->childCount[0])*shift);

    memmove(&node->keys[curSlot+1],
    &node->keys[curSlot],
    sizeof(node->keys[0])*(shift-1));

    memset(node->keys[curSlot],0,B_MAX_NAME_LENGTH);
    strncpy(node->keys[curSlot],key,B_MAX_NAME_LENGTH);
    node->head[curSlot+1].bPtr=headPtr;
    node->tail[curSlot+1].bPtr=NULL;
    node->present[curSlot+1]=true;
    //node->childCount[node->used]=?;
    }//else
    if(++node->used==B_MAX_KEYS)splitNode(node);
    return;
    }//bTree::insertNode

    bNode*
    bTree::allocEmptyNode(void){
    bNode*newNode=newbNode;

    memset(newNode,0,sizeof(bNode));
    newNode->magic1=B_NODE_MAGIC_1;
    newNode->magic2=B_NODE_MAGIC_2;
    newNode->parent.bPtr=NULL;
    newNode->tag=++tag;//thiswillstartat1(0istheheadernode)
    returnnewNode;
    }//bTree::allocEmptyNode

    void
    bTree::Info(constbNode*node){
    ubixfsInode*inode=NULL;
    if(node==NULL||root==NULL)return;
    cout<<node<<"|"<<node->parent.bPtr<<endl;
    for(unsignedinti=0;i<=node->used;i++){
    inode=node->head[i].iPtr;
    //cout<<"("<<node->childCount[i]<<")";
    for(unsignedintk=0;k<node->childCount[i];k++){
    cout<<"["<<inode->name<<"]";
    inode=inode->next.iPtr;
    }//fork
    if(i!=node->used)cout<<"{"<<node->keys[i]<<"}";
    }//fori
    cout<<endl;
    return;
    #if0
    for(unsignedinti=0;i<node->used;i++){
    cout<<"keys["<<i<<"]:"<<node->keys[i]<<"";
    }//fori
    cout<<endl;
    cout<<"node->used:"<<node->used<<endl;
    cout<<"leaf:"<<node->leaf<<endl;
    for(unsignedinti=0;i<=node->used;i++){
    inode=(ubixfsInode*)node->head[i];
    cout<<"node->childCount["<<i<<"]:"<<node->childCount[i]<<endl;
    for(unsignedintj=0;j<node->childCount[i];j++){
    assert(inode);
    cout<<"["<<i<<"].["<<j<<"]->"<<inode->name<<endl;
    inode=inode->next;
    }//forj
    }//fori
    #endif
    }//bTree::Info

    void
    bTree::Info(void){
    ubixfsInode*inode=NULL;

    cout<<"treedepth:"<<header->treeDepth<<endl;
    cout<<"treewidth:"<<header->treeWidth<<endl;
    cout<<"treeleafcount:"<<header->treeLeafCount<<endl;
    cout<<"tag:"<<tag<<endl;

    if(root==NULL)return;

    for(unsignedinti=0;i<=root->used;i++){
    cout<<"CC["<<i<<"]:"<<root->childCount[i]<<"";
    }//fori

    cout<<endl;
    for(unsignedinti=0;i<=root->used;i++){
    cout<<"CH["<<i<<"]:"<<root->head[i].bPtr<<"";
    }//fori

    cout<<endl;
    for(unsignedinti=0;i<=root->used;i++){
    cout<<"CT["<<i<<"]:"<<root->tail[i].bPtr<<"";
    }//fori
    cout<<endl;
    for(unsignedinti=0;i<root->used;i++){
    cout<<"keys["<<i<<"]:"<<root->keys[i]<<"";
    }//fori
    cout<<endl;

    cout<<"root->used:"<<root->used<<endl;
    for(unsignedinti=0;i<=root->used;i++){
    inode=root->head[i].iPtr;
    cout<<"root->childCount["<<i<<"]:"<<root->childCount[i]<<endl;
    if(root->leaf){
    cout<<"rootcontainsleafnode"<<endl;
    for(unsignedintj=0;j<root->childCount[i];j++){
    assert(inode);
    cout<<"["<<i<<"].["<<j<<"]->"<<inode->name<<endl;
    inode=inode->next.iPtr;
    }//forj
    }//ifroot->leaf
    }//fori
    }//bTree::Info

    void
    bTree::Print(void){
    ubixfsInode*node=GetFirstNode();
    while(node!=NULL){
    cout<<node->name<<endl;
    node=node->next.iPtr;
    }
    }//bTree::Print

    ubixfsInode*
    bTree::Find(constchar*key){
    /*
    ubixfsInode*tmp=GetFirstNode();
    while(tmp!=NULL){
    if(strcmp(tmp->name,key)==0)returntmp;
    tmp=tmp->next.iPtr;
    }
    returnNULL;
    */
    returntreeSearch(root,key);
    }//bTree::Find

    ubixfsInode*
    bTree::inodeSearch(ubixfsInode*inode,constchar*key){
    if(inode==NULL||key==NULL)returnNULL;
    intresult=strcmp(inode->name,key);
    if(result==0)returninode;

    if(result<0){
    inode=inode->next.iPtr;
    while(inode!=NULL&&((result=strcmp(inode->name,key))<0)){
    inode=inode->next.iPtr;
    }//while
    }else{
    inode=inode->prev.iPtr;
    while(inode!=NULL&&((result=strcmp(inode->name,key))>0)){
    inode=inode->prev.iPtr;
    }//while
    }//else
    return(result==0?inode:NULL);
    }//bTree::inodeSearch

    ubixfsInode*
    bTree::treeSearch(bNode*bnode,constchar*key){

    if(bnode==NULL||key==NULL||bnode->used==0)returnNULL;

    if(bnode->leaf)
    returninodeSearch(GetFirstNode(bnode),key);

    if(strcmp(key,bnode->keys[0])<0){
    returntreeSearch(bnode->head[0].bPtr,key);
    }//if

    if(strcmp(key,bnode->keys[bnode->used-1])>=0){
    returntreeSearch(bnode->head[bnode->used].bPtr,key);
    }//if

    for(unsignedinti=1;i<bnode->used;i++){
    if(strcmp(key,bnode->keys[i])<0){
    returntreeSearch(bnode->head[i].bPtr,key);
    }//if
    }//fori

    returnNULL;
    }//bTree::treeSearch

    ubixfsInode*
    bTree::GetFirstNode(void){
    returnGetFirstNode(root);
    }//bTree::GetFirstNode

    ubixfsInode*
    bTree::GetFirstNode(bNode*node){
    bNode*tmpNode=node;

    if(tmpNode==NULL)returnNULL;

    while(!tmpNode->leaf){
    for(unsignedinti=0;i<tmpNode->used;i++){
    if(tmpNode->head[i].bPtr!=NULL){
    tmpNode=tmpNode->head[i].bPtr;
    break;
    }//if
    }//fori
    }//while

    for(unsignedinti=0;i<tmpNode->used;i++){
    if(tmpNode->head[i].iPtr!=NULL)returntmpNode->head[i].iPtr;
    }//fori
    returnNULL;
    }//bTree::GetFirstNode

    bNode*
    bTree::findLeafNode(bNode*node,constchar*key){
    assert(node);
    assert(key);
    if(node==NULL||key==NULL)returnNULL;
    assert(node->used);
    if(node->leaf)returnnode;

    if(strcmp(key,node->keys[0])<0)
    returnfindLeafNode(node->head[0].bPtr,key);

    if(strcmp(key,node->keys[node->used-1])>=0)
    returnfindLeafNode(node->head[node->used].bPtr,key);

    for(unsignedinti=1;i<node->used;i++){
    if(strcmp(key,node->keys[i])<0)
    returnfindLeafNode(node->head[i].bPtr,key);
    }//fori

    returnNULL;
    }//bTree::findLeafNode

    void
    bTree::saveNode(FILE*fd,bNode*node,void*tmpPtr){

    bNode*ptr=(bNode*)tmpPtr;
    assert(tmpPtr);
    assert(fd);
    assert(node);
    cout<<"writingtag:"<<node->tag<<endl;

    memcpy(tmpPtr,node,sizeof(bNode));

    if(node->parent.bPtr!=NULL)
    ptr->parent.offset=node->parent.bPtr->tag*sizeof(bNode);
    else
    ptr->parent.offset=0;

    for(unsignedinti=0;i<=node->used;i++){
    bNode*bPtr=node->head[i].bPtr;

    if(bPtr!=NULL)
    ptr->head[i].offset=bPtr->tag*sizeof(bNode);
    else
    ptr->head[i].offset=~0;
    ptr->present[i]=false;
    }//fori

    if(node->leaf){

    for(unsignedinti=0;i<=node->used;i++){
    //ubixfsInode*inode=node->head[i].iPtr;
    //mjiif(inode!=NULL)tmp->head[i]=inode->
    }//fori
    }else{

    for(unsignedinti=0;i<=node->used;i++){

    if(node->head[i].bPtr!=NULL)saveNode(fd,node->head[i].bPtr,tmpPtr);

    }//fori

    }//else

    return;
    }//bTree::saveNode

    bool
    bTree::Save(constchar*filename){
    ubixfsInode*uPtr=NULL;
    if(filename==NULL)returnfalse;
    FILE*fd=NULL;
    if((fd=fopen(filename,"wb+"))==NULL)returnfalse;

    cout<<"tags:"<<tag<<endl;
    lseek(fileno(fd),tag*sizeof(bNode),SEEK_END);

    header->firstNodeOffset=sizeof(bNode);
    header->firstDeleted=-1;
    void*tmpPtr=malloc(sizeof(bNode));
    assert(tmpPtr);
    uPtr=(ubixfsInode*)tmpPtr;
    memset(tmpPtr,0,sizeof(bNode));
    fwrite(header,sizeof(bTreeHeader),1,fd);
    saveNode(fd,root,tmpPtr);

    fclose(fd);
    free(tmpPtr);
    returntrue;
    }//bTree::Save

    bool
    bTree::Load(constchar*filename){
    if(filename==NULL)returnfalse;
    returntrue;
    }//bTree::Load

    bool
    bTree::Delete(constchar*key){

    if(key==NULL)returnfalse;
    returntrue;
    }//bTree::Delete

    bool
    bTree::Verify(void){
    ubixfsInode*node=GetFirstNode();
    if(node==NULL)returntrue;

    while(node!=NULL){
    ubixfsInode*next=node->next.iPtr;
    if(next!=NULL){
    //cout<<node->name<<"::"<<node->next->name<<":::"<<strcmp(node->name,node->next->name)<<endl;
    if(strcmp(node->name,next->name)>0)returnfalse;
    }
    node=next;
    }//while
    returntrue;
    }//bTree::Verify

    void
    bTree::Print(bNode*node){
    if(node==NULL)return;
    Info(node);
    if(!node->leaf)
    for(unsignedinti=0;i<=node->used;i++){
    Print(node->head[i].bPtr);
    }//fori
    }//bTree::Print

    void
    bTree::PrintWholeTree(void){
    Print(root);
    }//bTree::PrintWholeTree;

    bTree::~bTree(void){
    cout<<"treedepth:"<<header->treeDepth<<endl;
    cout<<"treewidth:"<<header->treeWidth<<endl;
    cout<<"treeleafcount:"<<header->treeLeafCount<<endl;
    }//bTree::~bTree