Page MenuHomeWildfire Games
Files F5232723

D8.id2426.diff
No OneTemporary
Actions

Size
32 KB
Referenced Files
None
Subscribers
None

D8.id2426.diff
View Options

Index: source/simulation2/components/CCmpRangeManager.cpp
===================================================================
--- source/simulation2/components/CCmpRangeManager.cpp
+++ source/simulation2/components/CCmpRangeManager.cpp
@@ -539,7 +539,7 @@
entdata.size = cmpObstruction->GetSize().ToInt_RoundToInfinity();
// Remember this entity
- m_EntityData.insert(ent, entdata);
+ m_EntityData.insert_or_assign(ent, entdata);
break;
}
case MT_PositionChanged:
Index: source/simulation2/system/EntityMap.h
===================================================================
--- source/simulation2/system/EntityMap.h
+++ source/simulation2/system/EntityMap.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2013 Wildfire Games.
+/* Copyright (C) 2017 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
@@ -19,226 +19,171 @@
#include "Entity.h"
+#include <utility>
+
+static const size_t ENTITYMAP_DEFAULT_SIZE = 4096;
/**
* A fast replacement for map<entity_id_t, T>.
- * We make the following assumptions:
- * - entity id's (keys) are unique
- * - modifications (add / delete) are far less frequent then look-ups
- * - preformance for iteration is important
+ * Behaves like a much faster std:map.
*/
-template<class T> class EntityMap
+
+template<class V, entity_id_t FIRST_VALID_ENTITY_ID = 1, size_t initialSize = ENTITYMAP_DEFAULT_SIZE>
+class EntityMap
{
private:
- EntityMap(const EntityMap&); // non-copyable
- EntityMap& operator=(const EntityMap&); // non-copyable
+ friend class TestEntityMap;
+
+ EntityMap(const EntityMap&) = delete;
+ EntityMap& operator=(const EntityMap&) = delete;
public:
typedef entity_id_t key_type;
- typedef T mapped_type;
- template<class K, class V> struct key_val {
- typedef K first_type;
- typedef V second_type;
- K first;
- V second;
- };
- typedef key_val<entity_id_t, T> value_type;
+ typedef V mapped_type;
+ typedef std::pair<entity_id_t, V> value_type;
private:
- size_t m_BufferSize; // number of elements in the buffer
- size_t m_BufferCapacity; // capacity of the buffer
- value_type* m_Buffer; // vector with all the mapped key-value pairs
+ std::vector<value_type> m_Data;
- size_t m_Count; // number of 'valid' entity id's
+ // number of 'valid' entity id's
+ size_t m_Count;
+ // EntityMap keeps a valid entity ID at the end() so _iter<>::operator++ knows when to stop the loop
+ // Use FIRST_VALID_ENTITY_ID since we are sure that that is indeed a valid ID.
+#define ITERATOR_GATE {FIRST_VALID_ENTITY_ID, V()}
public:
- inline EntityMap() : m_BufferSize(1), m_BufferCapacity(4096), m_Count(0)
+ EntityMap()
+ : m_Count(0)
{
- // for entitymap we allocate the buffer right away
- // with first element in buffer being the Invalid Entity
- m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1));
-
- // create the first element:
- m_Buffer[0].first = INVALID_ENTITY;
- m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
- }
- inline ~EntityMap()
- {
- free(m_Buffer);
+ ENSURE(FIRST_VALID_ENTITY_ID > INVALID_ENTITY);
+ m_Data.reserve(initialSize);
+ m_Data.push_back(ITERATOR_GATE);
}
- // Iterators
template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
{
U* val;
- inline _iter(U* init) : val(init) {}
- inline U& operator*() { return *val; }
- inline U* operator->() { return val; }
- inline _iter& operator++() // ++it
- {
- ++val;
- while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
+ _iter(U* init) : val(init) {}
+ template<class T>
+ _iter(const _iter<T>& it) : val(it.val) {}
+
+ U& operator*() { return *val; }
+ U* operator->() { return val; }
+
+ _iter& operator++() // ++it
+ {
+ do
+ ++val;
+ while (val->first == INVALID_ENTITY);
return *this;
}
- inline _iter& operator++(int) // it++
+ _iter operator++(int) // it++
{
- U* ptr = val;
- ++val;
- while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
- return ptr;
- }
- inline bool operator==(_iter other) { return val == other.val; }
- inline bool operator!=(_iter other) { return val != other.val; }
- inline operator _iter<U const>() const { return _iter<U const>(val); }
+ _iter orig = *this;
+ ++(*this);
+ return orig;
+ }
+ bool operator==(_iter other) { return val == other.val; }
+ bool operator!=(_iter other) { return val != other.val; }
+ //operator _iter<const U>() const { return _iter<const U>(val); }
};
typedef _iter<value_type> iterator;
- typedef _iter<value_type const> const_iterator;
+ typedef _iter<const value_type> const_iterator;
- inline iterator begin()
+ iterator begin()
{
- value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
- while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
- return ptr;
+ iterator it = &m_Data.front();
+ if (it->first == INVALID_ENTITY)
+ ++it; // skip all invalid entities
+ return it;
}
- inline iterator end()
+
+ const_iterator begin() const
{
- return iterator(m_Buffer + m_BufferSize);
+ const_iterator it = &m_Data.front();
+ if (it->first == INVALID_ENTITY)
+ ++it;
+ return it;
}
- inline const_iterator begin() const
+
+ iterator end()
{
- value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
- while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
- return ptr;
+ return iterator(&m_Data.back());
}
- inline const_iterator end() const
+
+ const_iterator end() const
{
- return const_iterator(m_Buffer + m_BufferSize);
+ return const_iterator(&m_Data.back());
}
- // Size
- inline bool empty() const { return m_Count == 0; }
- inline size_t size() const { return m_Count; }
+ bool empty() const { return m_Count == 0; }
+ size_t size() const { return m_Count; }
- // Modification
- void insert(const key_type key, const mapped_type& value)
+ std::pair<iterator, bool> insert_or_assign(const key_type& key, const mapped_type& value)
{
- if (key >= m_BufferCapacity) // do we need to resize buffer?
- {
- size_t newCapacity = m_BufferCapacity + 4096;
- while (key >= newCapacity) newCapacity += 4096;
- // always allocate +1 behind the scenes, because end() must have a 0xFFFFFFFF key
- value_type* mem = (value_type*)realloc(m_Buffer, sizeof(value_type) * (newCapacity + 1));
- if (!mem)
- {
- debug_warn("EntityMap::insert() realloc failed! Out of memory.");
- throw std::bad_alloc(); // fail to expand and insert
- }
- m_BufferCapacity = newCapacity;
- m_Buffer = mem;
- goto fill_gaps;
- }
- else if (key > m_BufferSize) // weird insert far beyond the end
- {
-fill_gaps:
- // set all entity id's to INVALID_ENTITY inside the new range
- for (size_t i = m_BufferSize; i <= key; ++i)
- m_Buffer[i].first = INVALID_ENTITY;
- m_BufferSize = key; // extend the new size
- }
+ // Note for the future: if we ever re-use IDs, this check should be removed and the insert_or_assign pattern will make more sense.
+ ENSURE (key >= FIRST_VALID_ENTITY_ID);
- value_type& item = m_Buffer[key];
- key_type oldKey = item.first;
- item.first = key;
- if (key == m_BufferSize) // push_back
- {
- ++m_BufferSize; // expand
- ++m_Count;
- new (&item.second) mapped_type(value); // copy ctor to init
- m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
- }
- else if(!item.first) // insert new to middle
+ if (key-FIRST_VALID_ENTITY_ID+1 >= m_Data.size())
{
- ++m_Count;
- new (&item.second) mapped_type(value); // copy ctor to init
+ // Fill [end(),…,key[ invalid entities, our new key, and then add a new iterator gate at the end;
+ // resize, make sure to keep a valid entity ID at the en
+ m_Data.back().first = INVALID_ENTITY; // reset current iterator gate
+ m_Data.resize(key-FIRST_VALID_ENTITY_ID+2, {INVALID_ENTITY, V()});
+ m_Data.back() = ITERATOR_GATE;
}
- else // set existing value
+ bool inserted = false;
+ if (m_Data[key-FIRST_VALID_ENTITY_ID].first == INVALID_ENTITY)
{
- if (oldKey == INVALID_ENTITY)
- m_Count++;
- item.second = value; // overwrite existing
+ inserted = true;
+ m_Count++;
}
+
+ m_Data[key-FIRST_VALID_ENTITY_ID] = {key, value};
+ return {iterator(&m_Data[key-FIRST_VALID_ENTITY_ID]), inserted};
}
- void erase(iterator it)
+ size_t erase(iterator it)
{
- value_type* ptr = it.val;
- if (ptr->first != INVALID_ENTITY)
+ if (it->first != INVALID_ENTITY && it != end())
{
- ptr->first = INVALID_ENTITY;
- ptr->second.~T(); // call dtor
+ it->first = INVALID_ENTITY;
+ it->second.~V(); // call dtor
--m_Count;
+ return 1;
}
+ return 0;
}
- void erase(const entity_id_t key)
- {
- if (key < m_BufferSize)
- {
- value_type* ptr = m_Buffer + key;
- if (ptr->first != INVALID_ENTITY)
- {
- ptr->first = INVALID_ENTITY;
- ptr->second.~T(); // call dtor
- --m_Count;
- }
- }
- }
- inline void clear()
+
+ size_t erase(const key_type& key)
{
- // orphan whole range
- value_type* ptr = m_Buffer;
- value_type* end = m_Buffer + m_BufferSize;
- for (; ptr != end; ++ptr)
- {
- if (ptr->first != INVALID_ENTITY)
- {
- ptr->first = INVALID_ENTITY;
- ptr->second.~T(); // call dtor
- }
- }
- m_Count = 0; // no more valid entities
+ if (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size())
+ return erase(&m_Data.front() + key - FIRST_VALID_ENTITY_ID);
+ return 0;
}
- // Operations
- inline iterator find(const entity_id_t key)
+ void clear()
{
- if (key < m_BufferSize) // is this key in the range of existing entitites?
- {
- value_type* ptr = m_Buffer + key;
- if (ptr->first != INVALID_ENTITY)
- return ptr;
- }
- return m_Buffer + m_BufferSize; // return iterator end()
+ m_Data.clear();
+ m_Count = 0;
+ m_Data.push_back(ITERATOR_GATE);
}
- inline const_iterator find(const entity_id_t key) const
+
+ iterator find(const key_type& key)
{
- if (key < m_BufferSize) // is this key in the range of existing entitites?
- {
- const value_type* ptr = m_Buffer + key;
- if (ptr->first != INVALID_ENTITY)
- return ptr;
- }
- return m_Buffer + m_BufferSize; // return iterator end()
+ if (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size() && m_Data[key-FIRST_VALID_ENTITY_ID].first != INVALID_ENTITY)
+ return &m_Data.front() + (key - FIRST_VALID_ENTITY_ID);
+ return end();
}
- inline size_t count(const entity_id_t key) const
+
+ const_iterator find(const key_type& key) const
{
- if (key < m_BufferSize)
- {
- if (m_Buffer[key].first != INVALID_ENTITY)
- return 1;
- }
- return 0;
+ if (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size() && m_Data[key-FIRST_VALID_ENTITY_ID].first != INVALID_ENTITY)
+ return &m_Data.front() + (key - FIRST_VALID_ENTITY_ID);
+ return end();
}
+#undef ITERATOR_GATE
};
template<class VSerializer>
@@ -273,7 +218,7 @@
V v;
deserialize.NumberU32_Unbounded("key", k);
VSerializer()(deserialize, "value", v);
- value.insert(k, v);
+ value.insert_or_assign(k, v);
}
}
};
Index: source/simulation2/system/EntityMap_old.h
===================================================================
--- /dev/null
+++ source/simulation2/system/EntityMap_old.h
@@ -0,0 +1,283 @@
+/* Copyright (C) 2013 Wildfire Games.
+ * This file is part of 0 A.D.
+ *
+ * 0 A.D. 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, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * 0 A.D. 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 0 A.D. If not, see <http://www.gnu.org/licenses/>.
+ */
+#ifndef INCLUDED_ENTITYMAP
+#define INCLUDED_ENTITYMAP
+
+#include "Entity.h"
+
+/**
+ * A fast replacement for map<entity_id_t, T>.
+ * We make the following assumptions:
+ * - entity id's (keys) are unique
+ * - modifications (add / delete) are far less frequent then look-ups
+ * - preformance for iteration is important
+ */
+template<class T> class EntityMap
+{
+private:
+ friend class TestEntityMapOld;
+ EntityMap(const EntityMap&); // non-copyable
+ EntityMap& operator=(const EntityMap&); // non-copyable
+
+public:
+ typedef entity_id_t key_type;
+ typedef T mapped_type;
+ template<class K, class V> struct key_val {
+ typedef K first_type;
+ typedef V second_type;
+ K first;
+ V second;
+ };
+ typedef key_val<entity_id_t, T> value_type;
+
+private:
+ size_t m_BufferSize; // number of elements in the buffer
+ size_t m_BufferCapacity; // capacity of the buffer
+ value_type* m_Buffer; // vector with all the mapped key-value pairs
+
+ size_t m_Count; // number of 'valid' entity id's
+
+public:
+
+ inline EntityMap() : m_BufferSize(1), m_BufferCapacity(4096), m_Count(0)
+ {
+ // for entitymap we allocate the buffer right away
+ // with first element in buffer being the Invalid Entity
+ m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1));
+
+ // create the first element:
+ m_Buffer[0].first = INVALID_ENTITY;
+ m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
+ }
+ inline ~EntityMap()
+ {
+ free(m_Buffer);
+ }
+
+ // Iterators
+ template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
+ {
+ U* val;
+ inline _iter(U* init) : val(init) {}
+ inline U& operator*() { return *val; }
+ inline U* operator->() { return val; }
+ inline _iter& operator++() // ++it
+ {
+ ++val;
+ while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
+ return *this;
+ }
+ inline _iter& operator++(int) // it++
+ {
+ U* ptr = val;
+ ++val;
+ while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
+ return ptr;
+ }
+ inline bool operator==(_iter other) { return val == other.val; }
+ inline bool operator!=(_iter other) { return val != other.val; }
+ inline operator _iter<U const>() const { return _iter<U const>(val); }
+ };
+
+ typedef _iter<value_type> iterator;
+ typedef _iter<value_type const> const_iterator;
+
+ inline iterator begin()
+ {
+ value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
+ while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
+ return ptr;
+ }
+ inline iterator end()
+ {
+ return iterator(m_Buffer + m_BufferSize);
+ }
+ inline const_iterator begin() const
+ {
+ value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
+ while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
+ return ptr;
+ }
+ inline const_iterator end() const
+ {
+ return const_iterator(m_Buffer + m_BufferSize);
+ }
+
+ // Size
+ inline bool empty() const { return m_Count == 0; }
+ inline size_t size() const { return m_Count; }
+
+ // Modification
+ void insert(const key_type key, const mapped_type& value)
+ {
+ if (key >= m_BufferCapacity) // do we need to resize buffer?
+ {
+ size_t newCapacity = m_BufferCapacity + 4096;
+ while (key >= newCapacity) newCapacity += 4096;
+ // always allocate +1 behind the scenes, because end() must have a 0xFFFFFFFF key
+ value_type* mem = (value_type*)realloc(m_Buffer, sizeof(value_type) * (newCapacity + 1));
+ if (!mem)
+ {
+ debug_warn("EntityMap::insert() realloc failed! Out of memory.");
+ throw std::bad_alloc(); // fail to expand and insert
+ }
+ m_BufferCapacity = newCapacity;
+ m_Buffer = mem;
+ goto fill_gaps;
+ }
+ else if (key > m_BufferSize) // weird insert far beyond the end
+ {
+fill_gaps:
+ // set all entity id's to INVALID_ENTITY inside the new range
+ for (size_t i = m_BufferSize; i <= key; ++i)
+ m_Buffer[i].first = INVALID_ENTITY;
+ m_BufferSize = key; // extend the new size
+ }
+
+ value_type& item = m_Buffer[key];
+ key_type oldKey = item.first;
+ item.first = key;
+ if (key == m_BufferSize) // push_back
+ {
+ ++m_BufferSize; // expand
+ ++m_Count;
+ new (&item.second) mapped_type(value); // copy ctor to init
+ m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
+ }
+ else if(!item.first) // insert new to middle
+ {
+ ++m_Count;
+ new (&item.second) mapped_type(value); // copy ctor to init
+ }
+ else // set existing value
+ {
+ if (oldKey == INVALID_ENTITY)
+ m_Count++;
+ item.second = value; // overwrite existing
+ }
+ }
+
+ void erase(iterator it)
+ {
+ value_type* ptr = it.val;
+ if (ptr->first != INVALID_ENTITY)
+ {
+ ptr->first = INVALID_ENTITY;
+ ptr->second.~T(); // call dtor
+ --m_Count;
+ }
+ }
+ void erase(const entity_id_t key)
+ {
+ if (key < m_BufferSize)
+ {
+ value_type* ptr = m_Buffer + key;
+ if (ptr->first != INVALID_ENTITY)
+ {
+ ptr->first = INVALID_ENTITY;
+ ptr->second.~T(); // call dtor
+ --m_Count;
+ }
+ }
+ }
+ inline void clear()
+ {
+ // orphan whole range
+ value_type* ptr = m_Buffer;
+ value_type* end = m_Buffer + m_BufferSize;
+ for (; ptr != end; ++ptr)
+ {
+ if (ptr->first != INVALID_ENTITY)
+ {
+ ptr->first = INVALID_ENTITY;
+ ptr->second.~T(); // call dtor
+ }
+ }
+ m_Count = 0; // no more valid entities
+ }
+
+ // Operations
+ inline iterator find(const entity_id_t key)
+ {
+ if (key < m_BufferSize) // is this key in the range of existing entitites?
+ {
+ value_type* ptr = m_Buffer + key;
+ if (ptr->first != INVALID_ENTITY)
+ return ptr;
+ }
+ return m_Buffer + m_BufferSize; // return iterator end()
+ }
+ inline const_iterator find(const entity_id_t key) const
+ {
+ if (key < m_BufferSize) // is this key in the range of existing entitites?
+ {
+ const value_type* ptr = m_Buffer + key;
+ if (ptr->first != INVALID_ENTITY)
+ return ptr;
+ }
+ return m_Buffer + m_BufferSize; // return iterator end()
+ }
+ inline size_t count(const entity_id_t key) const
+ {
+ if (key < m_BufferSize)
+ {
+ if (m_Buffer[key].first != INVALID_ENTITY)
+ return 1;
+ }
+ return 0;
+ }
+};
+
+template<class VSerializer>
+struct SerializeEntityMap
+{
+ template<class V>
+ void operator()(ISerializer& serialize, const char* UNUSED(name), EntityMap<V>& value)
+ {
+ size_t len = value.size();
+ serialize.NumberU32_Unbounded("length", (u32)len);
+ size_t count = 0;
+ for (typename EntityMap<V>::iterator it = value.begin(); it != value.end(); ++it)
+ {
+ serialize.NumberU32_Unbounded("key", it->first);
+ VSerializer()(serialize, "value", it->second);
+ count++;
+ }
+ // test to see if the entityMap count wasn't wrong
+ // (which causes a crashing deserialisation)
+ ENSURE(count == len);
+ }
+
+ template<class V>
+ void operator()(IDeserializer& deserialize, const char* UNUSED(name), EntityMap<V>& value)
+ {
+ value.clear();
+ uint32_t len;
+ deserialize.NumberU32_Unbounded("length", len);
+ for (size_t i = 0; i < len; ++i)
+ {
+ entity_id_t k;
+ V v;
+ deserialize.NumberU32_Unbounded("key", k);
+ VSerializer()(deserialize, "value", v);
+ value.insert(k, v);
+ }
+ }
+};
+
+
+#endif
Index: source/simulation2/tests/test_EntityMap.h
===================================================================
--- /dev/null
+++ source/simulation2/tests/test_EntityMap.h
@@ -0,0 +1,309 @@
+/* Copyright (C) 2010 Wildfire Games.
+ * This file is part of 0 A.D.
+ *
+ * 0 A.D. 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, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * 0 A.D. 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 0 A.D. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "lib/self_test.h"
+#include "lib/timer.h"
+
+#include "simulation2/serialization/ISerializer.h"
+#include "simulation2/serialization/IDeserializer.h"
+
+#include "simulation2/system/EntityMap.h"
+
+class TestEntityMap : public CxxTest::TestSuite
+{
+public:
+ void setUp()
+ {
+ }
+
+ void tearDown()
+ {
+ }
+
+ void test_insert()
+ {
+ EntityMap<int, 1> test;
+
+ TS_ASSERT(test.empty());
+
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+ test.insert(4,5);
+ test.insert(4,6);
+
+ TS_ASSERT(test.m_Data.size() == 5);
+ TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
+ TS_ASSERT(test.size() == 4);
+ TS_ASSERT(test.find(3)->second == 3);
+ TS_ASSERT(test.find(4)->second == 6);
+
+ test.insert(10,7);
+ TS_ASSERT(test.m_Data.size() == 11);
+ TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
+ TS_ASSERT(test.size() == 5);
+ TS_ASSERT(test.find(4)->second == 6);
+ TS_ASSERT(test.find(5) == test.end());
+ TS_ASSERT(test.find(6) == test.end());
+ TS_ASSERT(test.find(7) == test.end());
+ TS_ASSERT(test.find(8) == test.end());
+ TS_ASSERT(test.find(9) == test.end());
+ TS_ASSERT(test.find(10)->second == 7);
+
+ EntityMap<int, 5> test2;
+
+ test2.insert(8,5);
+ TS_ASSERT(test2.find(8)->second == 5);
+ TS_ASSERT(test2.m_Data.size() == 5);
+ TS_ASSERT(test2.size() == 1);
+
+ }
+ void test_iterators()
+ {
+ EntityMap<int, 1> test;
+
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+
+ EntityMap<int, 1>::iterator it = test.begin();
+ TS_ASSERT(it->first == 1);
+ it++;
+ TS_ASSERT(it->first == 2);
+ ++it;
+ TS_ASSERT(it->first == 3);
+ it = test.end();
+ TS_ASSERT(it->first == test.m_Data.back().first);
+
+ EntityMap<int, 1>::const_iterator cit = test.begin();
+ TS_ASSERT(cit->first == 1);
+ cit = test.end();
+ TS_ASSERT(cit->first == test.m_Data.back().first);
+
+ size_t iter = 0;
+ for (auto& v : test)
+ {
+ ++iter;
+ TS_ASSERT(test.find(iter)->second == (int)iter);
+ TS_ASSERT(test.find(iter)->second == v.second);
+ }
+ TS_ASSERT(iter == 4);
+
+ test.clear();
+
+ test.insert(10,1);
+ test.insert(20,2);
+ test.insert(30,3);
+ test.insert(40,4);
+
+ it = test.begin();
+ TS_ASSERT(it->second == 1);
+ it++;
+ TS_ASSERT(it->second == 2);
+ ++it;
+ TS_ASSERT(it->second == 3);
+ it = test.end();
+ TS_ASSERT(it->first == test.m_Data.back().first);
+
+ }
+
+ void test_erase()
+ {
+ EntityMap<int> test;
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+
+ test.erase(2);
+
+ TS_ASSERT(test.m_Data.size() == 5);
+ TS_ASSERT(test.size() == 3);
+ TS_ASSERT(test.find(2) == test.end());
+
+ test.erase(1);
+ test.erase(3);
+ TS_ASSERT(test.erase(4) == 1);
+
+ TS_ASSERT(test.m_Data.size() == 5);
+ TS_ASSERT(test.size() == 0);
+
+ TS_ASSERT(test.erase(5) == 0);
+
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+
+ test.erase(test.begin());
+ TS_ASSERT(test.m_Data.size() == 5);
+ TS_ASSERT(test.size() == 3);
+ TS_ASSERT(test.find(1) == test.end());
+
+ TS_ASSERT(test.erase(test.end()) == 0);
+ TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
+ }
+
+ void test_clear()
+ {
+ EntityMap<int> test;
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+
+ test.clear();
+
+ TS_ASSERT(test.m_Data.size() == 1);
+ TS_ASSERT(test.size() == 0);
+ }
+
+ void test_find()
+ {
+ EntityMap<int> test;
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(40,4);
+
+ TS_ASSERT(test.find(1)->second == 1);
+ TS_ASSERT(test.find(40)->second == 4);
+ TS_ASSERT(test.find(30) == test.end());
+ }
+
+ void test_perf()
+ {
+ EntityMap<int> test;
+ std::cout << std::endl << "Testing performance of EntityMap" << std::endl;
+
+ double t = timer_Time();
+ for (int i = 1; i <= 200000; ++i)
+ test.insert(i,i);
+ double tt = timer_Time() - t;
+ std::cout << "Inserting 200K elements in order: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (int i = 1; i <= 200000; ++i)
+ test.erase(i);
+ tt = timer_Time() - t;
+ std::cout << "Erasing 200K elements, by key: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (int i = 200000; i >= 1; --i)
+ test.insert(i,i);
+ tt = timer_Time() - t;
+ std::cout << "Inserting 200K elements in reverse order: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (auto i = test.begin(); i != test.end(); ++i)
+ test.erase(i);
+ tt = timer_Time() - t;
+ std::cout << "Erasing 200K elements, by iterator: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (int i = 1; i <= 200000; ++i)
+ test.erase(i);
+ tt = timer_Time() - t;
+ std::cout << "Erasing 200K non-existing elements: " << tt << "s" << std::endl;
+
+ // prep random vector
+ std::vector<int> vec;
+ for (int i = 1; i <= 200000; ++i)
+ vec.push_back(i);
+ std::random_shuffle(vec.begin(), vec.end());
+
+ for (int i = 1; i <= 200000; ++i)
+ test.insert(i,i);
+
+ t = timer_Time();
+ for (int i = 1; i <= 200000; ++i)
+ test.find(vec[i])->second = 3;
+ tt = timer_Time() - t;
+ std::cout << "200K random lookups in random order: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (auto& p : test)
+ p.second = 3;
+ tt = timer_Time() - t;
+ std::cout << "auto iteration on 200K continuous entitymap: " << tt << "s" << std::endl;
+
+ test.clear();
+
+ for (int i = 1; i <= 200000; ++i)
+ test.insert(i*5,i);
+
+ t = timer_Time();
+ for (auto& p : test)
+ p.second = 3;
+ tt = timer_Time() - t;
+ std::cout << "auto iteration on 200K sparse (holes of 5): " << tt << "s" << std::endl;
+
+ test.clear();
+
+ for (int i = 1; i <= 4000; ++i)
+ test.insert(i*50,i);
+
+ t = timer_Time();
+ for (auto& p : test)
+ p.second = 3;
+ tt = timer_Time() - t;
+ std::cout << "auto iteration on 4K sparse (holes of 50): " << tt << "s" << std::endl;
+
+ test.clear();
+
+ for (int i = 1; i <= 200000; ++i)
+ test.insert(i*50,i);
+
+ t = timer_Time();
+ for (auto& p : test)
+ p.second = 3;
+ tt = timer_Time() - t;
+ std::cout << "auto iteration on 200K sparse (holes of 50): " << tt << "s" << std::endl;
+
+ test.clear();
+
+ for (int i = 1; i <= 2000000; ++i)
+ test.insert(i*50,i);
+
+ t = timer_Time();
+ for (auto i = test.begin(); i != test.end(); ++i)
+ i->second = 3;
+ tt = timer_Time() - t;
+ std::cout << "manual ++iteration on 2000K sparse (holes of 50) (warmup 1): " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (auto i = test.begin(); i != test.end(); i++)
+ i->second = 3;
+ tt = timer_Time() - t;
+ std::cout << "manual iteration++ on 2000K sparse (holes of 50) (warmup 2): " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (auto i = test.begin(); i != test.end(); ++i)
+ i->second = 3;
+ tt = timer_Time() - t;
+ std::cout << "manual ++iteration on 2000K sparse (holes of 50): " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (auto i = test.begin(); i != test.end(); i++)
+ i->second = 3;
+ tt = timer_Time() - t;
+ std::cout << "manual iteration++ on 2000K sparse (holes of 50): " << tt << "s" << std::endl;
+
+ }
+};
Index: source/simulation2/tests/test_EntityMap_old.h
===================================================================
--- /dev/null
+++ source/simulation2/tests/test_EntityMap_old.h
@@ -0,0 +1,238 @@
+/* Copyright (C) 2010 Wildfire Games.
+ * This file is part of 0 A.D.
+ *
+ * 0 A.D. 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, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * 0 A.D. 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 0 A.D. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "lib/self_test.h"
+#include "lib/timer.h"
+
+#include "simulation2/serialization/ISerializer.h"
+#include "simulation2/serialization/IDeserializer.h"
+
+#include "simulation2/system/EntityMap_old.h"
+
+class TestEntityMapOld : public CxxTest::TestSuite
+{
+public:
+ void setUp()
+ {
+ }
+
+ void tearDown()
+ {
+ }
+
+ void test_insert()
+ {
+ EntityMap<int> test;
+
+ TS_ASSERT(test.empty());
+
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+ test.insert(4,5);
+ test.insert(4,6);
+
+ TS_ASSERT(test.size() == 4);
+ TS_ASSERT(test.find(3)->second == 3);
+ TS_ASSERT(test.find(4)->second == 6);
+
+ test.insert(10,7);
+ TS_ASSERT(test.size() == 5);
+ TS_ASSERT(test.find(4)->second == 6);
+ TS_ASSERT(test.find(5) == test.end());
+ TS_ASSERT(test.find(6) == test.end());
+ TS_ASSERT(test.find(7) == test.end());
+ TS_ASSERT(test.find(8) == test.end());
+ TS_ASSERT(test.find(9) == test.end());
+ TS_ASSERT(test.find(10)->second == 7);
+
+ }
+ void test_iterators()
+ {
+ EntityMap<int> test;
+
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+
+ EntityMap<int>::iterator it = test.begin();
+ TS_ASSERT(it->first == 1);
+
+ EntityMap<int>::const_iterator cit = test.begin();
+ TS_ASSERT(cit->first == 1);
+
+ size_t iter = 0;
+ for (auto& v : test)
+ {
+ ++iter;
+ TS_ASSERT(test.find(iter)->second == (int)iter);
+ TS_ASSERT(test.find(iter)->second == v.second);
+ }
+ TS_ASSERT(iter == 4);
+ }
+
+ void test_erase()
+ {
+ EntityMap<int> test;
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+
+ test.erase(2);
+
+ TS_ASSERT(test.size() == 3);
+ TS_ASSERT(test.find(2) == test.end());
+
+ test.erase(1);
+ test.erase(3);
+ test.erase(4);
+
+ TS_ASSERT(test.size() == 0);
+
+
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+
+ test.erase(test.begin());
+ TS_ASSERT(test.size() == 3);
+ TS_ASSERT(test.find(1) == test.end());
+
+ }
+
+ void test_clear()
+ {
+ EntityMap<int> test;
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(4,4);
+
+ test.clear();
+
+ TS_ASSERT(test.size() == 0);
+ }
+
+ void test_find()
+ {
+ EntityMap<int> test;
+ test.insert(1,1);
+ test.insert(2,2);
+ test.insert(3,3);
+ test.insert(40,4);
+
+ TS_ASSERT(test.find(1)->second == 1);
+ TS_ASSERT(test.find(40)->second == 4);
+ TS_ASSERT(test.find(30) == test.end());
+ }
+
+ void test_perf()
+ {
+ EntityMap<int> test;
+ std::cout << std::endl << "Testing performance of old EntityMap" << std::endl;
+
+ double t = timer_Time();
+ for (int i = 1; i <= 200000; ++i)
+ test.insert(i,i);
+ double tt = timer_Time() - t;
+ std::cout << "Inserting 200K elements in order: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (int i = 1; i <= 200000; ++i)
+ test.erase(i);
+ tt = timer_Time() - t;
+ std::cout << "Erasing 200K elements, by key: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (int i = 200000; i >= 1; --i)
+ test.insert(i,i);
+ tt = timer_Time() - t;
+ std::cout << "Inserting 200K elements in reverse order: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (auto i = test.begin(); i != test.end(); ++i)
+ test.erase(i);
+ tt = timer_Time() - t;
+ std::cout << "Erasing 200K elements, by iterator: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (int i = 1; i <= 200000; ++i)
+ test.erase(i);
+ tt = timer_Time() - t;
+ std::cout << "Erasing 200K non-existing elements: " << tt << "s" << std::endl;
+
+ // prep random vector
+ std::vector<int> vec;
+ for (int i = 1; i <= 200000; ++i)
+ vec.push_back(i);
+ std::random_shuffle(vec.begin(), vec.end());
+
+ for (int i = 1; i <= 200000; ++i)
+ test.insert(i,i);
+
+ t = timer_Time();
+ for (int i = 1; i <= 200000; ++i)
+ test.find(vec[i])->second = 3;
+ tt = timer_Time() - t;
+ std::cout << "200K random lookups in random order: " << tt << "s" << std::endl;
+
+ t = timer_Time();
+ for (auto& p : test)
+ p.second = 3;
+ tt = timer_Time() - t;
+ std::cout << "auto iteration on 200K continuous entitymap: " << tt << "s" << std::endl;
+
+ test.clear();
+
+ for (int i = 1; i <= 200000; ++i)
+ test.insert(i*5,i);
+
+ t = timer_Time();
+ for (auto& p : test)
+ p.second = 3;
+ tt = timer_Time() - t;
+ std::cout << "auto iteration on 200K sparse (holes of 5): " << tt << "s" << std::endl;
+
+ test.clear();
+
+ for (int i = 1; i <= 4000; ++i)
+ test.insert(i*50,i);
+
+ t = timer_Time();
+ for (auto& p : test)
+ p.second = 3;
+ tt = timer_Time() - t;
+ std::cout << "auto iteration on 4K sparse (holes of 50): " << tt << "s" << std::endl;
+
+ test.clear();
+
+ for (int i = 1; i <= 200000; ++i)
+ test.insert(i*50,i);
+
+ t = timer_Time();
+ for (auto& p : test)
+ p.second = 3;
+ tt = timer_Time() - t;
+ std::cout << "auto iteration on 200K sparse (holes of 50): " << tt << "s" << std::endl;
+
+ test.clear();
+ }
+};

File Metadata

Mime Type
text/plain
Expires
Sat, Sep 28, 4:08 PM (9 h, 47 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
3385556
Default Alt Text
D8.id2426.diff (32 KB)

Event Timeline

Wildfire Games · Phabricator