LCOV - code coverage report
Current view: top level - source/simulation2/system - EntityMap.h (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 56 105 53.3 %
Date: 2022-06-14 00:41:00 Functions: 2 40 5.0 %

          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           5 :     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           5 :         m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1));
      62             : 
      63             :         // create the first element:
      64           5 :         m_Buffer[0].first = INVALID_ENTITY;
      65           5 :         m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
      66             :     }
      67             :     inline ~EntityMap()
      68             :     {
      69           5 :         free(m_Buffer);
      70             :     }
      71             : 
      72             :     // Iterators
      73             :     template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
      74             :     {
      75             :         U* val;
      76             :         inline _iter(U* init) : val(init) {}
      77           0 :         inline U& operator*() { return *val; }
      78           0 :         inline U* operator->() { return val; }
      79             :         inline _iter& operator++() // ++it
      80             :         {
      81        2150 :             ++val;
      82        2168 :             while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
      83             :             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           0 :         inline bool operator==(_iter other) { return val == other.val; }
      93           0 :         inline bool operator!=(_iter other) { return val != other.val; }
      94        4207 :         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           0 :     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           6 :         return ptr;
     105             :     }
     106           0 :     inline iterator end()
     107             :     {
     108        5244 :         return iterator(m_Buffer + m_BufferSize);
     109             :     }
     110           0 :     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           0 :         return ptr;
     115             :     }
     116           0 :     inline const_iterator end() const
     117             :     {
     118         157 :         return const_iterator(m_Buffer + m_BufferSize);
     119             :     }
     120             : 
     121             :     // Size
     122           0 :     inline bool empty() const { return m_Count == 0; }
     123           0 :     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           0 :     void erase(iterator it)
     176             :     {
     177           1 :         value_type* ptr = it.val;
     178           0 :         if (ptr->first != INVALID_ENTITY)
     179             :         {
     180           1 :             ptr->first = INVALID_ENTITY;
     181             :             ptr->second.~T(); // call dtor
     182           1 :             --m_Count;
     183             :         }
     184           0 :     }
     185             :     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             :     }
     198             :     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          12 :         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           1 :         m_Count = 0; // no more valid entities
     212             :     }
     213             : 
     214             :     // Operations
     215           0 :     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           0 :                 return ptr;
     222             :         }
     223          10 :         return m_Buffer + m_BufferSize; // return iterator end()
     224             :     }
     225           0 :     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           0 :                 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

Generated by: LCOV version 1.13