home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / io / dskbtree.cxx < prev    next >
C/C++ Source or Header  |  1995-04-06  |  10KB  |  387 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6. /*
  7.  *
  8.  *          Copyright (C) 1994, M. A. Sridhar
  9.  *  
  10.  *
  11.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  12.  *     to copy, modify or distribute this software  as you see fit,
  13.  *     and to use  it  for  any  purpose, provided   this copyright
  14.  *     notice and the following   disclaimer are included  with all
  15.  *     copies.
  16.  *
  17.  *                        DISCLAIMER
  18.  *
  19.  *     The author makes no warranties, either expressed or implied,
  20.  *     with respect  to  this  software, its  quality, performance,
  21.  *     merchantability, or fitness for any particular purpose. This
  22.  *     software is distributed  AS IS.  The  user of this  software
  23.  *     assumes all risks  as to its quality  and performance. In no
  24.  *     event shall the author be liable for any direct, indirect or
  25.  *     consequential damages, even if the  author has been  advised
  26.  *     as to the possibility of such damages.
  27.  *
  28.  */
  29.  
  30.  
  31.  
  32.  
  33. #if defined(__GNUC__)
  34. #pragma implementation
  35. #endif
  36.  
  37.  
  38. #include "base/bytestrm.h"
  39.  
  40. #include "io/dskbtree.h"
  41. #include "io/bytstore.h"
  42.  
  43.  
  44. #include <iostream.h>
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52. class CL_DiskBTreeNode: public CL_GenericBTreeNode, public CL_Object {
  53.  
  54. public:
  55.     CL_DiskBTreeNode (short order, const CL_GenericBTree& tree,
  56.                       CL_AbstractComparator& cmp);
  57.     
  58.     ~CL_DiskBTreeNode () {};
  59.     
  60.     bool ReadFrom (const CL_Stream&);
  61.  
  62.     bool WriteTo  (CL_Stream&) const;
  63.  
  64.     const char* ClassName () const { return "CL_DiskBTreeNode";};
  65.  
  66. };
  67.  
  68.  
  69.  
  70. class CL_DiskBTreeNodeSpace: public CL_BTreeNodeSpace {
  71.  
  72. public:
  73.     CL_DiskBTreeNodeSpace (short order, CL_ByteStringStore& store,
  74.                            const CL_DiskBTree& tree,
  75.                            CL_AbstractComparator& cmp,
  76.                            CL_ObjectBuilder* f, bool create = FALSE);
  77.  
  78.     ~CL_DiskBTreeNodeSpace ();
  79.     
  80.     // --------------- Override all virtual functions ----------------
  81.     
  82.     CL_BTreeNodeHandle RootHandle () const;
  83.  
  84.     void NewRoot (CL_BTreeNodeHandle h);
  85.     
  86.     CL_BTreeNodeHandle CreateNode ();
  87.  
  88.     CL_GenericBTreeNode* BorrowNode (CL_BTreeNodeHandle h) const;
  89.     
  90.     void ReturnNode (CL_GenericBTreeNode* ) const;
  91.     
  92.     void NodeModified (CL_GenericBTreeNode*);
  93.     
  94.     void DestroyNode (CL_GenericBTreeNode* node);
  95.  
  96.     virtual void DestroyItem (CL_VoidPtr p) const
  97.         {if (p) delete (CL_ObjectPtr) p;};
  98.     
  99.     CL_ObjectBuilder* ItemBuilder () const {return _builder;};
  100.  
  101. protected:
  102.     CL_ByteStringStore&  _store;
  103.     CL_ObjectBuilder*    _builder;
  104.     CL_GenericBTreeNode* _tmp;  // A (hopefully temporary) hack to remember
  105.                                 // the most recently returned node.
  106. };
  107.  
  108.  
  109.  
  110. static const short DEFAULT_SIZE = 70;
  111. // This value is used as the starting size of ByteStrings that serve as
  112. // ByteStreams for  storing representations of nodes. Its purpose is to
  113. // speed up the algorithms by obviating the need for repeated resizing of
  114. // the ByteString.
  115.  
  116.  
  117. // --------------------- DiskBTreeNodeSpace methods -----------------------
  118.  
  119.  
  120. struct DiskBTreeHeader {
  121.     CL_SlottedFileHandle root;
  122.     short order;
  123. };
  124.  
  125. CL_DiskBTreeNodeSpace::CL_DiskBTreeNodeSpace
  126.     (short order, CL_ByteStringStore& store,
  127.      const CL_DiskBTree& tree, CL_AbstractComparator& cmp,
  128.      CL_ObjectBuilder* f, bool create)
  129. :CL_BTreeNodeSpace (order, tree._tree, cmp), _store (store)
  130. {
  131.     if (!f)
  132.         CL_Error::Warning ("DiskBTree constructor: null builder function");
  133.     _builder = f;
  134.     if (create) {
  135.         CL_BTreeNodeHandle h = CreateNode ();
  136.         NewRoot (h);
  137.     }
  138.     _tmp = NULL;
  139. }
  140.  
  141. CL_DiskBTreeNodeSpace::~CL_DiskBTreeNodeSpace ()
  142. {
  143.     if (_tmp)
  144.         _Destroy (_tmp);
  145. }
  146.  
  147.  
  148.  
  149.  
  150. /* ------------------------------------------------------------------ */
  151.  
  152. CL_BTreeNodeHandle CL_DiskBTreeNodeSpace::RootHandle () const
  153. {
  154.     CL_ByteString hdr (sizeof (DiskBTreeHeader));
  155.     if (!_store.ReadHeader (hdr))
  156.         return 0;
  157.     DiskBTreeHeader* p = (DiskBTreeHeader*) hdr.AsPtr();
  158.     return p->root;
  159. }
  160.  
  161.  
  162.  
  163. /* ------------------------------------------------------------------ */
  164.  
  165.  
  166. void CL_DiskBTreeNodeSpace::NewRoot (CL_BTreeNodeHandle h)
  167. {
  168.     CL_ByteString hdr (sizeof (DiskBTreeHeader));
  169.     DiskBTreeHeader* p = (DiskBTreeHeader*) hdr.AsPtr();
  170.     p->root = h;
  171.     p->order = _order;
  172.     _store.WriteHeader (hdr);
  173. }
  174.  
  175.  
  176.  
  177. /* ------------------------------------------------------------------ */
  178.  
  179.  
  180. CL_BTreeNodeHandle CL_DiskBTreeNodeSpace::CreateNode ()
  181. {
  182.     CL_ByteString dummy (DEFAULT_SIZE);
  183.     CL_ByteStream s (dummy);
  184.     CL_DiskBTreeNode node (_order, _tree, _cmp);
  185.     CL_BTreeNodeHandle h = _store.Allocate ();
  186.     _SetHandle (node, h);
  187.     node.WriteTo (s);
  188.     _store.Modify (h, dummy);
  189.     return h;
  190. }
  191.  
  192.  
  193.  
  194. /* ------------------------------------------------------------------ */
  195.  
  196.  
  197. CL_GenericBTreeNode* CL_DiskBTreeNodeSpace::BorrowNode
  198.     (CL_BTreeNodeHandle h) const
  199. {
  200.     CL_ByteString node_data (DEFAULT_SIZE);
  201.     if (!_store.Retrieve (h, node_data))
  202.         return NULL;
  203.     CL_ByteStream s (node_data);
  204.     CL_DiskBTreeNode* n = new CL_DiskBTreeNode (_order, _tree, _cmp);
  205.     if (n) {
  206.         n->ReadFrom (s);
  207.         _SetHandle (*n, h);
  208.     }
  209.     return n;
  210. }
  211.  
  212.  
  213.  
  214. /* ------------------------------------------------------------------ */
  215.  
  216.  
  217. void CL_DiskBTreeNodeSpace::ReturnNode (CL_GenericBTreeNode* n) const
  218. {
  219.     if (_tmp)
  220.         _Destroy (_tmp);
  221.     ((CL_DiskBTreeNodeSpace*) this)->_tmp = n; // cast away const
  222. }
  223.  
  224.  
  225.  
  226. /* ------------------------------------------------------------------ */
  227.  
  228.  
  229. void CL_DiskBTreeNodeSpace::NodeModified (CL_GenericBTreeNode* node)
  230. {
  231.     if (!node)
  232.         return;
  233.     CL_ByteString node_data (DEFAULT_SIZE);
  234.     CL_ByteStream s (node_data);
  235.     ((CL_DiskBTreeNode*) node)->WriteTo (s);
  236.     _store.Modify (node->Handle(), node_data);
  237. }
  238.  
  239.  
  240. /* ------------------------------------------------------------------ */
  241.  
  242. void CL_DiskBTreeNodeSpace::DestroyNode (CL_GenericBTreeNode* node)
  243. {
  244.     _store.Remove (node->Handle());
  245. }
  246.  
  247.  
  248.  
  249.  
  250. // --------------------- CL_DiskBTreeNode methods ----------------------
  251.  
  252.  
  253. CL_DiskBTreeNode::CL_DiskBTreeNode (short order,
  254.                                     const CL_GenericBTree& tree,
  255.                                     CL_AbstractComparator& cmp)
  256. : CL_GenericBTreeNode (order, tree.NodeSpace(), cmp)
  257. {
  258. }
  259.  
  260.  
  261. /* ------------------------------------------------------------------ */
  262.  
  263. bool CL_DiskBTreeNode::ReadFrom (const CL_Stream& s)
  264. {
  265.     if (s.Read (_keyCount) && s.Read ((short&) _isLeaf) && s.Read
  266.         (_subtreeSize)) {
  267.         if (!_subtree)
  268.             return FALSE;
  269.         // _subtree is already allocated in the BTreeNode constructor
  270.         if (_keyCount <= 0)
  271.             return TRUE;
  272.         for (short i = 0; i <= _keyCount; i++)
  273.             if (!s.Read (_subtree[i]))
  274.                 return FALSE;
  275.         CL_ObjectBuilder* bld =
  276.             ((CL_DiskBTreeNodeSpace*) _nodeSpace)->ItemBuilder ();
  277.         for (i = 0; i < _keyCount; i++) {
  278.             CL_Object* p = bld->BuildFrom (s);
  279.             if (!p)
  280.                 return FALSE;
  281.             _item[i] = p;
  282.         }
  283.         return TRUE;
  284.     }
  285.     return FALSE;
  286. }
  287.  
  288.  
  289. /* ------------------------------------------------------------------ */
  290.  
  291. bool CL_DiskBTreeNode::WriteTo  (CL_Stream& s) const
  292. {
  293.     if (s.Write (_keyCount) && s.Write ((short) _isLeaf) && s.Write
  294.         (_subtreeSize)) {
  295.         for (short i = 0; i <= _keyCount; i++)
  296.             if (!s.Write (_subtree[i]))
  297.                 return FALSE;
  298.         for (i = 0; i < _keyCount; i++) {
  299.             if (!((CL_Object*) _item[i])->WriteTo (s))
  300.                 return FALSE;
  301.         }
  302.         return TRUE;
  303.     }
  304.     return FALSE;
  305. }
  306.  
  307.  
  308.  
  309. /* ------------------------------------------------------------------ */
  310.  
  311.  
  312.  
  313.  
  314.  
  315. // static short _ReadOrder (CL_ByteStringStore& store)
  316. // {
  317. //     // This doesn't seem to serve its purpose, because of
  318. //     // order-of-initialization problems. Will try to fix it later.
  319. //     // -- MAS 8/22/94
  320. //     CL_ByteString hdr (sizeof (DiskBTreeHeader));
  321. //     if (!store.ReadHeader (hdr))
  322. //         return 0;
  323. //     DiskBTreeHeader* p = (DiskBTreeHeader*) hdr.AsPtr();
  324. //     return p->order;
  325. // }
  326.  
  327.  
  328. CL_DiskBTree::CL_DiskBTree (CL_ByteStringStore& store,
  329.                             CL_ObjectBuilder* f, short order, bool create)
  330. : CL_BTree<CL_ObjectPtr>
  331.   (order,
  332.    (_diskNodeSpace = new CL_DiskBTreeNodeSpace (order, store, *this,
  333.                                                 _comparator, f, create))
  334.   ),
  335.   _store (store)
  336. {
  337. }
  338.  
  339.  
  340. CL_DiskBTree::~CL_DiskBTree ()
  341. {
  342.     delete _diskNodeSpace;
  343. }
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350. // void CL_DiskBTree::IntoStream (ostream& strm) const
  351. // {
  352. //     CL_BTreeNodeSpace* space = NodeSpace ();
  353. //     if (space) {
  354. //         CL_BTreeNodeHandle h = space->RootHandle();
  355. //         PrintTree (h, 0, strm);
  356. //     }
  357. // }
  358. // 
  359. // 
  360. // 
  361. // 
  362. // 
  363. // void CL_DiskBTree::PrintTree (CL_BTreeNodeHandle h, short level,
  364. //                               ostream& strm) const
  365. // {
  366. // 
  367. //     if (h == 0)
  368. //         return;
  369. //     CL_BTreeNodeSpace* space = NodeSpace ();
  370. //     CL_GenericBTreeNode* z = space->BorrowNode (h);
  371. // 
  372. //     for (short i = 0; i < z->Size(); i++) {
  373. //         PrintTree (z->Subtree(i), level+1, strm);
  374. //         for (short j = 0; j < 4*level; j++)
  375. //             strm << ' ';
  376. //         CL_ObjectPtr q = (CL_ObjectPtr) z->Item(i);
  377. //         CL_String s;
  378. //         if (q)
  379. //             s = q->AsString();
  380. //         strm << "------>" << s << endl << flush;
  381. //     }
  382. //     PrintTree (z->Subtree(z->Size()), level+1, strm);
  383. //     space->ReturnNode (z);
  384. // }
  385.  
  386.  
  387.