home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / db02_src.zip / btree.h < prev    next >
C/C++ Source or Header  |  1993-11-05  |  5KB  |  186 lines
  1. /**************************************************************************
  2.  * Source Id :
  3.  *
  4.  * $Id: btree.h,v 1.20 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 bTree code. Implements a B+Tree (sort of)
  24.  *
  25.  *
  26.  *  Original Author : Daz & Kev
  27.  *
  28.  *-------------------------------------------------------------------------
  29.  * Revision History:
  30.  *
  31.  * $Log: btree.h,v $
  32.  * Revision 1.20  1993/06/23  05:21:22  kevinl
  33.  * Mallocs are now in angular brackets
  34.  *
  35.  * Revision 1.19  1993/05/11  14:44:50  kevinl
  36.  * Added version number output
  37.  *
  38.  * Revision 1.18  1993/05/01  14:27:04  kevinl
  39.  * Stripped ;'s off inlines
  40.  * Got rid of ints
  41.  * Made inBTree two functions
  42.  *
  43.  * Revision 1.17  1993/04/29  07:00:03  kevinl
  44.  * Added lsoeBucket
  45.  *
  46.  * Revision 1.16  1993/04/24  14:31:27  kevinl
  47.  * Comments
  48.  * Some small fixups and error code changes.
  49.  *
  50.  * Revision 1.15  1993/04/19  15:50:03  kevinl
  51.  * fixParent is no longer boolean. now int
  52.  *
  53.  * Revision 1.14  1993/04/15  07:55:24  kevinl
  54.  * Traverse & dump now have intonly mode
  55.  * inBTree takes optional reference to return spot where found.
  56.  *
  57.  * Revision 1.13  1993/04/08  07:23:40  kevinl
  58.  * insertInternal now takes refernce to bucket* so delete on outside works
  59.  *
  60.  * Revision 1.12  1993/03/28  13:58:23  kevinl
  61.  * Added inBTree
  62.  *
  63.  * Revision 1.11  1993/03/28  10:35:26  kevinl
  64.  * Modifed for dbErr
  65.  *
  66.  * Revision 1.10  1993/03/28  19:07:10  davison
  67.  * Deleted pError member.
  68.  *
  69.  * Revision 1.9  1993/03/26  06:16:38  darrenp
  70.  * standardized error codes.
  71.  *
  72.  * Revision 1.8  1993/03/24  06:15:58  kevinl
  73.  * Added pError and bterror members
  74.  *
  75.  * Revision 1.7  1993/03/17  14:26:31  kevinl
  76.  * Fixed up include files and mutiple include protection.
  77.  *
  78.  * Revision 1.6  1993/03/15  13:56:27  kevinl
  79.  * Put query stuff (back) in and finished all of it.
  80.  *
  81.  * Revision 1.5  1993/03/08  00:30:15  kevinl
  82.  * Added (and ifdef'd out) beginnings of query code
  83.  * Added integrity checks.
  84.  *
  85.  * Revision 1.4  1993/02/18  05:40:16  kevinl
  86.  * Added query transaction methods
  87.  *
  88.  * Revision 1.3  1993/02/17  12:14:02  darrenp
  89.  * Fixed definition of findInternal
  90.  *
  91.  * Revision 1.2  1993/02/13  00:54:07  kevinl
  92.  * new members added for insertInternal, createNewBucket, writeBucket
  93.  * added dbError enum for error codes
  94.  *
  95.  **************************************************************************/
  96.  
  97. #ifndef __BTREE_H__
  98. #define __BTREE_H__
  99.  
  100. #include <defs.h>
  101. #include <rserv.h>
  102. #include <object.h>
  103.  
  104. // The header data that the btree stores at the start of its revServer
  105.  
  106. struct bTreeHead {
  107.     long keyLen;
  108.     bucketId rootBucket;
  109. };
  110.  
  111. // The query structure for bTree. The constructor is so that the class
  112. // that uses this can compile. All its structures/subclasses must have
  113. // constructors.
  114.  
  115. struct bTreeQuery {
  116.     pKeyType    key;    // Current key, used if unsafe
  117.     bucket*        bptr;    // Current bucket
  118.     long        idx;    // The index into bptr, used if !unsafe
  119.     bool        unsafe;    // Has someone made a change to influence this query
  120.     bool        used;    // Query used?
  121.     bTreeQuery() {}        // Keep the compiler happy
  122. };
  123.  
  124. // The bTree class. It inherits recServer to store its data.
  125. // Each recServer record is a bucket in the bTree.
  126.  
  127. class bTree : public recServer
  128. {
  129.     bTreeHead head;
  130.     long indNum; // Which index to quote when asking for comparisons.
  131.     bTreeQuery query[MAX_QUERY];
  132.  
  133.     void findInternal(
  134.         object         &searchObject,
  135.         bucketId     rootBucket,
  136.         bool        &Found,
  137.         bucket        **bptr,
  138.         long        &ptrIdx,
  139.         int            fixParent = 0
  140.     );
  141.     bucket* fetchBucket(bucketId idx);
  142.     bucket* createNewBucket(e_leaf leaf, bucketId parentId, bucketId nextBucket, bucketId prevBucket);
  143.     void writeBucket(bucket* bptr);
  144.     void loseBucket(bucketId id);
  145.     void traverse(bucket* b, bool intonly);
  146.     void initQueries(void);
  147.     bool internalCheckIntegrity(bucketId buck);
  148.  
  149. public:
  150. #if 0
  151.     dbError status;
  152.     inline dbError bterror(dbError err) { return (status = err); };
  153. #endif
  154.  
  155.     char* verStr(void);
  156.     bTree(char *name, long bucketSize, long keyLen, long newIndNum=0); // create constructor
  157.     bTree(char *name, long newIndNum=0);  // open constructor
  158.     bTree(void) {} // Blank constructor. Use with care.
  159.     dbError add(object &newObject, long extPtr);
  160.     dbError del(object &delObject);
  161. //    dbError find(object &findObject, long &extPtr); // see qFind
  162.     bool checkIntegrity(void);
  163.     bool inBTree(object &theObject, long& idx);
  164.     inline bool inBTree(object &theObject)
  165.         {
  166.             long temp;
  167.             return inBTree(theObject, temp);
  168.         }
  169.     dbError qBegin(long& qNum);
  170.     dbError qEnd(long qNum);
  171.     dbError qFirst(long qNum, object &theObject, long &extPtr); // Act as peek
  172.     dbError qLast(long qNum, object &theObject, long &extPtr); // Act as peek
  173.     dbError qFind(long qNum, object& findObject, long& extPtr);
  174.     dbError qNext(long qNum, object &theObject, long &extPtr);
  175.     dbError qPrev(long qNum, object &theObject, long &extPtr);
  176.     dbError qPeekNext(long qNum, object &theObject, long &extPtr);
  177.     dbError qPeekPrev(long qNum, object &theObject, long &extPtr);
  178.  
  179.     void dump(bool intonly = false);
  180.  
  181. private:
  182.     dbError insertInternal(bucket*& bptr,object &newObj,long extPtr);
  183. };
  184.  
  185. #endif
  186.