src/core/pool_func.hpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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/>.
   6  */
   7
   8 /** @file pool_func.hpp Some methods of Pool are placed here in order to reduce compilation time and binary size. */
   9
  10 #ifndef POOL_FUNC_HPP
  11 #define POOL_FUNC_HPP
  12
  13 #include "alloc_func.hpp"
  14 #include "bitmath_func.hpp"
  15 #include "mem_func.hpp"
  16 #include "pool_type.hpp"
  17 #include "../error_func.h"
  18
  19 #include "../saveload/saveload_error.hpp" // SlErrorCorruptFmt
  20
  21 /**
  22  * Helper for defining the method's signature.
  23  * @param type The return type of the method.
  24  */
  25 #define DEFINE_POOL_METHOD(type) \
  26         template <class Titem, typename Tindex, size_t Tgrowth_step, size_t Tmax_size, PoolType Tpool_type, bool Tcache, bool Tzero> \
  27         type Pool<Titem, Tindex, Tgrowth_step, Tmax_size, Tpool_type, Tcache, Tzero>
  28
  29 /**
  30  * Create a clean pool.
  31  * @param name The name for the pool.
  32  */
  33 DEFINE_POOL_METHOD(inline)::Pool(const char *name) :
  34                 PoolBase(Tpool_type),
  35                 name(name),
  36                 size(0),
  37                 first_free(0),
  38                 first_unused(0),
  39                 items(0),
  40 #ifdef WITH_ASSERT
  41                 checked(0),
  42 #endif /* WITH_ASSERT */
  43                 cleaning(false),
  44                 data(nullptr),
  45                 alloc_cache(nullptr)
  46 { }
  47
  48 /**
  49  * Resizes the pool so 'index' can be addressed
  50  * @param index index we will allocate later
  51  * @pre index >= this->size
  52  * @pre index < Tmax_size
  53  */
  54 DEFINE_POOL_METHOD(inline void)::ResizeFor(size_t index)
  55 {
  56         assert(index >= this->size);
  57         assert(index < Tmax_size);
  58
  59         size_t new_size = std::min(Tmax_size, Align(index + 1, Tgrowth_step));
  60
  61         this->data = ReallocT(this->data, new_size);
  62         MemSetT(this->data + this->size, 0, new_size - this->size);
  63
  64         this->used_bitmap.resize(Align(new_size, BITMAP_SIZE) / BITMAP_SIZE);
  65         if (this->size % BITMAP_SIZE != 0) {
  66                 /* Already-allocated bits above old size are now unused. */
  67                 this->used_bitmap[this->size / BITMAP_SIZE] &= ~((~static_cast<BitmapStorage>(0)) << (this->size % BITMAP_SIZE));
  68         }
  69         if (new_size % BITMAP_SIZE != 0) {
  70                 /* Bits above new size are considered used. */
  71                 this->used_bitmap[new_size / BITMAP_SIZE] |= (~static_cast<BitmapStorage>(0)) << (new_size % BITMAP_SIZE);
  72         }
  73
  74         this->size = new_size;
  75 }
  76
  77 /**
  78  * Searches for first free index
  79  * @return first free index, NO_FREE_ITEM on failure
  80  */
  81 DEFINE_POOL_METHOD(inline size_t)::FindFirstFree()
  82 {
  83         for (auto it = std::next(std::begin(this->used_bitmap), this->first_free / BITMAP_SIZE); it != std::end(this->used_bitmap); ++it) {
  84                 BitmapStorage available = ~(*it);
  85                 if (available == 0) continue;
  86                 return std::distance(std::begin(this->used_bitmap), it) * BITMAP_SIZE + FindFirstBit(available);
  87         }
  88
  89         assert(this->first_unused == this->size);
  90
  91         if (this->first_unused < Tmax_size) {
  92                 this->ResizeFor(this->first_unused);
  93                 return this->first_unused;
  94         }
  95
  96         assert(this->first_unused == Tmax_size);
  97
  98         return NO_FREE_ITEM;
  99 }
 100
 101 /**
 102  * Makes given index valid
 103  * @param size size of item
 104  * @param index index of item
 105  * @pre index < this->size
 106  * @pre this->Get(index) == nullptr
 107  */
 108 DEFINE_POOL_METHOD(inline void *)::AllocateItem(size_t size, size_t index)
 109 {
 110         assert(this->data[index] == nullptr);
 111
 112         this->first_unused = std::max(this->first_unused, index + 1);
 113         this->items++;
 114
 115         Titem *item;
 116         if (Tcache && this->alloc_cache != nullptr) {
 117                 assert(sizeof(Titem) == size);
 118                 item = reinterpret_cast<Titem *>(this->alloc_cache);
 119                 this->alloc_cache = this->alloc_cache->next;
 120                 if (Tzero) {
 121                         /* Explicitly casting to (void *) prevents a clang warning -
 122                          * we are actually memsetting a (not-yet-constructed) object */
 123                         memset(static_cast<void *>(item), 0, sizeof(Titem));
 124                 }
 125         } else if (Tzero) {
 126                 item = reinterpret_cast<Titem *>(CallocT<uint8_t>(size));
 127         } else {
 128                 item = reinterpret_cast<Titem *>(MallocT<uint8_t>(size));
 129         }
 130         this->data[index] = item;
 131         SetBit(this->used_bitmap[index / BITMAP_SIZE], index % BITMAP_SIZE);
 132         item->index = (Tindex)(uint)index;
 133         return item;
 134 }
 135
 136 /**
 137  * Allocates new item
 138  * @param size size of item
 139  * @return pointer to allocated item
 140  * @note FatalError() on failure! (no free item)
 141  */
 142 DEFINE_POOL_METHOD(void *)::GetNew(size_t size)
 143 {
 144         size_t index = this->FindFirstFree();
 145
 146 #ifdef WITH_ASSERT
 147         assert(this->checked != 0);
 148         this->checked--;
 149 #endif /* WITH_ASSERT */
 150         if (index == NO_FREE_ITEM) {
 151                 FatalError("{}: no more free items", this->name);
 152         }
 153
 154         this->first_free = index + 1;
 155         return this->AllocateItem(size, index);
 156 }
 157
 158 /**
 159  * Allocates new item with given index
 160  * @param size size of item
 161  * @param index index of item
 162  * @return pointer to allocated item
 163  * @note SlErrorCorruptFmt() on failure! (index out of range or already used)
 164  */
 165 DEFINE_POOL_METHOD(void *)::GetNew(size_t size, size_t index)
 166 {
 167         if (index >= Tmax_size) {
 168                 SlErrorCorruptFmt("{} index {} out of range ({})", this->name, index, Tmax_size);
 169         }
 170
 171         if (index >= this->size) this->ResizeFor(index);
 172
 173         if (this->data[index] != nullptr) {
 174                 SlErrorCorruptFmt("{} index {} already in use", this->name, index);
 175         }
 176
 177         return this->AllocateItem(size, index);
 178 }
 179
 180 /**
 181  * Deallocates memory used by this index and marks item as free
 182  * @param index item to deallocate
 183  * @pre unit is allocated (non-nullptr)
 184  * @note 'delete nullptr' doesn't cause call of this function, so it is safe
 185  */
 186 DEFINE_POOL_METHOD(void)::FreeItem(size_t index)
 187 {
 188         assert(index < this->size);
 189         assert(this->data[index] != nullptr);
 190         if (Tcache) {
 191                 AllocCache *ac = reinterpret_cast<AllocCache *>(this->data[index]);
 192                 ac->next = this->alloc_cache;
 193                 this->alloc_cache = ac;
 194         } else {
 195                 free(this->data[index]);
 196         }
 197         this->data[index] = nullptr;
 198         this->first_free = std::min(this->first_free, index);
 199         this->items--;
 200         if (!this->cleaning) {
 201                 ClrBit(this->used_bitmap[index / BITMAP_SIZE], index % BITMAP_SIZE);
 202                 Titem::PostDestructor(index);
 203         }
 204 }
 205
 206 /** Destroys all items in the pool and resets all member variables. */
 207 DEFINE_POOL_METHOD(void)::CleanPool()
 208 {
 209         this->cleaning = true;
 210         for (size_t i = 0; i < this->first_unused; i++) {
 211                 delete this->Get(i); // 'delete nullptr;' is very valid
 212         }
 213         assert(this->items == 0);
 214         free(this->data);
 215         this->used_bitmap.clear();
 216         this->used_bitmap.shrink_to_fit();
 217         this->first_unused = this->first_free = this->size = 0;
 218         this->data = nullptr;
 219         this->cleaning = false;
 220
 221         if (Tcache) {
 222                 while (this->alloc_cache != nullptr) {
 223                         AllocCache *ac = this->alloc_cache;
 224                         this->alloc_cache = ac->next;
 225                         free(ac);
 226                 }
 227         }
 228 }
 229
 230 #undef DEFINE_POOL_METHOD
 231
 232 /**
 233  * Force instantiation of pool methods so we don't get linker errors.
 234  * Only methods accessed from methods defined in pool.hpp need to be
 235  * forcefully instantiated.
 236  */
 237 #define INSTANTIATE_POOL_METHODS(name) \
 238         template void * name ## Pool::GetNew(size_t size); \
 239         template void * name ## Pool::GetNew(size_t size, size_t index); \
 240         template void name ## Pool::FreeItem(size_t index); \
 241         template void name ## Pool::CleanPool();
 242
 243 #endif /* POOL_FUNC_HPP */