home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Source Code / Visual Basic Source Code.iso / vbsource / vbdatabs / mnode.h < prev    next >
Encoding:
C/C++ Source or Header  |  1999-03-14  |  4.2 KB  |  108 lines
  1. // ------------------------------- //
  2. // -------- Start of File -------- //
  3. // ------------------------------- //
  4. // ----------------------------------------------------------- //
  5. // C++ Header File Name: mnode.h 
  6. // Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
  7. // Produced By: Doug Gaer   
  8. // File Creation Date: 02/12/1997 
  9. // Date Last Modified: 03/15/1999
  10. // Copyright (c) 1997 Douglas M. Gaer
  11. // ----------------------------------------------------------- // 
  12. // ---------- Include File Description and Details  ---------- // 
  13. // ----------------------------------------------------------- // 
  14. /*
  15. The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
  16. All those who put this code or its derivatives in a commercial
  17. product MUST mention this copyright in their documentation for
  18. users of the products in which this code or its derivative
  19. classes are used. Otherwise, you have the freedom to redistribute
  20. verbatim copies of this source code, adapt it to your specific
  21. needs, or improve the code and release your improvements to the
  22. public provided that the modified files carry prominent notices
  23. stating that you changed the files and the date of any change.
  24.  
  25. THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
  26. THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
  27. IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
  28. YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
  29. CORRECTION.
  30.  
  31. The Multi-way node (E)ntryKey class and (M)ulti-way (n)ode
  32. classes are used to make up (B)alanced multi-way (T)rees.
  33. Each node in the tree will have a left branch that leads to
  34. all nodes with keys smaller than the smallest key. The right
  35. branches will be paried with a key, each branch leading to all
  36. nodes with keys greater than the given key, but less than the
  37. key to the right. 
  38. */
  39. // ----------------------------------------------------------- //   
  40. #ifndef __MNODE_HPP
  41. #define __MNODE_HPP
  42.  
  43. #include "entrykey.h"
  44. #include "int32.h"
  45.  
  46. // Order of the tree and maximum number of branches for the node.
  47. // A MAXKEYSIZE of 64 each will generate Mnodes 464 bytes in
  48. // length: the count field, plus the left child pointer, plus six
  49. // entry keys. A 464 byte Mnode plus a 16 byte block header,
  50. // plus a 4 byte checksum makes a total of 484 bytes between
  51. // each Mnode in the B-tree index file.
  52. // NOTE: If the NBR constant (B-tree order) is changed, all the
  53. // VBD index files will have to rebuilt if they used a different
  54. // NBR value when they were created. 
  55. const int NBR = 7; // This will allow 4 nodes per branch
  56.  
  57. // (M)ulti-way (n)ode class 
  58. class Mnode
  59. {
  60. public:
  61.   Mnode() { cnt = 0; left = 0; }
  62.  
  63. public:
  64.   int Search(const EntryKey &e, int &posn);
  65.   int FullSearch(const EntryKey &e, int &posn);
  66.   void Split(Mnode &b, int split_posn);
  67.   void InsEntryKey(EntryKey &e, int posn);
  68.   void Cat(EntryKey &e) { InsEntryKey(e, cnt); }
  69.   void Cat(Mnode &n);
  70.   void DelEntryKey(int posn);
  71.   INT32 &Branch(int posn);
  72.   INT32 &GetBranchs(int posn);
  73.   INT32 LastPosn() { return cnt-1; }
  74.  
  75.   // Returns true if node is empty
  76.   int IsEmpty() { return cnt == 0; }
  77.  
  78.   // Returns true if node if full
  79.   int IsFull() { return cnt == NBR-1; }
  80.  
  81.   // Returns true if node hase fewer than the minimum number of entries
  82.   int IsPoor() { return cnt < (NBR-1)/2; }
  83.  
  84.   // Returns true if node has more than the minimum number of entries
  85.   int IsPlentiful() { return cnt > (NBR-1)/2; }
  86.  
  87. public:
  88.   // The cnt field indicates how many entries are actually in use.
  89.   INT32 cnt;  // Must come before left
  90.  
  91.   // Branches are indexed from -1 to NBR-2. The -1th branch
  92.   // represents  the left branch and the 0th branch is the
  93.   // right branch of the of the first entry.
  94.  
  95.   // NOTE: In order for the Branch() function to work with this
  96.   // indexing scheme there cannot be any gaps between the left
  97.   // and entry fields.
  98.   
  99.   INT32 left; // Points to leftmost child. Must come before entry[].
  100.   EntryKey entry[NBR-1];
  101. };
  102.  
  103. #endif // __MNODE_HPP
  104. // ----------------------------------------------------------- // 
  105. // ------------------------------- //
  106. // --------- End of File --------- //
  107. // ------------------------------- //
  108.