Line data Source code
1 : /* Copyright (C) 2013 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 :
22 : #include "simulation2/serialization/SerializeTemplates.h"
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 : */
31 : template<class T> class EntityMap
32 : {
33 : private:
34 : EntityMap(const EntityMap&); // non-copyable
35 : EntityMap& operator=(const EntityMap&); // non-copyable
36 :
37 : public:
38 : typedef entity_id_t key_type;
39 : typedef T mapped_type;
40 : template<class K, class V> struct key_val {
41 : typedef K first_type;
42 : typedef V second_type;
43 : K first;
44 : V second;
45 : };
46 : typedef key_val<entity_id_t, T> value_type;
47 :
48 : private:
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 :
55 : public:
56 :
57 17 : inline EntityMap() : m_BufferSize(1), m_BufferCapacity(4096), m_Count(0)
58 : {
59 : // for entitymap we allocate the buffer right away
60 : // with first element in buffer being the Invalid Entity
61 17 : m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1));
62 :
63 : // create the first element:
64 17 : m_Buffer[0].first = INVALID_ENTITY;
65 17 : m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
66 17 : }
67 17 : inline ~EntityMap()
68 : {
69 17 : free(m_Buffer);
70 17 : }
71 :
72 : // Iterators
73 : template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
74 : {
75 : U* val;
76 14969 : inline _iter(U* init) : val(init) {}
77 4 : inline U& operator*() { return *val; }
78 28257 : inline U* operator->() { return val; }
79 2150 : inline _iter& operator++() // ++it
80 : {
81 2150 : ++val;
82 2168 : while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
83 2150 : return *this;
84 : }
85 : inline _iter& operator++(int) // it++
86 : {
87 : U* ptr = val;
88 : ++val;
89 : while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
90 : return ptr;
91 : }
92 1059 : inline bool operator==(_iter other) { return val == other.val; }
93 4344 : inline bool operator!=(_iter other) { return val != other.val; }
94 6292 : inline operator _iter<U const>() const { return _iter<U const>(val); }
95 : };
96 :
97 : typedef _iter<value_type> iterator;
98 : typedef _iter<value_type const> const_iterator;
99 :
100 2091 : inline iterator begin()
101 : {
102 2091 : value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
103 207030 : while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
104 2091 : return ptr;
105 : }
106 5245 : inline iterator end()
107 : {
108 5245 : return iterator(m_Buffer + m_BufferSize);
109 : }
110 72 : inline const_iterator begin() const
111 : {
112 72 : value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
113 7200 : while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
114 72 : return ptr;
115 : }
116 157 : inline const_iterator end() const
117 : {
118 157 : return const_iterator(m_Buffer + m_BufferSize);
119 : }
120 :
121 : // Size
122 1 : inline bool empty() const { return m_Count == 0; }
123 6 : inline size_t size() const { return m_Count; }
124 :
125 : // Modification
126 34 : void insert(const key_type key, const mapped_type& value)
127 : {
128 34 : if (key >= m_BufferCapacity) // do we need to resize buffer?
129 : {
130 0 : size_t newCapacity = m_BufferCapacity + 4096;
131 0 : while (key >= newCapacity) newCapacity += 4096;
132 : // always allocate +1 behind the scenes, because end() must have a 0xFFFFFFFF key
133 0 : value_type* mem = (value_type*)realloc(m_Buffer, sizeof(value_type) * (newCapacity + 1));
134 0 : if (!mem)
135 : {
136 0 : debug_warn("EntityMap::insert() realloc failed! Out of memory.");
137 0 : throw std::bad_alloc(); // fail to expand and insert
138 : }
139 0 : m_BufferCapacity = newCapacity;
140 0 : m_Buffer = mem;
141 0 : goto fill_gaps;
142 : }
143 34 : else if (key > m_BufferSize) // weird insert far beyond the end
144 : {
145 8 : fill_gaps:
146 : // set all entity id's to INVALID_ENTITY inside the new range
147 287 : for (size_t i = m_BufferSize; i <= key; ++i)
148 279 : m_Buffer[i].first = INVALID_ENTITY;
149 8 : m_BufferSize = key; // extend the new size
150 : }
151 :
152 34 : value_type& item = m_Buffer[key];
153 34 : key_type oldKey = item.first;
154 34 : item.first = key;
155 34 : if (key == m_BufferSize) // push_back
156 : {
157 28 : ++m_BufferSize; // expand
158 28 : ++m_Count;
159 28 : new (&item.second) mapped_type(value); // copy ctor to init
160 28 : m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
161 : }
162 6 : else if(!item.first) // insert new to middle
163 : {
164 0 : ++m_Count;
165 0 : new (&item.second) mapped_type(value); // copy ctor to init
166 : }
167 : else // set existing value
168 : {
169 6 : if (oldKey == INVALID_ENTITY)
170 4 : m_Count++;
171 6 : item.second = value; // overwrite existing
172 : }
173 34 : }
174 :
175 1 : void erase(iterator it)
176 : {
177 1 : value_type* ptr = it.val;
178 1 : if (ptr->first != INVALID_ENTITY)
179 : {
180 1 : ptr->first = INVALID_ENTITY;
181 : ptr->second.~T(); // call dtor
182 1 : --m_Count;
183 : }
184 1 : }
185 5 : void erase(const entity_id_t key)
186 : {
187 5 : if (key < m_BufferSize)
188 : {
189 4 : value_type* ptr = m_Buffer + key;
190 4 : if (ptr->first != INVALID_ENTITY)
191 : {
192 4 : ptr->first = INVALID_ENTITY;
193 : ptr->second.~T(); // call dtor
194 4 : --m_Count;
195 : }
196 : }
197 5 : }
198 2 : inline void clear()
199 : {
200 : // orphan whole range
201 2 : value_type* ptr = m_Buffer;
202 2 : value_type* end = m_Buffer + m_BufferSize;
203 22 : for (; ptr != end; ++ptr)
204 : {
205 10 : if (ptr->first != INVALID_ENTITY)
206 : {
207 8 : ptr->first = INVALID_ENTITY;
208 : ptr->second.~T(); // call dtor
209 : }
210 : }
211 2 : m_Count = 0; // no more valid entities
212 2 : }
213 :
214 : // Operations
215 1099 : inline iterator find(const entity_id_t key)
216 : {
217 1099 : if (key < m_BufferSize) // is this key in the range of existing entitites?
218 : {
219 1097 : value_type* ptr = m_Buffer + key;
220 1097 : if (ptr->first != INVALID_ENTITY)
221 1089 : return ptr;
222 : }
223 10 : return m_Buffer + m_BufferSize; // return iterator end()
224 : }
225 13 : inline const_iterator find(const entity_id_t key) const
226 : {
227 13 : if (key < m_BufferSize) // is this key in the range of existing entitites?
228 : {
229 13 : const value_type* ptr = m_Buffer + key;
230 13 : if (ptr->first != INVALID_ENTITY)
231 13 : return ptr;
232 : }
233 0 : return m_Buffer + m_BufferSize; // return iterator end()
234 : }
235 : inline size_t count(const entity_id_t key) const
236 : {
237 : if (key < m_BufferSize)
238 : {
239 : if (m_Buffer[key].first != INVALID_ENTITY)
240 : return 1;
241 : }
242 : return 0;
243 : }
244 : };
245 :
246 : template<typename T>
247 : struct SerializeHelper<EntityMap<T>>
248 : {
249 0 : void operator()(ISerializer& serialize, const char* UNUSED(name), EntityMap<T>& value)
250 : {
251 0 : size_t len = value.size();
252 0 : serialize.NumberU32_Unbounded("length", (u32)len);
253 0 : size_t count = 0;
254 0 : for (typename EntityMap<T>::iterator it = value.begin(); it != value.end(); ++it)
255 : {
256 0 : serialize.NumberU32_Unbounded("key", it->first);
257 0 : Serializer(serialize, "value", it->second);
258 0 : count++;
259 : }
260 : // test to see if the entityMap count wasn't wrong
261 : // (which causes a crashing deserialisation)
262 0 : ENSURE(count == len);
263 0 : }
264 :
265 0 : void operator()(IDeserializer& deserialize, const char* UNUSED(name), EntityMap<T>& value)
266 : {
267 0 : value.clear();
268 : uint32_t len;
269 0 : deserialize.NumberU32_Unbounded("length", len);
270 0 : for (size_t i = 0; i < len; ++i)
271 : {
272 : entity_id_t k;
273 0 : T v;
274 0 : deserialize.NumberU32_Unbounded("key", k);
275 0 : Serializer(deserialize, "value", v);
276 0 : value.insert(k, v);
277 : }
278 0 : }
279 : };
280 :
281 :
282 : #endif
|
