home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / io / bytstore.cxx < prev    next >
C/C++ Source or Header  |  1995-04-04  |  14KB  |  489 lines
  1.  
  2.  
  3.  
  4.  
  5. /*
  6.  *
  7.  *          Copyright (C) 1994, M. A. Sridhar
  8.  *  
  9.  *
  10.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  11.  *     to copy, modify or distribute this software  as you see fit,
  12.  *     and to use  it  for  any  purpose, provided   this copyright
  13.  *     notice and the following   disclaimer are included  with all
  14.  *     copies.
  15.  *
  16.  *                        DISCLAIMER
  17.  *
  18.  *     The author makes no warranties, either expressed or implied,
  19.  *     with respect  to  this  software, its  quality, performance,
  20.  *     merchantability, or fitness for any particular purpose. This
  21.  *     software is distributed  AS IS.  The  user of this  software
  22.  *     assumes all risks  as to its quality  and performance. In no
  23.  *     event shall the author be liable for any direct, indirect or
  24.  *     consequential damages, even if the  author has been  advised
  25.  *     as to the possibility of such damages.
  26.  *
  27.  */
  28.  
  29.  
  30.  
  31.  
  32. #if defined(__GNUC__)
  33. #pragma implementation
  34. #endif
  35.  
  36.  
  37. #include "base/bytstrng.h"
  38. #include "io/bytstore.h"
  39.  
  40.  
  41. /* ------------------------------------------------------------------ */
  42.  
  43. // The data  structure  used is a   SlottedFile,  whose slots  are of  size
  44. // CHUNK_SIZE. Each ByteString written into the SlottedFile is written in a
  45. // linked list of  slots,  which we  will  call  the ByteString list.   The
  46. // collection  of all ByteString    lists in  the  SlottedFile are   linked
  47. // together into   a doubly-linked list,  which we  will  call the iterator
  48. // list.  The first slot of the ByteString list contains  the handle of the
  49. // next slot (zero if no other slots), the actual length of the ByteString,
  50. // the handles of the first slots of the next and previous ByteString lists
  51. // in  the   iterator  list,   followed    by   the  actual  data   of  the
  52. // ByteString. Each subsequent  slot  of the  ByteString list contains  the
  53. // handle of the next slot in the list, followed by the ByteString's data.
  54. // 
  55. // The iterator  list is used  to support  efficient  iteration through the
  56. // ByteStrings  stored  in the file.    This necessitates the  head of  the
  57. // iterator list to be stored in the user-header area of the slotted file.
  58.  
  59.  
  60. #define CHUNK_SIZE 64 // Must be at least 20
  61.  
  62.  
  63. struct PrimarySlot {
  64.     CL_SlottedFileHandle next; // First secondary slot
  65.     long                 byteStringSize;
  66.     CL_SlottedFileHandle iter_next, iter_prev;
  67.     uchar                data[1];
  68.     long DataOffset () const
  69.         {return (long) ((uchar*) &data - (uchar*) &next);};
  70. };
  71.  
  72. struct SecondarySlot {
  73.     CL_SlottedFileHandle next; // Next secondary slot
  74.     uchar                data[1];
  75.     long DataOffset () const
  76.         {return (long) ((uchar*) &data - (uchar*) &next);};
  77. };
  78.  
  79.  
  80. struct HeaderForSlottedFile {
  81.     CL_SlottedFileHandle iter_list_head;
  82.     CL_SlottedFileHandle user_header;
  83. };
  84.  
  85.  
  86.  
  87. CL_ByteStringStore::CL_ByteStringStore (const char* path, bool create, bool
  88.                                       report_errors)
  89. {
  90.     if (create) {
  91.         HeaderForSlottedFile hdr;
  92.         hdr.iter_list_head = 0L;
  93.         _file = new CL_PrivateSlottedFile
  94.             (path, CHUNK_SIZE, sizeof (HeaderForSlottedFile), report_errors);
  95.         if (_file) {
  96.             // Create a dummy header string
  97.             CL_ByteString dummy (12);
  98.             hdr.user_header = Add (dummy);
  99.             _file->WriteHeader ((uchar*) &hdr);
  100.         }
  101.     }
  102.     else
  103.         _file = new CL_PrivateSlottedFile (path, report_errors);
  104. }
  105.  
  106.  
  107.  
  108. /* ------------------------------------------------------------------ */
  109.  
  110.  
  111. CL_ByteStringStore::~CL_ByteStringStore ()
  112. {
  113.     if (_file)
  114.         delete _file;
  115. }
  116.  
  117.  
  118.  
  119. /* ------------------------------------------------------------------ */
  120.  
  121.  
  122.  
  123.     
  124. // Add the given array of bytes into the store, and return the
  125. // associated handle. Return 0 on failure.
  126.  
  127.  
  128. CL_SlottedFileHandle CL_ByteStringStore::Add (const CL_ByteArray& data)
  129. {
  130.     CL_ByteString slot_data (CHUNK_SIZE);
  131.     long data_size = data.Size();
  132.     PrimarySlot* p = (PrimarySlot*) slot_data.AsPtr ();
  133.     long offset = p->DataOffset();
  134.  
  135.     CL_SlottedFileHandle ihead; // Iterator list head
  136.     HeaderForSlottedFile hdr;
  137.     
  138.     long used = minl (CHUNK_SIZE - offset, data_size);
  139.     p->byteStringSize = data_size;
  140.     p->next = (data_size - used > 0)
  141.         ? _Add (data.AsPtr() + used, data_size - used)
  142.         : 0L;
  143.     slot_data.CopyFrom (data.AsPtr(), used, p->DataOffset());
  144.  
  145.     if (!_file->ReadHeader ((uchar*) &hdr))
  146.         return 0;
  147.     ihead = hdr.iter_list_head;
  148.     CL_SlottedFileHandle h = _file->AllocateSlot ();
  149.  
  150.     // Insert the new string at the head of the iterator list: first change
  151.     // the list head pointer, in the file header
  152.     CL_SlottedFileHandle next = p->iter_next = ihead;
  153.     p->iter_prev = 0;
  154.     hdr.iter_list_head = ihead = h;
  155.     if (!_file->ModifyRecord (h, slot_data) ||
  156.         !_file->WriteHeader ((uchar*) &hdr))
  157.         return 0;
  158.  
  159.     // Now set the previous pointer of the next string in the iterator list
  160.     if (next) {
  161.         if (!_file->RetrieveRecord (next, slot_data))
  162.             return 0;
  163.         p->iter_prev = h;
  164.         if (!_file->ModifyRecord (next, slot_data))
  165.             return 0;
  166.     }
  167.     return h;
  168. }
  169.  
  170.  
  171.  
  172.  
  173.  
  174. /* ------------------------------------------------------------------ */
  175. CL_SlottedFileHandle CL_ByteStringStore::Allocate ()
  176. {
  177.     CL_ByteString s (10); // Small byte string
  178.     return Add (s);
  179. }
  180.  
  181.  
  182.  
  183.  
  184.  
  185. /* ------------------------------------------------------------------ */
  186.  
  187.  
  188. // Remove the byte string associated with the given handle. Return
  189. // TRUE on success, FALSE if either the handle was invalid or an I/O
  190. // error occurred.
  191. bool CL_ByteStringStore::Remove (CL_SlottedFileHandle h)
  192. {
  193.     CL_ByteString slot (CHUNK_SIZE), tmp_slot (CHUNK_SIZE);
  194.     // Retrieve the primary slot
  195.     if (!_file->RetrieveRecord (h, slot))
  196.         return FALSE;
  197.     // Remove it from the iterator list
  198.     CL_SlottedFileHandle inext, iprev;
  199.     PrimarySlot* p = (PrimarySlot*) slot.AsPtr();
  200.     PrimarySlot* q = (PrimarySlot*) tmp_slot.AsPtr();
  201.     inext = p->iter_next;
  202.     iprev = p->iter_prev;
  203.     if (inext) {
  204.         if (!_file->RetrieveRecord (inext, tmp_slot))
  205.             return FALSE;
  206.         q->iter_prev = iprev;
  207.         if (!_file->ModifyRecord (inext, tmp_slot))
  208.             return FALSE;
  209.     }
  210.     if (iprev) {
  211.         if (!_file->RetrieveRecord (iprev, tmp_slot))
  212.             return FALSE;
  213.         q->iter_next = inext;
  214.         if (!_file->ModifyRecord (iprev, tmp_slot))
  215.             return FALSE;
  216.     }
  217.     else {
  218.         // No previous element, this must be the head of the iterator list
  219.         HeaderForSlottedFile hdr;
  220.         if (!_file->ReadHeader ((uchar*) &hdr))
  221.             return FALSE;
  222.         hdr.iter_list_head = p->iter_next; 
  223.         if (!_file->WriteHeader ((uchar*) &hdr))
  224.             return FALSE;
  225.     }
  226.     return _Remove (p->next) && _file->DeleteRecord (h);
  227. }
  228.  
  229.  
  230. /* ------------------------------------------------------------------ */
  231.  
  232.  
  233. // Retrieve the byte string associated with the given handle (first
  234. // parameter), and return it in the second. Return TRUE as the
  235. // function value if successful, FALSE on I/O error or invalid handle.
  236. bool CL_ByteStringStore::Retrieve  (CL_SlottedFileHandle h, CL_ByteString&
  237.                                    value) const
  238. {
  239.     CL_SlottedFileHandle next;
  240.     
  241.     return _Retrieve (h, value, next);
  242. }
  243.  
  244.  
  245.  
  246. /* ------------------------------------------------------------------ */
  247.  
  248. // Modify the byte string associated with the given handle (first
  249. // parameter) to be equal to the second. Note that the length of the
  250. // second parameter need not bear any relationship to the length of
  251. // the string currently associated with the given handle.
  252. //     Return TRUE as the function value if successful, FALSE on I/O
  253. // error or invalid handle.
  254. bool CL_ByteStringStore::Modify (CL_SlottedFileHandle h, const CL_ByteArray& b)
  255. {
  256.     CL_ByteString slot (CHUNK_SIZE);
  257.     CL_SlottedFileHandle current = h;
  258.     // Read the first chunk
  259.     if (!_file->RetrieveRecord (h, slot.AsPtr()))
  260.         return FALSE;
  261.     PrimarySlot* p = (PrimarySlot*) slot.AsPtr();
  262.     long i = 0; // Count of #bytes in b that have been written out
  263.     long new_size = b.Size();
  264.     p->byteStringSize = new_size;
  265.     long offset = p->DataOffset();
  266.     uchar* data = b.AsPtr ();
  267.     SecondarySlot* q = (SecondarySlot*) slot.AsPtr(); 
  268.     while (i < new_size) {
  269.         long used = minl (CHUNK_SIZE - offset, new_size - i);
  270.         slot.CopyFrom (data, used, offset);
  271.         data += used;
  272.         i += used;
  273.     if (p->next == 0) break;
  274.         if (!_file->ModifyRecord (current, slot))
  275.             return 0L;
  276.         current = p->next;
  277.         offset = q->DataOffset();
  278.         if (!_file->RetrieveRecord (current, slot))
  279.             return FALSE;
  280.     }
  281.     if (i < new_size) {
  282.         // We've hit the end of the old list
  283.         q->next = _Add (data, new_size - i);
  284.     }
  285.     else {
  286.         // We've run out of data in the parameter array
  287.         _Remove (q->next);
  288.         q->next = 0L;
  289.     }
  290.     if (!_file->ModifyRecord (current, slot))
  291.         return FALSE;
  292.     return TRUE;
  293. }
  294.  
  295.  
  296.  
  297.  
  298. /* ------------------------------------------------------------------ */
  299.  
  300.  
  301.  
  302.  
  303.  
  304. bool CL_ByteStringStore::ReadHeader (CL_ByteString& header) const
  305. {
  306.     HeaderForSlottedFile hdr;
  307.     if (_file) {
  308.         _file->ReadHeader ((uchar*) &hdr);
  309.         return Retrieve (hdr.user_header, header);
  310.     }
  311.     return FALSE;
  312. }
  313.  
  314.  
  315.  
  316. /* ------------------------------------------------------------------ */
  317.  
  318.  
  319. // Write the parameter into the user-defined header. Returns
  320. // TRUE on success, FALSE on i/o error.
  321. bool CL_ByteStringStore::WriteHeader (const CL_ByteString& header)
  322. {
  323.     HeaderForSlottedFile hdr;
  324.     if (_file) {
  325.         _file->ReadHeader ((uchar*) &hdr);
  326.         return Modify (hdr.user_header, header);
  327.     }
  328.     return FALSE;
  329. }
  330.  
  331.  
  332.  
  333.  
  334.  
  335. /* ------------------------------------------------------------------ */
  336.  
  337.  
  338.  
  339. // Protected methods:
  340.  
  341.  
  342. /* ------------------------------------------------------------------ */
  343.  
  344.  
  345. CL_SlottedFileHandle CL_ByteStringStore::_Add (uchar* data, long data_size)
  346. {
  347.     if (data_size <= 0)
  348.         return 0;
  349.     CL_ByteString slot_data (CHUNK_SIZE);
  350.     SecondarySlot* p = (SecondarySlot*) slot_data.AsPtr();
  351.     CL_SlottedFileHandle ret_val = _file->AllocateSlot();
  352.     long i = 0;
  353.     long available = CHUNK_SIZE - p->DataOffset();
  354.     CL_SlottedFileHandle current = ret_val;
  355.     while (i < data_size) {
  356.         long leftover_data = data_size - i;
  357.         long used;
  358.         CL_SlottedFileHandle next;
  359.         if (leftover_data > available) {
  360.             used = available;
  361.             next = _file->AllocateSlot();
  362.         }
  363.         else {
  364.             used = leftover_data;
  365.             next = 0L;
  366.         }
  367.         p->next = next;
  368.         slot_data.CopyFrom (data, used, p->DataOffset());
  369.         if (!_file->ModifyRecord (current, slot_data))
  370.             return 0L;
  371.         current = next;
  372.         data += used;
  373.         i += used;
  374.     }
  375.     return ret_val;
  376. }
  377.  
  378.  
  379. /* ------------------------------------------------------------------ */
  380.  
  381. bool CL_ByteStringStore::_Remove (CL_SlottedFileHandle h)
  382. {
  383.     CL_ByteString slot (CHUNK_SIZE);
  384.     SecondarySlot* p = (SecondarySlot*) slot.AsPtr();
  385.     while (h != 0L) {
  386.         if (!_file->RetrieveRecord (h, slot))
  387.             return FALSE;
  388.         if (!_file->DeleteRecord (h))
  389.             return FALSE;
  390.         h = p->next;
  391.     }
  392.     return TRUE;
  393. }
  394.  
  395.  
  396.  
  397. /* ------------------------------------------------------------------ */
  398.  
  399. bool CL_ByteStringStore::_Retrieve  (CL_SlottedFileHandle h,
  400.                                     CL_ByteString& value,
  401.                                     CL_SlottedFileHandle& itr_next) const
  402. {
  403.     CL_ByteString slot (CHUNK_SIZE);
  404.     PrimarySlot* p = (PrimarySlot*) slot.AsPtr();
  405.  
  406.     // Read and copy the first chunk
  407.     if (!_file->RetrieveRecord (h, slot.AsPtr()))
  408.         return FALSE;
  409.     long size = p->byteStringSize;
  410.     if (!value.ChangeSize (size))
  411.         return FALSE;
  412.     itr_next = p->iter_next;
  413.     h = p->next;
  414.  
  415.     long count = minl (CHUNK_SIZE - p->DataOffset(), size);
  416.     value.CopyFrom ((uchar*) &p->data, count);
  417.  
  418.  
  419.     // Now read the remaining (secondary) chunks, if any:
  420.     SecondarySlot* q = (SecondarySlot*) slot.AsPtr();
  421.     uchar* out = value.AsPtr () + count;
  422.     CL_ByteArray in (q->data, CHUNK_SIZE - q->DataOffset());
  423.     while (h != 0L && count < size) {
  424.         if (!_file->RetrieveRecord (h, slot.AsPtr()))
  425.             return FALSE;
  426.         // Compute #usable bytes in this chunk:
  427.         long usable  = minl (size - count,  in.Size());
  428.         // Copy the data segment over
  429.         in.CopyTo (out, usable);
  430.         count += usable;
  431.         out += usable;
  432.         h = q->next;
  433.     }
  434. #ifdef ERROR_CHECKING
  435.     if (i < size || h != 0L)
  436.         CL_Error::Warning ("CL_ByteStringStore::_Retrieve: internal error:"
  437.                            " length mismatch");
  438. #endif
  439.     return TRUE;
  440. }
  441.  
  442.  
  443.  
  444.  
  445.  
  446.  
  447. CL_ByteStoreIterator::CL_ByteStoreIterator (const CL_ByteStringStore& s)
  448. : _store (s)
  449. {
  450. }
  451. CL_ByteStoreIterator::CL_ByteStoreIterator (const CL_ByteStoreIterator&
  452.                                             itr)
  453. : _store (itr._store)
  454. {
  455. }
  456.  
  457.  
  458.  
  459.  
  460.  
  461. /* ------------------------------------------------------------------ */
  462.  
  463. void CL_ByteStoreIterator::Reset ()
  464. {
  465.     HeaderForSlottedFile hdr;
  466.     if (_store._file) {
  467.         _store._file->ReadHeader ((uchar*) &hdr);
  468.         _next = hdr.iter_list_head;
  469.     }
  470.     else
  471.         _next = 0;
  472. }
  473.  
  474.  
  475.  
  476. /* ------------------------------------------------------------------ */
  477.  
  478. CL_SlottedFileHandle CL_ByteStoreIterator::Next (CL_ByteString& b)
  479. {
  480.     if (_next == 0 || !_store._file)
  481.         return 0;
  482.     CL_SlottedFileHandle h = _next;
  483.     if (!_store._Retrieve (h, b, _next))
  484.         return FALSE;
  485.     return h;
  486. }
  487.  
  488.  
  489.