320 lines
9.2 KiB
C++
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)
|