home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / 11 < prev    next >
Encoding:
Text File  |  1992-06-07  |  4.3 KB  |  108 lines
  1. #ifndef __RWDISKTREE_H__
  2. #define __RWDISKTREE_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * Declarations for B-Trees on disk.
  7.  *
  8.  * $Header:   E:/vcs/rw/disktree.h_v   1.3   18 Feb 1992 09:54:16   KEFFER  $
  9.  *
  10.  ****************************************************************************
  11.  *
  12.  * Rogue Wave 
  13.  * P.O. Box 2328
  14.  * Corvallis, OR 97339
  15.  * Voice: (503) 754-3010    FAX: (503) 757-6650
  16.  *
  17.  * Copyright (C) 1989, 1990, 1991. This software is subject to copyright 
  18.  * protection under the laws of the United States and other countries.
  19.  *
  20.  ***************************************************************************
  21.  *
  22.  * $Log:   E:/vcs/rw/disktree.h_v  $
  23.  * 
  24.  *    Rev 1.3   18 Feb 1992 09:54:16   KEFFER
  25.  * 
  26.  *    Rev 1.2   28 Oct 1991 09:08:12   keffer
  27.  * Changed inclusions to <rw/xxx.h>
  28.  * 
  29.  *    Rev 1.1   28 Jul 1991 12:36:04   keffer
  30.  * No longer uses macro "Const"
  31.  * 
  32.  *    Rev 1.0   28 Jul 1991 08:14:14   keffer
  33.  * Tools.h++ V4.0.5 PVCS baseline version
  34.  *
  35.  */
  36.  
  37. #include "rw/tooldefs.h"
  38. #include "rw/filemgr.h"
  39.  
  40. // Order is half the maximum number of keys per mode.
  41. // Setting it higher will reduce disk accesses, but increase
  42. // stack size requirements and CPU computations.  Suggested size is 10.
  43. const int     order         = 10;
  44. const int     twoTimesOrder     = 2*order;
  45. const int    KEY_SIZE    = 16;
  46.  
  47. typedef void    (*applyRWBTreeOnDisk)(const char*, storedValue, void*);
  48.  
  49. class RWDiskTreeNode {
  50. friend class RWExport RWBTreeOnDisk;
  51.  
  52.   // Private constructors:
  53.   RWDiskTreeNode();   // Construct a node with no contents.
  54.   RWDiskTreeNode(const char* key, storedValue); // Construct node with one item.
  55.  
  56.   // Private data:
  57.   int                 counter;   // How many of the [twoTimesOrder] fields are used.
  58.   nodeOffset          next[twoTimesOrder+1];   // Array of offsets to children nodes.
  59.   storedValue         item[twoTimesOrder];     // Array of offsets to stored objects.
  60.   char                key[twoTimesOrder][KEY_SIZE];  // Array of keys.
  61.  
  62.   // Private member function:
  63.   int                 binarySearch(const char*) const;    // Binary search for insertion.
  64. };
  65.  
  66. class RWExport RWBTreeOnDisk {
  67. private:
  68.   RWDiskTreeNode       root;        // Root node (in memory).
  69.   nodeOffset         rootOffset;    // Offset to root node on disk.
  70.   RWFileManager*       file;        // File manager for B-tree on disk.
  71.   RWDiskTreeNode       workNode;    // Work space for node (in memory).
  72.   nodeOffset         workOffset;    // Offset to work node on disk. Flag for node in work space
  73.   storedValue        newa;        // Place holder to handle node over- and underflow.
  74.   char               newk[KEY_SIZE];    // Place holder to handle node over- and underflow.
  75.   nodeOffset         newn;        // Place holder to handle node over- and underflow.
  76. private:
  77.   void            countChildren(nodeOffset, int& nitems);    // Count children.
  78.   void            deleteChildren(nodeOffset);        // Delete nodes.
  79.   void             diskTreeErr(RWErrNo) const;
  80.   void              freeNode(nodeOffset);            // Free up space on disk; 
  81.   RWDiskTreeNode*           getNode(nodeOffset);
  82.   int            insertInChildren(const char* key, storedValue, nodeOffset);
  83.   void            operateOnChildren(nodeOffset, applyRWBTreeOnDisk, void*);
  84.   void               putNode(RWDiskTreeNode*);
  85.   void            readNode(RWDiskTreeNode*, nodeOffset p=RWNIL); 
  86.   int            removeFromChildren(const char* key, nodeOffset);// Remove key from tree.
  87.   // Write at position p. Return offset, or RWNIL if unsuccessful.
  88.   nodeOffset        writeNode(RWDiskTreeNode*, nodeOffset p=RWNIL);
  89.   void             writeRootOffset();
  90.   RWBTreeOnDisk(const RWBTreeOnDisk&);    // Cannot have 2 RWBTreeOnDisk for the same file.
  91.   void            operator=(const RWBTreeOnDisk&);
  92. public:
  93.   RWBTreeOnDisk(RWFileManager&);
  94.  
  95.   void             clear();                // Remove all nodes.
  96.   int              entries();                // Return number of items.
  97.   void             applyToKeyAndValue(applyRWBTreeOnDisk, void*); // Operate on all items
  98.   storedValue        find(const char* key);            // Return item where compare = 0
  99.   void            findKeyAndValue(const char* key, storedValue&); // Alternative find.
  100.   int              height();                // Return height of tree.
  101.   int              insertKeyAndValue(const char* key, storedValue p); // Add key & value.
  102.   int              isEmpty() const {return rootOffset==RWNIL;}// Return 1 for empty tree.
  103.   void             remove(const char* key);            // Remove item where compare = 0.
  104. };    
  105.  
  106. pragma pop_align_members();
  107. #endif /*  __RWDISKTREE_H__ */
  108.