/** * @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 DefaultLinkMode; typedef Boost::intrusive::link_mode SafeLinkMode; typedef Boost::intrusive::link_mode AutoUnlinkMode; // --------------------------------------------------------------------------------------------------------------------------------- // --------------------------------------------------------------------------------------------------------------------------------- //! Unordered base set hook helper class. template class UnorderedSetBaseHookHelper : public Boost::intrusive::make_unordered_set_base_hook >::type { public: static const bool StoreHash = STORE_HASH; }; // --------------------------------------------------------------------------------------------------------------------------------- // --------------------------------------------------------------------------------------------------------------------------------- // The delete disposer object function. template 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 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(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(Boost::hash()(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::value, BoostHash, Crc32Hash>::type type; }; // --------------------------------------------------------------------------------------------------------------------------------- // --------------------------------------------------------------------------------------------------------------------------------- //! Bucket manager class. template 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 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 BucketManager::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 inline size_t BucketManager::GetSize() const { return m_buckets.size(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename BucketManager::BucketTraits BucketManager::GetBucketTraits() { return BucketTraits(&m_buckets[0], m_buckets.size()); } // --------------------------------------------------------------------------------------------------------------------------------- template inline uint16_t BucketManager::GetBucketGrowFillPercent() const { return static_cast(m_bucketGrowFillPercent * 100); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void BucketManager::SetBucketGrowFillPercent(const uint16_t bucketGrowFillPercent) { m_bucketGrowFillPercent = bucketGrowFillPercent / 100.0; SetBucketFillThresholds(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void BucketManager::SetBucketFillThresholds() { m_bucketGrowFillThreshold = static_cast(m_bucketGrowFillPercent * m_buckets.size()); m_bucketShrinkFillThreshold = static_cast(m_bucketShrinkFillPercent * m_buckets.size()); if (m_bucketShrinkFillThreshold < m_initialNumberOfBuckets) m_bucketShrinkFillThreshold = m_initialNumberOfBuckets; } // --------------------------------------------------------------------------------------------------------------------------------- template inline void BucketManager::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 inline void BucketManager::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(newBucketSize * m_bucketGrowFillPercent)) newBucketSize *= 2; SetBucketCount(set, newBucketSize); SetBucketFillThresholds(); } } // --------------------------------------------------------------------------------------------------------------------------------- template inline void BucketManager::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(newBucketSize * m_bucketShrinkFillPercent); while ((setSize < adjustedBucketSize) && (adjustedBucketSize > m_initialNumberOfBuckets)) { newBucketSize /= 2; adjustedBucketSize = static_cast(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)