src/misc/fixedsizearray.hpp

   1 /* $Id: fixedsizearray.hpp 23640 2011-12-20 17:57:56Z truebrain $ */
   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()
  45         {
  46                 return *(ArrayHeader*)(((byte*)data) - HeaderSize);
  47         }
  48
  49         /** return reference to the array header (const) */
  50         inline const ArrayHeader& Hdr() const
  51         {
  52                 return *(ArrayHeader*)(((byte*)data) - HeaderSize);
  53         }
  54
  55         /** return reference to the block reference counter */
  56         inline uint& RefCnt()
  57         {
  58                 return Hdr().reference_count;
  59         }
  60
  61         /** return reference to number of used items */
  62         inline uint& SizeRef()
  63         {
  64                 return Hdr().items;
  65         }
  66
  67 public:
  68         /** Default constructor. Preallocate space for items and header, then initialize header. */
  69         FixedSizeArray()
  70         {
  71                 /* Ensure the size won't overflow. */
  72                 assert_compile(C < (SIZE_MAX - HeaderSize) / Tsize);
  73
  74                 /* allocate block for header + items (don't construct items) */
  75                 data = (T*)((MallocT<byte>(HeaderSize + C * Tsize)) + HeaderSize);
  76                 SizeRef() = 0; // initial number of items
  77                 RefCnt() = 1; // initial reference counter
  78         }
  79
  80         /** Copy constructor. Preallocate space for items and header, then initialize header. */
  81         FixedSizeArray(const FixedSizeArray<T, C> &src)
  82         {
  83                 /* share block (header + items) with the source array */
  84                 data = src.data;
  85                 RefCnt()++; // now we share block with the source
  86         }
  87
  88         /** destroy remaining items and free the memory block */
  89         ~FixedSizeArray()
  90         {
  91                 /* release one reference to the shared block */
  92                 if ((--RefCnt()) > 0) return; // and return if there is still some owner
  93
  94                 Clear();
  95                 /* free the memory block occupied by items */
  96                 free(((byte*)data) - HeaderSize);
  97                 data = nullptr;
  98         }
  99
 100         /** Clear (destroy) all items */
 101         inline void Clear()
 102         {
 103                 /* Walk through all allocated items backward and destroy them
 104                  * Note: this->Length() can be zero. In that case data[this->Length() - 1] is evaluated unsigned
 105                  *       on some compilers with some architectures. (e.g. gcc with x86) */
 106                 for (T *pItem = this->data + this->Length() - 1; pItem >= this->data; pItem--) {
 107                         pItem->~T();
 108                 }
 109                 /* number of items become zero */
 110                 SizeRef() = 0;
 111         }
 112
 113         /** return number of used items */
 114         inline uint Length() const
 115         {
 116                 return Hdr().items;
 117         }
 118
 119         /** return true if array is full */
 120         inline bool IsFull() const
 121         {
 122                 return Length() >= C;
 123         }
 124
 125         /** return true if array is empty */
 126         inline bool IsEmpty() const
 127         {
 128                 return Length() <= 0;
 129         }
 130
 131         /** add (allocate), but don't construct item */
 132         inline T *Append()
 133         {
 134                 assert(!IsFull());
 135                 return &data[SizeRef()++];
 136         }
 137
 138         /** add and construct item using default constructor */
 139         inline T *AppendC()
 140         {
 141                 T *item = Append();
 142                 new(item)T;
 143                 return item;
 144         }
 145         /** return item by index (non-const version) */
 146         inline T& operator[](uint index)
 147         {
 148                 assert(index < Length());
 149                 return data[index];
 150         }
 151
 152         /** return item by index (const version) */
 153         inline const T& operator[](uint index) const
 154         {
 155                 assert(index < Length());
 156                 return data[index];
 157         }
 158 };
 159
 160 #endif /* FIXEDSIZEARRAY_HPP */