Files
@ r24263:09a2277924d6
Branch filter:
Location: cpp/openttd-patchpack/source/src/core/smallstack_type.hpp
r24263:09a2277924d6
8.7 KiB
text/x-c++hdr
Add: [CMake] Always export compile commands (#8199)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 | /*
* This file is part of OpenTTD.
* 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.
* 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.
* 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/>.
*/
/** @file smallstack_type.hpp Minimal stack that uses a pool to avoid pointers and doesn't allocate any heap memory if there is only one valid item. */
#ifndef SMALLSTACK_TYPE_HPP
#define SMALLSTACK_TYPE_HPP
#include "smallvec_type.hpp"
#include <mutex>
/**
* A simplified pool which stores values instead of pointers and doesn't
* redefine operator new/delete. It also never zeroes memory and always reuses
* it.
*/
template<typename Titem, typename Tindex, Tindex Tgrowth_step, Tindex Tmax_size>
class SimplePool {
public:
inline SimplePool() : first_unused(0), first_free(0) {}
/**
* Get the mutex. We don't lock the mutex in the pool methods as the
* SmallStack isn't necessarily in a consistent state after each method.
* @return Mutex.
*/
inline std::mutex &GetMutex() { return this->mutex; }
/**
* Get the item at position index.
* @return Item at index.
*/
inline Titem &Get(Tindex index) { return this->data[index]; }
/**
* Create a new item and return its index.
* @return Index of new item.
*/
inline Tindex Create()
{
Tindex index = this->FindFirstFree();
if (index < Tmax_size) {
this->data[index].valid = true;
this->first_free = index + 1;
this->first_unused = max(this->first_unused, this->first_free);
}
return index;
}
/**
* Destroy (or rather invalidate) the item at the given index.
* @param index Index of item to be destroyed.
*/
inline void Destroy(Tindex index)
{
this->data[index].valid = false;
this->first_free = min(this->first_free, index);
}
private:
inline Tindex FindFirstFree()
{
Tindex index = this->first_free;
for (; index < this->first_unused; index++) {
if (!this->data[index].valid) return index;
}
if (index >= this->data.size() && index < Tmax_size) {
this->data.resize(index + 1);
}
return index;
}
struct SimplePoolPoolItem : public Titem {
bool valid;
};
Tindex first_unused;
Tindex first_free;
std::mutex mutex;
std::vector<SimplePoolPoolItem> data;
};
/**
* Base class for SmallStack. We cannot add this into SmallStack itself as
* certain compilers don't like it.
*/
template <typename Titem, typename Tindex>
struct SmallStackItem {
Tindex next; ///< Pool index of next item.
Titem value; ///< Value of current item.
/**
* Create a new item.
* @param value Value of the item.
* @param next Next item in the stack.
*/
inline SmallStackItem(const Titem &value, Tindex next) :
next(next), value(value) {}
SmallStackItem() = default;
};
/**
* Minimal stack that uses a pool to avoid pointers. It has some peculiar
* properties that make it useful for passing around lists of IDs but not much
* else:
* 1. It always includes an invalid item as bottom.
* 2. It doesn't have a deep copy operation but uses smart pointers instead.
* Every copy is thus implicitly shared.
* 3. Its items are immutable.
* 4. Due to 2. and 3. memory management can be done by "branch counting".
* Whenever you copy a smallstack, the first item on the heap increases its
* branch_count, signifying that there are multiple items "in front" of it.
* When deleting a stack items are deleted up to the point where
* branch_count > 0.
* 5. You can choose your own index type, so that you can align it with your
* value type. E.G. value types of 16 bits length like to be combined with
* index types of the same length.
* 6. All accesses to the underlying pool are guarded by a mutex and atomic in
* the sense that the mutex stays locked until the pool has reacquired a
* consistent state. This means that even though a common data structure is
* used the SmallStack is still reentrant.
* @tparam Titem Value type to be used.
* @tparam Tindex Index type to use for the pool.
* @tparam Tinvalid Invalid item to keep at the bottom of each stack.
* @tparam Tgrowth_step Growth step for pool.
* @tparam Tmax_size Maximum size for pool.
*/
template <typename Titem, typename Tindex, Titem Tinvalid, Tindex Tgrowth_step, Tindex Tmax_size>
class SmallStack : public SmallStackItem<Titem, Tindex> {
public:
typedef SmallStackItem<Titem, Tindex> Item;
/**
* SmallStack item that can be kept in a pool.
*/
struct PooledSmallStack : public Item {
Tindex branch_count; ///< Number of branches in the tree structure this item is parent of
};
typedef SimplePool<PooledSmallStack, Tindex, Tgrowth_step, Tmax_size> SmallStackPool;
/**
* Constructor for a stack with one or two items in it.
* @param value Initial item. If not missing or Tinvalid there will be Tinvalid below it.
*/
inline SmallStack(const Titem &value = Tinvalid) : Item(value, Tmax_size) {}
/**
* Remove the head of stack and all other items members that are unique to it.
*/
inline ~SmallStack()
{
/* Pop() locks the mutex and after each pop the pool is consistent.*/
while (this->next != Tmax_size) this->Pop();
}
/**
* Shallow copy the stack, marking the first item as branched.
* @param other Stack to copy from
*/
inline SmallStack(const SmallStack &other) : Item(other) { this->Branch(); }
/**
* Shallow copy the stack, marking the first item as branched.
* @param other Stack to copy from
* @return This smallstack.
*/
inline SmallStack &operator=(const SmallStack &other)
{
if (this == &other) return *this;
while (this->next != Tmax_size) this->Pop();
this->next = other.next;
this->value = other.value;
/* Deleting and branching are independent operations, so it's fine to
* acquire separate locks for them. */
this->Branch();
return *this;
}
/**
* Pushes a new item onto the stack if there is still space in the
* underlying pool. Otherwise the topmost item's value gets overwritten.
* @param item Item to be pushed.
*/
inline void Push(const Titem &item)
{
if (this->value != Tinvalid) {
std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
Tindex new_item = SmallStack::GetPool().Create();
if (new_item != Tmax_size) {
PooledSmallStack &pushed = SmallStack::GetPool().Get(new_item);
pushed.value = this->value;
pushed.next = this->next;
pushed.branch_count = 0;
this->next = new_item;
}
}
this->value = item;
}
/**
* Pop an item from the stack.
* @return Current top of stack.
*/
inline Titem Pop()
{
Titem ret = this->value;
if (this->next == Tmax_size) {
this->value = Tinvalid;
} else {
std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
PooledSmallStack &popped = SmallStack::GetPool().Get(this->next);
this->value = popped.value;
if (popped.branch_count == 0) {
SmallStack::GetPool().Destroy(this->next);
} else {
--popped.branch_count;
/* We can't use Branch() here as we already have the mutex.*/
if (popped.next != Tmax_size) {
++(SmallStack::GetPool().Get(popped.next).branch_count);
}
}
/* Accessing popped here is no problem as the pool will only set
* the validity flag, not actually delete the item, on Destroy().
* It's impossible for another thread to acquire the same item in
* the mean time because of the mutex. */
this->next = popped.next;
}
return ret;
}
/**
* Check if the stack is empty.
* @return If the stack is empty.
*/
inline bool IsEmpty() const
{
return this->value == Tinvalid && this->next == Tmax_size;
}
/**
* Check if the given item is contained in the stack.
* @param item Item to look for.
* @return If the item is in the stack.
*/
inline bool Contains(const Titem &item) const
{
if (item == Tinvalid || item == this->value) return true;
if (this->next != Tmax_size) {
std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
const SmallStack *in_list = this;
do {
in_list = static_cast<const SmallStack *>(
static_cast<const Item *>(&SmallStack::GetPool().Get(in_list->next)));
if (in_list->value == item) return true;
} while (in_list->next != Tmax_size);
}
return false;
}
protected:
static SmallStackPool &GetPool()
{
static SmallStackPool pool;
return pool;
}
/**
* Create a branch in the pool if necessary.
*/
inline void Branch()
{
if (this->next != Tmax_size) {
std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
++(SmallStack::GetPool().Get(this->next).branch_count);
}
}
};
#endif
|