home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / db02_src.zip / bucket.cc < prev    next >
C/C++ Source or Header  |  1993-11-05  |  11KB  |  443 lines
  1. /**************************************************************************
  2.  * Source Id :
  3.  *
  4.  * $Id: bucket.cc,v 1.31 1993/10/05 07:29:18 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.  *  Bucket Module
  24.  *
  25.  *  Original Author : Andy & Kev (with inspiration from Daz)
  26.  *
  27.  *-------------------------------------------------------------------------
  28.  * Revision History:
  29.  *
  30.  * $Log: bucket.cc,v $
  31. // Revision 1.31  1993/10/05  07:29:18  kevinl
  32. // Fixed negative offset problem in bucket::del
  33. //
  34. // Revision 1.30  1993/07/20  13:05:14  kevinl
  35. // No longer complains about unused 'in' in sploosh.
  36. //
  37. // Revision 1.29  1993/07/20  12:59:30  kevinl
  38. // Some unisgned int vs long problems
  39. //
  40. // Revision 1.28  1993/06/23  05:21:22  kevinl
  41. // Mallocs are now in angular brackets
  42. //
  43. // Revision 1.27  1993/06/20  13:43:05  kevinl
  44. // Fixed multiple mallocs
  45. //
  46. // Revision 1.26  1993/05/26  01:01:39  kevinl
  47. // MALLOC_H_MISSING
  48. //
  49. // Revision 1.25  1993/05/11  14:44:50  kevinl
  50. // Added version number output
  51. //
  52. // Revision 1.24  1993/05/06  04:00:19  kevinl
  53. // SASC define for malloc.h
  54. //
  55. // Revision 1.23  1993/05/03  23:33:37  kevinl
  56. // long aligned data
  57. //
  58. // Revision 1.22  1993/05/03  01:33:03  kevinl
  59. // Cosmetic (mainly) changes for CC
  60. //
  61. // Revision 1.21  1993/05/01  14:29:12  kevinl
  62. // Replaced linear searchForKey with a binary search
  63. // Got rid of ints
  64. //
  65. // Revision 1.20  1993/04/30  07:45:45  kevinl
  66. // Some optimizing
  67. //
  68. // Revision 1.19  1993/04/28  11:30:15  kevinl
  69. // Fixed up inlines
  70. //
  71. // Revision 1.18  1993/04/25  09:52:39  kevinl
  72. // Fixed some dberror calls
  73. //
  74. // Revision 1.17  1993/04/24  07:15:27  kevinl
  75. // Comments!
  76. //
  77. // Revision 1.16  1993/04/19  15:49:37  kevinl
  78. // empty() now handles internal vs leaf nodes correctly
  79. //
  80. // Revision 1.15  1993/04/15  07:57:57  kevinl
  81. // Added findIndex, del and empty
  82. // Shortened full()
  83. //
  84. // Revision 1.14  1993/04/08  10:57:27  kevinl
  85. // played with bcopy prototype to placate linux.
  86. //
  87. // Revision 1.13  1993/04/04  23:56:25  kevinl
  88. // Rounded off keyLengths
  89. // searchForKey returns orrect indicies
  90. //
  91. // Revision 1.12  1993/03/29  08:20:09  darrenp
  92. // Added new malloc library support
  93. //
  94. // Revision 1.11  1993/03/18  08:33:58  kevinl
  95. // Fixed up reinitiaised default argument
  96. //
  97. // Revision 1.10  1993/03/17  14:27:42  kevinl
  98. // Added index number to bucket constructor
  99. // Added keyNum entry to all object key accesses
  100. //
  101. // Revision 1.9  1993/03/15  13:58:35  kevinl
  102. // Added setParent
  103. // changed some int's to long
  104. //
  105. // Revision 1.8  1993/03/08  00:30:50  kevinl
  106. // Replaced BORLANDC with __BORLANDC__
  107. //
  108. // Revision 1.7  1993/02/17  12:15:53  kevinl
  109. // Added getLink and setLink to solve alignment problems
  110. // some tidying
  111. //
  112. // Revision 1.6  1993/02/13  00:55:33  kevinl
  113. // replaced some long's with bucketId
  114. //
  115. // Revision 1.5  1993/02/11  03:53:38  kevinl
  116. // a few fixes.
  117. //
  118. // Revision 1.4  1993/02/10  07:56:34  darrenp
  119. // commented now.
  120. //
  121. // Revision 1.3  1993/02/08  14:33:24  davison
  122. // Andy: wrote sploosh
  123. // Kev: minor fixes to sploosh, comments, some output routines for debugging
  124. //
  125. // Revision 1.2  1993/02/08  00:12:28  kevinl
  126. // Kevin adds a constructor...
  127. //
  128. // Revision 1.1  1993/02/06  16:50:36  davison
  129. // Initial revision
  130. //
  131.  **************************************************************************/
  132.  
  133. #if !defined(MALLOC_H_MISSING) && !defined(MALLOC_H_INCLUDED)
  134. extern "C" {
  135. #include <malloc.h>
  136. }
  137. #define MALLOC_H_INCLUDED
  138. #endif
  139. #include <defs.h>
  140. #include <object.h>
  141. #include <iostream.h>
  142.  
  143. // Borland needs mem.h for memmove.
  144.  
  145. #ifdef __BORLANDC__
  146. #include <mem.h>
  147. #endif
  148.  
  149. // Ultrix hides it's bcopy prototype in here
  150.  
  151. #ifdef __ultrix
  152. #include <memory.h>
  153. #endif
  154.  
  155. char* bucket::verStr(void)
  156. {    
  157.     return "$Id: bucket.cc,v 1.31 1993/10/05 07:29:18 kevinl Exp $";
  158. }
  159.  
  160. // The constructor.
  161.  
  162. bucket::bucket(bucketId newId, long newKeyLength, long newSize, e_leaf newLeaf, bucketId newParentId, bucketId newNextBucket, bucketId newPrevBucket, long newKeyNum)
  163. {
  164.  
  165. // Allocate the data for the bucket and grab a pointer to the header data.
  166.     
  167.     // Size is rounded up to the size of a long for allocation purposes
  168.     // only. This is array of longs to satisfy potential alignment problems
  169.     // with casting this to a headerData*
  170.  
  171.     data = new long[((size = newSize)+sizeof(long)-1) / sizeof(long)];
  172.  
  173.     headerData *h = (headerData*)data;
  174.  
  175. // Store the characteristics of the bucket
  176.  
  177.     h->leaf = newLeaf;
  178.     h->parentId = newParentId;
  179.     h->nextBucket = newNextBucket;
  180.     h->prevBucket = newPrevBucket;
  181.     h->activeKeys = 0;
  182.  
  183.     id = newId;
  184.  
  185.     keyLength = newKeyLength;
  186.     keyNum = newKeyNum;
  187.  
  188.     // Each tuple contains a key, the length of which is defined by
  189.     // the object and stored by the constructor, and a long link.
  190.  
  191.     // Round keyLength up to a multiple of 4
  192.  
  193.     myTupleSize = ((keyLength+3)&(~3)) + sizeof(long);
  194.  
  195. // The number of keys is as many tuples as will fit in the bucket, taking
  196. // the header and initial pointer into account.
  197.  
  198.     numKeys = (size - headerSize() - sizeof(long)) / tupleSize();
  199. }
  200.  
  201. bucket::~bucket()
  202. {
  203.     delete data;
  204. }
  205.  
  206. // A little info for the programmer if s/he desires
  207. void
  208. bucket::info(void)
  209. {
  210.     cout << "HeaderSize = " << dec << headerSize() << endl
  211.         << "TupleSize = " << tupleSize() << endl
  212.         << "ActiveKeys = " << header()->activeKeys << endl
  213.         << "Previous = " << header()->prevBucket << "    Next = " << header()->nextBucket << endl;
  214. }
  215.  
  216. // Used during debugging. NB Key is assumed to start with a long
  217.  
  218. void 
  219. bucket::dump(void)
  220. {
  221.     cout << "Bucket Dump" << endl;
  222.  
  223.     cout << "Link: " << getLink(0) << endl;
  224.     for (long i = 1; i <= header()->activeKeys; i++)
  225.         cout << "Data: " << hex << *((long *)getKeyAddr(i)) << endl
  226.              << "Link: " << dec << getLink(i) << endl;
  227. }
  228.  
  229. // Actually return the data in the link itself
  230.  
  231. bucketId
  232. bucket::getLink(long pos)
  233. {
  234.     bucketId link;
  235.     bcopy(getLinkAddr(pos), (char*)&link, sizeof(bucketId));
  236.     return link;
  237. }
  238.  
  239. // Store a new link
  240.  
  241. void
  242. bucket::setLink(long pos, bucketId link)
  243. {
  244.     bcopy((char*)&link, getLinkAddr(pos), sizeof(bucketId));
  245. }
  246.  
  247. // The key in theObject and the link are inserted into the bucket in the
  248. // appropriate spot.
  249.  
  250. void
  251. bucket::insert(object& theObject,long link)
  252. {
  253.     long pos = 0;
  254.  
  255. // This returns the position where theObject should be inserted in the bucket.
  256.  
  257.     searchForKey(theObject,pos);
  258.  
  259. // Shift the existing data along one.
  260.  
  261.     pKeyType tempKey = getKeyAddr(pos+1); // to stop it being called twice
  262.     bcopy((char *)tempKey,(char *)getKeyAddr(pos+2), (header()->activeKeys-pos)*tupleSize());
  263.  
  264. // Now put the key in.
  265.  
  266.     pKeyType key = theObject.getKey(keyNum);
  267.     bcopy((char *)key,(char *)tempKey,keyLength);
  268.     delete key;
  269.  
  270. // Now the Link.
  271.     setLink(pos+1, link);
  272.  
  273. // Now we have one more...
  274.  
  275.     header()->activeKeys++;
  276. }
  277.  
  278. // Delete a key from a bucket
  279.  
  280. dbError
  281. bucket::del(long pos)
  282. {
  283.     // Can't delete an entry that is not there.
  284.     // Are there pos in the bucket?
  285.  
  286.     if (pos > header()->activeKeys || pos < 0)
  287.         return dbErr(db_range);
  288.  
  289.     // All after pos roll over and one falls out...
  290.     // NB For Inner nodes, we move starting at a link, not a key. This is
  291.     // so that the less than link at the start of the bucket is maintained
  292.     // accurate. The number to move is therefore 1 tuple less plus the extra
  293.     // link.
  294.  
  295.     if (header()->leaf)
  296.         bcopy((char*)getKeyAddr(pos+1), (char*)getKeyAddr(pos), (header()->activeKeys - pos) * tupleSize());
  297.     else
  298.         if (header()->activeKeys > pos)
  299.             bcopy((char*)getLinkAddr(pos+1), (char*)getLinkAddr(pos), (header()->activeKeys - pos - 1) * tupleSize() + sizeof(long));
  300.  
  301.     // And there was one less entry in the bucket.
  302.     header()->activeKeys--;
  303.  
  304.     return dbErr(db_ok);
  305. }
  306.  
  307. // Find a key in the bucket or return where it should go.
  308. // If the key is not found then return the entry before where it would be
  309. // If the key is found, return the spot where it is
  310.  
  311. // This function has been replaced by the binary chop version below.
  312.  
  313. #if 0
  314. bool
  315. bucket::searchForKey(object& theObject, long& ptr)
  316. {
  317.     long i=1;
  318.  
  319.     while (i <= header()->activeKeys) // NB pairs are numbered 1 to n
  320.     {
  321.         pKeyType key = getKeyAddr(i);
  322.         if (theObject.isLessThan(key, keyNum) )
  323.         {
  324.             ptr = i-1; // Needs to be inserted before i
  325.             return FALSE;
  326.         }
  327.         else if (theObject.isEqual(key, keyNum) )
  328.         {
  329.             ptr = i;
  330.             return TRUE;
  331.         }
  332.         i++;
  333.     }
  334.     ptr=i-1;
  335.     return FALSE;
  336. }
  337. #endif
  338.  
  339. bool
  340. bucket::searchForKey(object& theObject, long& ptr)
  341. {
  342.     long high = header()->activeKeys;
  343.     long low = 1; // NB pairs are numbered 1 to n
  344.  
  345.     while (low <= high)
  346.     {
  347.         long mid = (low + high) / 2;
  348.         pKeyType key = getKeyAddr(mid);
  349.         if (theObject.isEqual(key, keyNum) )
  350.         {
  351.             ptr = mid;
  352.             return TRUE;
  353.         }
  354.         if (theObject.isLessThan(key, keyNum) )
  355.             high = mid - 1;
  356.         else
  357.             low = mid + 1;
  358.     }
  359.     // OK, now high is less than low. The key must therefore go after
  360.     // position high
  361.  
  362.     ptr = high;
  363.     return FALSE;
  364. }
  365.  
  366. // Search a bucket for a particular link and return it's position. This is
  367. // used during delete, when trying to find where, in it's parent, a deleted
  368. // bucket was positioned.
  369.  
  370. void
  371. bucket::findIndex(long& ind, bool& found)
  372. {
  373.     found = false;
  374.     for (long i=0; i <= header()->activeKeys; i++)
  375.         if (getLink(i) == ind)
  376.         {
  377.             found = true;
  378.             ind = i;
  379.             break;
  380.         }
  381. }
  382.  
  383. // When a bucket is full, it contents need to be split into two buckets.
  384. // The calling function creates the new bucket and fixes the forward and
  385. // backward links.
  386. // In the case of a leaf bucket, the first key in the new bucket is returned
  387. // in 'out'. In the case of an inner node, the key deleted is returned.
  388.  
  389. void
  390. bucket::sploosh(bucket* newBucket, pKeyType in, pKeyType out, object& theObject,
  391.                 long link)
  392. {
  393.     in = in;
  394.  
  395.     long newKeyPos=0;
  396.     long delFromPos=header()->activeKeys/2+1;
  397. //    pKeyType medianKey = getKeyAddr(header()->activeKeys / 2);
  398.  
  399. // This loop is a little ugly! It determines where the key must be inserted.
  400.  
  401.     for(long i=1;(!newKeyPos) && i<=header()->activeKeys;i++)
  402.     {
  403.         // is in < current key ?
  404.         if (theObject.isLessThan(getKeyAddr(i), keyNum)) // && (newKeyPos!=0))
  405.             newKeyPos = i;
  406.     }
  407.     if (!newKeyPos)
  408.         newKeyPos = i;
  409.  
  410. // Now put the excess values into the new bucket.
  411.     
  412.     bcopy((char *)getKeyAddr(delFromPos),(char *)newBucket->getKeyAddr(1),
  413.             (header()->activeKeys-delFromPos+1)*tupleSize());
  414.     newBucket->setActiveKeys(header()->activeKeys-delFromPos+1);
  415.  
  416.     setActiveKeys(delFromPos-1);
  417.  
  418. // Now add the new key where appropriate...
  419.     
  420.     if (newKeyPos <= delFromPos)
  421.         insert(theObject,link);
  422.     else
  423.         newBucket->insert(theObject,link);
  424.  
  425. #ifdef __CC
  426.     memcpy(out,newBucket->getKeyAddr(1),(int)keyLength);
  427. #else
  428.     memcpy(out,newBucket->getKeyAddr(1),keyLength);
  429. #endif
  430.  
  431. // If this is an inner node then move everything in the new bucket down one.
  432. // Note that it is not the first tuple that is deleted, but the link number
  433. // 0 and key number 1. This deletes the key that will be sent back in 'out'
  434. // and leaves the correct link in the extra spot.
  435.  
  436.     if (header()->leaf == INNER)
  437.     {
  438.         bcopy( newBucket->getLinkAddr(1),(char *)newBucket->firstTuple(),
  439.                 (newBucket->header()->activeKeys-1)*tupleSize()+sizeof(long));
  440.         newBucket->setActiveKeys(newBucket->header()->activeKeys-1);
  441.     }
  442. }
  443.