src/misc/fixedsizearray.hpp

   1 /* $Id$ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   8  */
   9
  10 /** @file fixedsizearray.hpp A fixed size array that doesn't create items until needed. */
  11
  12 #ifndef FIXEDSIZEARRAY_HPP
  13 #define FIXEDSIZEARRAY_HPP
  14
  15 #include "../core/alloc_func.hpp"
  16
  17 /**
  18  * fixed size array
  19  *  Upon construction it preallocates fixed size block of memory
  20  *  for all items, but doesn't construct them. Item's construction
  21  *  is delayed.
  22  */
  23 template <class T, uint C>
  24 struct FixedSizeArray {
  25 protected:
  26         /** header for fixed size array */
  27         struct ArrayHeader
  28         {
  29                 uint items;           ///< number of items in the array
  30                 uint reference_count; ///< block reference counter (used by copy constructor and by destructor)
  31         };
  32
  33         /* make constants visible from outside */
  34         static const uint Tsize = sizeof(T);                ///< size of item
  35         static const uint HeaderSize = sizeof(ArrayHeader); ///< size of header
  36
  37         /**
  38          * the only member of fixed size array is pointer to the block
  39          *  of C array of items. Header can be found on the offset -sizeof(ArrayHeader).
  40          */
  41         T *data;
  42
  43         /** return reference to the array header (non-const) */
  44         inline ArrayHeader& Hdr() { return *(ArrayHeader*)(((byte*)data) - HeaderSize); }
  45         /** return reference to the array header (const) */
  46         inline const ArrayHeader& Hdr() const { return *(ArrayHeader*)(((byte*)data) - HeaderSize); }
  47         /** return reference to the block reference counter */
  48         inline uint& RefCnt() { return Hdr().reference_count; }
  49         /** return reference to number of used items */
  50         inline uint& SizeRef() { return Hdr().items; }
  51
  52 public:
  53         /** Default constructor. Preallocate space for items and header, then initialize header. */
  54         FixedSizeArray()
  55         {
  56                 /* Ensure the size won't overflow. */
  57                 assert_compile(C < (SIZE_MAX - HeaderSize) / Tsize);
  58
  59                 /* allocate block for header + items (don't construct items) */
  60                 data = (T*)((MallocT<byte>(HeaderSize + C * Tsize)) + HeaderSize);
  61                 SizeRef() = 0; // initial number of items
  62                 RefCnt() = 1; // initial reference counter
  63         }
  64
  65         /** Copy constructor. Preallocate space for items and header, then initialize header. */
  66         FixedSizeArray(const FixedSizeArray<T, C>& src)
  67         {
  68                 /* share block (header + items) with the source array */
  69                 data = src.data;
  70                 RefCnt()++; // now we share block with the source
  71         }
  72
  73         /** destroy remaining items and free the memory block */
  74         ~FixedSizeArray()
  75         {
  76                 /* release one reference to the shared block */
  77                 if ((--RefCnt()) > 0) return; // and return if there is still some owner
  78
  79                 Clear();
  80                 /* free the memory block occupied by items */
  81                 free(((byte*)data) - HeaderSize);
  82                 data = NULL;
  83         }
  84
  85         /** Clear (destroy) all items */
  86         inline void Clear()
  87         {
  88                 /* Walk through all allocated items backward and destroy them
  89                  * Note: this->Length() can be zero. In that case data[this->Length() - 1] is evaluated unsigned
  90                  *       on some compilers with some architectures. (e.g. gcc with x86) */
  91                 for (T *pItem = this->data + this->Length() - 1; pItem >= this->data; pItem--) {
  92                         pItem->~T();
  93                 }
  94                 /* number of items become zero */
  95                 SizeRef() = 0;
  96         }
  97
  98         /** return number of used items */
  99         inline uint Length() const { return Hdr().items; }
 100         /** return true if array is full */
 101         inline bool IsFull() const { return Length() >= C; }
 102         /** return true if array is empty */
 103         inline bool IsEmpty() const { return Length() <= 0; }
 104         /** add (allocate), but don't construct item */
 105         inline T *Append() { assert(!IsFull()); return &data[SizeRef()++]; }
 106         /** add and construct item using default constructor */
 107         inline T *AppendC() { T *item = Append(); new(item)T; return item; }
 108         /** return item by index (non-const version) */
 109         inline T& operator [] (uint index) { assert(index < Length()); return data[index]; }
 110         /** return item by index (const version) */
 111         inline const T& operator [] (uint index) const { assert(index < Length()); return data[index]; }
 112 };
 113
 114 #endif /* FIXEDSIZEARRAY_HPP */