home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / sequence.cxx < prev    next >
C/C++ Source or Header  |  1994-10-14  |  8KB  |  284 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.  
  33.  
  34.  
  35.  
  36.  /* Tue Nov 16 22:10:33 1993 */
  37.  
  38.  
  39. #ifdef __GNUC__
  40. #pragma implementation
  41. #endif
  42.  
  43.  
  44.  
  45. #define _no_cl_sequence_typedefs_
  46. #define _no_cl_set_typedefs_
  47.  
  48. #include "base/seqimp.cxx"
  49.  
  50. #ifdef DEBUG
  51. #include "base/memory.h"
  52. #endif
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66. // Implementation of the SegmentedSequence class
  67.  
  68.  
  69.  
  70. struct SegDesc {
  71.     short _cap;  // Number of cells
  72.     long* _data; // The cells themselves
  73. };
  74.  
  75.  
  76.  
  77. // Addressing scheme: low 13 bits are offset; next higher 13 bits are
  78. // segment number. We maintain this invariant: there are _numSegs segments,
  79. // among which the first _numSegs-1 are "full", i.e., have 0x1fff+1 == 8192
  80. // cells. The remaining (last) segment will have the following size: if the
  81. // capacity needed is c, then the first _numSegs-1 segments contribute
  82. // (_numSegs-1)*8192 bytes (as above), so the last segment will have the
  83. // nearest higher power of 2 above c - (_numSegs-1)*8192 cells.
  84.  
  85.  
  86.  
  87.  
  88. static short NearestHigher2Power (short l)
  89. {
  90.     // This function only works for l <= 16383
  91.     if (l == 0)
  92.         return 0;
  93.     short mask = 0x4000;
  94.     short old_mask;
  95.     do {
  96.         old_mask = mask;
  97.         mask >>= 1;
  98.     } while (!(mask & l));
  99.     return (mask == l) ? l : old_mask;
  100. }
  101.  
  102. SegmentedSequence::SegmentedSequence (long initial_cap)
  103. {
  104.     _totalCap = maxl (initial_cap, 8);
  105.     _numSegs   = (short) ((_totalCap >> 13) + 1);
  106.     _segs = new SegDesc [_numSegs];
  107.     if (!_segs) {
  108.         // No memory
  109.         _totalCap = _numSegs = 0;
  110.         return;
  111.     }
  112.     for (short i = 0; i < _numSegs-1; i++) {
  113.         _segs[i]._data = new long[0x1fff + 1];
  114.         if (!_segs[i]._data) break;
  115.         _segs[i]._cap = 0x1fff + 1;
  116.     }
  117.     _numSegs = i;
  118.     short needed = (short) (_totalCap & 0x1fff); // Size of last segment
  119.     if (needed) {
  120.         needed = NearestHigher2Power (needed);
  121.  
  122.         // Allocate segment
  123.         _segs[i]._data = new long[needed];
  124.         if (!_segs[i]._data)
  125.             return;
  126.         _numSegs++;
  127.         _segs[i]._cap = needed;
  128.         _totalCap = ((_numSegs-1) << 13) | needed;
  129.     }
  130. }
  131.  
  132. SegmentedSequence::~SegmentedSequence ()
  133. {
  134.     for (short i = 0; i < _numSegs; i++)
  135.         if (_segs[i]._data)
  136.             delete [] _segs[i]._data;
  137.     delete [] _segs;
  138. }
  139.  
  140.  
  141. CL_VoidPtr& SegmentedSequence::operator[] (long index)
  142. {
  143.     return (CL_VoidPtr&) (_segs[index >> 13]._data[index & 0x1fff]);
  144. }
  145.  
  146.  
  147.  
  148.  
  149.  
  150. bool SegmentedSequence::ResizeTo    (long new_cap)
  151. {
  152.     if (_totalCap >= new_cap && _totalCap < new_cap + 0x1fff + 1)
  153.         return TRUE;
  154.  
  155.     // First let's reallocate the "segments" array
  156.     short segs_needed = (short) (new_cap >> 13);  // Total # segments needed
  157.     if (new_cap & 0x1fff)
  158.         segs_needed++;
  159.     short seg_diff = segs_needed - _numSegs; // Number of new segments
  160.                                              // (may be positive or negative)
  161.     if (segs_needed != _numSegs) { // We need a different number of segments
  162.         SegDesc* dsc = new SegDesc[segs_needed];
  163.         if (!dsc)
  164.             return FALSE;
  165.         short n = (short) minl (_numSegs, segs_needed);
  166.         for (short i = 0; i < n; i++)
  167.             dsc[i] = _segs[i];
  168.         if (n < _numSegs) {
  169.             // If the number of segments is less than before, get rid of
  170.             // excess segments
  171.             for (i = n; i < _numSegs; i++)
  172.                 delete [] _segs[i]._data;
  173.             _numSegs = n;
  174.         }
  175.         if (_segs)
  176.             delete [] _segs;
  177.         _segs = dsc;
  178.     }    
  179.     if (new_cap > _totalCap) { // Need to grow
  180.         SegDesc lastSeg = {0, 0};
  181.         if ((_totalCap & 0x1fff) == 0) {
  182.             // Our capacity is currently an exact multiple of 8192, so
  183.             // retain the current last segment in the new data structure
  184.             for (short i = _numSegs; i <= segs_needed-2; i++) {
  185.                 _segs[i]._data = new long [0x1fff + 1];
  186.                 if (!_segs[i]._data)
  187.                     return FALSE;
  188.                 _segs[i]._cap = 0x1fff + 1;
  189.             }
  190.         }
  191.         else {
  192.             // Our current capacity is  not an exact multiple of 8192, so
  193.             // we'll grow the last segment
  194.             lastSeg = _segs[_numSegs-1];
  195.             if (seg_diff >= 1) {
  196.                 // Allocate the all but the last segment
  197.                 for (short i = _numSegs-1; i <= segs_needed-2; i++) {
  198.                     _segs[i]._data = new long [0x1fff + 1];
  199.                     if (!_segs[i]._data)
  200.                         return FALSE;
  201.                     _segs[i]._cap = 0x1fff + 1;
  202.                 }
  203.             }
  204.         }
  205.         // Allocate the new last segment
  206.         short last_seg_size = NearestHigher2Power ((short) (new_cap & 0x1fff)); 
  207.         if (last_seg_size == 0)
  208.             last_seg_size = 0x1fff + 1;
  209.         else
  210.             last_seg_size = (short) maxl (8, last_seg_size);
  211.         long* p = new long [last_seg_size];
  212.         if (!p)
  213.             return FALSE;
  214.         short last_seg_index = _numSegs + seg_diff - 1;
  215.         _segs[last_seg_index]._data = p;
  216.         _segs[last_seg_index]._cap = last_seg_size;
  217.  
  218.         if (lastSeg._cap != 0) {
  219.             // The old capacity was not an exact multiple of 8192, so we
  220.             // must have grown the last segment. Therefore,
  221.             // copy back the contents of the old last segment
  222.             for (short i = 0; i < lastSeg._cap; i++)
  223.                 _segs[_numSegs-1]._data[i] = lastSeg._data[i];
  224.             delete [] lastSeg._data;
  225.         }
  226.         _numSegs += seg_diff;
  227.         _totalCap = last_seg_size + (_numSegs-1) * (0x1fffL + 1);
  228.     }
  229.     else { // new_cap < totalCap
  230.         // We've already destroyed the excess segments; we just need to
  231.         // shrink the last segment
  232.  
  233.         short last_seg_size;
  234.         if (new_cap & 0x1fff) {
  235.             // The new capacity is not an exact multiple of 8192, so we
  236.             // have to shrink the last segment. Therefore,
  237.             // copy back the contents of the old last segment
  238.             last_seg_size = NearestHigher2Power ((short) (new_cap & 0x1fff)); 
  239.             if (last_seg_size == 0)
  240.                 last_seg_size = 0x1fff + 1;
  241.             else
  242.                 last_seg_size = (short) maxl (8, last_seg_size);
  243.             short current_cap = _segs[_numSegs-1]._cap;
  244.             if (last_seg_size*2 >= current_cap &&
  245.                 last_seg_size < current_cap) { 
  246.                 // We hang on to memory a little longer, if the shrinkage
  247.                 // is not too much
  248.                 return TRUE;
  249.             }
  250.             long* p = new long [last_seg_size];
  251.             if (!p)
  252.                 return FALSE;
  253.             short l = _numSegs-1;
  254.             short m = (short) minl (current_cap, last_seg_size);
  255.             for (short i = 0; i < m; i++)
  256.                 p[i] = _segs[l]._data[i];
  257.             delete _segs[l]._data;
  258.             _segs[l]._data = p;
  259.             _segs[l]._cap  = last_seg_size;
  260.         }
  261.         else
  262.             last_seg_size = 0x2000;
  263.         _numSegs = segs_needed;
  264.         _totalCap = last_seg_size + (_numSegs-1) * (0x1fffL + 1);
  265.     }
  266.     return TRUE;
  267. }
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276. #ifdef __BORLANDC__
  277. typedef CL_Sequence<CL_String> stringseq;
  278. typedef CL_Sequence<CL_ObjectPtr> objseq;
  279. typedef CL_Sequence<CL_VoidPtr> voidseq;
  280. // Instantiated here, instead of strgseq.cxx and objseq.cxx, because
  281. // otherwise CL_Sequence<long> is indirectly instantiated multiple times by
  282. // Borland C++.
  283. #endif
  284.