home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / db02_src.zip / btree.cc < prev    next >
C/C++ Source or Header  |  1993-11-05  |  33KB  |  1,260 lines
  1. /**************************************************************************
  2.  * Source Id :
  3.  *
  4.  * $Id: btree.cc,v 1.38 1993/06/23 05:21:22 kevinl Exp $
  5.  *-------------------------------------------------------------------------
  6.  * Project Notes :
  7.  *
  8.  *  Diamond Base
  9.  *  ============
  10.  *      A solid database implementation, spurred on by the continuing
  11.  *  Metal (Lead) Base saga.
  12.  *
  13.  *  Project Team :
  14.  *        A. Davison
  15.  *        K. Lentin
  16.  *        D. Platt
  17.  *
  18.  *    Project Commenced : 05-02-1993
  19.  *
  20.  *-------------------------------------------------------------------------
  21.  *  Module Notes :
  22.  *
  23.  *  The main B-Tree implemetation
  24.  *
  25.  *
  26.  *  Original Author : Daz & Kev
  27.  *
  28.  *-------------------------------------------------------------------------
  29.  * Revision History:
  30.  *
  31.  * $Log: btree.cc,v $
  32. // Revision 1.38  1993/06/23  05:21:22  kevinl
  33. // Mallocs are now in angular brackets
  34. //
  35. // Revision 1.37  1993/06/20  13:43:05  kevinl
  36. // Fixed multiple mallocs
  37. //
  38. // Revision 1.36  1993/05/26  01:01:39  kevinl
  39. // MALLOC_H_MISSING
  40. //
  41. // Revision 1.35  1993/05/11  14:44:50  kevinl
  42. // Added version number output
  43. //
  44. // Revision 1.34  1993/05/06  04:00:19  kevinl
  45. // SASC define for malloc.h
  46. //
  47. // Revision 1.33  1993/05/03  01:33:03  kevinl
  48. // Cosmetic (mainly) changes for CC
  49. //
  50. // Revision 1.32  1993/05/01  14:27:42  kevinl
  51. // Got rid of ints
  52. //
  53. // Revision 1.31  1993/04/30  04:07:28  kevinl
  54. // Incorrect !used queries
  55. //
  56. // Revision 1.30  1993/04/29  15:10:01  kevinl
  57. // Fixed the BIG BUG. idx = 1 was all that was needed!
  58. //
  59. // Revision 1.29  1993/04/29  12:55:16  kevinl
  60. // Fixed up setting of query[]->key
  61. //
  62. // Revision 1.28  1993/04/29  07:00:03  kevinl
  63. // Added lsoeBucket
  64. //
  65. // Revision 1.27  1993/04/28  14:29:31  kevinl
  66. // inBTree returning incorrect idx
  67. //
  68. // Revision 1.26  1993/04/28  10:36:47  kevinl
  69. // qPeekNext, qPeekPrev not expecting eof from bTree
  70. //
  71. // Revision 1.25  1993/04/27  07:02:47  kevinl
  72. // Next and PeekNext return codes were broken
  73. //
  74. // Revision 1.24  1993/04/24  14:31:27  kevinl
  75. // Comments
  76. // Some small fixups and error code changes.
  77. //
  78. // Revision 1.23  1993/04/19  15:50:29  kevinl
  79. // fixParent is now an int.
  80. // Convert root node to LEAF when it becomes empty/
  81. //
  82. // Revision 1.22  1993/04/15  07:56:13  kevinl
  83. // Traverse & dump have intonly mode
  84. // inBTree takes optional reference to return spot where found
  85. // Added del
  86. //
  87. // Revision 1.21  1993/04/11  10:24:56  kevinl
  88. // Fixed up jumping from bucket to bucket in a find
  89. //
  90. // Revision 1.20  1993/04/08  15:39:38  kevinl
  91. // put some output into DEBUG blocks
  92. //
  93. // Revision 1.19  1993/04/08  07:23:40  kevinl
  94. // insertInternal now takes refernce to bucket* so delete on outside works
  95. //
  96. // Revision 1.18  1993/04/08  06:41:14  kevinl
  97. // Memory leak related to findInternal()
  98. //
  99. // Revision 1.17  1993/04/06  05:47:26  kevinl
  100. // Moved key reinstatement down
  101. //
  102. // Revision 1.16  1993/04/05  07:50:08  kevinl
  103. // Fixed the rereading in add
  104. //
  105. // Revision 1.15  1993/04/05  01:13:11  kevinl
  106. // Fixed incorrect idx entries from searchForKey
  107. // Made traverse/dump more friendly
  108. // made fixparent a little less disk intensive
  109. //
  110. // Revision 1.14  1993/03/29  08:18:39  darrenp
  111. // Added query bptr validity check
  112. // malloc lib
  113. //
  114. // Revision 1.13  1993/03/28  13:58:23  kevinl
  115. // Added inBTree
  116. //
  117. // Revision 1.12  1993/03/28  10:37:11  kevinl
  118. // Modified for dbErr
  119. //
  120. // Revision 1.11  1993/03/28  19:06:27  davison
  121. // Changed references to pError to dbErr().
  122. //
  123. // Revision 1.10  1993/03/26  06:15:57  darrenp
  124. // standardised error codes.
  125. //
  126. // Revision 1.9  1993/03/24  06:15:58  kevinl
  127. // Added pError and bterror members
  128. //
  129. // Revision 1.8  1993/03/21  00:47:49  davison
  130. // Included <stdio.h> to fix pError error.
  131. //
  132. // Revision 1.7  1993/03/20  14:08:45  kevinl
  133. // Fixed up call to recServer constructor
  134. // Check return code of recServer constructor
  135. //
  136. // Revision 1.6  1993/03/17  14:27:00  kevinl
  137. // Added indNum to bucket creation calls
  138. //
  139. // Revision 1.5  1993/03/15  13:59:46  kevinl
  140. // Added parent pointer fixup
  141. // Added integrity check
  142. // Finished query members
  143. //
  144. // Revision 1.4  1993/03/08  00:29:32  kevinl
  145. // Added multiple index handling
  146. // Added (and ifdef'ed out) query handling - partial
  147. // Added integrity check for next/prev links
  148. //
  149. // Revision 1.3  1993/02/17  12:14:29  darrenp
  150. // Insert, find and search work correctly
  151. // still minor bug in insert routine to be found
  152. //
  153. // Revision 1.2  1993/02/13  00:53:01  kevinl
  154. // fixed insertInternal to point where it compiles
  155. // added supporting functions: writeBucket, createNewBucket
  156. //
  157.  **************************************************************************/
  158.  
  159. #include <stdlib.h>
  160. #include <stdio.h>
  161.  
  162. #if !defined(MALLOC_H_MISSING) && !defined(MALLOC_H_INCLUDED)
  163. extern "C" {
  164. #include <malloc.h>
  165. }
  166. #define MALLOC_H_INCLUDED
  167. #endif
  168. #include <iostream.h>
  169. #include <btree.h>
  170.  
  171. extern "C" {
  172. int isprint(char);
  173. }
  174.  
  175. char* bTree::verStr(void)
  176. {
  177.     return "$Id: btree.cc,v 1.38 1993/06/23 05:21:22 kevinl Exp $";
  178. }
  179.  
  180. // The create constructor. This creates a new empty recServer correctly set
  181. // up for the bTree.
  182.  
  183. bTree::bTree(char *name, long bucketSize, long keyLen, long newIndNum) : recServer()
  184. {
  185.     bucketId idx;
  186.     
  187.     initQueries();
  188.  
  189.     // This is the index number that this bTree is being used for.
  190.     // It is passed to all object member functions.
  191.  
  192.     indNum = newIndNum;
  193.  
  194.     if (createDb(name, bucketSize, sizeof(bTreeHead)) != db_ok)
  195.     {
  196.         // Oops. recServer failed. Die very ungracefully
  197.         dbErr(name);
  198.         exit (1);
  199.     }
  200.  
  201.     // Find a place for the root bucket
  202.  
  203.     if (newRec(idx) != db_ok)
  204.     {
  205.         dbErr("newRec");
  206.         exit (1);
  207.     }
  208.  
  209.  
  210.     // This is a bit presumptuous, but it sort of ensures that an empty
  211.     // recServer has being correctly created.
  212.  
  213.     if (idx)
  214.     {
  215.         cerr << "First record of created db should be 0 - " << idx << " instead" << endl;
  216.         exit (1);
  217.     }
  218.  
  219.     head.rootBucket = idx;
  220.     head.keyLen = keyLen;
  221.  
  222.     // Create the root bucket. It is a LEAF bucket with no siblings or parent
  223.  
  224.     bucket b(idx, keyLen, bucketSize, LEAF, -1L, -1L, -1L, indNum);
  225.  
  226.     // Write out the header data.
  227.  
  228.     if (!writeData(0, (void *)&head, sizeof(bTreeHead)))
  229.     {
  230.         dbErr("Write bTreeHead");
  231.         exit (1);
  232.     }
  233.  
  234.     // Now write out the root bucket.
  235.  
  236.     if (putRec(idx, b.getData()) != db_ok)
  237.     {
  238.         cerr << "Record " << idx;
  239.         dbErr("");
  240.         exit (1);
  241.     }
  242. }
  243.  
  244. // fetchBucket:
  245. // Create a new bucket and load the requested entry from the recServer.
  246. // It is the responsibility of the calling function to deallocate the memory.
  247. // The LEAF status, sibling and parent info are all overwritten by the
  248. // recServer read.
  249.  
  250. bucket*
  251. bTree::fetchBucket(bucketId idx)
  252. {    
  253.     bucket *buck = new bucket(idx, head.keyLen, header.recLength, LEAF, 0, 0, 0, indNum);
  254.     getRec(idx, buck->getData());
  255.     return buck;
  256. }
  257.  
  258. // The load constructor. This is for instantiating an existing bTree and
  259. // load it into the recServer. The recServer is told of the amount of user
  260. // data that is present. All other data, besides the index number are stored
  261. // in the recServer.
  262.  
  263. bTree::bTree(char *name, long newIndNum) : recServer(name, sizeof(bTreeHead))
  264. {
  265.     if (!isOpen)
  266.     {    
  267.         dbErr("bTree: recServer constructor failed");
  268.         exit (1);
  269.     }
  270.  
  271.     // Zero out the query array and store the index number
  272.  
  273.     initQueries();
  274.     indNum = newIndNum;
  275.  
  276.     // Get the header data from the recServer.
  277.  
  278.     if (!readData(0, &head, sizeof(bTreeHead)))
  279.     {
  280.         dbErr("read bTreeHead");
  281.         exit (1);
  282.     }
  283. }
  284.  
  285. //
  286. // The internal find routine, as so accurately predicated by Kevin Lentin.
  287. //
  288. // (Thanks for the credit Daz :-)
  289. // findInternal starts with the root bucket and continually searches for
  290. // the requested object, loading the found (or following) bucket until a leaf
  291. // node is found. It then returns if and where it found (or did not find) the
  292. // requested key.
  293. // bptr is a bucket** because findInternal actually returns to the caller
  294. // the bucket where the object was found. findInternal frees any existing
  295. // bucket and ensures all internally used buckets are freed, thus bptr is the
  296. // only unfree bucket lieing around.
  297. // 
  298.  
  299. void bTree::findInternal(
  300.     object&        searchObject,    // What we're looking for
  301.     bucketId     rootBucket,        // Where to start
  302.     bool&        Found,            // Did we find it?
  303.     bucket**    bptr,            // The bucket to search for.
  304.     long&        ptrIdx,
  305.     int            fixParent
  306. )
  307. {
  308.  
  309.     // We start at the very beginning...
  310.  
  311.     bucketId     nextBucket = rootBucket;
  312.     bucketId    parent = -1;
  313.  
  314.     do {
  315.         long found;
  316.         
  317.         // Get the next bucket, deleting the old one if appropriate
  318.  
  319.         if (*bptr) delete (*bptr);
  320.         *bptr = fetchBucket(nextBucket);
  321.  
  322.         // The parent pointer can be corrupted during the sploosh process
  323.         // because the bucket is split in half and it is wastefull to go down
  324.         // and change all buckets under the new node.
  325.         // Hence, if, while searching, we find a full bucket and are part
  326.         // of an add (fixParent == 1), we ensure the parent is correct so that
  327.         // the possibly impending sploosh will be able to traverse up the tree
  328.         // correctly.
  329.         // If we are doing a delete and the bucket is about to become
  330.         // empty, we similarly fix the parent pointer.
  331.         // To save time, we only do this if the parent is wrong.
  332.  
  333.         if    ((        (fixParent==1 && (*bptr)->full())
  334.                 ||    (fixParent==2 && (*bptr)->header()->activeKeys==1))
  335.             && (*bptr)->getParent() != parent) 
  336.         {
  337.             (*bptr)->setParent(parent);
  338. #ifdef DEBUG
  339.             cout << "Fixing parent pointer" << endl;
  340. #endif
  341.             writeBucket(*bptr);
  342.         }
  343.  
  344.         found = (*bptr)->searchForKey(searchObject,ptrIdx);
  345.         // This returns the ptrIdx of the ptr after the key (if found)
  346.         // or the ptr to follow if it wasn't found. If you're in an internal
  347.         // node, then you probably want to follow the following pointer
  348.         if (found) {
  349.             // We got one!
  350.             if ((*bptr)->header()->leaf == LEAF) {
  351.                 // We have found the record in a leaf, so this is
  352.                 // the real thing.
  353.                 Found = true; 
  354.                 return;
  355.             } else {
  356.                 // Found the record in an internal node, so it's just a
  357.                 // guide index, follow the pointer next to it.
  358.                 parent = nextBucket;// Store the current bucket as the
  359.                                     // parent of the next one
  360.                 nextBucket = (*bptr)->getLink(ptrIdx);
  361.             }
  362.         } else { // Not found
  363.             if ((*bptr)->header()->leaf == LEAF) {
  364.                 // End of the road - report not found.
  365.                 Found = false;
  366.                 return;
  367.             }
  368.             // ok, we didn't find it in this internal node, but
  369.             // we have the ptrIdx for the bucket pointer we should
  370.             // follow.
  371.             parent = nextBucket;
  372.             nextBucket = (*bptr)->getLink(ptrIdx);
  373.         }
  374.     } while(1); // Return is through the found and not found states above
  375. }
  376.  
  377. // del:
  378. // Finally, we have a delete. We start by searching down the tree for the
  379. // object. If it is not there we return an error, otherwise we remove it
  380. // from the bucket. If the bucket is empty, we delete the bucket from the
  381. // recServer, patch up the neighbouring previous and next pointers and then we
  382. // we load up the parent bucket and search for the pointer to the current
  383. // bucket. If this is not found, this is a serious error. We continue up the
  384. // tree in the way till a non-empty bucket is found or we reach the root.
  385.  
  386. dbError
  387. bTree::del(object& theObject)
  388. {
  389.  
  390.     bucket *bptr = 0;
  391.     dbError err;
  392.     bool found;
  393.     long ptrIdx;
  394.     bool first = true;
  395.  
  396.     while (1)
  397.     {
  398.         // Let's find the record or bucket
  399.         // If this is the first time around, we look for the record...
  400.         if (first)
  401.             findInternal(theObject, head.rootBucket, found, &bptr, ptrIdx, 2);
  402.         else
  403.             // Otherwise we search for the bucket we just deleted
  404.             //
  405.             // findIndex replaces ptrIdx with the position where ptrIdx was
  406.             // found. This is ok, since we are finished with ptrIdx once
  407.             // it is found.
  408.             bptr->findIndex(ptrIdx, found);
  409.         
  410.         // Not there. BANG!
  411.  
  412.         if (!found)
  413.         {
  414.             delete bptr; // Make sure we take care of our memory.
  415.  
  416.             // If this is the first time around, the object was not found,
  417.             // otherwise there was a serious structural error in the bTree.
  418.  
  419.             return dbErr(first?db_nfound:db_err);
  420.         }
  421.  
  422.         // We got one!! Tell the bucket to nuke the entry
  423.         // If there's anything left in the bucket, save it and all is well
  424.  
  425.         bptr->del(ptrIdx);
  426.         if (!bptr->empty())
  427.         {
  428.             writeBucket(bptr);
  429.             delete bptr; // Take care of our buckets
  430.             return dbErr(db_ok);
  431.         }
  432.  
  433.         // We have to delete the current bucket that is in bptr
  434.         // Find out who it is ...
  435.  
  436.         ptrIdx = bptr->getId(); // This is the bucket to delete.
  437.  
  438.         // If this is the root bucket, leave it there empty
  439.  
  440.         if (ptrIdx == head.rootBucket)
  441.         {
  442.             // If the root bucket is empty and an INNER node, make it a LEAF
  443.             if (bptr->header()->leaf==INNER)
  444.             {
  445.                 bptr->setActiveKeys(0);
  446.                 bptr->header()->leaf=LEAF;
  447.             }
  448.             writeBucket(bptr);
  449.             delete bptr;
  450.             return dbErr(db_ok);
  451.         }
  452.  
  453.         // First fix up the next and prev pointers in the adjoining buckets
  454.  
  455.         if (bptr->header()->nextBucket != -1)
  456.         {
  457.             // There is a next bucket so fix it up
  458.  
  459.             bucket* b = fetchBucket(bptr->header()->nextBucket);
  460.             b->header()->prevBucket = bptr->header()->prevBucket;
  461.             writeBucket(b);
  462.             delete b;
  463.         }
  464.         if (bptr->header()->prevBucket != -1)
  465.         {
  466.             // There is a prev bucket so fix it up
  467.  
  468.             bucket* b = fetchBucket(bptr->header()->prevBucket);
  469.             b->header()->nextBucket = bptr->header()->nextBucket;
  470.             writeBucket(b);
  471.             delete b;
  472.         }
  473.  
  474.         // Take the bucket out of the recServer
  475.  
  476.         if ((err = delRec(ptrIdx)) != db_ok)
  477.             return dbErr(err);
  478.         loseBucket(ptrIdx);
  479.  
  480.         // Now it's time to move up the tree and delete this entry
  481.  
  482.         first = false;
  483.  
  484.         // The next bucket is the parent of this one
  485.         // Out of that we will delete the record pointing to ptrIdx
  486.  
  487.         // Need a temporary spot to remember what is next
  488.         bucketId next = bptr->header()->parentId;
  489.  
  490.         // Nuke the current bucket and get the next one.
  491.         delete bptr;
  492.         bptr = fetchBucket(next);
  493.     }
  494.     
  495.     // Never executed. Just here to make the compiler happy.
  496. #ifndef __CC
  497.     return dbErr(db_err);
  498. #endif
  499.  
  500. }
  501.  
  502. // add:
  503. // Add first checks that the key does not already exist in the btree. If it
  504. // does it errors. Otherwise we call the internal insert routine.
  505.  
  506. dbError
  507. bTree::add(object& newObject, long extPtr)
  508. {
  509.     bucket *bptr = 0;
  510.     dbError err;
  511.     bool found;
  512.     long ptrIdx;
  513.  
  514.     findInternal(newObject,head.rootBucket,found,&bptr,ptrIdx,1);
  515.  
  516.     if (found) 
  517.     {
  518.         err = db_dup;
  519.     }
  520.     else
  521.     {
  522.         // Not found, so we now have a pointer to the bucket involved, and
  523.         // know the pointer position just before the insertion point.
  524.         err = insertInternal(bptr, newObject, extPtr);
  525.     }
  526.  
  527.     // Clean up and return the appropriate error code.
  528.     delete bptr;
  529.     return dbErr(err);
  530. }
  531.  
  532. #if 0
  533. void swapKeyPtr(pKeyType a,pKeyType b)
  534. {
  535.     pKeyType t = a;
  536.     a = b;
  537.     b = t;
  538. }
  539. #endif
  540.  
  541. // insertInternal:
  542. // This function has the solemn duty of inserting the actual
  543. // index/pointer pair into the bucket. If the bucket is going to
  544. // overflow, then a new bucket has to be created - and the contents
  545. // split etc.
  546. // extPtr holds the pointer half of the pair, and the indexing
  547. // info can come out of the object itself.
  548.  
  549. dbError
  550. bTree::insertInternal(bucket*& bptr,object &newObject,long extPtr)
  551. {
  552.     // This will be used below to hold temporary keys en route
  553.     // between buckets.
  554.     // NB we are responsible for the temporary key in outKey
  555.  
  556.     pKeyType outKey = bptr->allocTmpKey();
  557.  
  558.     // NB The contents of the key of newObject may be modified by this
  559.     // function. So we take a copy of it here to restore later.
  560.  
  561.     pKeyType inKey = newObject.getKey(indNum);
  562.  
  563.     // Is the bucket too full to accomodate one more entry ?
  564.     while (bptr->full())
  565.     {
  566.         // Overfull bucket - create a new bucket, split contents
  567.         // between the two buckets, then migrate the median
  568.         // object and the pointer to the NEW bucket (which contains the
  569.         // bigger half of the values, up into the parent.
  570.  
  571. #ifdef DEBUG
  572.         cout << "Splitting ..." << endl;
  573. #endif
  574.  
  575.         // Make new bucket. It has the same parent and next as the current
  576.         // bucket and the current bucket will be its prevBucket.
  577.  
  578.         headerData *h = bptr->header();
  579.         bucket *newBucket = createNewBucket(h->leaf, h->parentId, h->nextBucket, bptr->id);
  580.         if (!newBucket) return dbErr(db_nobuckets);
  581.  
  582.         // The current bucket's nextBucket is now the new bucket
  583.         h->nextBucket = newBucket->id;
  584.  
  585.         // We need to move half of the elements (the bigger half)
  586.         // across into the new bucket, chuck in the new object, and retrieve
  587.         // an object which has both the bucket pointer and key value, for
  588.         // passing to our superior.
  589.  
  590.         bptr->sploosh(newBucket,0,outKey,newObject,extPtr);
  591.  
  592.         // sploosh has told us what new key and id to promote up the tree.
  593.         // We therefore set a new extPtr and modify the object's key.
  594.         // NB This destroys the key section of the original object. It is
  595.         // restored just before exiting this funciton below.
  596.  
  597.         extPtr = newBucket->id;
  598.         newObject.setKey(outKey, indNum);
  599.  
  600.         // Finally, head up to the parent bucket. If we are at the root,
  601.         // create a new root node above it.
  602.  
  603.         if (bptr->id == head.rootBucket) {
  604.             // Hmm, we've hit the ceiling, make a new bucket
  605.             bucket* rootBptr = createNewBucket(INNER, -1L, -1L, -1L);
  606.             if (!rootBptr) return dbErr(db_nobuckets);
  607.  
  608.             // This is the parent of the old and new buckets
  609.             bptr->header()->parentId = newBucket->header()->parentId = rootBptr->id;
  610.  
  611.             // Set the less than all link to the old root (bptr)
  612.             rootBptr->setLink(0, bptr->id);
  613.             head.rootBucket = rootBptr->id; // update root node.
  614.             writeBucket(bptr);
  615.             delete bptr; // We're finished with the current bucket now
  616.  
  617.             bptr = rootBptr; // We're now dealing with the root
  618.             if (!writeData(0, (void *)&head, sizeof(bTreeHead)))
  619.                 // This is actually quite fatal!
  620.                 return dbErr(db_err);
  621.  
  622.         } else {
  623.             // worry about the deletion of memory later - I don't
  624.             // think fetchBucket should expect the memory to be
  625.             // deallocated.
  626.             // Kev: Actually fetchBucket's users are expected to delete
  627.             // their returned buckets.
  628.  
  629.             // Move up 
  630.             bucketId parent = bptr->header()->parentId;
  631.             writeBucket(bptr);
  632.             delete bptr;
  633.             bptr = fetchBucket(parent);
  634.  
  635.             // We also need to examine the next bucket in the chain and
  636.             // update its predecessor bucket. (if necessary)
  637.  
  638.             if (newBucket->header()->nextBucket != -1)
  639.             {
  640.                 bucket *tmpBptr;
  641.  
  642.                 // ***** Have to do something about repsonsibilty for mem allocation
  643.                 // Yeah, we are responsible.
  644.  
  645.                 tmpBptr = fetchBucket(newBucket->header()->nextBucket);
  646.                 tmpBptr->header()->prevBucket = newBucket->id;
  647.                 writeBucket(tmpBptr);
  648.                 delete tmpBptr;
  649.             }
  650.         }
  651.         // Make sure the newly created bucket is tucked away and deleted.
  652.         writeBucket(newBucket);
  653.         delete newBucket;
  654.     };
  655.  
  656.     delete outKey; // Get rid of the temporary storage
  657.  
  658.     // Yay - something easy at last - inserting a key/pointer pair
  659.     // which doesn't overflow a bucket.
  660.  
  661.     // Shove it into the bucket, giving the bucket a hint as to
  662.     // where it will go.
  663.  
  664.     bptr->insert(newObject, extPtr);
  665.  
  666.     // Ok, put the key back, in case it was nuked.
  667.     newObject.setKey(inKey, indNum);
  668.     delete inKey; // Because getKey returns our own private copy
  669.     
  670.     // Write out the bucket. Note that we return the bucket intact, and do
  671.     // not delete it.
  672.     writeBucket(bptr);
  673.     return dbErr(db_ok);
  674. }
  675.  
  676. // createNewBucket:
  677. // Open up a new record in the recServer and create a new bucket
  678. // We don't actually put anything in the bucket or save it to the
  679. // recServer.
  680.  
  681. bucket*
  682. bTree::createNewBucket(e_leaf leaf, bucketId parentId, bucketId nextBucket, bucketId prevBucket)
  683. {
  684.     bucket*        b;
  685.     bucketId    idx;
  686.  
  687.     // Create the record
  688.     newRec(idx);
  689.  
  690.     // Create the bucket and return it.
  691.     b = new bucket(idx, head.keyLen, header.recLength, leaf, parentId, nextBucket, prevBucket, indNum);
  692.     return b;
  693. }
  694.  
  695. // Because this bucket has been modified, we check for all used
  696. // queries that are using this bucket and, if so, we set them as
  697. // unsafe.
  698.  
  699. void
  700. bTree::loseBucket(bucketId id)
  701. {
  702.     for (long i=0; i < MAX_QUERY; i++)
  703.         if (query[i].used)
  704.             if (query[i].bptr && query[i].bptr->id == id)
  705.                 query[i].unsafe = true;
  706. }
  707.  
  708. // Write out a bucket.
  709.  
  710. void
  711. bTree::writeBucket(bucket* bptr)
  712. {
  713.     if (putRec(bptr->id, bptr->getData()) != db_ok)
  714.     {
  715.         cerr << "writeBucket: " << bptr->id; 
  716.         dbErr("");
  717.         exit (1);
  718.     }
  719.     
  720.     loseBucket(bptr->id);
  721. }
  722.  
  723. void
  724. bTree::dump(bool intonly)
  725. {
  726.     // Do an inorder traversal of the btree.
  727.     bucket *b;
  728.  
  729.     b = fetchBucket(head.rootBucket);
  730.     traverse(b, intonly);
  731.     delete b;
  732. }
  733.  
  734. // Dump out the whole bucket.
  735.  
  736. void
  737. bTree::traverse(bucket* b, bool intonly)
  738. {    
  739.     headerData *h = b->header();
  740.     cout << "Bucket id: " << b->id << "   " << ((h->leaf)?"LEAF":"INNER")
  741.          << "     " << h->activeKeys << " active keys,  parent = " << h->parentId << endl;
  742.     b->info();
  743.     for (long i=((h->leaf==INNER)?0:1); i<=h->activeKeys; i++)
  744.     {
  745.         if (h->leaf==INNER) cout << "Bucket id: " << b->id;
  746.         if (i)
  747.         {
  748.             unsigned char* c = (unsigned char*)b->getKeyAddr(i);
  749.             bool lastchar = true;
  750.             cout << "  Key: " << hex;
  751.             for (long j=0; j < b->keyLength; j++)
  752.  
  753.             // If intonly is set then all elements are printed as hex
  754.             // integers, otherwise printable characters are printed out.
  755.                 if (!intonly && isprint(c[j]))
  756.                 {
  757.                     if (!lastchar)
  758.                     {
  759.                         lastchar = true;
  760.                         cout << ",";
  761.                     }
  762.                     cout << c[j];
  763.                 }
  764.                 else
  765.                 {
  766.                     if (j) cout << ",";
  767.                     cout << c[j] / 16 << c[j] % 16;
  768.                     lastchar = false;
  769.                 }
  770.             cout << dec;
  771. //            long l;
  772. //            bcopy(b->getKeyAddr(i), &l, sizeof(long));
  773. //            cout << "  Key: " << hex << l << dec;
  774.         }
  775.         if (h->leaf == INNER)
  776.         {
  777.             cout << "  Link: " << b->getLink(i) << endl;
  778.             bucket *next = fetchBucket(b->getLink(i));
  779.             traverse(next, intonly);
  780.             delete next;
  781.         }
  782.         else
  783.             cout << endl;
  784.     }
  785. }
  786.  
  787. // Verify all the pointers and the structure of the bTree
  788.  
  789. bool
  790. bTree::checkIntegrity(void)
  791. {
  792.     return internalCheckIntegrity(head.rootBucket);
  793. }
  794.  
  795. bool
  796. bTree::internalCheckIntegrity(bucketId buck)
  797. {
  798.     bucket* b;
  799.     bool res = true;
  800.  
  801. #pragma warn -pia
  802.     if (!(b = fetchBucket(buck)))
  803. #pragma warn .pia
  804.     {
  805.         cerr << "checkIntegrity: Unable to fetch bucket number " << buck;
  806.         dbErr("");
  807.         return false;
  808.     }
  809.  
  810.     if (!b->header()->leaf)
  811.     {
  812.         for (long i=0; i<=b->header()->activeKeys; i++)
  813.         {
  814.             bucket* b1 = fetchBucket(b->getLink(i));
  815.             if (b1->getId() != b->getLink(i))
  816.             {
  817.                 cerr << "Bucket " << buck << "(" << i << ")=" << b->getLink(i) << " failed id check - returned " << b1->getId() << " instead" << endl;
  818.                 res = false;
  819.             }
  820.             if (i && b->getLink(i-1) != b1->header()->prevBucket)
  821.             {
  822.                 cerr << "Bucket id " << buck << " link " << i-1 << " does not equal bucket " << b1->getId() << " previous pointer" << endl;
  823.                 res = false;
  824.             }
  825.             if (i<b->header()->activeKeys && b->getLink(i+1) != b1->header()->nextBucket)
  826.             {
  827.                 cerr << "Bucket id " << buck << " link " << i+1 << " does not equal bucket " << b1->getId() << " next pointer" << endl;
  828.                 res = false;
  829.             }
  830.             if (!internalCheckIntegrity(b1->getId()))
  831.             {
  832.             //    delete b1;
  833.                 res = false;
  834.             }
  835.             delete b1;
  836.         }
  837.     }
  838.     delete b;
  839.     return res;
  840. }
  841.  
  842. // Initialise the query array.
  843.  
  844. void
  845. bTree::initQueries(void)
  846. {
  847.     for (long i=0; i<MAX_QUERY; query[i++].used = false);
  848. }
  849.  
  850. // Start a new query. This sets up an empty (unsafe) query
  851.  
  852. dbError
  853. bTree::qBegin(long& qNum)
  854. {
  855.     // Find an empty query.
  856.     for (long i=0; i < MAX_QUERY && query[i].used; i++);
  857.  
  858.     // None left, too bad.
  859.     if (i == MAX_QUERY)
  860.         return dbErr(db_toomany, "bTree queries");
  861.     else
  862.     {
  863.         qNum = i;
  864.         query[qNum].unsafe = true;
  865.         query[qNum].used = true;
  866.         query[qNum].bptr = 0;
  867.         query[qNum].key = 0;
  868.     }
  869.     return dbErr(db_ok);
  870. }
  871.  
  872. // End a query, freeing appropriate memory
  873.  
  874. dbError
  875. bTree::qEnd(long qNum)
  876. {
  877.     // Is this query number in range?
  878.     if (qNum < 0 || qNum >= MAX_QUERY)
  879.         return dbErr(db_range);
  880.  
  881.     // Is it currently active
  882.     else if (!query[qNum].used)
  883.         return dbErr(db_noquery);
  884.     else
  885.     {
  886.         if (query[qNum].bptr)
  887.             delete query[qNum].bptr; // Clean up the bucket
  888.         if (query[qNum].key)
  889.             delete query[qNum].key; // Clean up the key
  890.         query[qNum].used = false;    // We're done with it now
  891.         return dbErr(db_ok);
  892.     }
  893. }
  894.  
  895. // Is the object in the bTree?
  896. // Eventually, this should be clever enough to somehow remember the
  897. // position so that subsequent (inevitable) adds can save themselves a
  898. // (potentially expensive) findInternal call.
  899.  
  900. bool
  901. bTree::inBTree(object& theObject, long& idx)
  902. {
  903.     bool found;
  904.     bucket *bptr = 0;
  905.  
  906.     findInternal(theObject, head.rootBucket, found, &bptr, idx);
  907.     // Convert bucket link number to recServer record number
  908.     idx = bptr->getLink(idx);
  909.     delete bptr; // findInternal always gives back a bucket
  910.     return found;
  911. }
  912.  
  913. // qFind:
  914. // This does a find on the bTree base on the findObject and updates the
  915. // appropriate query entry.
  916.  
  917. dbError
  918. bTree::qFind(long qNum, object& findObject, long& extPtr)
  919. {
  920.     bool found;
  921.     long idx;
  922.  
  923.     // Sorry wrong one!
  924.     if (!query[qNum].used)
  925.         return dbErr(db_noquery);
  926.  
  927.     findInternal(findObject, head.rootBucket, found, &query[qNum].bptr, idx);
  928.  
  929.     // If it is not found then findInternal returns the position _AFTER_
  930.     // which it should go (for add purposes). In this case, we actually want
  931.     // to leave the query pointing to the record _after_ where it should go.
  932.     if (!found)
  933.         idx++;
  934.  
  935.     // Store the point in the bucket we are at and set the query as safe
  936.     // (we can use the data in the bucket).
  937.     query[qNum].idx = idx;
  938.     query[qNum].unsafe = false;
  939.  
  940.     // If the object was not found, then it is possible that we have now
  941.     // moved off the end of the bucket. If so we shouldmove to the next bucket
  942.     // (if there is one!)
  943.  
  944.     if (idx > query[qNum].bptr->header()->activeKeys)
  945.     {
  946.         bucketId next = query[qNum].bptr->header()->nextBucket;
  947.         if (next == -1) // There isn't a next one!
  948.             return dbErr(db_eof);
  949.  
  950.         // Get the new bucket
  951.         delete query[qNum].bptr;
  952.         query[qNum].bptr = fetchBucket(next);
  953.  
  954.         // And we're at the beginning of it.
  955.         query[qNum].idx = 1;
  956.         idx = 1;
  957.     }
  958.  
  959.     // idx shows where the entry is. Now get out the stored record number
  960.     extPtr = query[qNum].bptr->getLink(idx);
  961.  
  962.     // If we don't have a key, get space for one.
  963.     if (!query[qNum].key)
  964.         query[qNum].key = query[qNum].bptr->allocTmpKey();
  965.  
  966.     // Now copy the key out of the object to here. This key is stored
  967.     // so that when the query becomes unsafe, we can still do a search to
  968.     // carry on from where we left off. This ensures that if records get
  969.     // inserted around where we are, we always get current data.
  970.     bcopy(query[qNum].bptr->getKeyAddr(idx), query[qNum].key, query[qNum].bptr->keyLength);
  971.  
  972.     // And tell the world what happened.
  973.     return dbErr(found?db_ok:db_nfound);
  974. }
  975.  
  976. // qPeekNext:
  977. // This function returns the key that is next in the bTree index.
  978. // It makes use of the data stored in the query to speed up the lookup.
  979.  
  980. dbError
  981. bTree::qPeekNext(long qNum, object &theObject, long &extPtr)
  982. {
  983.     // This just makes the references to the query look shorter
  984.     bTreeQuery *q = &query[qNum];
  985.  
  986.     // Is it in use?
  987.     if (!q->used)
  988.         return dbErr(db_noquery);
  989.  
  990.     // If the query is unsafe or we don't have a bucket, we have to do a
  991.     // find
  992.     if (q->unsafe || !q->bptr)
  993.     {
  994.         dbError res;
  995.  
  996.         // If we have a key, we set it in the object and do a find
  997.         // If not, we take the first record.
  998.         // Either of these 2 will ensure we have a valid bptr and key in
  999.         // the query.
  1000.         if (q->key)
  1001.         {
  1002.             theObject.setKey(q->key, indNum);
  1003.  
  1004.             switch (res = qFind(qNum, theObject, extPtr))
  1005.             {
  1006.                 case db_nfound:
  1007.                 case db_ok:
  1008.                 case db_eof: // effectively a nfound when empty
  1009.                     break;
  1010.                 default:
  1011.                     cerr << "Time/space continuum anomoly calling find in qPeekNext - error code " << res << endl;
  1012.                     exit (1);
  1013.             }
  1014.         }
  1015.         else
  1016.             switch (res = qFirst(qNum, theObject, extPtr))
  1017.             {
  1018.                 case db_ok:
  1019.                 case db_eof:
  1020.                     break;
  1021.                 default:
  1022.                     cerr << "Time/space continuum anomoly calling first in qPeekNext - error code " << res << endl;
  1023.                     exit (1);
  1024.             }
  1025.             
  1026.     }
  1027.  
  1028.     // We're off the edge, go to the next bucket
  1029.     if (q->idx > q->bptr->header()->activeKeys)
  1030.     {
  1031.         bucketId next = q->bptr->header()->nextBucket;
  1032.         if (next == -1)
  1033.             return dbErr(db_eof);
  1034.         delete q->bptr;
  1035. #pragma warn -pia
  1036.         if (!(q->bptr = fetchBucket(next)))
  1037. #pragma warn .pia
  1038.             return dbErr(db_err, "qPeekNext: Unable to fetch bucket ");
  1039.         q->idx = 1;
  1040.         q->unsafe = false; // Now we're safe
  1041.     }
  1042.  
  1043.     // idx points to where in the bucket it is.
  1044.     // extract the external record pointer and the key for return.
  1045.  
  1046.     extPtr = q->bptr->getLink(q->idx);
  1047.     theObject.setKey(q->bptr->getKeyAddr(q->idx), indNum);
  1048.  
  1049.     // If we don't have a key, get space for one.
  1050.     if (!q->key)
  1051.         q->key = q->bptr->allocTmpKey();
  1052.  
  1053.     // Save the key
  1054.     bcopy(q->bptr->getKeyAddr(q->idx), q->key, q->bptr->keyLength);
  1055.  
  1056.     return dbErr(db_ok);
  1057. }
  1058.  
  1059. // qNext:
  1060. // Return the next entry in the bTree based solely on the query
  1061.  
  1062. dbError
  1063. bTree::qNext(long qNum, object& theObject, long& extPtr)
  1064. {
  1065.     // Use qPeekNext to check what the next record is. This returns with
  1066.     // the query safe, with a bucket and key (if not eof)
  1067.     // qPeekNext checks the validity of the query.
  1068.     dbError res = qPeekNext(qNum, theObject, extPtr);
  1069.  
  1070.     if (res != db_ok)
  1071.         return res;
  1072.  
  1073.     bTreeQuery* q = &query[qNum]; // It's easier to type
  1074.  
  1075.     // We have used PeekNext to find out what the next one is, now advance
  1076.     // the bTree.
  1077.     q->idx++;
  1078.  
  1079.     // We're off the end of the bucket, so go to the next one
  1080.     if (q->idx > q->bptr->header()->activeKeys)
  1081.     {
  1082.         bucketId next = q->bptr->header()->nextBucket;
  1083.         if (next == -1)
  1084.             return dbErr(db_ok);    // NB This is not an EOF condition
  1085.                                     // EOF has been reached but error is
  1086.                                     // on next call
  1087.         delete q->bptr;
  1088. #pragma warn -pia
  1089.         if (!(q->bptr = fetchBucket(next)))
  1090. #pragma warn .pia
  1091.             return dbErr(db_err, "qNext: Unable to fetch bucket ");
  1092.  
  1093.         q->idx = 1;
  1094.         q->unsafe = false;
  1095.     }
  1096.  
  1097.     return dbErr(db_ok);
  1098. }
  1099.  
  1100. // qFirst:
  1101. // This returns the first key in the bTree.
  1102. // NB This function acts like a Peek. The next call to PeekNext or Next
  1103. // will return the same thing. This behaviour can be (and in dbObj, is)
  1104. // overridden by simply calling next after first.
  1105.  
  1106. dbError
  1107. bTree::qFirst(long qNum, object& theObject, long& extPtr)
  1108. {
  1109.     // Is it in use?
  1110.     if (!query[qNum].used)
  1111.         return dbErr(db_noquery);
  1112.  
  1113.     // We start at the root
  1114.     bucket* b = fetchBucket(head.rootBucket);
  1115.  
  1116.     // Find the leftmost leaf
  1117.     while (b && !b->header()->leaf)
  1118.     {
  1119.         bucketId bid = b->getLink(0);
  1120.         delete b;
  1121.         b = fetchBucket(bid);
  1122.     }
  1123.  
  1124.     if (!b)
  1125.         return dbErr(db_err, "qFirst: fell off the beginning of the world");
  1126.  
  1127.     // Make the query point to what we've done
  1128.     query[qNum].unsafe = false;
  1129.     query[qNum].idx = 1;
  1130.     if (query[qNum].bptr)
  1131.         delete query[qNum].bptr;
  1132.     query[qNum].bptr = b;
  1133.  
  1134.     // This is a very convenient way to get a look at the next record and
  1135.     //return appropriate info. Since we have ensured that the query is safe,
  1136.     //most of the dirty work in qPeekNext will be skipped over but we will
  1137.     //get back a proper error code etc.
  1138.     return qPeekNext(qNum, theObject, extPtr);
  1139. }
  1140.  
  1141. // qLast is analogous to qFirst except almost everything is switched
  1142. // around.
  1143.  
  1144. dbError
  1145. bTree::qLast(long qNum, object& theObject, long& extPtr)
  1146. {
  1147.     // Is it in use?
  1148.     if (!query[qNum].used)
  1149.         return dbErr(db_noquery);
  1150.  
  1151.     bucket* b = fetchBucket(head.rootBucket);
  1152.  
  1153.     while (b && !b->header()->leaf)
  1154.     {
  1155.         bucketId bid = b->getLink(b->header()->activeKeys);
  1156.         delete b;
  1157.         b = fetchBucket(bid);
  1158.     }
  1159.  
  1160.     if (!b)
  1161.         return dbErr(db_err, "qLast: fell off the end of the world");
  1162.  
  1163.     query[qNum].unsafe = false;
  1164.     query[qNum].idx = b->header()->activeKeys + 1;
  1165.     if (query[qNum].bptr)
  1166.         delete query[qNum].bptr;
  1167.     query[qNum].bptr = b;
  1168.     return qPeekPrev(qNum, theObject, extPtr);
  1169. }
  1170.  
  1171. // qPeekPrev is analogous to qPeekNext but everything is turned around
  1172.  
  1173. dbError
  1174. bTree::qPeekPrev(long qNum, object &theObject, long &extPtr)
  1175. {
  1176.     bTreeQuery *q = &query[qNum];
  1177.     if (!q->used)
  1178.         return dbErr(db_noquery);
  1179.  
  1180.     if (q->unsafe || !q->bptr)
  1181.     {
  1182.         dbError res;
  1183.         if (q->key)
  1184.         {
  1185.             theObject.setKey(q->key, indNum);
  1186.  
  1187.             switch (res = qFind(qNum, theObject, extPtr))
  1188.             {
  1189.                 case db_nfound:
  1190.                 case db_ok:
  1191.                 case db_eof: // effectively a nfound when empty
  1192.                     break;
  1193.                 default:
  1194.                     cerr << "Time/space continuum anomoly calling find in qPeekPrev - error code " << res << endl;
  1195.                     exit (1);
  1196.             }
  1197.         }
  1198.         else
  1199.             qLast(qNum, theObject, extPtr);
  1200.     }
  1201.     if (q->idx <= 1)
  1202.     {
  1203.         bucketId prev = q->bptr->header()->prevBucket;
  1204.         if (prev == -1)
  1205.             return dbErr(db_eof);
  1206.         delete q->bptr;
  1207. #pragma warn -pia
  1208.         if (!(q->bptr = fetchBucket(prev)))
  1209. #pragma warn .pia
  1210.             return dbErr(db_err, "qPeekPrev: Unable to fetch bucket");
  1211.  
  1212.         q->idx = q->bptr->header()->activeKeys+1;
  1213.         q->unsafe = false;
  1214.     }
  1215.     extPtr = q->bptr->getLink(q->idx-1);
  1216.     theObject.setKey(q->bptr->getKeyAddr(q->idx-1), indNum);
  1217.  
  1218.     // If we don't have a key, get space for one.
  1219.     if (!q->key)
  1220.         q->key = q->bptr->allocTmpKey();
  1221.  
  1222.     // Save the key
  1223.     bcopy(q->bptr->getKeyAddr(q->idx-1), q->key, q->bptr->keyLength);
  1224.  
  1225.     return dbErr(db_ok);
  1226. }
  1227.  
  1228. // qPrev is like qNext, but oposite
  1229.  
  1230. dbError
  1231. bTree::qPrev(long qNum, object& theObject, long& extPtr)
  1232. {
  1233.     dbError res = qPeekPrev(qNum, theObject, extPtr);
  1234.  
  1235.     if (res == db_eof)
  1236.         return res;
  1237.  
  1238.     bTreeQuery* q = &query[qNum];
  1239.  
  1240.     q->idx--;
  1241.  
  1242.     if (q->idx <= 1)
  1243.     {
  1244.         bucketId prev = q->bptr->header()->prevBucket;
  1245.         if (prev == -1)
  1246.             return dbErr(db_ok);    // NB This is not an EOF condition
  1247.                                     // EOF has been reached but error is
  1248.                                     // on next call
  1249.         delete q->bptr;
  1250. #pragma warn -pia
  1251.         if (!(q->bptr = fetchBucket(prev)))
  1252. #pragma warn .pia
  1253.             return dbErr(db_err, "qPrev: Unable to fetch bucket");
  1254.  
  1255.         q->idx = q->bptr->header()->activeKeys+1;
  1256.         q->unsafe = false;
  1257.     }
  1258.     return dbErr(db_ok);
  1259. }
  1260.