/** * @file include/ActivMiddleware/Misc/UnorderedMap.h * * @brief Header for the UnorderedMap class. */ #if (!defined ACTIV_MISC_UNORDERED_MAP_H) #define ACTIV_MISC_UNORDERED_MAP_H #include "Detail/UnorderedMapDetail.h" //! Activ namespace. namespace Activ { /** * @brief Replacement for unordered_map that pools memory used for allocating nodes. * * The interface resembles std::unordered_map, but has not been exhaustively checked for compatibility (for the features that are * present). * * Under the hood uses Boost intrusive unordered_set. This was chosen for 2 main reasons: * 1. In the future it would be good to support incremental rehashing. * 2. It simplifies pooling/allocation, though it may have been possible to use stateful allocators in C++03 using boost somehow. * * Dereferencing an iterator is a little odd in that it gives access to the underlying node type. */ template ::type> class UnorderedMap { private: //! The node type. typedef Detail::UnorderedMapNode Node; //! The node pool type. typedef Detail::UnorderedMapPool NodePool; //! Underlying implementation type. typedef typename IntrusiveSetHelper::UnorderedSet IntrusiveSet; public: typedef typename IntrusiveSet::key_type key_type; typedef typename std::pair value_type; typedef typename IntrusiveSet::iterator iterator; typedef typename IntrusiveSet::const_iterator const_iterator; /** * @brief Constructor. * * @param bucketCount initial bucket count, default 256. */ UnorderedMap(const size_t bucketCount = 256); // Iterator methods. iterator begin() { return m_set.begin(); } const_iterator begin() const { return m_set.begin(); } const_iterator cbegin() const { return m_set.begin(); } iterator end() { return m_set.end(); } const_iterator end() const { return m_set.end(); } const_iterator cend() const { return m_set.end(); } // Capacity methods. bool empty() const { return m_set.empty(); } size_t size() const { return m_set.size(); } // Modifier methods. void clear() { return m_set.clear(); } std::pair insert(const value_type &value); template std::pair emplace(const key_type &key, const A0 &a0); // Erase methods. void erase(const iterator &pos) { m_set.erase_stable(pos); } void erase(const const_iterator &pos) { m_set.erase_stable(pos); } size_t erase(const key_type &key) { return m_set.erase_stable(key); } // Lookup methods. T &operator[](const key_type &key); iterator find(const key_type &key) { return m_set.find(key); } const_iterator find(const key_type &key) const { return m_set.find(key); } // Bucket interface. size_t bucket_count() const { return m_set.GetBucketCount(); } // Hash policy. float load_factor() const; float max_load_factor() const; void max_load_factor(const float ml); // Custom interface /** * @brief Reserve space for nodeCount elements. * * Buckets and nodes are allocated. * * All iterators will be invalidated after this call. * * @param nodeCount the number of nodes to reserve. */ void reserve(const size_t nodeCount); private: NodePool m_nodePool; ///< The pool to allocate nodes from. IntrusiveSet m_set; ///< The underlying implementation. }; // --------------------------------------------------------------------------------------------------------------------------------- template inline UnorderedMap::UnorderedMap(const size_t bucketCount) : m_nodePool(sizeof(Node)), m_set(Detail::UnorderedMapSanitiseBucketCount(bucketCount), 80, 13, typename Node::Disposer(m_nodePool)) { } // --------------------------------------------------------------------------------------------------------------------------------- template inline std::pair::iterator, bool> UnorderedMap::insert(const value_type &value) { std::pair result = m_set.insert_check(value.first); if (result.second) { void *pBuffer = m_nodePool.malloc(); if (ACTIV_UNLIKELY(!pBuffer)) throw std::bad_alloc(); try { Node *pNode = new (pBuffer) Node(value); result.first = m_set.insert_commit_unstable(pNode); } ACTIV_CATCH_ALL() { m_nodePool.free(pBuffer); throw; } } return result; } // --------------------------------------------------------------------------------------------------------------------------------- template template inline std::pair::iterator, bool> UnorderedMap::emplace(const key_type &key, const A0 &a0) { std::pair result = m_set.insert_check(key); if (result.second) { void *pBuffer = m_nodePool.malloc(); if (ACTIV_UNLIKELY(!pBuffer)) throw std::bad_alloc(); try { Node *pNode = new (pBuffer) Node(key, a0); result.first = m_set.insert_commit_unstable(pNode); } ACTIV_CATCH_ALL() { m_nodePool.free(pBuffer); throw; } } return result; } // --------------------------------------------------------------------------------------------------------------------------------- template inline T &UnorderedMap::operator[](const key_type &key) { std::pair result = m_set.insert_check(key); if (result.second) { void *pBuffer = m_nodePool.malloc(); if (ACTIV_UNLIKELY(!pBuffer)) throw std::bad_alloc(); try { Node *pNode = new (pBuffer) Node(key, T()); result.first = m_set.insert_commit_unstable(pNode); } ACTIV_CATCH_ALL() { m_nodePool.free(pBuffer); throw; } } return result.first->second; } // --------------------------------------------------------------------------------------------------------------------------------- template inline float UnorderedMap::load_factor() const { assert(bucket_count() > 0); return float(size()) / bucket_count(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline float UnorderedMap::max_load_factor() const { return float(m_set.GetBucketGrowFillPercent()) / 100; } // --------------------------------------------------------------------------------------------------------------------------------- template inline void UnorderedMap::max_load_factor(const float ml) { m_set.SetBucketGrowFillPercent(static_cast(ml * 100)); } // --------------------------------------------------------------------------------------------------------------------------------- template void UnorderedMap::reserve(const size_t nodeCount) { if (nodeCount <= size()) return; const size_t newBucketCount = Detail::UnorderedMapSanitiseBucketCount(static_cast((nodeCount + 1)/ max_load_factor())); // Reserve the right number of buckets only if it is larger than the current bucket count. if (newBucketCount > m_set.GetBucketCount()) m_set.SetBucketCount(newBucketCount); // Allocate node memory for the additional nodes from the pool. ACTIV_BOOST_STATIC_ASSERT(sizeof(void *) <= sizeof(Node)); // Malloc node buffers, creating a linked list of buffers as we go. void *pLastBuffer = ACTIV_NULLPTR; for (size_t i = 0; i < nodeCount - size(); ++i) { void *pBuffer = m_nodePool.malloc(); *(static_cast(pBuffer)) = pLastBuffer; pLastBuffer = pBuffer; } // Walk back through the linked list, returning buffers to the pool. // Thought it might be polite to clear the pointers after, but the pools seem to re-use the front of the buffers anyway. while (pLastBuffer) { void *pBuffer = pLastBuffer; pLastBuffer = *(static_cast(pBuffer)); m_nodePool.free(pBuffer); } } } // namespace Activ #endif // (!defined ACTIV_MISC_UNORDERED_MAP_H)