Differential D8 Diff 7278 ps/trunk/source/simulation2/system/EntityMap.h

Changeset View

Standalone View

ps/trunk/source/simulation2/system/EntityMap.h

/* Copyright (C) 2013 Wildfire Games.		/* Copyright (C) 2019 Wildfire Games.
* This file is part of 0 A.D.		* This file is part of 0 A.D.
*		*
* 0 A.D. is free software: you can redistribute it and/or modify		* 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		* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or		* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.		* (at your option) any later version.
*		*
* 0 A.D. is distributed in the hope that it will be useful,		* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of		* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.		* GNU General Public License for more details.
*		*
* You should have received a copy of the GNU General Public License		* 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/>.		* along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
*/		*/
#ifndef INCLUDED_ENTITYMAP		#ifndef INCLUDED_ENTITYMAP
#define INCLUDED_ENTITYMAP		#define INCLUDED_ENTITYMAP

#include "Entity.h"		#include "Entity.h"

		#include <utility>

		static const size_t ENTITYMAP_DEFAULT_SIZE = 4096;
/**		/**
* A fast replacement for map<entity_id_t, T>.		* A fast replacement for map<entity_id_t, T>.
* We make the following assumptions:		* Behaves like a much faster std:map.
* - entity id's (keys) are unique		* The drawback is memory usage, as this uses sparse storage.
* - modifications (add / delete) are far less frequent then look-ups		* So creating/deleting entities will lead to inefficiency.
* - preformance for iteration is important
*/		*/
template<class T> class EntityMap
		template<class V, entity_id_t FIRST_VALID_ENTITY_ID = 1, size_t initialSize = ENTITYMAP_DEFAULT_SIZE>
		class EntityMap
{		{
		static_assert(FIRST_VALID_ENTITY_ID > INVALID_ENTITY, "Entity IDs start at INVALID_ENTITY");
private:		private:
EntityMap(const EntityMap&); // non-copyable		friend class TestEntityMap;
EntityMap& operator=(const EntityMap&); // non-copyable
		EntityMap(const EntityMap&) = delete;
		EntityMap& operator=(const EntityMap&) = delete;

public:		public:
typedef entity_id_t key_type;		typedef entity_id_t key_type;
typedef T mapped_type;		typedef V mapped_type;
template<class K, class V> struct key_val {		typedef std::pair<entity_id_t, V> value_type;
typedef K first_type;
typedef V second_type;
K first;
V second;
};
typedef key_val<entity_id_t, T> value_type;

private:		private:
size_t m_BufferSize; // number of elements in the buffer		std::vector<value_type> m_Data;
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		// 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_FENCE {FIRST_VALID_ENTITY_ID, V()}
public:		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);		m_Data.reserve(initialSize);
		m_Data.push_back(ITERATOR_FENCE);
}		}

// Iterators
template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>		template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
{		{
U* val;		U* val;
inline _iter(U* init) : val(init) {}		_iter(U* init) : val(init) {}
inline U& operator() { return val; }		template<class T>
inline U* operator->() { return val; }		_iter(const _iter<T>& it) : val(it.val) {}
inline _iter& operator++() // ++it
		U& operator() { return val; }
		U* operator->() { return val; }

		_iter& operator++() // ++it
{		{
		do
++val;		++val;
while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities		while (val->first == INVALID_ENTITY);
return *this;		return *this;
}		}
inline _iter& operator++(int) // it++		_iter operator++(int) // it++
{		{
U* ptr = val;		_iter orig = *this;
++val;		++(*this);
while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities		return orig;
return ptr;
}		}
inline bool operator==(_iter other) { return val == other.val; }		bool operator==(_iter other) { return val == other.val; }
inline bool operator!=(_iter other) { return val != other.val; }		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> 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		iterator it = &m_Data.front();
while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities		if (it->first == INVALID_ENTITY)
return ptr;		++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		return iterator(&m_Data.back()); // return the ITERATOR_FENCE, see above
while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
return ptr;
}		}
inline const_iterator end() const
		const_iterator end() const
{		{
return const_iterator(m_Buffer + m_BufferSize);		return const_iterator(&m_Data.back()); // return the ITERATOR_FENCE, see above
}		}

// Size		bool empty() const { return m_Count == 0; }
inline bool empty() const { return m_Count == 0; }		size_t size() const { return m_Count; }
inline size_t size() const { return m_Count; }

// Modification		std::pair<iterator, bool> insert_or_assign(const key_type& key, const mapped_type& value)
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:		ENSURE(key >= FIRST_VALID_ENTITY_ID);
// 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];		if (key-FIRST_VALID_ENTITY_ID+1 >= m_Data.size())
key_type oldKey = item.first;
item.first = key;
if (key == m_BufferSize) // push_back
{		{
++m_BufferSize; // expand		// Fill [end(),…,key[ invalid entities, our new key, and then add a new iterator gate at the end;
++m_Count;		// resize, make sure to keep a valid entity ID at the end by adding a new ITERATOR_FENCE
new (&item.second) mapped_type(value); // copy ctor to init		m_Data.back().first = INVALID_ENTITY; // reset current iterator gate
m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF		m_Data.resize(key-FIRST_VALID_ENTITY_ID+2, {INVALID_ENTITY, V()});
		m_Data.back() = ITERATOR_FENCE;
}		}
else if(!item.first) // insert new to middle		bool inserted = false;
		if (m_Data[key-FIRST_VALID_ENTITY_ID].first == INVALID_ENTITY)
{		{
		inserted = true;
++m_Count;		++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)		m_Data[key-FIRST_VALID_ENTITY_ID] = {key, value};
{		return {iterator(&m_Data[key-FIRST_VALID_ENTITY_ID]), inserted};
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)
{		size_t erase(iterator it)
if (key < m_BufferSize)
{		{
value_type* ptr = m_Buffer + key;		if (it->first != INVALID_ENTITY && it != end())
if (ptr->first != INVALID_ENTITY)
{		{
ptr->first = INVALID_ENTITY;		it->first = INVALID_ENTITY;
ptr->second.~T(); // call dtor		it->second.~V(); // call dtor
--m_Count;		--m_Count;
		return 1;
}		}
		return 0;
}		}
}
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;		if (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size())
ptr->second.~T(); // call dtor		return erase(&m_Data.front() + key - FIRST_VALID_ENTITY_ID);
}		return 0;
}
m_Count = 0; // no more valid entities
}		}

// Operations		void clear()
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;		m_Data.clear();
if (ptr->first != INVALID_ENTITY)		m_Count = 0;
return ptr;		m_Data.push_back(ITERATOR_FENCE);
}		}
return m_Buffer + m_BufferSize; // return iterator end()
}		iterator find(const key_type& key)
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 (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size() && m_Data[key-FIRST_VALID_ENTITY_ID].first != INVALID_ENTITY)
if (ptr->first != INVALID_ENTITY)		return &m_Data.front() + (key - FIRST_VALID_ENTITY_ID);
return ptr;		return end();
}		}
return m_Buffer + m_BufferSize; // return iterator end()
}		const_iterator find(const key_type& key) const
inline size_t count(const entity_id_t key) const
{
if (key < m_BufferSize)
{		{
if (m_Buffer[key].first != INVALID_ENTITY)		if (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size() && m_Data[key-FIRST_VALID_ENTITY_ID].first != INVALID_ENTITY)
return 1;		return &m_Data.front() + (key - FIRST_VALID_ENTITY_ID);
}		return end();
return 0;
}		}
		#undef ITERATOR_FENCE
};		};

template<class VSerializer>		template<class VSerializer>
struct SerializeEntityMap		struct SerializeEntityMap
{		{
template<class V>		template<class V>
void operator()(ISerializer& serialize, const char* UNUSED(name), EntityMap<V>& value)		void operator()(ISerializer& serialize, const char* UNUSED(name), EntityMap<V>& value)
{		{
Show All 18 Lines	void operator()(IDeserializer& deserialize, const char* UNUSED(name), EntityMap<V>& value)
uint32_t len;		uint32_t len;
deserialize.NumberU32_Unbounded("length", len);		deserialize.NumberU32_Unbounded("length", len);
for (size_t i = 0; i < len; ++i)		for (size_t i = 0; i < len; ++i)
{		{
entity_id_t k;		entity_id_t k;
V v;		V v;
deserialize.NumberU32_Unbounded("key", k);		deserialize.NumberU32_Unbounded("key", k);
VSerializer()(deserialize, "value", v);		VSerializer()(deserialize, "value", v);
value.insert(k, v);		value.insert_or_assign(k, v);
}		}
}		}
};		};


#endif		#endif