/** * @file include/ActivMiddleware/ActivBase/IntrusiveSetHelper.h * * @brief Header file for intrusive set helper. */ #if (!defined ACTIV_BASE_INTRUSIVE_SET_HELPER_H) #define ACTIV_BASE_INTRUSIVE_SET_HELPER_H #include "ActivMiddleware/ActivBase/External.h" #include "ActivMiddleware/ActivBase/Detail/IntrusiveSetHelperDetail.h" //! Activ namespace. namespace Activ { namespace IntrusiveSetHelper { //! Set entries must be derived from a BaseHook or include a public MemberHook. typedef Boost::intrusive::make_set_base_hook::type SetBaseHook; typedef Boost::intrusive::make_set_member_hook::type SetMemberHook; typedef Detail::UnorderedSetBaseHookHelper UnorderedSetBaseHook; typedef Detail::UnorderedSetBaseHookHelper UnorderedSetBaseHookStoreHash; typedef Boost::intrusive::make_unordered_set_member_hook::type UnorderedSetMemberHook; // --------------------------------------------------------------------------------------------------------------------------------- // --------------------------------------------------------------------------------------------------------------------------------- /** * @brief Unordered set class. * This set owns any objects placed in the container. They will be deleted when erased or the container cleared. * * @tparam T value type of the set. * @tparam KEY key type of the set. * @tparam DISPOSER disposer function object. * @tparam HASH hash function object. */ template, typename GET_KEY_FUNC = typename T::GetKey, typename HASH = typename Detail::HashSelector::type> class UnorderedSet : private Boost::noncopyable { public: typedef Boost::intrusive::unordered_set< T, Boost::intrusive::hash, Boost::intrusive::power_2_buckets, Boost::intrusive::compare_hash, Boost::intrusive::key_of_value > UnorderedSetType; typedef typename UnorderedSetType::key_type key_type; typedef typename UnorderedSetType::value_type value_type; typedef typename UnorderedSetType::iterator iterator; typedef typename UnorderedSetType::const_iterator const_iterator; typedef DISPOSER Disposer; /** * @brief Constructor. * * @param initialNumberOfBuckets * @param bucketGrowFillPercent * @param bucketShrinkFillPercent * @param disposer */ UnorderedSet(const size_t initialNumberOfBuckets = 65536, const uint16_t bucketGrowFillPercent = 80, const uint16_t bucketShrinkFillPercent = 13, const Disposer &disposer = Disposer()); //! Destructor. ~UnorderedSet(); //! Get bucket count. size_t GetBucketCount() const; //! Set the bucket count, causes a rehash. void SetBucketCount(const size_t bucketCount); //! Get the bucket grow fill percent. uint16_t GetBucketGrowFillPercent() const; //! Set the bucket grow fill percent. void SetBucketGrowFillPercent(const uint16_t bucketGrowFillPercent); //! Get an iterator to the first element. iterator begin(); //! Get an iterator to the first element. const_iterator begin() const; //! Get an iterator to one past the last element. iterator end(); //! Get an iterator to one past the last element. const_iterator end() const; //! Empty. bool empty() const; //! Size. size_t size() const; /** * @brief Insert check. Note, a call to insert_check and insert_commit must be done as a pair. It is invalid to call * insert_check twice with different keys followed by an insert_commit of the first item. * * @param key check presence of element with this key. * * @return A pair of iterator and bool. If the key exists the iterator will point to it and the boolean will be false else the * boolean will be true if an element can be inserted. */ std::pair insert_check(const key_type &key); /** * @brief Insert commit stable. Note, a call to insert_check and insert_commit must be done as a pair. It is invalid to call * insert_check twice with different keys followed by an insert_commit of the first item. * Does not perform a rehash hence iterators are still valid after calling. Container should be rehashed after. * * @param pEntry the new element. * * @return An iterator to the new element. */ iterator insert_commit_stable(value_type *pEntry); /** * @brief Insert commit unstable. Note, a call to insert_check and insert_commit must be done as a pair. It is invalid to call * insert_check twice with different keys followed by an insert_commit of the first item. * Potentially performs a rehash, all iterators (including end) are invalidated during a rehash. * * @param pEntry the new element. * * @return An iterator to the new element. */ iterator insert_commit_unstable(value_type *pEntry); /** * @brief Erase stable. * Does not perform a rehash hence iterators are still valid after calling. Container should be rehashed after. * * @param iterator element to erase. */ void erase_stable(const_iterator iterator); /** * @brief Erase stable. * Does not perform a rehash hence iterators are still valid after calling. Container should be rehashed after. * * @param key the key of the element to erase. * * @return the number of elements erased. */ size_t erase_stable(const key_type &key); /** * @brief Erase unstable. * Potentially performs a rehash, all iterators (including end) are invalidated during a rehash. * * @param iterator element to erase. */ void erase_unstable(const_iterator iterator); /** * @brief Erase unstable. * Potentially performs a rehash, all iterators (including end) are invalidated during a rehash. * * @param key the key of the element to erase. * * @return the number of elements erased. */ size_t erase_unstable(const key_type &key); //! Clear. void clear(); /** * @brief Find. * * @param key the key of the element to find an iterator to. * * @return An iterator to the element or end(). */ iterator find(const key_type &key); /** * @brief Find. * * @param key the key of the element to find an iterator to. * * @return An iterator to the element or end(). */ const_iterator find(const key_type &key) const; /** * @brief Find. * * @param keyType the compatible key type to find an iterator to. * @param hasher hasher functor for compatible key type. * @param equalFunctor equality functor for compatible key type. * * @return An iterator to the element or end(). */ template iterator find(const KeyType &keyType, KeyHasher hasher, KeyEqual equalFunctor); /** * @brief Find. * * @param keyType the compatible key type to find an iterator to. * @param hasher hasher functor for compatible key type. * @param equalFunctor equality functor for compatible key type. * * @return An iterator to the element or end(). */ template const_iterator find(const KeyType &keyType, KeyHasher hasher, KeyEqual equalFunctor) const; /** * @brief Iterator to. * * @param value the value to get an iterator for (must exist in container). * * @return An iterator to value. */ iterator iterator_to(value_type &value); /** * @brief Iterator to. * * @param value the value to get an iterator for (must exist in container). * * @return An iterator to value. */ const_iterator iterator_to(const value_type &value) const; //! Rehash. invalidates all iterators (including end). void rehash(); private: Detail::BucketManager m_bucketManager; Disposer m_disposer; UnorderedSetType m_unorderedSet; typename UnorderedSetType::insert_commit_data m_commitData; }; // --------------------------------------------------------------------------------------------------------------------------------- template inline UnorderedSet::UnorderedSet(const size_t initialNumberOfBuckets, const uint16_t bucketGrowFillPercent, const uint16_t bucketShrinkFillPercent, const Disposer &disposer) : m_bucketManager(initialNumberOfBuckets, bucketGrowFillPercent, bucketShrinkFillPercent), m_disposer(disposer), m_unorderedSet(m_bucketManager.GetBucketTraits()) { } // --------------------------------------------------------------------------------------------------------------------------------- template inline UnorderedSet::~UnorderedSet() { clear(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline size_t UnorderedSet::GetBucketCount() const { return m_bucketManager.GetSize(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void UnorderedSet::SetBucketCount(const size_t bucketCount) { m_bucketManager.SetBucketCount(m_unorderedSet, bucketCount); } // --------------------------------------------------------------------------------------------------------------------------------- template inline uint16_t UnorderedSet::GetBucketGrowFillPercent() const { return m_bucketManager.GetBucketGrowFillPercent(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void UnorderedSet::SetBucketGrowFillPercent(const uint16_t bucketGrowFillPercent) { m_bucketManager.SetBucketGrowFillPercent(bucketGrowFillPercent); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::iterator UnorderedSet::begin() { return m_unorderedSet.begin(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::const_iterator UnorderedSet::begin() const { return m_unorderedSet.cbegin(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::iterator UnorderedSet::end() { return m_unorderedSet.end(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::const_iterator UnorderedSet::end() const { return m_unorderedSet.cend(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline bool UnorderedSet::empty() const { return m_unorderedSet.empty(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline size_t UnorderedSet::size() const { return m_unorderedSet.size(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline std::pair::iterator, bool> UnorderedSet::insert_check(const key_type &key) { return m_unorderedSet.insert_check(key, m_unorderedSet.hash_function(), m_unorderedSet.key_eq(), m_commitData); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::iterator UnorderedSet::insert_commit_stable(value_type *pEntry) { return m_unorderedSet.insert_commit(*pEntry, m_commitData); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::iterator UnorderedSet::insert_commit_unstable(value_type *pEntry) { m_bucketManager.CheckRehashOnInsert(m_unorderedSet); return m_unorderedSet.insert_commit(*pEntry, m_commitData); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void UnorderedSet::erase_stable(const_iterator iterator) { m_unorderedSet.erase_and_dispose(iterator, m_disposer); } // --------------------------------------------------------------------------------------------------------------------------------- template inline size_t UnorderedSet::erase_stable(const key_type &key) { return m_unorderedSet.erase_and_dispose(key, m_unorderedSet.hash_function(), m_unorderedSet.key_eq(), m_disposer); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void UnorderedSet::erase_unstable(const_iterator iterator) { m_bucketManager.CheckRehashOnErase(m_unorderedSet); m_unorderedSet.erase_and_dispose(iterator, m_disposer); } // --------------------------------------------------------------------------------------------------------------------------------- template inline size_t UnorderedSet::erase_unstable(const key_type &key) { m_bucketManager.CheckRehashOnErase(m_unorderedSet); return m_unorderedSet.erase_and_dispose(key, m_unorderedSet.hash_function(), m_unorderedSet.key_eq(), m_disposer); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void UnorderedSet::clear() { return m_unorderedSet.clear_and_dispose(m_disposer); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::iterator UnorderedSet::find(const key_type &key) { return m_unorderedSet.find(key, m_unorderedSet.hash_function(), m_unorderedSet.key_eq()); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::const_iterator UnorderedSet::find(const key_type &key) const { return m_unorderedSet.find(key, m_unorderedSet.hash_function(), m_unorderedSet.key_eq()); } // --------------------------------------------------------------------------------------------------------------------------------- template template inline typename UnorderedSet::iterator UnorderedSet::find(const KeyType &keyType, KeyHasher hasher, KeyEqual equalFunctor) { return m_unorderedSet.find(keyType, hasher, equalFunctor); } // --------------------------------------------------------------------------------------------------------------------------------- template template inline typename UnorderedSet::const_iterator UnorderedSet::find(const KeyType &keyType, KeyHasher hasher, KeyEqual equalFunctor) const { return m_unorderedSet.find(keyType, hasher, equalFunctor); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::iterator UnorderedSet::iterator_to(value_type &value) { return m_unorderedSet.iterator_to(value); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename UnorderedSet::const_iterator UnorderedSet::iterator_to(const value_type &value) const { return m_unorderedSet.iterator_to(value); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void UnorderedSet::rehash() { m_bucketManager.CheckRehashOnInsert(m_unorderedSet); m_bucketManager.CheckRehashOnErase(m_unorderedSet); } // --------------------------------------------------------------------------------------------------------------------------------- // --------------------------------------------------------------------------------------------------------------------------------- /** * @brief Set class. * This set owns any objects placed in the container. They will be deleted when erased or the container cleared. * * @tparam T value type of the set. * @tparam KEY key type of the set. * @tparam DISPOSER disposer function object. * @tparam GET_KEY_FUNC function object return the key of T. */ template, typename GET_KEY_FUNC = typename T::GetKey> class Set : private Boost::noncopyable { public: typedef Boost::intrusive::set< T, Boost::intrusive::key_of_value > SetType; typedef typename SetType::key_type key_type; typedef typename SetType::value_type value_type; typedef typename SetType::iterator iterator; typedef typename SetType::const_iterator const_iterator; typedef DISPOSER Disposer; //! Default Constructor. Set(); //! Destructor. ~Set(); //! Get an iterator to the first element. iterator begin(); //! Get an iterator to the first element. const_iterator begin() const; //! Get an iterator to one past the last element. iterator end(); //! Get an iterator to one past the last element. const_iterator end() const; //! Empty. bool empty() const; //! Size. size_t size() const; /** * @brief Insert check. Note, a call to insert_check and insert_commit must be done as a pair. It is invalid to call * insert_check twice with different keys followed by an insert_commit of the first item. * * @param key check presence of element with this key. * * @return A pair of iterator and bool. If the key exists the iterator will point to it and the boolean will be false else the * boolean will be true if an element can be inserted. */ std::pair insert_check(const key_type &key); /** * @brief Insert check. Note, a call to insert_check and insert_commit must be done as a pair. It is invalid to call * insert_check twice with different keys followed by an insert_commit of the first item. * * @param hint insertion point hint. * @param key check presence of element with this key. * * @return A pair of iterator and bool. If the key exists the iterator will point to it and the boolean will be false else the * boolean will be true if an element can be inserted. */ std::pair insert_check(const_iterator hint, const key_type &key); /** * @brief Insert commit. Note, a call to insert_check and insert_commit must be done as a pair. It is invalid to call * insert_check twice with different keys followed by an insert_commit of the first item. * * @param pEntry the new element. * * @return An iterator to the new element. */ iterator insert_commit(value_type *pEntry); /** * @brief Erase. * * @param iterator element to erase. */ void erase(const_iterator iterator); /** * @brief Erase. * * @param key the key of the element to erase. * * @return the number of elements erased. */ size_t erase(const key_type &key); //! Clear. void clear(); /** * @brief Lower bound. * * @param key the key to find the lower bound of. * * @return An iterator to the first element is not less than key or end(). */ iterator lower_bound(const key_type &key); /** * @brief Lower bound. * * @param key the key to find the lower bound of. * * @return An iterator to the first element is not less than key or end(). */ const_iterator lower_bound(const key_type &key) const; /** * @brief Upper bound. * * @param key the key to find the upper bound of. * * @return An iterator to the first element greater than key or end(). */ iterator upper_bound(const key_type &key); /** * @brief Upper bound. * * @param key the key to find the upper bound of. * * @return An iterator to the first element greater than key or end(). */ const_iterator upper_bound(const key_type &key) const; /** * @brief Find. * * @param key the key of the element to find an iterator to. * * @return An iterator to the element or end(). */ iterator find(const key_type &key); /** * @brief Find. * * @param key the key of the element to find an iterator to. * * @return An iterator to the element or end(). */ const_iterator find(const key_type &key) const; /** * @brief Iterator to. * * @param value the value to get an iterator for (must exist in container). * * @return An iterator to value. */ iterator iterator_to(value_type &value); /** * @brief Iterator to. * * @param value the value to get an iterator for (must exist in container). * * @return An iterator to value. */ const_iterator iterator_to(const value_type &value) const; private: Disposer m_disposer; SetType m_set; typename SetType::insert_commit_data m_commitData; }; // --------------------------------------------------------------------------------------------------------------------------------- template inline Set::Set() { } // --------------------------------------------------------------------------------------------------------------------------------- template inline Set::~Set() { clear(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::iterator Set::begin() { return m_set.begin(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::const_iterator Set::begin() const { return m_set.cbegin(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::iterator Set::end() { return m_set.end(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::const_iterator Set::end() const { return m_set.cend(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline bool Set::empty() const { return m_set.empty(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline size_t Set::size() const { return m_set.size(); } // --------------------------------------------------------------------------------------------------------------------------------- template inline std::pair::iterator, bool> Set::insert_check(const key_type &key) { return m_set.insert_check(key, m_set.value_comp(), m_commitData); } // --------------------------------------------------------------------------------------------------------------------------------- template inline std::pair::iterator, bool> Set::insert_check(const_iterator hint, const key_type &key) { return m_set.insert_check(hint, key, m_set.value_comp(), m_commitData); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::iterator Set::insert_commit(value_type *pEntry) { return m_set.insert_commit(*pEntry, m_commitData); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void Set::erase(const_iterator iterator) { m_set.erase_and_dispose(iterator, m_disposer); } // --------------------------------------------------------------------------------------------------------------------------------- template inline size_t Set::erase(const key_type &key) { return m_set.erase_and_dispose(key, m_set.value_comp(), m_disposer); } // --------------------------------------------------------------------------------------------------------------------------------- template inline void Set::clear() { return m_set.clear_and_dispose(m_disposer); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::iterator Set::lower_bound(const key_type &key) { return m_set.lower_bound(key, m_set.value_comp()); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::const_iterator Set::lower_bound(const key_type &key) const { return m_set.lower_bound(key, m_set.value_comp()); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::iterator Set::upper_bound(const key_type &key) { return m_set.upper_bound(key, m_set.value_comp()); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::const_iterator Set::upper_bound(const key_type &key) const { return m_set.upper_bound(key, m_set.value_comp()); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::iterator Set::find(const key_type &key) { return m_set.find(key, m_set.value_comp()); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::const_iterator Set::find(const key_type &key) const { return m_set.find(key, m_set.value_comp()); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::iterator Set::iterator_to(value_type &value) { return m_set.iterator_to(value); } // --------------------------------------------------------------------------------------------------------------------------------- template inline typename Set::const_iterator Set::iterator_to(const value_type &value) const { return m_set.iterator_to(value); } } // namespace IntrusiveSetHelper } // namespace Activ #endif // (!defined ACTIV_BASE_INTRUSIVE_SET_HELPER_H)