src/mem/gems_common/Vector.hh

   1 /*
   2  * Copyright (c) 1999-2005 Mark D. Hill and David A. Wood
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /*
  30  * Description: The Vector class is a generic container which acts
  31  * much like an array.  The Vector class handles dynamic sizing and
  32  * resizing as well as performing bounds checking on each access.  An
  33  * "insertAtBottom" operation is supported to allow adding elements to
  34  * the Vector much like you would add new elements to a linked list or
  35  * queue.
  36  */
  37
  38 #ifndef VECTOR_H
  39 #define VECTOR_H
  40
  41 #include "std-includes.hh"
  42
  43 template <class TYPE>
  44 class Vector
  45 {
  46 public:
  47   Vector();
  48   explicit Vector(int initial_size);  // Construct with an initial max size
  49   ~Vector();
  50   const TYPE& ref(int index) const;   // Get an element of the vector
  51   TYPE& ref(int index);               // Get an element of the vector
  52   void clear();                       // remove all elements of the vector
  53   void sortVector();                  // sort all elements using < operator
  54   int size() const { return m_size; }
  55   void setSize(int new_size);         // Increase size, reallocates memory as needed
  56   void expand(int num) { setSize(m_size+num); } // Increase size by num
  57   void increaseSize(int new_size, const TYPE& reset);    // and adds num of slots at the bottom set to reset value
  58   void insertAtTop(const TYPE& element);  // Increase size by one and set last element
  59     // FIXME - WARNING: insertAtTop is currently O(n) and needs to be fixed
  60   void insertAtBottom(const TYPE& element);  // Increase size by one and set last element
  61   TYPE sum() const;  // Uses the += operator to sum all the elements of the vector
  62   void deletePointers(); // Walks the Vector calling delete on all
  63                          // elements and sets them to NULL, can only
  64                          // be used when the TYPE is a pointer type.
  65   void removeFromTop(int num);  // removes elements from top
  66   void print(ostream& out) const;
  67
  68
  69   // Array Reference operator overloading
  70   const TYPE& operator[](int index) const { return ref(index); }
  71   TYPE& operator[](int index) { return ref(index); }
  72
  73   // Public copy constructor and assignment operator
  74   Vector(const Vector& vec);
  75   Vector<TYPE>& operator=(const Vector& vec);
  76 private:
  77
  78   void grow(int new_max_size);  // Expands vector to new_max_size
  79
  80   // Data members
  81   TYPE* m_vec;           // Array to hold the elements
  82   int m_size;            // Number of elements in use
  83   int m_max_size;        // Size of allocated array
  84 };
  85
  86 template <class TYPE>
  87 ostream& operator<<(ostream& out, const Vector<TYPE>& vec);
  88
  89 // *********************
  90
  91 template <class TYPE>
  92 Vector<TYPE>::Vector()
  93 {
  94   m_size = 0;
  95   m_max_size = 0;
  96   m_vec = NULL;
  97 }
  98
  99 template <class TYPE>
 100 Vector<TYPE>::Vector(int initial_size)
 101 {
 102   m_size = 0;
 103   m_max_size = initial_size;
 104   m_vec = NULL;
 105   grow(initial_size);
 106 }
 107
 108 template <class TYPE>
 109 Vector<TYPE>::~Vector()
 110 {
 111   delete [] m_vec;
 112 }
 113
 114 template <class TYPE>
 115 const TYPE& Vector<TYPE>::ref(int index) const
 116 {
 117 #ifndef NO_VECTOR_BOUNDS_CHECKS
 118   assert(m_size != 0);
 119   assert(index < m_size);
 120   assert(index >= 0);
 121 #endif
 122   return m_vec[index];
 123 }
 124
 125 template <class TYPE>
 126 TYPE& Vector<TYPE>::ref(int index)
 127 {
 128 #ifndef NO_VECTOR_BOUNDS_CHECKS
 129   assert(m_size != 0);
 130   assert(index < m_size);
 131   assert(index >= 0);
 132 #endif
 133   return m_vec[index];
 134 }
 135
 136
 137 template <class TYPE>
 138 void Vector<TYPE>::setSize(int new_size)
 139 {
 140   // FIXME - this should also decrease or shrink the size of the array at some point.
 141   if (new_size > m_max_size) {
 142     grow(max((m_max_size+1)*2, new_size));
 143   }
 144   m_size = new_size;
 145 #ifndef NO_VECTOR_BOUNDS_CHECKS
 146   assert(m_size <= m_max_size);
 147   assert(m_size >= 0);
 148 #endif
 149 }
 150
 151 template <class TYPE>
 152 inline
 153 void Vector<TYPE>::increaseSize(int new_size, const TYPE& reset)
 154 {
 155   assert(new_size >= m_size);
 156   if (new_size >= m_max_size) {
 157     grow(max((m_max_size+1)*2, new_size));
 158   }
 159   int old_size = m_size;
 160   m_size = new_size;
 161   for (int j = old_size; j < m_size; j++) {
 162     ref(j) = reset;
 163   }
 164
 165 #ifndef NO_VECTOR_BOUNDS_CHECKS
 166     assert(m_size <= m_max_size);
 167     assert(m_size >= 0);
 168 #endif
 169 }
 170
 171 template <class TYPE>
 172 inline
 173 void Vector<TYPE>::clear()
 174 {
 175   m_size = 0;
 176   m_max_size = 0;
 177   delete [] m_vec;
 178   m_vec = NULL;
 179 }
 180
 181 template <class TYPE>
 182 inline
 183 void Vector<TYPE>::sortVector()
 184 {
 185   sort(&m_vec[0], &m_vec[m_size]);
 186 }
 187
 188 template <class TYPE>
 189 inline
 190 void Vector<TYPE>::insertAtTop(const TYPE& element)
 191 {
 192   setSize(m_size+1);
 193   for (int i = m_size-1; i >= 1; i--) {
 194     ref(i) = ref(i-1);
 195   }
 196   ref(0) = element;
 197 }
 198
 199 template <class TYPE>
 200 inline
 201 void Vector<TYPE>::removeFromTop(int num)
 202 {
 203   if (num > m_size) {
 204     num = m_size;
 205   }
 206   for (int i = 0; i < m_size - num; i++) {
 207     m_vec[i] = m_vec[i+num];
 208   }
 209   m_size = m_size - num;
 210
 211 }
 212
 213 template <class TYPE>
 214 void Vector<TYPE>::insertAtBottom(const TYPE& element)
 215 {
 216   setSize(m_size+1);
 217   ref(m_size-1) = element;
 218 }
 219
 220 template <class TYPE>
 221 TYPE Vector<TYPE>::sum() const
 222 {
 223   assert(m_size > 0);
 224   TYPE sum = ref(0);
 225   for(int i=1; i<m_size; i++) {
 226     sum += ref(i);
 227   }
 228   return sum;
 229 }
 230
 231 template <class TYPE>
 232 void Vector<TYPE>::deletePointers()
 233 {
 234   assert(m_size >= 0);
 235   for(int i=0; i<m_size; i++) {
 236     // FIXME this function should be non-member function, otherwise this
 237     // prevent template instantiation for non-pointer types
 238     //
 239     // Also, there is warning of Switch.cc which use void* here
 240     delete ref(i);
 241     ref(i) = NULL;
 242   }
 243 }
 244
 245 template <class TYPE>
 246 void Vector<TYPE>::print(ostream& out) const
 247 {
 248   out << "[ ";
 249   for(int i=0; i<m_size; i++) {
 250     if (i != 0) {
 251       out << " ";
 252     }
 253     out << ref(i);
 254   }
 255   out << " ]";
 256   out << flush;
 257 }
 258
 259 // Copy constructor
 260 template <class TYPE>
 261 Vector<TYPE>::Vector(const Vector& vec)
 262 {
 263   // Setup the new memory
 264   m_size = vec.m_size;
 265   m_max_size = vec.m_max_size;
 266   if (m_max_size != 0) {
 267     m_vec = new TYPE[m_max_size];
 268     assert(m_vec != NULL);
 269   } else {
 270     m_vec = NULL;
 271   }
 272
 273   // Copy the elements of the array
 274   for(int i=0; i<m_size; i++) {
 275     m_vec[i] = vec.m_vec[i];  // Element copy
 276   }
 277 }
 278
 279 template <class TYPE>
 280 Vector<TYPE>& Vector<TYPE>::operator=(const Vector& vec)
 281 {
 282   if (this == &vec) {
 283     //    assert(0);
 284   } else {
 285     // Free the old memory
 286     delete [] m_vec;
 287
 288     // Setup the new memory
 289     m_size = vec.m_size;
 290     m_max_size = vec.m_max_size;
 291
 292     if (m_max_size != 0) {
 293       m_vec = new TYPE[m_max_size];
 294       assert(m_vec != NULL);
 295     } else {
 296       m_vec = NULL;
 297     }
 298
 299     // Copy the elements of the array
 300     for(int i=0; i<m_size; i++) {
 301       m_vec[i] = vec.m_vec[i];  // Element copy
 302     }
 303   }
 304   return *this;
 305 }
 306
 307 template <class TYPE>
 308 void Vector<TYPE>::grow(int new_max_size)
 309 {
 310   TYPE* temp_vec;
 311   m_max_size = new_max_size;
 312   if (new_max_size != 0) {
 313     temp_vec = new TYPE[new_max_size];
 314     assert(temp_vec != NULL);
 315   } else {
 316     temp_vec = NULL;
 317   }
 318
 319   // Copy the elements of the array
 320   for(int i=0; i<m_size; i++) {
 321     temp_vec[i] = m_vec[i];  // Element copy
 322   }
 323   delete [] m_vec;
 324   m_vec = temp_vec;
 325 }
 326
 327 template <class TYPE>
 328 ostream& operator<<(ostream& out, const Vector<TYPE>& vec)
 329 {
 330   vec.print(out);
 331   return out;
 332 }
 333
 334 #endif //VECTOR_H