Files

273 lines
8.2 KiB
C++

/**
* @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 <typename Key, typename T, typename Hash = typename Detail::UnorderedMapDefaultHash<Key, T>::type>
class UnorderedMap
{
private:
//! The node type.
typedef Detail::UnorderedMapNode<Key, T> Node;
//! The node pool type.
typedef Detail::UnorderedMapPool NodePool;
//! Underlying implementation type.
typedef typename IntrusiveSetHelper::UnorderedSet<Node, Key, typename Node::Disposer, typename Node::GetKey, Hash> IntrusiveSet;
public:
typedef typename IntrusiveSet::key_type key_type;
typedef typename std::pair<const Key, T> 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<iterator, bool> insert(const value_type &value);
template <typename A0>
std::pair<iterator, bool> 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 <typename Key, typename T, typename Hash>
inline UnorderedMap<Key, T, Hash>::UnorderedMap(const size_t bucketCount) :
m_nodePool(sizeof(Node)),
m_set(Detail::UnorderedMapSanitiseBucketCount(bucketCount), 80, 13, typename Node::Disposer(m_nodePool))
{
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename Key, typename T, typename Hash>
inline std::pair<typename UnorderedMap<Key, T, Hash>::iterator, bool> UnorderedMap<Key, T, Hash>::insert(const value_type &value)
{
std::pair<iterator, bool> 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 <typename Key, typename T, typename Hash>
template <typename A0>
inline std::pair<typename UnorderedMap<Key, T, Hash>::iterator, bool>
UnorderedMap<Key, T, Hash>::emplace(const key_type &key, const A0 &a0)
{
std::pair<iterator, bool> 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 <typename Key, typename T, typename Hash>
inline T &UnorderedMap<Key, T, Hash>::operator[](const key_type &key)
{
std::pair<iterator, bool> 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 <typename Key, typename T, typename Hash>
inline float UnorderedMap<Key, T, Hash>::load_factor() const
{
assert(bucket_count() > 0);
return float(size()) / bucket_count();
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename Key, typename T, typename Hash>
inline float UnorderedMap<Key, T, Hash>::max_load_factor() const
{
return float(m_set.GetBucketGrowFillPercent()) / 100;
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename Key, typename T, typename Hash>
inline void UnorderedMap<Key, T, Hash>::max_load_factor(const float ml)
{
m_set.SetBucketGrowFillPercent(static_cast<uint16_t>(ml * 100));
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename Key, typename T, typename Hash>
void UnorderedMap<Key, T, Hash>::reserve(const size_t nodeCount)
{
if (nodeCount <= size())
return;
const size_t newBucketCount = Detail::UnorderedMapSanitiseBucketCount(static_cast<size_t>((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<void **>(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<void **>(pBuffer));
m_nodePool.free(pBuffer);
}
}
} // namespace Activ
#endif // (!defined ACTIV_MISC_UNORDERED_MAP_H)