Pyrogenesis trunk
EntityMap.h
Go to the documentation of this file.
1/* Copyright (C) 2023 Wildfire Games.
2 * This file is part of 0 A.D.
3 *
4 * 0 A.D. is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * 0 A.D. is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 */
17#ifndef INCLUDED_ENTITYMAP
18#define INCLUDED_ENTITYMAP
19
20#include "Entity.h"
21
23
24/**
25 * A fast replacement for map<entity_id_t, T>.
26 * We make the following assumptions:
27 * - entity id's (keys) are unique
28 * - modifications (add / delete) are far less frequent then look-ups
29 * - preformance for iteration is important
30 */
31template<class T> class EntityMap
32{
33private:
34 EntityMap(const EntityMap&); // non-copyable
35 EntityMap& operator=(const EntityMap&); // non-copyable
36
37public:
39 typedef T mapped_type;
40 template<class K, class V> struct key_val {
41 typedef K first_type;
42 typedef V second_type;
45 };
47
48private:
49 size_t m_BufferSize; // number of elements in the buffer
50 size_t m_BufferCapacity; // capacity of the buffer
51 value_type* m_Buffer; // vector with all the mapped key-value pairs
52
53 size_t m_Count; // number of 'valid' entity id's
54
55public:
56
58 {
59 // for entitymap we allocate the buffer right away
60 // with first element in buffer being the Invalid Entity
61 m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1));
62
63 // create the first element:
65 m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
66 }
67 inline ~EntityMap()
68 {
69 free(m_Buffer);
70 }
71
72 // Iterators
73 template<class U> struct _iter
74 {
75 using iterator_category = std::forward_iterator_tag;
76 using value_type = U;
77 using difference_type = std::ptrdiff_t;
78 using pointer = U*;
79 using reference = U&;
80
81 U* val;
82 inline _iter(U* init) : val(init) {}
83 inline U& operator*() { return *val; }
84 inline U* operator->() { return val; }
85 inline _iter& operator++() // ++it
86 {
87 ++val;
88 while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
89 return *this;
90 }
91 inline _iter& operator++(int) // it++
92 {
93 U* ptr = val;
94 ++val;
95 while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
96 return ptr;
97 }
98 inline bool operator==(_iter other) { return val == other.val; }
99 inline bool operator!=(_iter other) { return val != other.val; }
100 inline operator _iter<U const>() const { return _iter<U const>(val); }
101 };
102
105
107 {
108 value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
109 while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
110 return ptr;
111 }
112 inline iterator end()
113 {
115 }
116 inline const_iterator begin() const
117 {
118 value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
119 while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
120 return ptr;
121 }
122 inline const_iterator end() const
123 {
125 }
126
127 // Size
128 inline bool empty() const { return m_Count == 0; }
129 inline size_t size() const { return m_Count; }
130
131 // Modification
132 void insert(const key_type key, const mapped_type& value)
133 {
134 if (key >= m_BufferCapacity) // do we need to resize buffer?
135 {
136 size_t newCapacity = m_BufferCapacity + 4096;
137 while (key >= newCapacity) newCapacity += 4096;
138 // always allocate +1 behind the scenes, because end() must have a 0xFFFFFFFF key
139 value_type* mem = (value_type*)realloc(m_Buffer, sizeof(value_type) * (newCapacity + 1));
140 if (!mem)
141 {
142 debug_warn("EntityMap::insert() realloc failed! Out of memory.");
143 throw std::bad_alloc(); // fail to expand and insert
144 }
145 m_BufferCapacity = newCapacity;
146 m_Buffer = mem;
147 goto fill_gaps;
148 }
149 else if (key > m_BufferSize) // weird insert far beyond the end
150 {
151fill_gaps:
152 // set all entity id's to INVALID_ENTITY inside the new range
153 for (size_t i = m_BufferSize; i <= key; ++i)
154 m_Buffer[i].first = INVALID_ENTITY;
155 m_BufferSize = key; // extend the new size
156 }
157
158 value_type& item = m_Buffer[key];
159 key_type oldKey = item.first;
160 item.first = key;
161 if (key == m_BufferSize) // push_back
162 {
163 ++m_BufferSize; // expand
164 ++m_Count;
165 new (&item.second) mapped_type(value); // copy ctor to init
166 m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
167 }
168 else if(!item.first) // insert new to middle
169 {
170 ++m_Count;
171 new (&item.second) mapped_type(value); // copy ctor to init
172 }
173 else // set existing value
174 {
175 if (oldKey == INVALID_ENTITY)
176 m_Count++;
177 item.second = value; // overwrite existing
178 }
179 }
180
182 {
183 value_type* ptr = it.val;
184 if (ptr->first != INVALID_ENTITY)
185 {
186 ptr->first = INVALID_ENTITY;
187 ptr->second.~T(); // call dtor
188 --m_Count;
189 }
190 }
192 {
193 if (key < m_BufferSize)
194 {
195 value_type* ptr = m_Buffer + key;
196 if (ptr->first != INVALID_ENTITY)
197 {
198 ptr->first = INVALID_ENTITY;
199 ptr->second.~T(); // call dtor
200 --m_Count;
201 }
202 }
203 }
204 inline void clear()
205 {
206 // orphan whole range
207 value_type* ptr = m_Buffer;
209 for (; ptr != end; ++ptr)
210 {
211 if (ptr->first != INVALID_ENTITY)
212 {
213 ptr->first = INVALID_ENTITY;
214 ptr->second.~T(); // call dtor
215 }
216 }
217 m_Count = 0; // no more valid entities
218 }
219
220 // Operations
222 {
223 if (key < m_BufferSize) // is this key in the range of existing entitites?
224 {
225 value_type* ptr = m_Buffer + key;
226 if (ptr->first != INVALID_ENTITY)
227 return ptr;
228 }
229 return m_Buffer + m_BufferSize; // return iterator end()
230 }
231 inline const_iterator find(const entity_id_t key) const
232 {
233 if (key < m_BufferSize) // is this key in the range of existing entitites?
234 {
235 const value_type* ptr = m_Buffer + key;
236 if (ptr->first != INVALID_ENTITY)
237 return ptr;
238 }
239 return m_Buffer + m_BufferSize; // return iterator end()
240 }
241 inline size_t count(const entity_id_t key) const
242 {
243 if (key < m_BufferSize)
244 {
245 if (m_Buffer[key].first != INVALID_ENTITY)
246 return 1;
247 }
248 return 0;
249 }
250};
251
252template<typename T>
254{
255 void operator()(ISerializer& serialize, const char* UNUSED(name), EntityMap<T>& value)
256 {
257 size_t len = value.size();
258 serialize.NumberU32_Unbounded("length", (u32)len);
259 size_t count = 0;
260 for (typename EntityMap<T>::iterator it = value.begin(); it != value.end(); ++it)
261 {
262 serialize.NumberU32_Unbounded("key", it->first);
263 Serializer(serialize, "value", it->second);
264 count++;
265 }
266 // test to see if the entityMap count wasn't wrong
267 // (which causes a crashing deserialisation)
268 ENSURE(count == len);
269 }
270
271 void operator()(IDeserializer& deserialize, const char* UNUSED(name), EntityMap<T>& value)
272 {
273 value.clear();
274 uint32_t len;
275 deserialize.NumberU32_Unbounded("length", len);
276 for (size_t i = 0; i < len; ++i)
277 {
278 entity_id_t k;
279 T v;
280 deserialize.NumberU32_Unbounded("key", k);
281 Serializer(deserialize, "value", v);
282 value.insert(k, v);
283 }
284 }
285};
286
287
288#endif
Helper templates definitions for serializing/deserializing common objects.
void Serializer(S &serialize, const char *name, Args &&... args)
Definition: SerializeTemplates.h:51
A fast replacement for map<entity_id_t, T>.
Definition: EntityMap.h:32
size_t size() const
Definition: EntityMap.h:129
EntityMap()
Definition: EntityMap.h:57
const_iterator end() const
Definition: EntityMap.h:122
void erase(iterator it)
Definition: EntityMap.h:181
EntityMap(const EntityMap &)
size_t m_Count
Definition: EntityMap.h:53
void insert(const key_type key, const mapped_type &value)
Definition: EntityMap.h:132
const_iterator begin() const
Definition: EntityMap.h:116
_iter< value_type const > const_iterator
Definition: EntityMap.h:104
const_iterator find(const entity_id_t key) const
Definition: EntityMap.h:231
_iter< value_type > iterator
Definition: EntityMap.h:103
void clear()
Definition: EntityMap.h:204
EntityMap & operator=(const EntityMap &)
size_t count(const entity_id_t key) const
Definition: EntityMap.h:241
T mapped_type
Definition: EntityMap.h:39
~EntityMap()
Definition: EntityMap.h:67
iterator find(const entity_id_t key)
Definition: EntityMap.h:221
size_t m_BufferCapacity
Definition: EntityMap.h:50
void erase(const entity_id_t key)
Definition: EntityMap.h:191
value_type * m_Buffer
Definition: EntityMap.h:51
entity_id_t key_type
Definition: EntityMap.h:38
key_val< entity_id_t, T > value_type
Definition: EntityMap.h:46
size_t m_BufferSize
Definition: EntityMap.h:49
bool empty() const
Definition: EntityMap.h:128
iterator begin()
Definition: EntityMap.h:106
iterator end()
Definition: EntityMap.h:112
Deserialization interface; see serialization overview.
Definition: IDeserializer.h:35
virtual void NumberU32_Unbounded(const char *name, uint32_t &out)
Definition: IDeserializer.cpp:124
Serialization interface; see serialization overview.
Definition: ISerializer.h:121
void NumberU32_Unbounded(const char *name, uint32_t value)
Serialize a number.
Definition: ISerializer.h:171
#define UNUSED(param)
mark a function parameter as unused and avoid the corresponding compiler warning.
Definition: code_annotation.h:40
#define debug_warn(expr)
display the error dialog with the given text.
Definition: debug.h:332
#define ENSURE(expr)
ensure the expression <expr> evaluates to non-zero.
Definition: debug.h:290
#define T(string_literal)
Definition: secure_crt.cpp:77
const entity_id_t INVALID_ENTITY
Invalid entity ID.
Definition: Entity.h:35
u32 entity_id_t
Entity ID type.
Definition: Entity.h:29
Definition: EntityMap.h:74
U * val
Definition: EntityMap.h:81
bool operator!=(_iter other)
Definition: EntityMap.h:99
std::ptrdiff_t difference_type
Definition: EntityMap.h:77
_iter(U *init)
Definition: EntityMap.h:82
U * pointer
Definition: EntityMap.h:78
std::forward_iterator_tag iterator_category
Definition: EntityMap.h:75
bool operator==(_iter other)
Definition: EntityMap.h:98
_iter & operator++()
Definition: EntityMap.h:85
_iter & operator++(int)
Definition: EntityMap.h:91
U & reference
Definition: EntityMap.h:79
U * operator->()
Definition: EntityMap.h:84
U value_type
Definition: EntityMap.h:76
U & operator*()
Definition: EntityMap.h:83
Definition: EntityMap.h:40
K first_type
Definition: EntityMap.h:41
V second
Definition: EntityMap.h:44
V second_type
Definition: EntityMap.h:42
K first
Definition: EntityMap.h:43
void operator()(IDeserializer &deserialize, const char *name, EntityMap< T > &value)
Definition: EntityMap.h:271
void operator()(ISerializer &serialize, const char *name, EntityMap< T > &value)
Definition: EntityMap.h:255
Definition: SerializeTemplates.h:42
uint32_t u32
Definition: types.h:39
unsigned int uint32_t
Definition: wposix_types.h:53
pthread_key_t key
Definition: wpthread.cpp:149