Files
@ r21247:551dd5576334
Branch filter:
Location: cpp/openttd-patchpack/source/src/core/smallstack_type.hpp
r21247:551dd5576334
6.1 KiB
text/x-c++hdr
(svn r26335) -Update from WebTranslator v3.0:
croatian - 7 changes by VoyagerOne
frisian - 54 changes by Geoloep
korean - 1 changes by telk5093
spanish - 1 changes by Welder05
croatian - 7 changes by VoyagerOne
frisian - 54 changes by Geoloep
korean - 1 changes by telk5093
spanish - 1 changes by Welder05
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 | /* $Id$ */
/*
* 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 "pool_type.hpp"
#include "pool_func.hpp"
/**
* Base class for SmallStack. We cannot add this into SmallStack itself as
* certain compilers don't like it.
*/
template <typename Tindex, typename Titem>
class SmallStackItem {
protected:
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) {}
};
/**
* 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.
* @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, size_t Tgrowth_step, size_t Tmax_size>
class SmallStack : public SmallStackItem<Tindex, Titem> {
protected:
class PooledSmallStack;
/**
* Create a branch in the pool if necessary.
*/
void Branch()
{
if (PooledSmallStack::IsValidID(this->next)) {
PooledSmallStack::Get(this->next)->CreateBranch();
}
}
public:
typedef SmallStackItem<Tindex, Titem> Item;
typedef Pool<PooledSmallStack, Tindex, Tgrowth_step, Tmax_size, PT_NORMAL, true, false> 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()
{
if (PooledSmallStack::IsValidID(this->next)) {
PooledSmallStack *item = PooledSmallStack::Get(this->next);
if (item->NumBranches() == 0) {
delete item;
} else {
item->DeleteBranch();
}
}
}
/**
* 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;
this->~SmallStack();
this->next = other.next;
this->value = other.value;
this->Branch();
return *this;
}
/**
* Push a new item onto the stack.
* @param item Item to be pushed.
*/
inline void Push(const Titem &item)
{
if (this->value != Tinvalid) {
assert(PooledSmallStack::CanAllocateItem());
PooledSmallStack *next = new PooledSmallStack(this->value, this->next);
this->next = next->index;
}
this->value = item;
}
/**
* Pop an item from the stack.
* @return Current top of stack.
*/
inline Titem Pop()
{
Titem ret = this->value;
if (!PooledSmallStack::IsValidID(this->next)) {
this->value = Tinvalid;
} else {
PooledSmallStack *next = PooledSmallStack::Get(this->next);
static_cast<Item &>(*this) = *next;
if (next->NumBranches() == 0) {
delete next;
} else {
next->DeleteBranch();
this->Branch();
}
}
return ret;
}
/**
* Check if the stack is empty.
* @return If the stack is empty.
*/
inline bool IsEmpty() const
{
return this->value == Tinvalid && !PooledSmallStack::IsValidID(this->next);
}
/**
* 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;
const SmallStack *in_list = this;
while (PooledSmallStack::IsValidID(in_list->next)) {
in_list = static_cast<const SmallStack *>(
static_cast<const Item *>(PooledSmallStack::Get(in_list->next)));
if (in_list->value == item) return true;
}
return false;
}
protected:
static SmallStackPool _pool;
/**
* SmallStack item that can be kept in a pool (by having an index).
*/
class PooledSmallStack : public Item, public SmallStackPool::template PoolItem<&SmallStack::_pool> {
private:
Tindex branch_count; ///< Number of branches in the tree structure this item is parent of
public:
PooledSmallStack(Titem value, Tindex next) : Item(value, next), branch_count(0) {}
inline void CreateBranch() { ++this->branch_count; }
inline void DeleteBranch() { --this->branch_count; }
inline Tindex NumBranches() { return this->branch_count; }
};
};
#endif
|