home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / Jikes / src / jcl / jcl_dynamic.h < prev    next >
Encoding:
C/C++ Source or Header  |  1999-12-09  |  7.4 KB  |  254 lines
  1. // $Id: jcl_dynamic.h,v 1.2 1999/12/09 18:02:26 lord Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #ifndef jcl_DYNAMIC_INCLUDED
  11. #define jcl_DYNAMIC_INCLUDED
  12.  
  13. #include <stdlib.h>
  14. #include <string.h>
  15.  
  16. //
  17. // This DynamicArray template class can be used to construct a dynamic
  18. // array of arbitrary objects. The space for the array is allocated in
  19. // blocks of size 2**LOG_BLKSIZE. In declaring a dynamic array the user
  20. // may specify a value for LOG_BLKSIZE which by default is 10. Also,
  21. // as the array is implemented using a base+offset strategy, the user
  22. // may also specify the number of "slots" to add to the base when the
  23. // current base runs out of space. Each slot points to a block.
  24. //
  25. template <class T, int LOG_BLKSIZE = 10, int BASE_INCREMENT = 16>
  26. class DynamicArray
  27. {
  28.     T **base;
  29.     int base_size,
  30.         top,
  31.         size;
  32.  
  33.     //
  34.     // Reallocate the base and initialize the new elements to NULL.
  35.     //
  36.     void reallocate_base();
  37.  
  38.     //
  39.     // Allocate another block of storage for the dynamic array.
  40.     //
  41.     void allocate_more_space();
  42.  
  43. public:
  44.  
  45.     //
  46.     // This function is invoked with an integer argument n. It ensures
  47.     // that enough space is allocated for n elements in the dynamic array.
  48.     // I.e., that the array will be indexable in the range  (0..n-1)
  49.     //
  50.     // Note that this function can be used as a garbage collector.  When
  51.     // invoked with no argument(or 0), it frees up all dynamic space that
  52.     // was allocated for the array.
  53.     //
  54.     void resize(const int n = 0);
  55.  
  56.     //
  57.     // This function is used to reset the size of a dynamic array without
  58.     // allocating or deallocting space. It may be invoked with an integer 
  59.     // argument n which indicates the new size or with no argument which
  60.     // indicates that the size should be reset to 0.
  61.     //
  62.     void reset(const int n = 0)
  63.     {
  64.         if (n < 0 || n >= size)
  65.             /* throw range exception */ ;
  66.         top = n;
  67.     }
  68.  
  69.     //
  70.     // Return length of the dynamic array.
  71.     //
  72.     int length() { return top; }
  73.  
  74.     //
  75.     // Return a reference to the ith element of the dynamic array.
  76.     //
  77.     // Note that no check is made here to ensure that 0 <= i < top.
  78.     // Such a check might be useful for debugging and a range exception
  79.     // should be thrown if it yields true.
  80.     //
  81.     T& operator[](const int i) { return base[i >> LOG_BLKSIZE][i]; }
  82.  
  83.     //
  84.     // Add an element to the dynamic array and return the top index.
  85.     //
  86.     int next_index()
  87.     {
  88.         int i = top++;
  89.         if (i == size)
  90.             allocate_more_space();
  91.         return i;
  92.     }
  93.  
  94.     //
  95.     // Add an element to the dynamic array and return a reference to
  96.     // that new element. 
  97.     //
  98.     T& next() { int i = next_index(); return base[i >> LOG_BLKSIZE][i]; }
  99.  
  100.     //
  101.     // Assignment of a dynamic array to another.
  102.     //
  103.     DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>&
  104.         operator=(const DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>& rhs)
  105.     {
  106.         if (this != &rhs)
  107.         {
  108.             resize(rhs.top);
  109.             for (int i = 0; i < rhs.top; i++)
  110.                 base[i >> LOG_BLKSIZE][i] = rhs.base[i >> LOG_BLKSIZE][i];
  111.         }
  112.  
  113.         return *this;
  114.     }
  115.  
  116.     //
  117.     // Constructor of a dynamic array.
  118.     //
  119.     DynamicArray(const int n = 0)
  120.     {
  121.         base_size = 0;
  122.         size = 0;
  123.         base = NULL;
  124.         resize(n);
  125.     }
  126.  
  127.     //
  128.     // Initialization of a dynamic array.
  129.     //
  130.     DynamicArray(const DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>& rhs)
  131.     {
  132.         base_size = 0;
  133.         size = 0;
  134.         base = NULL;
  135.         *this = rhs;
  136.     }
  137.  
  138.     //
  139.     // Destructor of a dynamic array.
  140.     //
  141.     ~DynamicArray() { resize(0); }
  142. };
  143.  
  144. //
  145. // Reallocate the base and initialize the new elements to null.
  146. //
  147. template <class T, int LOG_BLKSIZE, int BASE_INCREMENT>
  148.     void DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>::reallocate_base()
  149.     {
  150.         int old_base_size = base_size;
  151.         T **old_base = base;
  152.     
  153.         base_size += BASE_INCREMENT;
  154.         base = new T*[base_size];
  155.     
  156.         if (old_base != NULL)
  157.             memmove(base, old_base, old_base_size * sizeof(T *));
  158.         memset(&base[old_base_size], 0, (base_size - old_base_size) * sizeof(T *));
  159.     }
  160.     
  161. //
  162. // Allocate another block of storage for the dynamic array.
  163. //
  164. template <class T, int LOG_BLKSIZE, int BASE_INCREMENT>
  165.     void DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>::allocate_more_space()
  166.     {
  167.         //
  168.         // The variable size always indicates the maximum number of
  169.         // elements that has been allocated for the array.
  170.         // Initially, it is set to 0 to indicate that the array is empty.
  171.         // The pool of available elements is divided into segments of size
  172.         // 2**log_blksize each. Each segment is pointed to by a slot in
  173.         // the array base.
  174.         //
  175.         // By dividing size by the size of the segment we obtain the
  176.         // index for the next segment in base. If base is full, it is
  177.         // reallocated.
  178.         //
  179.         //
  180.         int blksize = 1 << LOG_BLKSIZE;
  181.         int k = size >> LOG_BLKSIZE; /* which segment? */
  182.     
  183.         if (k == base_size)      // base overflowed? reallocate
  184.             reallocate_base();
  185.     
  186.         //
  187.         // We allocate a new segment and place its adjusted address in 
  188.         // base[k]. The adjustment allows us to index the segment directly,
  189.         // instead of having to perform a subtraction for each reference.
  190.         // See operator[] below.
  191.         //
  192.         base[k] = new T[blksize];
  193.         base[k] -= size;
  194.     
  195.         //
  196.         // Finally, we update SIZE.
  197.         //
  198.         size += blksize;
  199.     
  200.         return;
  201.     }
  202.  
  203. //
  204. // This function is invoked with an integer argument n. It ensures
  205. // that enough space is allocated for n elements in the dynamic array.
  206. // I.e., that the array will be indexable in the range  (0..n-1)
  207. //
  208. // Note that this function can be used as a garbage collector.  When
  209. // invoked with no argument(or 0), it frees up all dynamic space that
  210. // was allocated for the array.
  211. //
  212. template <class T, int LOG_BLKSIZE, int BASE_INCREMENT>
  213.     void DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>::resize(const int n)
  214.     {
  215.         //
  216.         // If array did not previously contain enough space, allocate
  217.         // the necessary additional space. Otherwise, if the array had
  218.         // more blocks than are needed, release the extra blocks.
  219.         //
  220.         if (n > size)
  221.         {
  222.             do
  223.             {
  224.                 allocate_more_space();
  225.             } while (n > size);
  226.         }
  227.         else if (n < size)
  228.         {
  229.             // slot is the index of the base element whose block
  230.             // will contain the (n-1)th element.
  231.             int blksize = 1 << LOG_BLKSIZE;
  232.             int slot = (n <= 0 ? -1 : (n - 1) >> LOG_BLKSIZE);
  233.     
  234.             for (int k = (size >> LOG_BLKSIZE) - 1; k > slot; k--)
  235.             {
  236.                 size -= blksize;
  237.                 base[k] += size;
  238.                 delete [] base[k];
  239.                 base[k] = NULL;
  240.             }
  241.     
  242.             if (slot < 0)
  243.             {
  244.                 delete [] base;
  245.                 base = NULL;
  246.                 base_size = 0;
  247.             }
  248.         }
  249.     
  250.         top  = n;
  251.     }
  252.     
  253. #endif /* #ifndef DYNAMIC_INCLUDED */
  254.