home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / db02_src.zip / mserv.cc < prev    next >
C/C++ Source or Header  |  1993-11-05  |  15KB  |  684 lines
  1. /**************************************************************************
  2.  * Source Id :
  3.  *
  4.  * $Id: mserv.cc,v 1.10 1993/10/24 09:14:11 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.  *  mserv.cc:
  24.  *     A memory server. Effectively a malloc style space allocator in
  25.  *     a file to provide variable length records.
  26.  *
  27.  *  Original Author : Kev
  28.  *
  29.  *-------------------------------------------------------------------------
  30.  * Revision History:
  31.  *
  32.  * $Log: mserv.cc,v $
  33. // Revision 1.10  1993/10/24  09:14:11  kevinl
  34. // Fixed empty string problem
  35. //
  36. // Revision 1.9  1993/10/19  11:25:06  kevinl
  37. // Removed use of operator=(int) on dbData's
  38. //
  39. // Revision 1.8  1993/09/26  06:40:32  kevinl
  40. // Added dbData support
  41. //
  42. // Revision 1.7  1993/08/29  10:46:26  kevinl
  43. // A small assertion
  44. //
  45. // Revision 1.6  1993/07/19  11:57:13  kevinl
  46. // Fixed up constant initialisation
  47. //
  48. // Revision 1.5  1993/07/11  09:42:05  kevinl
  49. // Changed String to dbString
  50. //
  51. // Revision 1.4  1993/07/02  05:18:37  kevinl
  52. // delString added
  53. //
  54. // Revision 1.3  1993/06/23  05:21:22  kevinl
  55. // Mallocs are now in angular brackets
  56. //
  57. // Revision 1.2  1993/06/20  13:40:17  kevinl
  58. // Fixed multiple mallocs
  59. // Added extra error strings to some returns
  60. // Size/back in wrong order in getString. Also reduce size by 2 longs in getString
  61. // Removed extra char* in getString. Now manipulate String directly
  62. // writes fill in padding so last record will read properly
  63. //
  64. // Revision 1.1  1993/06/18  12:28:43  kevinl
  65. // Initial revision
  66. //
  67.  **************************************************************************/
  68.  
  69. #if !defined(MALLOC_H_MISSING) && !defined(MALLOC_H_INCLUDED)
  70. extern "C" {
  71. #include <malloc.h>
  72. }
  73. #define MALLOC_H_INCLUDED
  74. #endif
  75. #include <mserv.h>
  76.  
  77. const unsigned long memServer::GRAN = 1<<3;
  78. const long memServer::END_HEADER = 12;
  79. const long memServer::EXTRA = 8;
  80.  
  81. void
  82. memServer::readHeader(void)
  83. {
  84.     mRead(startDelChain, 0);
  85.     mRead(endDelChain);
  86.     mRead(lastEntry);
  87. }
  88.  
  89. void
  90. memServer::writeHeader(void)
  91. {
  92.     mWrite(startDelChain, 0);
  93.     mWrite(endDelChain);
  94.     mWrite(lastEntry);
  95. }
  96.  
  97. void
  98. memServer::setNextFree(void)
  99. {
  100.     if (lastEntry)
  101.     {
  102.         // Read in the size of the last entry
  103.         mRead(nextFree, lastEntry);
  104.         if (nextFree < 0) nextFree = -nextFree;
  105.         nextFree+=lastEntry;
  106.     }
  107.     else
  108.         nextFree = (END_HEADER + GRAN - 1) & ~(GRAN-1);
  109. }
  110.  
  111. memServer::memServer(const char* name)
  112. {
  113. #ifdef __BORLANDC__
  114.     fd = open(name,O_RDWR | O_BINARY);
  115. #elif defined(__SASC)
  116.     fd = open((char*)name,O_RDWR | O_BINARY);
  117. #else
  118.     fd = open(name,O_RDWR);
  119. #endif
  120.  
  121.     if (fd==-1) return;
  122.     readHeader();
  123.     setNextFree();
  124. }
  125.  
  126. dbError
  127. memServer::createMem(const char* name)
  128. {
  129. #ifdef __BORLANDC__
  130.     fd = open(name,O_CREAT | O_RDWR | O_BINARY, 0644);
  131. #elif defined(__SASC)
  132.     fd = open((char*)name,O_CREAT | O_RDWR | O_BINARY, 0644);
  133. #else
  134.     fd = open(name,O_CREAT | O_RDWR | O_TRUNC, 0644);
  135. #endif
  136.     if (fd==-1)
  137.         return dbErr(db_err);
  138.  
  139.     startDelChain = 0;
  140.     endDelChain = 0;
  141.     lastEntry = 0;
  142.     writeHeader();
  143.     setNextFree();
  144.     return dbErr(db_ok);
  145. }
  146.     
  147. dbError
  148. memServer::getString(dbData& st, long off)
  149. {
  150.     // If the string doesn't have an offset it is meant to be null 
  151.  
  152.     if (off == 0) {
  153.         st.dispose();
  154.         return dbErr(db_ok);
  155.     }
  156.  
  157.     if (fd == -1)
  158.         return dbErr(db_notopen);
  159.  
  160.     if ((off < END_HEADER) || (off & (GRAN-1)))
  161.         return dbErr(db_range, "Granularity problem"); // Must be on multiple of granularity
  162.  
  163.     if (off > nextFree)
  164.         return dbErr(db_eof, "Offset too high"); // Can't be off the end
  165.  
  166.     if (mSeek(off) != off)
  167.         return dbErr(db_eof, "Seek error");
  168.  
  169.     long size; mRead(size); size -= 2*sizeof(long);
  170.     long back; mRead(back);
  171.  
  172.     if (size == 0) {
  173.         st.dispose();
  174.         return dbErr(db_ok);
  175.     }
  176.  
  177. #if DEBUG
  178.     cout << "getString request: " << off << D(lastEntry) << D(nextFree) << D(size) << endl;
  179. #endif
  180.     st.setSize(size+1);
  181.     if (read(fd, (char*)st, size) != size)
  182.     {
  183. #if DEBUG
  184.         cout << "Actually managed to read " << k << endl;
  185. #endif
  186.         return dbErr(db_eof, "Problem reading from file");
  187.     }
  188.  
  189.     return dbErr(db_ok);
  190. }
  191.  
  192. // Remove the deleted segment at off from the delete chain
  193.  
  194. dbError
  195. memServer::removeDel(long off)
  196. {
  197.     if (mSeek(off) != off)
  198.         return dbErr(db_eof);
  199.     long size; mRead(size);
  200.     long back; mRead(back);
  201.     long prev; mRead(prev);
  202.     long next; mRead(next);
  203.     if (prev == 0)
  204.     {
  205.         startDelChain = next;
  206.         writeHeader();
  207.     }
  208.     else
  209.     {
  210.         // change the 'next delete' pointer of the previous deleted block
  211.         mWrite(next, prev+(3*sizeof(long)));
  212.     }
  213.  
  214.     if (next == 0)
  215.     {
  216.         endDelChain = prev;
  217.         writeHeader();
  218.     }
  219.     else
  220.     {
  221.         // change the 'prev delete' pointer of the next deleted block
  222.         mWrite(prev, next+2*sizeof(long));
  223.     }
  224.     return dbErr(db_ok);
  225. }
  226.  
  227. // Find a block of size size or make a new one
  228.  
  229. long
  230. memServer::getChunk(long& newSize, long& back)
  231. {
  232.     long delSize;
  233.     long cur = startDelChain;
  234.     newSize = (newSize+GRAN-1) & ~(GRAN-1);
  235.     long actualSize = newSize+EXTRA;
  236. #if DEBUG
  237.     cout << "getChunk:" << D(newSize) << D(actualSize) << endl;
  238. #endif
  239.     while (cur)
  240.     {
  241.         mRead(delSize, cur);
  242.         mRead(back);
  243. #if DEBUG
  244.         cout << "getChunk:" << D(cur) << D(delSize) << D(back) << endl;
  245. #endif
  246.         if (delSize <= -actualSize) // Got one!
  247.         {
  248.             // Remove the block form the delete chain
  249.             removeDel(cur);
  250.  
  251.             // If this block was too big, make a smaller block
  252.             // and then delete it
  253. #if DEBUG
  254.         cout << "got one:" << D(actualSize) << D(delSize) << D(-2*EXTRA) << endl;
  255. #endif
  256.             // Does the new block leave enough for a deleted bit on the end?
  257.  
  258.             if (actualSize + delSize <= -2*EXTRA)
  259.             {
  260.                 long extraSize = -delSize-actualSize;
  261.                 long where = cur+actualSize;
  262.                 mWrite(actualSize, cur);
  263.                 mWrite(extraSize, where);
  264.                 mWrite(cur); // set the back pointer
  265.                 if (cur == lastEntry)
  266.                 {
  267.                     lastEntry = where;
  268.                     nextFree = cur-delSize;
  269.                 }
  270.                 else
  271.                 {
  272.                     mWrite(where, cur-delSize+sizeof(long)); // set back of next
  273.                 }
  274.                 deleteBlock(where);
  275.             }
  276.             else
  277.             { // we have to increase newSize a bit (max 2*EXTRA)
  278.                 actualSize = -delSize;
  279.                 newSize = actualSize-EXTRA;
  280.             }
  281.             return cur;
  282.         }
  283.         mRead(cur, cur+3*sizeof(long));
  284.     }
  285.  
  286. #if DEBUG
  287.     cout << "getChunk:" << D(lastEntry) << D(nextFree) << D(cur) << endl;
  288. #endif
  289.     // We have to make some more space at the end
  290.     back=lastEntry;
  291.     cur=lastEntry=nextFree;
  292.     nextFree+=actualSize;
  293.     writeHeader();
  294. #if DEBUG
  295.     cout << "getChunk:" << D(lastEntry) << D(nextFree) << D(cur) << endl;
  296. #endif
  297.     return cur;
  298. }
  299.  
  300. dbError
  301. memServer::delString(dbData& s, long& off)
  302. {
  303.     if (off == 0) {
  304.         s.dispose();
  305.         return dbErr(db_ok);
  306.     }
  307.  
  308.     dbError err = getString(s, off);
  309.     if (err != db_ok)
  310.         return err;
  311.  
  312.     deleteBlock(off);
  313.     return dbErr(db_ok);
  314. }
  315.  
  316. void
  317. memServer::deleteBlock(long off)
  318. {
  319.     // Find the newly nuked block and get the size and back pointer
  320.     long size; mRead(size, off);
  321.     long back; mRead(back);
  322.     long done = 0;
  323.  
  324.     if (back) // Let's see if it is also deleted
  325.     {
  326.         long backSize; mRead(backSize, back);
  327.         if (backSize < 0) // It's deleted
  328.         {
  329.             // Fix the size of the previous block
  330.             backSize -= size;
  331.             mWrite(backSize, back);
  332.  
  333.             // Fix the back pointer of the next block
  334.             mWrite(back, off+size+sizeof(long));
  335.             done = 1;
  336.             off = back;
  337.             size = -backSize;
  338.         }
  339.     }
  340.  
  341.     if (off != lastEntry)
  342.     {
  343.         long next = off + size;
  344.         long nextSize; mRead(nextSize, next);
  345. #if DEBUG
  346.         cout << "Check next" << D(next) << D(nextSize) << endl;
  347. #endif
  348.         if (nextSize < 0)
  349.         { // We have a deleted block
  350.             // Remove it from the deleted chain
  351.             removeDel(next);
  352.  
  353.             // Fix the backward pointer of the next block
  354.             if (lastEntry == next)
  355.             {
  356.                 // The next block was the last, the new one is now
  357.                 lastEntry = off;
  358.             }
  359.             else
  360.             {
  361.                 // Fix the next block's back pointer
  362. #ifdef DEBUG
  363.                 cout << "Fixing back" << D(off) << D(off+size-nextSize+sizeof(long)) << endl;
  364. #endif
  365.                 mWrite(off, off + size - nextSize + sizeof(long));
  366.             }
  367.             
  368.             // Fix the size of the deleted block
  369.             size = -size + nextSize;
  370.             if (done)
  371.             {
  372.                 // We're dealing with a deleted block
  373.                 mWrite(size, off);
  374.             }
  375.             else
  376.             {
  377.                 // Need to delete it below
  378.                 size = -size;
  379.             }
  380.         }
  381.     }
  382.  
  383.     if (!done)
  384.     {
  385.         // If there is already a chain...
  386.         if (endDelChain)
  387.         {
  388.             // Find end of del chain + size & back &prev
  389.             // Previous pointer stays the same
  390.  
  391.             // Next pointer is now the new block
  392.             mWrite(off, endDelChain+3*sizeof(long));
  393.         }
  394.  
  395.         size = -size;
  396.         // put it back negative
  397.         mWrite(size, off);
  398.  
  399.         // Prev is the old endDelChain
  400.         mWrite(endDelChain, off+2*sizeof(long));
  401.         // Next is 0
  402.         long next=0; mWrite(next);
  403.  
  404.         if (!startDelChain)
  405.             startDelChain=off;
  406.         endDelChain=off;
  407.         writeHeader();
  408.     }
  409. }
  410.  
  411. dbError
  412. memServer::putString(dbData& s, long& off)
  413. {
  414.     if (fd == -1)
  415.         return dbErr(db_notopen);
  416.  
  417.     // Must be on multiple of granularity (can be 0)
  418.     if (off && (off < END_HEADER) || (off & (GRAN-1)))
  419.         return dbErr(db_range, "Bad offset");
  420.  
  421.     long len = s.len();
  422.  
  423.     // If the string is null length. It should not be added in and the off
  424.     // should become 0. Before doing that however, we delete the string
  425.     // that was there.
  426.     if (len < 1)
  427.         return delString(s, off);
  428.  
  429.     if (off > nextFree)
  430.         return dbErr(db_eof); // Can't be off the end
  431.     
  432.     if (off)
  433.         if (mSeek(off) != off)
  434.             return dbErr(db_eof);
  435.  
  436.     // no -1 on length so that we have space for the 0
  437.     long newSize = (len + GRAN) & ~(GRAN-1);
  438.     long actualSize = newSize+EXTRA;
  439.     long size = 0;
  440.     long back = 0;
  441.     if (off)
  442.     {
  443.         mRead(size);
  444.         mRead(back);
  445.     }
  446.  
  447.     long newoff = off;
  448.  
  449.     if (actualSize > size)
  450.     {
  451. #if DEBUG
  452.         cout << "It's too big!" D(actualSize) << D(size) << endl;
  453. #endif
  454.         bool gotit = false;
  455.         long next = off + size;
  456.         if (off && off == lastEntry) // Just extend it!
  457.         {
  458. #if DEBUG
  459.             cout << "Extending last entry" << endl;
  460. #endif
  461.             newoff = off;
  462.             gotit = true;
  463.             nextFree+=actualSize-size;
  464.         }
  465.         if (off && !gotit && next < nextFree) // We're in range
  466.         {
  467. #if DEBUG
  468.             cout << "Checking next block at " << next << D(nextFree) << endl;
  469. #endif
  470.             // Is the next block free and big enough?
  471.             if (mSeek(next) != next)
  472.                 return dbErr(db_err);
  473.             long delsize; mRead(delsize);
  474. #if DEBUG
  475.             cout << "next block sizes:" << D(size) << D(delsize) << D(size-delsize) << D(actualSize) << endl;
  476. #endif
  477.             if (size-delsize >= actualSize)
  478.             {
  479. #if DEBUG
  480.                 cout << "...Got one" << D(delsize) << D(newSize) << D(-actualSize) << endl;
  481. #endif
  482.                 newoff = off;
  483.                 actualSize = size-delsize;
  484.                 gotit = true;
  485.                 removeDel(next);
  486. #if DEBUG
  487.                 cout << "Fix back of next" << D(off) << D(actualSize) << endl;
  488. #endif
  489.                 mWrite(off, off+actualSize+sizeof(long));
  490.             }
  491.         }
  492.         if (off && !gotit && back >= END_HEADER) // We're in backward range
  493.         {
  494. #if DEBUG
  495.             cout << "Checking previous block" << endl;
  496. #endif
  497.             if (mSeek(back) != back)
  498.                 return dbErr(db_err);
  499.             long delsize; mRead(delsize);
  500. #if DEBUG
  501.             cout << "previous block sizes:" << D(size) << D(delsize) << D(size-delsize) << D(actualSize) << endl;
  502. #endif
  503.             if (size-delsize >= actualSize)
  504.             {
  505. #if DEBUG
  506.                 cout << "...Got one" << endl;
  507. #endif
  508.                 gotit = true;
  509.  
  510.                 // New position is previous block
  511.                 newoff = back;
  512.  
  513.                 // And get new previous
  514.                 mRead(back);
  515.  
  516.                 // Put this block number into next blocks previous because
  517.                 // we are joing the two blocks.
  518.                 mWrite(newoff, next+sizeof(long));
  519.  
  520.                 off = 0; // So we don't delete it!
  521.                 removeDel(newoff);
  522. #if DEBUG
  523.                 cout << "removing:" << D(newoff) << D(back) << endl;
  524. #endif
  525.                 actualSize = size-delsize;
  526.             }
  527.         }
  528.         if (!gotit)
  529.         {
  530. #if DEBUG
  531.             cout << "Get a new chunk then" << endl;
  532. #endif
  533.             newoff = getChunk(newSize, back);
  534. #if DEBUG
  535.             if (actualSize != newSize+EXTRA)
  536.                 cout << "Sizes changed" << D(actualSize) << D(newSize) << endl;
  537. #endif
  538.             actualSize = newSize+EXTRA; // In case newSize changes
  539.         }
  540.     }
  541.     //
  542.     // Is it shorter than the block and thus leaves some space for a
  543.     // deleted block?
  544.     //
  545.     else if (off && (size - actualSize > 2*EXTRA))
  546.     {
  547. #if DEBUG
  548.         cout << "Making a smaller deleted block" << endl;
  549. #endif
  550.         long extraSize = size - actualSize;
  551.         long where = off+actualSize;
  552.         mWrite(extraSize, where);
  553.         mWrite(newoff); // set the back pointer
  554.         if (lastEntry == off)
  555.         {
  556.             lastEntry = where;
  557.             nextFree = newoff+size;
  558.         }
  559.         else
  560.         {
  561.             // set back of next
  562.             mWrite(where, newoff+size+sizeof(long));
  563.         }
  564.         deleteBlock(where);
  565.     }
  566.     else
  567.     {
  568. #if DEBUG
  569.         cout << "Leaving exactly as it was! Will use size" << D(actualSize) << D(size) << endl;
  570. #endif
  571.         actualSize = size;
  572.     }
  573.  
  574. #if DEBUG
  575.     cout << "Selected a spot" << D(newoff) << D(back) << D(actualSize) << endl;
  576. #endif
  577.     // OK, now newoff points where we want and it is big enough.
  578.     mWrite(actualSize, newoff);
  579.     mWrite(back);
  580.  
  581.     // This is causing problems at the end of the file. We should add
  582.     // In the padding space so that the last entry is big enough.
  583.     //write(fd, (char*)s, len+1);
  584.     write(fd, (char*)s, newSize);
  585.  
  586.     if (off && (newoff != off)) // It's moved
  587.     {
  588. #if DEBUG
  589.         cout << "Deleting old block" << D(off) << endl;
  590. #endif
  591.         deleteBlock(off);
  592.     }
  593.  
  594.     off = newoff;
  595.     return dbErr(db_ok);
  596. };
  597.  
  598. bool
  599. memServer::checkChain(ostream& o, bool dump)
  600. {
  601.     char s[20];
  602.     if (dump)
  603.         o << D(startDelChain) << D(endDelChain) << D(lastEntry) << D(nextFree) << endl;
  604.     long cur = (END_HEADER + GRAN - 1) & ~(GRAN-1);
  605.     long last = 0;
  606.  
  607.     while (cur < nextFree)
  608.     {
  609.         long next = cur;
  610.         long size; mRead(size, cur);
  611.         long back; mRead(back);
  612.         if (dump)
  613.             o << D(cur) << D(size) << D(back);
  614.         if (size < 0)
  615.         {
  616.             long prevDel; mRead(prevDel);
  617.             long nextDel; mRead(nextDel);
  618.             if (dump)
  619.                 o << D(prevDel) << D(nextDel);
  620.             if (prevDel < 0 || prevDel > lastEntry || nextDel < 0 || nextDel > lastEntry)
  621.             {
  622.                 o << "Bad Del pointers" << endl;
  623.                 return false;
  624.             }
  625.             next-=size;
  626.         }
  627.         else
  628.         {
  629.             read(fd, s, (size<10)?size:10);
  630.             if (dump)
  631.             {
  632.                 s[(size<10)?size:10]=0;
  633.                 o << "  " << s;
  634.             }
  635.             next+=size;
  636.         }
  637.         if (dump)
  638.             o << endl;
  639.         if (back != last)
  640.         {
  641.             o << "Back pointer mismatch" << endl;
  642.             return false;
  643.         }
  644.         last = cur;
  645.         cur = next;
  646.     }
  647.     return true;
  648. }
  649.  
  650. bool
  651. memServer::checkDeleteChain(ostream& o)
  652. {
  653.     // Check that the delete chain makes sense.
  654.     // This does not verify that there are no lost deleted entries
  655.  
  656.     long cur = startDelChain;
  657.     long last = 0;
  658.  
  659.     while (cur)
  660.     {
  661.         long size; mRead(size, cur);
  662.         long back; mRead(back);
  663.         long prev; mRead(prev);
  664.         long next; mRead(next);
  665.  
  666.         if (prev != last)
  667.         {
  668.             o << "Deleted Block " << cur << D(prev) << " !=" << D(last) << endl;
  669.             return false;
  670.         }
  671.  
  672.         last  = cur;
  673.         cur = next;
  674.     }
  675.  
  676.     if (last != endDelChain)
  677.     {
  678.         o << "Last block " << last << " !=" << D(endDelChain) << endl;
  679.         return false;
  680.     }
  681.  
  682.     return true;
  683. }
  684.