Files

320 lines
9.2 KiB
C++

/**
* @file include/ActivMiddleware/ActivBase/Detail/IntrusiveSetHelperDetail.h
*
* @brief Header file for implementation details for intrusive set helper.
*/
#if (!defined ACTIV_BASE_INTRUSIVE_SET_HELPER_DETAIL_H)
#define ACTIV_BASE_INTRUSIVE_SET_HELPER_DETAIL_H
#include "ActivMiddleware/ActivBase/External.h"
#include "ActivMiddleware/ActivBase/Crc32Generator.h"
#include ACTIV_BOOST_INCLUDE(intrusive/set.hpp)
#include ACTIV_BOOST_INCLUDE(intrusive/unordered_set.hpp)
#include ACTIV_BOOST_INCLUDE(type_traits/conditional.hpp)
//! Activ namespace.
namespace Activ
{
namespace IntrusiveSetHelper
{
namespace Detail
{
//! The default link mode used for the set and unordered set.
typedef Boost::intrusive::link_mode<Boost::intrusive::normal_link> DefaultLinkMode;
typedef Boost::intrusive::link_mode<Boost::intrusive::safe_link> SafeLinkMode;
typedef Boost::intrusive::link_mode<Boost::intrusive::auto_unlink> AutoUnlinkMode;
// ---------------------------------------------------------------------------------------------------------------------------------
// ---------------------------------------------------------------------------------------------------------------------------------
//! Unordered base set hook helper class.
template<bool STORE_HASH>
class UnorderedSetBaseHookHelper : public
Boost::intrusive::make_unordered_set_base_hook<DefaultLinkMode, Boost::intrusive::store_hash<STORE_HASH> >::type
{
public:
static const bool StoreHash = STORE_HASH;
};
// ---------------------------------------------------------------------------------------------------------------------------------
// ---------------------------------------------------------------------------------------------------------------------------------
// The delete disposer object function.
template<typename T>
class DeleteDisposer
{
public:
void operator()(T *pT)
{
delete pT;
}
};
// ---------------------------------------------------------------------------------------------------------------------------------
// ---------------------------------------------------------------------------------------------------------------------------------
//! Hash selector class. Selects the most appropriate hash function based on the type of KEY.
template<typename T, typename KEY, typename GET_KEY_FUNC>
class HashSelector
{
private:
//! Crc32 hash.
class Crc32Hash
{
public:
/**
* @brief Function operator.
*
* @param key
*
* @return The hash of the key.
*/
size_t operator()(const KEY &key) const
{
return static_cast<size_t>(m_crc32Generator(key));
}
/**
* @brief Function operator. Assumes T has a member function GetKey().
*
* @param t
*
* @return The hash of the objects key.
*/
size_t operator()(const T &t) const
{
return operator()(GET_KEY_FUNC()(t));
}
private:
Crc32Generator<> m_crc32Generator;
};
//! Boost hash
class BoostHash
{
public:
/**
* @brief Function operator.
*
* @param key
*
* @return The hash of the key.
*/
size_t operator()(const KEY &key) const
{
return static_cast<size_t>(Boost::hash<KEY>()(key));
}
/**
* @brief Function operator. Assumes T has a member function GetKey().
*
* @param t
*
* @return The hash of the objects key.
*/
size_t operator()(const T &t) const
{
return operator()(GET_KEY_FUNC()(t));
}
};
public:
typedef typename Boost::conditional<
Boost::is_integral<KEY>::value,
BoostHash,
Crc32Hash>::type type;
};
// ---------------------------------------------------------------------------------------------------------------------------------
// ---------------------------------------------------------------------------------------------------------------------------------
//! Bucket manager class.
template<typename SET>
class BucketManager
{
public:
typedef typename SET::bucket_traits BucketTraits;
/**
* @brief Constructor.
*
* @param initialNumberOfBuckets
* @param bucketGrowFillPercent
* @param bucketShrinkFillPercent
*/
BucketManager(const size_t initialNumberOfBuckets, const uint16_t bucketGrowFillPercent,
const uint16_t bucketShrinkFillPercent);
//! Get number of buckets.
size_t GetSize() const;
//! Get bucket traits.
BucketTraits GetBucketTraits();
//! Get the bucket grow fill percent.
uint16_t GetBucketGrowFillPercent() const;
//! Set the bucket grow fill percent.
void SetBucketGrowFillPercent(const uint16_t bucketGrowFillPercent);
//! Set bucket fill thresholds.
void SetBucketFillThresholds();
//! Set a new bucket count, rehashes if different.
void SetBucketCount(SET &Set, const size_t newBucketCount);
/**
* @brief Check rehash on insert.
*
* @param set
*/
void CheckRehashOnInsert(SET &set);
/**
* @brief Check rehash on erase.
*
* @param set
*/
void CheckRehashOnErase(SET &set);
private:
typedef std::vector<typename SET::bucket_type> BucketTypeList;
const size_t m_initialNumberOfBuckets;
double m_bucketGrowFillPercent;
size_t m_bucketGrowFillThreshold;
const double m_bucketShrinkFillPercent;
size_t m_bucketShrinkFillThreshold;
BucketTypeList m_buckets;
};
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
BucketManager<SET>::BucketManager(const size_t initialNumberOfBuckets, const uint16_t bucketGrowFillPercent,
const uint16_t bucketShrinkFillPercent) :
m_initialNumberOfBuckets(initialNumberOfBuckets),
m_bucketGrowFillPercent(bucketGrowFillPercent / 100.0),
m_bucketShrinkFillPercent(bucketShrinkFillPercent / 100.0),
m_buckets(initialNumberOfBuckets)
{
SetBucketFillThresholds();
}
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
inline size_t BucketManager<SET>::GetSize() const
{
return m_buckets.size();
}
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
inline typename BucketManager<SET>::BucketTraits BucketManager<SET>::GetBucketTraits()
{
return BucketTraits(&m_buckets[0], m_buckets.size());
}
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
inline uint16_t BucketManager<SET>::GetBucketGrowFillPercent() const
{
return static_cast<uint16_t>(m_bucketGrowFillPercent * 100);
}
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
inline void BucketManager<SET>::SetBucketGrowFillPercent(const uint16_t bucketGrowFillPercent)
{
m_bucketGrowFillPercent = bucketGrowFillPercent / 100.0;
SetBucketFillThresholds();
}
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
inline void BucketManager<SET>::SetBucketFillThresholds()
{
m_bucketGrowFillThreshold = static_cast<size_t>(m_bucketGrowFillPercent * m_buckets.size());
m_bucketShrinkFillThreshold = static_cast<size_t>(m_bucketShrinkFillPercent * m_buckets.size());
if (m_bucketShrinkFillThreshold < m_initialNumberOfBuckets)
m_bucketShrinkFillThreshold = m_initialNumberOfBuckets;
}
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
inline void BucketManager<SET>::SetBucketCount(SET &set, const size_t newBucketCount)
{
if (m_buckets.size() == newBucketCount)
return;
BucketTypeList newBuckets(newBucketCount);
set.rehash(BucketTraits(&newBuckets[0], newBuckets.size()));
m_buckets.swap(newBuckets);
}
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
inline void BucketManager<SET>::CheckRehashOnInsert(SET &set)
{
const size_t setSize = set.size();
if (ACTIV_UNLIKELY(setSize >= m_bucketGrowFillThreshold))
{
size_t newBucketSize = m_buckets.size();
while (setSize >= static_cast<size_t>(newBucketSize * m_bucketGrowFillPercent))
newBucketSize *= 2;
SetBucketCount(set, newBucketSize);
SetBucketFillThresholds();
}
}
// ---------------------------------------------------------------------------------------------------------------------------------
template<typename SET>
inline void BucketManager<SET>::CheckRehashOnErase(SET &set)
{
const size_t setSize = set.size();
if (ACTIV_UNLIKELY(setSize < m_bucketShrinkFillThreshold) &&
ACTIV_UNLIKELY(m_bucketShrinkFillThreshold > m_initialNumberOfBuckets))
{
size_t newBucketSize = m_buckets.size();
size_t adjustedBucketSize = static_cast<size_t>(newBucketSize * m_bucketShrinkFillPercent);
while ((setSize < adjustedBucketSize) && (adjustedBucketSize > m_initialNumberOfBuckets))
{
newBucketSize /= 2;
adjustedBucketSize = static_cast<size_t>(newBucketSize * m_bucketShrinkFillPercent);
}
set.rehash(BucketTraits(&m_buckets[0], newBucketSize));
m_buckets.resize(newBucketSize);
SetBucketFillThresholds();
}
}
} // namespace Detail
} // namespace IntrusiveSetHelper
} // namespace Activ
#endif // (!defined ACTIV_BASE_INTRUSIVE_SET_HELPER_DETAIL_H)