# btree.cpp

Go to the documentation of this file.

    00001 // http://www.cs.msstate.edu/~cs2314/global/BTreeAnimation/algorithm.html
    00002 #include <stdlib.h>
    00003 #include <string.h>
    00004 #include <stdio.h>
    00005 #include <unistd.h>
    00006 #include <iostream>
    00007 #include <assert.h>
    00008 #include "btree.h"
    00009 #include "ubixfs.h"
    00010
    00011 using namespace std;
    00012 #define VERIFY(x, y, z, n) if ((x) != (y)) { cout << "verify " << z << " failed" << endl; PrintWholeTree(); }
    00013
    00014 bTree::bTree(UbixFS * filesystem, fileDescriptor * myfd) {
    00015   size_t result = 0;
    00016
    00017   root = NULL;
    00018   tag = 0;
    00019   fs = filesystem;
    00020   fd = myfd;
    00021   header = new bTreeHeader;
    00022   assert(header);
    00023   memset(header, 0, sizeof(bTreeHeader));
    00024   assert(fs);
    00025   result = fs->vfs_read(fd, header, 0, sizeof(bTreeHeader));
    00026   assert(result == sizeof(bTreeHeader));
    00027
    00028   // If there are any files in this dir, load the first node of the b+tree
    00029   if (header->treeLeafCount != 0) {
    00030     assert(header->firstNodeOffset != 0);
    00031     root = new bNode;
    00032     assert(root);
    00033     result = fs->vfs_read(fd, root, header->firstNodeOffset, sizeof(bNode));
    00034     assert(result == sizeof(bNode));
    00035   } // if
    00036
    00037 } // bTree::bTree
    00038
    00039 bTree::bTree(const char * key, ubixfsInode * inode) {
    00040 /* once the FS and the bTree are interfaced, this should go away */
    00041   root = NULL;
    00042   tag = 0;
    00043   header = new bTreeHeader;
    00044   assert(header);
    00045   memset(header, 0, sizeof(bTreeHeader));
    00046   header->treeDepth = 1;
    00047   header->treeWidth = 0;
    00048   header->treeLeafCount = 0;
    00049   header->firstDeleted = -1;
    00050   header->firstNodeOffset = sizeof(bTreeHeader);
    00051
    00052   if (inode == NULL) return;
    00053   root = allocEmptyNode();
    00054   if (root == NULL) return;
    00055   root->used = 1;
    00056   root->parent.bPtr = NULL;
    00057   root->leaf = true;
    00058   root->childCount[1] = 1;
    00059
    00060 // cout << "---Creating " << inode->name << "@" << inode << endl;
    00061   strncpy(root->keys[0], key, B_MAX_NAME_LENGTH);
    00062   // insert pointer to data page to the right of the data
    00063   root->head[1].iPtr = inode;
    00064   root->tail[1].iPtr = inode;
    00065
    00066   root->present[1] = true;
    00067   if (inode != NULL) {
    00068     inode->next.bPtr = inode->prev.bPtr = NULL;
    00069   } // if
    00070   return;
    00071 } // bTree:bTree
    00072
    00073 bool
    00074 bTree::Insert(const char * key, ubixfsInode * inode) {
    00075   bNode * bnode = root;
    00076   ubixfsInode * tmpInode = NULL;
    00077   unsigned int curSlot = 0;
    00078
    00079   if (inode == NULL) return false;
    00080
    00081   // note: this code is right out of the constructor
    00082   if (root == NULL) {
    00083     if (header == NULL) header = new bTreeHeader;
    00084     assert(header);
    00085     memset(header, 0, sizeof(bTreeHeader));
    00086     header->treeDepth = 1;
    00087     header->treeWidth = 0;
    00088     header->treeLeafCount = 0;
    00089     header->firstDeleted = -1;
    00090     header->firstNodeOffset = sizeof(bTreeHeader);
    00091
    00092     root = allocEmptyNode();
    00093     assert(root);
    00094     if (root == NULL) return false;
    00095
    00096     root->used = 1;
    00097     root->parent.bPtr = NULL;
    00098     root->leaf = true;
    00099     root->childCount[1] = 1;
    00100
    00101     strncpy(root->keys[0], key, B_MAX_NAME_LENGTH);
    00102     // insert pointer to data page to the right of the data
    00103     root->head[1].iPtr = inode;
    00104     root->tail[1].iPtr = inode;
    00105
    00106     root->present[1] = true;
    00107     inode->next.iPtr = inode->prev.iPtr = NULL;
    00108     return true;
    00109   } // if
    00110
    00111   tmpInode = Find(key);
    00112   if (tmpInode != NULL) return false;
    00113 //  PrintWholeTree();
    00114 // cout << "Insert(" << key << ")" << endl;
    00115 //Info(bnode);
    00116   ++header->treeLeafCount;
    00117   /*
    00118    * Find the leaf node the inode goes into
    00119    */
    00120   assert(bnode->used);
    00121 // cout << "---Inserting " << inode->name << " @ " << inode << endl;
    00122   while (bnode != NULL && !bnode->leaf) {
    00123     if (strcmp(key, bnode->keys[0]) < 0) {
    00124       bnode = bnode->head[0].bPtr;
    00125     } else {
    00126       if (strcmp(key, bnode->keys[bnode->used-1]) >= 0) {
    00127         bnode = bnode->head[bnode->used].bPtr;
    00128       } else {
    00129         for (unsigned int i = 1; i < bnode->used; i++) {
    00130           if (strcmp(key, bnode->keys[i]) < 0) {
    00131             bnode = bnode->head[i].bPtr;
    00132             break;
    00133           } // if
    00134         } // for i
    00135       } // else
    00136     }
    00137   } // while
    00138
    00139   /*
    00140    *
    00141    */
    00142
    00143 assert(bnode);
    00144 if (bnode->leaf != true) cout << "leafnode!=true" << endl;
    00145 assert(inode);
    00146
    00147   if (strcmp(key, bnode->keys[curSlot = 0]) < 0)
    00148     tmpInode = bnode->head[curSlot].iPtr;
    00149   else
    00150     if (strcmp(key, bnode->keys[(curSlot = bnode->used)-1]) >= 0)
    00151       tmpInode = bnode->head[bnode->used].iPtr;
    00152     else {
    00153       for (curSlot = 1; curSlot < bnode->used; curSlot++) {
    00154         if (strcmp(key, bnode->keys[curSlot]) < 0) {
    00155           tmpInode = bnode->head[curSlot].iPtr;
    00156           break;
    00157         } // if
    00158       } // for curSlot
    00159       tmpInode = bnode->head[curSlot].iPtr;
    00160     } // else
    00161
    00162
    00163   if (tmpInode == NULL) {
    00164     /*
    00165      * This is the first node in this leaf
    00166      */
    00167     bnode->head[curSlot].iPtr = bnode->tail[curSlot].iPtr = inode;
    00168     bnode->present[curSlot] = true;
    00169
    00170     if (curSlot == 0) {
    00171
    00172       if (bnode->head[1].iPtr != NULL)  {
    00173         ubixfsInode * iptr = bnode->head[1].iPtr;
    00174         inode->prev.iPtr = iptr->prev.iPtr;
    00175         inode->next.iPtr = iptr;
    00176         iptr->prev.iPtr = inode;
    00177         if (inode->prev.iPtr != NULL)
    00178           inode->prev.iPtr->next.iPtr = inode;
    00179       } else {
    00180         inode->next.iPtr = inode->prev.iPtr = NULL;
    00181       } // else
    00182
    00183     } else {
    00184       ++bnode->used;
    00185     } // else
    00186
    00187   } else {
    00188     /*
    00189      * Add node to leaf page. Scan through to find where it goes.
    00190      */
    00191     if (strcmp(key, bnode->head[curSlot].iPtr->name) < 0)
    00192     {
    00193
    00194       inode->next.iPtr = bnode->head[curSlot].iPtr;
    00195       inode->prev.iPtr = inode->next.iPtr->prev.iPtr;
    00196       inode->next.iPtr->prev.iPtr = inode;
    00197       if (inode->prev.iPtr != NULL) inode->prev.iPtr->next.iPtr = inode;
    00198       bnode->head[curSlot].iPtr = inode;
    00199
    00200     } else {
    00201
    00202       if (strcmp(key, bnode->tail[curSlot].iPtr->name) > 0) {
    00203
    00204         inode->prev.iPtr = bnode->tail[curSlot].iPtr;
    00205         inode->next.iPtr = inode->prev.iPtr->next.iPtr;
    00206         inode->prev.iPtr->next.iPtr = inode;
    00207
    00208         if (inode->next.iPtr != NULL) inode->next.iPtr->prev.iPtr = inode;
    00209         bnode->tail[curSlot].iPtr = inode;
    00210
    00211       } else {
    00212
    00213
    00214         ubixfsInode * tmpInode = bnode->head[curSlot].iPtr;
    00215         for (unsigned int i = 0; i < bnode->childCount[curSlot]; i++) {
    00216           if (strcmp(key, tmpInode->name) < 0) {
    00217             inode->next.iPtr = tmpInode;
    00218             inode->prev.iPtr = tmpInode->prev.iPtr;
    00219             inode->next.iPtr->prev.iPtr = inode;
    00220             inode->prev.iPtr->next.iPtr = inode;
    00221             break;
    00222           } // if
    00223           tmpInode = tmpInode->next.iPtr;
    00224         } // for i
    00225
    00226       } // else
    00227
    00228     } // else
    00229
    00230   } // else
    00231
    00232
    00233
    00234   if (++bnode->childCount[curSlot] == B_MAX_CHILD_COUNT) {
    00235
    00236 // cout << "---- before split ----" << endl;
    00237 // Info(bnode);
    00238
    00239     if (curSlot != bnode->used) {
    00240       int shift = bnode->used - curSlot +1;
    00241
    00242       memmove(&bnode->head[curSlot+1],
    00243               &bnode->head[curSlot],
    00244               sizeof(bnode->head[0]) * shift);
    00245       memmove(&bnode->tail[curSlot+1],
    00246               &bnode->tail[curSlot],
    00247               sizeof(bnode->tail[0]) * shift);
    00248       memmove(&bnode->present[curSlot+1],
    00249               &bnode->present[curSlot],
    00250               sizeof(bnode->present[0]) * shift);
    00251       memmove(&bnode->childCount[curSlot+1],
    00252               &bnode->childCount[curSlot],
    00253               sizeof(bnode->childCount[0]) * shift);
    00254
    00255       memmove(&bnode->keys[curSlot+1],
    00256               &bnode->keys[curSlot],
    00257               sizeof(bnode->keys[0]) * (shift-1));
    00258       memset(bnode->keys[curSlot], 0, B_MAX_NAME_LENGTH);
    00259     } else {
    00260       bnode->head[curSlot+1] = bnode->head[curSlot];
    00261       bnode->tail[curSlot+1] = bnode->tail[curSlot];
    00262       bnode->childCount[curSlot+1] = bnode->childCount[curSlot];
    00263       bnode->present[curSlot+1] = bnode->present[curSlot];
    00264     } // else
    00265
    00266     ubixfsInode * tmpInode = bnode->head[curSlot].iPtr;
    00267
    00268     for (unsigned int i = 0; i < (B_MAX_CHILD_COUNT+1) >> 1; i++) {
    00269       assert(tmpInode);
    00270       tmpInode = tmpInode->next.iPtr;
    00271     } // for i
    00272
    00273     strncpy(bnode->keys[curSlot], tmpInode->name, B_MAX_NAME_LENGTH);
    00274     bnode->head[curSlot+1].iPtr = tmpInode;
    00275     bnode->tail[curSlot].iPtr = tmpInode->prev.iPtr;
    00276     bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1;
    00277     bnode->childCount[curSlot+1] -= bnode->childCount[curSlot];
    00278     bnode->present[curSlot] = true;
    00279     ++header->treeWidth;
    00280     if (++bnode->used == B_MAX_KEYS) splitNode(bnode);
    00281
    00282   } // if leaf is full
    00283 // Info(bnode);
    00284   return true;
    00285 } // bTree::Insert
    00286
    00287 void
    00288 bTree::splitNode(bNode * oldNode) {
    00289   ubixfsInode * tmpInode = NULL;
    00290   assert(oldNode);
    00291   if (oldNode == NULL) return;
    00292   if (oldNode->used != B_MAX_KEYS) return;
    00293
    00294   bNode * newNode = allocEmptyNode();
    00295   if (newNode == NULL) return;
    00296
    00297   unsigned int shift = B_MAX_KEYS >> 1;
    00298   unsigned int splitLoc = B_MAX_KEYS - shift;
    00299   ++ shift;
    00300 // cout << "oldNode before split: " << endl;
    00301 // Info(oldNode);
    00302 // cout << "splitLoc: " << splitLoc << endl;
    00303 // cout << "shift: " << shift << endl;
    00304
    00305   newNode->used = oldNode->used = B_MAX_KEYS >> 1;
    00306   newNode->parent.bPtr = oldNode->parent.bPtr;
    00307   newNode->leaf = oldNode->leaf;
    00308
    00309 // cout << "newNode->used: " << newNode->used << endl;
    00310 // cout << "oldNode->used: " << oldNode->used << endl;
    00311
    00312   memcpy(&newNode->keys[0],
    00313          &oldNode->keys[splitLoc],
    00314          sizeof(newNode->keys[0]) * (shift-1));
    00315
    00316   memset(&oldNode->keys[splitLoc], 0, sizeof(newNode->keys[0]) * (shift-1));
    00317
    00318   memcpy(&newNode->present[0],
    00319          &oldNode->present[splitLoc],
    00320          sizeof(newNode->present[0]) * shift);
    00321
    00322   memset(&oldNode->present[splitLoc], 0, sizeof(newNode->present[0]) * shift);
    00323
    00324   memcpy(&newNode->head[0],
    00325          &oldNode->head[splitLoc],
    00326          sizeof(newNode->head[0]) * shift);
    00327
    00328   memset(&oldNode->head[splitLoc], 0,
    00329          sizeof(newNode->head[0]) * shift);
    00330
    00331   memcpy(&newNode->tail[0],
    00332          &oldNode->tail[splitLoc],
    00333          sizeof(newNode->tail[0]) * shift);
    00334
    00335   memset(&oldNode->tail[splitLoc], 0,
    00336          sizeof(newNode->tail[0]) * shift);
    00337
    00338   memcpy(&newNode->childCount[0],
    00339          &oldNode->childCount[splitLoc],
    00340          sizeof(newNode->childCount[0]) * shift);
    00341
    00342   memset(&oldNode->childCount[splitLoc], 0,
    00343          sizeof(newNode->childCount[0]) * shift);
    00344
    00345   if (!newNode->leaf) {
    00346     for (unsigned int i = 0; i <= newNode->used; i++) {
    00347       newNode->head[i].bPtr->parent.bPtr = newNode;
    00348     } // for i
    00349   } // if newNode isn't a leaf
    00350
    00351   tmpInode = GetFirstNode(newNode);
    00352   assert(tmpInode);
    00353
    00354   if (oldNode == root) {
    00355     // allocate a new root node
    00356     ++header->treeDepth;
    00357     root = allocEmptyNode();
    00358     oldNode->parent.bPtr = root;
    00359     newNode->parent.bPtr = root;
    00360  //   strncpy(root->keys[0], newNode->keys[0], B_MAX_NAME_LENGTH);
    00361     strncpy(root->keys[0], tmpInode->name, B_MAX_NAME_LENGTH);
    00362     root->head[0].bPtr = oldNode;
    00363     root->tail[0].bPtr = root->tail[1].bPtr = NULL;
    00364     root->head[1].bPtr = newNode;
    00365     root->used = 1;
    00366     root->leaf = false;
    00367     root->present[0] = root->present[1] = true;
    00368     root->childCount[0] = root->childCount[1] = 0;
    00369 //    root->childCount[0] = oldNode->used;
    00370 //    root->childCount[1] = newNode->used;
    00371
    00372 // cout << "parent" << endl;
    00373 // Info(newNode->parent);
    00374 // cout << "oldNode" << endl;
    00375 // Info(oldNode);
    00376 // cout << "-----" << endl;
    00377 // cout << "newNode" << endl;
    00378 // Info(newNode);
    00379 // cout << "-----" << endl;
    00380
    00381   } else {
    00382     insertNode(newNode->parent.bPtr, tmpInode->name, newNode);
    00383    // if (oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent);
    00384   } // else
    00385   return;
    00386 } // bTree::splitNode
    00387
    00388 void
    00389 bTree::insertNode(bNode * node, const char * key, bNode * headPtr) {
    00390   unsigned int curSlot = 0;
    00391   if (node == NULL || key == NULL) return;
    00392
    00393   if (strcmp(key, node->keys[node->used-1]) >= 0){
    00394     curSlot = node->used;
    00395     memset(node->keys[curSlot], 0, B_MAX_NAME_LENGTH);
    00396     strncpy(node->keys[curSlot], key, B_MAX_NAME_LENGTH);
    00397     node->head[curSlot+1].bPtr = headPtr;
    00398     node->tail[curSlot+1].bPtr = NULL;
    00399     node->present[curSlot+1] = true;
    00400     node->childCount[node->used] = 0; // maybe?
    00401
    00402   } else {
    00403
    00404     for (curSlot = 0; curSlot < node->used; curSlot++) {
    00405       if (strcmp(key, node->keys[curSlot]) < 0) break;
    00406     } // for
    00407
    00408     /*
    00409      * note that there is one more item for everything but keys
    00410      * So, make the shift count +1 and just subtract it from the key shift
    00411      * later
    00412      */
    00413     int shift = node->used - curSlot +1;
    00414
    00415     memmove(&node->head[curSlot+1],
    00416             &node->head[curSlot],
    00417             sizeof(node->head[0]) * shift);
    00418     memmove(&node->tail[curSlot+1],
    00419             &node->tail[curSlot],
    00420             sizeof(node->tail[0]) * shift);
    00421     memmove(&node->present[curSlot+1],
    00422             &node->present[curSlot],
    00423             sizeof(node->present[0]) * shift);
    00424     memmove(&node->childCount[curSlot+1],
    00425             &node->childCount[curSlot],
    00426             sizeof(node->childCount[0]) * shift);
    00427
    00428     memmove(&node->keys[curSlot+1],
    00429             &node->keys[curSlot],
    00430             sizeof(node->keys[0]) * (shift-1));
    00431
    00432     memset(node->keys[curSlot], 0, B_MAX_NAME_LENGTH);
    00433     strncpy(node->keys[curSlot], key, B_MAX_NAME_LENGTH);
    00434     node->head[curSlot+1].bPtr = headPtr;
    00435     node->tail[curSlot+1].bPtr = NULL;
    00436     node->present[curSlot+1] = true;
    00437 //    node->childCount[node->used] = ?;
    00438   } // else
    00439   if (++node->used == B_MAX_KEYS) splitNode(node);
    00440   return;
    00441 } // bTree::insertNode
    00442
    00443 bNode *
    00444 bTree::allocEmptyNode(void) {
    00445   bNode * newNode = new bNode;
    00446
    00447   memset(newNode, 0, sizeof(bNode));
    00448   newNode->magic1 = B_NODE_MAGIC_1;
    00449   newNode->magic2 = B_NODE_MAGIC_2;
    00450   newNode->parent.bPtr = NULL;
    00451   newNode->tag = ++tag; // this will start at 1 (0 is the header node)
    00452   return newNode;
    00453 } // bTree::allocEmptyNode
    00454
    00455 void
    00456 bTree::Info(const bNode * node) {
    00457   ubixfsInode * inode = NULL;
    00458   if (node == NULL || root == NULL) return;
    00459   cout <<  node << " | " << node->parent.bPtr << endl;
    00460   for (unsigned int i = 0; i <= node->used; i++) {
    00461     inode = node->head[i].iPtr;
    00462 //    cout << "(" << node->childCount[i] << ")";
    00463     for (unsigned int k = 0; k < node->childCount[i]; k++) {
    00464       cout << "[" << inode->name << "]";
    00465       inode = inode->next.iPtr;
    00466     } // for k
    00467     if (i != node->used) cout << " {" << node->keys[i] << "} ";
    00468   } // for i
    00469   cout << endl;
    00470   return;
    00471 #if 0
    00472   for (unsigned int i = 0; i < node->used; i++) {
    00473     cout << "keys[" << i << "]: " << node->keys[i] << "  ";
    00474   } // for i
    00475   cout << endl;
    00476   cout << "node->used: " << node->used << endl;
    00477   cout << "leaf: " << node->leaf << endl;
    00478   for (unsigned int i = 0; i <= node->used; i++) {
    00479     inode = (ubixfsInode *)node->head[i];
    00480 cout << "node->childCount["<<i<<"]: " << node->childCount[i] << endl;
    00481     for (unsigned int j = 0; j < node->childCount[i]; j++) {
    00482       assert(inode);
    00483       cout << "[" << i << "].[" << j << "]->" << inode->name << endl;
    00484       inode = inode->next;
    00485     } // for j
    00486   } // for i
    00487 #endif
    00488 } // bTree::Info
    00489
    00490 void
    00491 bTree::Info(void) {
    00492   ubixfsInode * inode = NULL;
    00493
    00494   cout << "tree depth: " << header->treeDepth << endl;
    00495   cout << "tree width: " << header->treeWidth << endl;
    00496   cout << "tree leaf count: " << header->treeLeafCount << endl;
    00497   cout << "tag: " << tag << endl;
    00498
    00499   if (root == NULL) return;
    00500
    00501   for (unsigned int i = 0; i <= root->used; i++) {
    00502     cout << "CC[" << i << "]: " << root->childCount[i] << "  ";
    00503   } // for i
    00504
    00505   cout << endl;
    00506   for (unsigned int i = 0; i <= root->used; i++) {
    00507     cout << "CH[" << i << "]: " << root->head[i].bPtr << "  ";
    00508   } // for i
    00509
    00510   cout << endl;
    00511   for (unsigned int i = 0; i <=root->used; i++) {
    00512     cout << "CT[" << i << "]: " << root->tail[i].bPtr << "  ";
    00513   } // for i
    00514   cout << endl;
    00515   for (unsigned int i = 0; i < root->used; i++) {
    00516     cout << "keys[" << i << "]: " << root->keys[i] << "  ";
    00517   } // for i
    00518   cout << endl;
    00519
    00520 cout << "root->used: " << root->used << endl;
    00521     for (unsigned int i = 0; i <= root->used; i++) {
    00522       inode = root->head[i].iPtr;
    00523 cout << "root->childCount["<<i<<"]: " << root->childCount[i] << endl;
    00524     if (root->leaf) {
    00525 cout << "root contains leaf node" << endl;
    00526       for (unsigned int j = 0; j < root->childCount[i]; j++) {
    00527         assert(inode);
    00528         cout << "[" << i << "].[" << j << "]->" << inode->name << endl;
    00529         inode = inode->next.iPtr;
    00530       } // for j
    00531     } // if root->leaf
    00532   } // for i
    00533 } // bTree::Info
    00534
    00535 void
    00536 bTree::Print(void) {
    00537   ubixfsInode * node = GetFirstNode();
    00538   while (node != NULL) {
    00539     cout << node->name << endl;
    00540     node = node->next.iPtr;
    00541   }
    00542 } // bTree::Print
    00543
    00544 ubixfsInode *
    00545 bTree::Find(const char * key) {
    00546 /*
    00547   ubixfsInode * tmp = GetFirstNode();
    00548   while (tmp!=NULL) {
    00549     if (strcmp(tmp->name, key) == 0) return tmp;
    00550     tmp = tmp->next.iPtr;
    00551   }
    00552   return NULL;
    00553 */
    00554   return treeSearch(root, key);
    00555 } // bTree::Find
    00556
    00557 ubixfsInode *
    00558 bTree::inodeSearch(ubixfsInode * inode, const char * key) {
    00559   if (inode == NULL || key == NULL) return NULL;
    00560   int result = strcmp(inode->name, key);
    00561   if (result == 0) return inode;
    00562
    00563   if (result < 0) {
    00564     inode = inode->next.iPtr;
    00565     while (inode != NULL && ((result = strcmp(inode->name, key)) < 0)) {
    00566       inode = inode->next.iPtr;
    00567     } // while
    00568   } else {
    00569     inode = inode->prev.iPtr;
    00570     while (inode != NULL && ((result = strcmp(inode->name, key)) > 0)) {
    00571       inode = inode->prev.iPtr;
    00572     } // while
    00573   } // else
    00574   return (result == 0 ? inode : NULL);
    00575 } // bTree::inodeSearch
    00576
    00577 ubixfsInode *
    00578 bTree::treeSearch(bNode * bnode, const char * key) {
    00579
    00580   if (bnode == NULL || key == NULL || bnode->used == 0) return NULL;
    00581
    00582   if (bnode->leaf)
    00583     return inodeSearch(GetFirstNode(bnode), key);
    00584
    00585   if (strcmp(key, bnode->keys[0]) < 0) {
    00586     return treeSearch(bnode->head[0].bPtr, key);
    00587   } // if
    00588
    00589   if (strcmp(key, bnode->keys[bnode->used-1]) >= 0) {
    00590     return treeSearch(bnode->head[bnode->used].bPtr, key);
    00591   } // if
    00592
    00593   for (unsigned int i = 1; i < bnode->used; i++) {
    00594     if (strcmp(key, bnode->keys[i]) < 0) {
    00595       return treeSearch(bnode->head[i].bPtr, key);
    00596     } // if
    00597   } // for i
    00598
    00599   return NULL;
    00600 } // bTree::treeSearch
    00601
    00602 ubixfsInode *
    00603 bTree::GetFirstNode(void) {
    00604   return GetFirstNode(root);
    00605 } // bTree::GetFirstNode
    00606
    00607 ubixfsInode *
    00608 bTree::GetFirstNode(bNode * node) {
    00609   bNode * tmpNode = node;
    00610
    00611   if (tmpNode == NULL) return NULL;
    00612
    00613   while (!tmpNode->leaf) {
    00614     for (unsigned int i = 0; i < tmpNode->used; i++) {
    00615       if (tmpNode->head[i].bPtr != NULL) {
    00616         tmpNode = tmpNode->head[i].bPtr;
    00617         break;
    00618       }  // if
    00619     } // for i
    00620   } // while
    00621
    00622   for (unsigned int i = 0; i < tmpNode->used; i++) {
    00623     if (tmpNode->head[i].iPtr != NULL) return tmpNode->head[i].iPtr;
    00624   } // for i
    00625   return NULL;
    00626 } // bTree::GetFirstNode
    00627
    00628 bNode *
    00629 bTree::findLeafNode(bNode * node, const char * key) {
    00630   assert(node);
    00631   assert(key);
    00632   if (node == NULL || key == NULL) return NULL;
    00633   assert(node->used);
    00634   if (node->leaf) return node;
    00635
    00636   if (strcmp(key, node->keys[0]) < 0)
    00637     return findLeafNode(node->head[0].bPtr, key);
    00638
    00639   if (strcmp(key, node->keys[node->used-1]) >= 0)
    00640     return findLeafNode(node->head[node->used].bPtr, key);
    00641
    00642   for (unsigned int i = 1; i < node->used; i++) {
    00643     if (strcmp(key, node->keys[i]) < 0)
    00644       return findLeafNode(node->head[i].bPtr, key);
    00645   } // for i
    00646
    00647   return NULL;
    00648 } // bTree::findLeafNode
    00649
    00650 void
    00651 bTree::saveNode(FILE * fd, bNode * node, void * tmpPtr) {
    00652
    00653   bNode * ptr = (bNode *)tmpPtr;
    00654   assert(tmpPtr);
    00655   assert(fd);
    00656   assert(node);
    00657   cout << "writing tag: " << node->tag << endl;
    00658
    00659   memcpy(tmpPtr, node, sizeof(bNode));
    00660
    00661   if (node->parent.bPtr != NULL)
    00662     ptr->parent.offset = node->parent.bPtr->tag * sizeof(bNode);
    00663   else
    00664     ptr->parent.offset = 0;
    00665
    00666   for (unsigned int i = 0; i <= node->used; i++) {
    00667     bNode * bPtr = node->head[i].bPtr;
    00668
    00669     if (bPtr != NULL)
    00670       ptr->head[i].offset = bPtr->tag * sizeof(bNode);
    00671     else
    00672       ptr->head[i].offset = ~0;
    00673     ptr->present[i] = false;
    00674   } // for i
    00675
    00676   if (node->leaf) {
    00677
    00678     for (unsigned int i = 0; i <= node->used; i++) {
    00679   //    ubixfsInode * inode = node->head[i].iPtr;
    00680   // mji    if (inode != NULL) tmp->head[i] = inode->
    00681     } // for i
    00682   } else {
    00683
    00684     for (unsigned int i = 0; i <= node->used; i++) {
    00685
    00686       if (node->head[i].bPtr != NULL) saveNode(fd, node->head[i].bPtr, tmpPtr);
    00687
    00688     } // for i
    00689
    00690   } // else
    00691
    00692   return;
    00693 } // bTree::saveNode
    00694
    00695 bool
    00696 bTree::Save(const char * filename) {
    00697   ubixfsInode * uPtr = NULL;
    00698   if (filename == NULL) return false;
    00699   FILE * fd = NULL;
    00700   if ((fd = fopen(filename, "wb+")) == NULL) return false;
    00701
    00702 cout << "tags: " << tag << endl;
    00703   lseek(fileno(fd), tag * sizeof(bNode), SEEK_END);
    00704
    00705   header->firstNodeOffset = sizeof(bNode);
    00706   header->firstDeleted = -1;
    00707   void * tmpPtr = malloc(sizeof(bNode));
    00708   assert(tmpPtr);
    00709   uPtr = (ubixfsInode *)tmpPtr;
    00710   memset(tmpPtr, 0, sizeof(bNode));
    00711   fwrite(header, sizeof(bTreeHeader), 1, fd);
    00712   saveNode(fd, root, tmpPtr);
    00713
    00714   fclose(fd);
    00715   free(tmpPtr);
    00716   return true;
    00717 } // bTree::Save
    00718
    00719 bool
    00720 bTree::Load(const char * filename) {
    00721   if (filename == NULL) return false;
    00722   return true;
    00723 } // bTree::Load
    00724
    00725 bool
    00726 bTree::Delete(const char * key) {
    00727
    00728   if (key == NULL) return false;
    00729   return true;
    00730 } // bTree::Delete
    00731
    00732 bool
    00733 bTree::Verify(void) {
    00734   ubixfsInode * node = GetFirstNode();
    00735   if (node == NULL) return true;
    00736
    00737   while (node != NULL) {
    00738     ubixfsInode * next = node->next.iPtr;
    00739     if (next != NULL) {
    00740   //  cout << node->name << "::" << node->next->name << ":::" << strcmp(node->name, node->next->name) << endl;
    00741       if (strcmp(node->name, next->name) > 0) return false;
    00742     }
    00743     node = next;
    00744   } // while
    00745   return true;
    00746 } // bTree::Verify
    00747
    00748 void
    00749 bTree::Print(bNode * node) {
    00750   if (node == NULL) return;
    00751   Info(node);
    00752   if (!node->leaf)
    00753     for (unsigned int i = 0; i <= node->used; i++) {
    00754       Print(node->head[i].bPtr);
    00755     } // for i
    00756 } // bTree::Print
    00757
    00758 void
    00759 bTree::PrintWholeTree(void) {
    00760   Print(root);
    00761 } // bTree::PrintWholeTree;
    00762
    00763 bTree::~bTree(void) {
    00764   cout << "tree depth: " << header->treeDepth << endl;
    00765   cout << "tree width: " << header->treeWidth << endl;
    00766   cout << "tree leaf count: " << header->treeLeafCount << endl;
    00767 } // bTree::~bTree