compiler2/vector.hh

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Copyright (c) 2000-2015 Ericsson Telecom AB
   3 // All rights reserved. This program and the accompanying materials
   4 // are made available under the terms of the Eclipse Public License v1.0
   5 // which accompanies this distribution, and is available at
   6 // http://www.eclipse.org/legal/epl-v10.html
   7 ///////////////////////////////////////////////////////////////////////////////
   8 #ifndef _Common_vector_HH
   9 #define _Common_vector_HH
  10
  11 #ifdef __SUNPRO_CC
  12 /**
  13  * Inclusion of the STL vector header file prevents the Sun Forte 6.2 C++
  14  * compiler from a mysterious internal error.
  15  */
  16 #include <vector>
  17 #include <stdio.h>
  18 #endif
  19
  20 #include "error.h"
  21 #include "../common/memory.h"
  22 #include <string.h> // for memmove
  23
  24 /**
  25  * Container optimized to store elements sequentially,
  26  * and access them randomly, referenced by indices.
  27  *
  28  * Accessing an element has constant time cost.
  29  * Adding an element at the end has amortized constant time const.
  30  * Other operations (adding at the beginning, replacing/deleting elements)
  31  * have linear time cost.
  32  *
  33  * If there aren't elements in the buffer, then no space is allocated.
  34  * If there are, the size of the allocated buffer is the smallest power of 2
  35  *   that is not smaller than the number of elements (num_e).
  36  *
  37  * The container stores pointers to objects of type T; it doesn't own them.
  38  * It is the responsibility of the caller to create and destroy the objects
  39  * and supply the pointers to the container.
  40  *
  41  * \ingroup containers
  42  */
  43 template<class T>
  44 class vector {
  45
  46 private:
  47
  48   size_t num_e;
  49   T **e_ptr;
  50
  51   static const size_t initial_size = 1, increment_factor = 2;
  52
  53   /** Copy constructor: DO NOT IMPLEMENT! */
  54   vector(const vector&);
  55   /** Copy assignment: DO NOT IMPLEMENT! */
  56   vector& operator=(const vector&);
  57
  58 public:
  59
  60   static const size_t max_vector_length = -1;
  61
  62   /** Creates an empty vector. */
  63   vector() : num_e(0), e_ptr(NULL) { }
  64
  65   /** Deallocates its memory. If the container is not empty,
  66    *  FATAL_ERROR occurs, so before destructing, clear() must be
  67    *  invoked explicitly.
  68    */
  69   ~vector() {
  70     if (num_e > 0) FATAL_ERROR("vector::~vector(): vector is not empty");
  71     Free(e_ptr);
  72   }
  73
  74   /** Returns the number of elements in the container. */
  75   size_t size() const { return num_e; }
  76
  77   /** Returns true if the container has no elements. */
  78   bool empty() const { return num_e == 0; }
  79
  80   /** Erases the entire container. */
  81   void clear() {
  82     num_e = 0;
  83     Free(e_ptr);
  84     e_ptr = NULL;
  85   }
  86
  87   /** Appends the \a elem to the end of vector. */
  88   void add(T *elem) {
  89     if (e_ptr == NULL) {
  90       e_ptr = static_cast<T**>(Malloc(initial_size * sizeof(*e_ptr)));
  91     } else {
  92       size_t max_e = initial_size;
  93       while (max_e < num_e) max_e *= increment_factor;
  94       if (max_e <= num_e) {
  95         if (max_e >= max_vector_length / increment_factor)
  96             FATAL_ERROR("vector::add(): vector index overflow");
  97         e_ptr = static_cast<T**>
  98                 (Realloc(e_ptr, max_e * increment_factor * sizeof(*e_ptr)));
  99       }
 100     }
 101     e_ptr[num_e++] = elem;
 102   }
 103
 104   /** Inserts the \a elem to the beginning of vector. */
 105   void add_front(T *elem) {
 106     if (e_ptr == NULL) {
 107       e_ptr = static_cast<T**>(Malloc(initial_size * sizeof(*e_ptr)));
 108     } else {
 109       size_t max_e = initial_size;
 110       while (max_e < num_e) max_e *= increment_factor;
 111       if (max_e <= num_e) {
 112         if (max_e >= max_vector_length / increment_factor)
 113             FATAL_ERROR("vector::add_front(): vector index overflow");
 114         e_ptr = static_cast<T**>
 115                 (Realloc(e_ptr, max_e * increment_factor * sizeof(*e_ptr)));
 116       }
 117     }
 118     memmove(e_ptr + 1, e_ptr, num_e * sizeof(*e_ptr));
 119     num_e++;
 120     e_ptr[0] = elem;
 121   }
 122
 123   /** Returns the <em>n</em>th element. The index of the first element is
 124    * zero. If no such index, then FATAL_ERROR occurs. */
 125   T* operator[](size_t n) const {
 126     if (n >= num_e)
 127       FATAL_ERROR("vector::operator[](size_t) const: index overflow");
 128     return e_ptr[n];
 129   }
 130
 131   /** Returns the <em>n</em>th element. The index of the first element is
 132    * zero. If no such index, then FATAL_ERROR occurs. */
 133   T*& operator[](size_t n) {
 134     if (n >= num_e)
 135       FATAL_ERROR("vector::operator[](size_t): index overflow");
 136     return e_ptr[n];
 137   }
 138
 139   /** Replaces \a n elements beginning from position \a pos
 140    * with elements in \a v. If \a pos+n > size() then FATAL_ERROR occurs.
 141    * If \a v == NULL then deletes the elements.
 142    */
 143   void replace(size_t pos, size_t n, const vector *v = NULL) {
 144     if (pos > num_e) FATAL_ERROR("vector::replace(): position points over " \
 145       "the last element");
 146     else if (n > num_e - pos) FATAL_ERROR("vector::replace(): not enough " \
 147       "elements after the start position");
 148     else if (v == this) FATAL_ERROR("vector::replace(): trying to replace " \
 149       "the original vector");
 150     size_t v_len = v != NULL ? v->num_e : 0;
 151     if (v_len > max_vector_length - num_e + n)
 152       FATAL_ERROR("vector::replace(): resulting vector size exceeds maximal " \
 153         "length");
 154     size_t new_len = num_e - n + v_len;
 155     if (new_len > num_e) {
 156       size_t max_e = initial_size;
 157       if (e_ptr == NULL) {
 158         while (max_e < new_len) max_e *= increment_factor;
 159         e_ptr = static_cast<T**>(Malloc(max_e * sizeof(*e_ptr)));
 160       } else {
 161         while (max_e < num_e) max_e *= increment_factor;
 162         if (new_len > max_e) {
 163           while (max_e < new_len) max_e *= increment_factor;
 164           e_ptr = static_cast<T**>(Realloc(e_ptr, max_e * sizeof(*e_ptr)));
 165         }
 166       }
 167     }
 168     if (pos + n < num_e && v_len != n) memmove(e_ptr + pos + v_len,
 169         e_ptr + pos + n, (num_e - pos - n) * sizeof(*e_ptr));
 170     if (v_len > 0) memcpy(e_ptr + pos, v->e_ptr, v_len * sizeof(*e_ptr));
 171     if (new_len < num_e) {
 172       if (new_len == 0) {
 173         Free(e_ptr);
 174         e_ptr = NULL;
 175       } else {
 176         size_t max_e = initial_size;
 177         while (max_e < num_e) max_e *= increment_factor;
 178         size_t max_e2 = initial_size;
 179         while (max_e2 < new_len) max_e2 *= increment_factor;
 180         if (max_e2 < max_e)
 181           e_ptr = static_cast<T**>(Realloc(e_ptr, max_e2 * sizeof(*e_ptr)));
 182       }
 183     }
 184     num_e = new_len;
 185   }
 186
 187   /**
 188    * Copies a part of the vector to a new vector. The part is
 189    * specified by the starting position (<em>pos</em>) and the number
 190    * of elements (<em>n</em>) to copy. If <em>n</em> is greater than
 191    * the number of elements beginning from the given <em>pos</em>,
 192    * then the returned vector contains less elements.
 193    *
 194    * \note The pointers are copied, the objects they refer to will not
 195    * be duplicated.
 196    */
 197   vector* subvector(size_t pos = 0, size_t n = max_vector_length) const
 198   {
 199     if (pos > num_e) FATAL_ERROR("vector::subvector(): position points " \
 200       "over last vector element");
 201     if (n > num_e - pos) n = num_e - pos;
 202     vector *tmp_vector = new vector;
 203     if (n > 0) {
 204       size_t max_e = initial_size;
 205       while (max_e < n) max_e *= increment_factor;
 206       tmp_vector->e_ptr = static_cast<T**>(Malloc(max_e * sizeof(*e_ptr)));
 207       memcpy(tmp_vector->e_ptr, e_ptr + pos, n * sizeof(*e_ptr));
 208       tmp_vector->num_e = n;
 209     }
 210     return tmp_vector;
 211   }
 212
 213 }; // class vector
 214
 215 /**
 216  * Container to store simple types (can have constructor, but it should be fast)
 217  * that are simple and small, stores the objects and not the pointers (copy
 218  * constructor must be implemented). The capacity is increased to be always the
 219  * power of two, the container capacity is never decreased. An initial
 220  * capacity value can be supplied to the constructor, this can be used to avoid
 221  * any further memory allocations during the life of the container.
 222  */
 223 template<class T>
 224 class dynamic_array {
 225 private:
 226   size_t count;
 227   size_t capacity; // 0,1,2,4,8,...
 228   T* data;
 229
 230   void clean_up();
 231   void copy_content(const dynamic_array& other);
 232 public:
 233
 234   dynamic_array() : count(0), capacity(0), data(NULL) {}
 235   // to avoid reallocations and copying
 236   dynamic_array(size_t init_capacity) : count(0), capacity(init_capacity), data(NULL)
 237     { if (capacity>0) data = new T[capacity]; }
 238   dynamic_array(const dynamic_array& other) : count(0), capacity(0), data(NULL) { copy_content(other); }
 239   dynamic_array& operator=(const dynamic_array& other) { clean_up(); copy_content(other); return *this; }
 240   ~dynamic_array() { clean_up(); }
 241
 242   bool operator==(const dynamic_array& other) const;
 243   bool operator!=(const dynamic_array& other) const { return (!(*this==other)); }
 244
 245   /** Returns the number of elements in the container. */
 246   size_t size() const { return count; }
 247
 248   /** Erases the entire container. */
 249   void clear() { clean_up(); }
 250
 251   /** Appends the \a elem to the end of vector. */
 252   void add(const T& elem);
 253
 254   /** Removes an element that is at index \a idx */
 255   void remove(size_t idx);
 256
 257   /** Returns the <em>n</em>th element. The index of the first element is
 258    * zero. If no such index, then FATAL_ERROR occurs. */
 259   const T& operator[](size_t n) const {
 260     if (n>=count) FATAL_ERROR("dynamic_array::operator[] const: index overflow");
 261     return data[n];
 262   }
 263
 264   /** Returns the <em>n</em>th element. The index of the first element is
 265    * zero. If no such index, then FATAL_ERROR occurs. */
 266   T& operator[](size_t n) {
 267     if (n>=count) FATAL_ERROR("dynamic_array::operator[]: index overflow");
 268     return data[n];
 269   }
 270 }; // class dynamic_array
 271
 272 template<class T>
 273 void dynamic_array<T>::clean_up()
 274 {
 275   delete[] data;
 276   data = NULL;
 277   capacity = 0;
 278   count = 0;
 279 }
 280
 281 template<class T>
 282 void dynamic_array<T>::copy_content(const dynamic_array<T>& other)
 283 {
 284   capacity = other.capacity;
 285   count = other.count;
 286   if (capacity>0) {
 287     data = new T[capacity];
 288     for (size_t i=0; i<count; i++) data[i] = other.data[i];
 289   }
 290 }
 291
 292 template<class T>
 293 bool dynamic_array<T>::operator==(const dynamic_array<T>& other) const
 294 {
 295   if (count!=other.count) return false;
 296   for (size_t i=0; i<count; i++) if (!(data[i]==other.data[i])) return false;
 297   return true;
 298 }
 299
 300 template<class T>
 301 void dynamic_array<T>::add(const T& elem)
 302 {
 303   if (data==NULL) {
 304     capacity = 1;
 305     count = 1;
 306     data = new T[1];
 307     data[0] = elem;
 308   } else {
 309     if (count<capacity) {
 310       data[count] = elem;
 311       count++;
 312     } else {
 313       // no more room, need to allocate new memory
 314       if (capacity==0) FATAL_ERROR("dynamic_array::add()");
 315       capacity *= 2;
 316       T* new_data = new T[capacity];
 317       for (size_t i=0; i<count; i++) new_data[i] = data[i];
 318       delete[] data;
 319       data = new_data;
 320       data[count] = elem;
 321       count++;
 322     }
 323   }
 324 }
 325
 326 template<class T>
 327 void dynamic_array<T>::remove(size_t idx)
 328 {
 329   if (idx>=count) FATAL_ERROR("dynamic_array::remove(): index overflow");
 330   for (size_t i=idx+1; i<count; i++) data[i-1] = data[i];
 331   count--;
 332 }
 333
 334 #endif // _Common_vector_HH