| ////////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Ion Gaztanaga 2005-2009. Distributed under the Boost |
| // Software License, Version 1.0. (See accompanying file |
| // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // See http://www.boost.org/libs/interprocess for documentation. |
| // |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| #ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP |
| #define BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP |
| |
| #include <boost/interprocess/detail/config_begin.hpp> |
| #include <boost/interprocess/detail/workaround.hpp> |
| |
| #include <functional> |
| #include <utility> |
| #include <boost/get_pointer.hpp> |
| #include <boost/interprocess/detail/utilities.hpp> |
| #include <boost/interprocess/containers/vector.hpp> |
| #include <boost/intrusive/unordered_set.hpp> |
| #include <boost/interprocess/allocators/allocator.hpp> |
| |
| //!\file |
| //!Describes index adaptor of boost::intrusive::unordered_set container, to use it |
| //!as name/shared memory index |
| |
| namespace boost { namespace interprocess { |
| |
| /// @cond |
| |
| //!Helper class to define typedefs |
| //!from IndexTraits |
| template <class MapConfig> |
| struct iunordered_set_index_aux |
| { |
| typedef typename |
| MapConfig::segment_manager_base segment_manager_base; |
| |
| typedef typename |
| segment_manager_base::void_pointer void_pointer; |
| |
| typedef typename bi::make_unordered_set_base_hook |
| < bi::void_pointer<void_pointer> |
| >::type derivation_hook; |
| |
| typedef typename MapConfig::template |
| intrusive_value_type<derivation_hook>::type value_type; |
| |
| typedef typename MapConfig:: |
| intrusive_compare_key_type intrusive_compare_key_type; |
| |
| typedef std::equal_to<value_type> value_equal; |
| |
| typedef typename MapConfig::char_type char_type; |
| |
| struct equal_function |
| { |
| bool operator()(const intrusive_compare_key_type &i, const value_type &b) const |
| { |
| return (i.m_len == b.name_length()) && |
| (std::char_traits<char_type>::compare |
| (i.mp_str, b.name(), i.m_len) == 0); |
| } |
| |
| bool operator()(const value_type &b, const intrusive_compare_key_type &i) const |
| { |
| return (i.m_len == b.name_length()) && |
| (std::char_traits<char_type>::compare |
| (i.mp_str, b.name(), i.m_len) == 0); |
| } |
| |
| bool operator()(const value_type &b1, const value_type &b2) const |
| { |
| return (b1.name_length() == b2.name_length()) && |
| (std::char_traits<char_type>::compare |
| (b1.name(), b2.name(), b1.name_length()) == 0); |
| } |
| }; |
| |
| struct hash_function |
| : std::unary_function<value_type, std::size_t> |
| { |
| std::size_t operator()(const value_type &val) const |
| { |
| const char_type *beg = detail::get_pointer(val.name()), |
| *end = beg + val.name_length(); |
| return boost::hash_range(beg, end); |
| } |
| |
| std::size_t operator()(const intrusive_compare_key_type &i) const |
| { |
| const char_type *beg = i.mp_str, |
| *end = beg + i.m_len; |
| return boost::hash_range(beg, end); |
| } |
| }; |
| |
| typedef typename bi::make_unordered_set |
| < value_type |
| , bi::hash<hash_function> |
| , bi::equal<equal_function> |
| >::type index_t; |
| typedef typename index_t::bucket_type bucket_type; |
| typedef allocator |
| <bucket_type, segment_manager_base> allocator_type; |
| |
| struct allocator_holder |
| { |
| allocator_holder(segment_manager_base *mngr) |
| : alloc(mngr) |
| {} |
| allocator_type alloc; |
| bucket_type init_bucket; |
| }; |
| }; |
| /// @endcond |
| |
| //!Index type based in boost::intrusive::set. |
| //!Just derives from boost::intrusive::set |
| //!and defines the interface needed by managed memory segments |
| template <class MapConfig> |
| class iunordered_set_index |
| //Derive class from map specialization |
| : private iunordered_set_index_aux<MapConfig>::allocator_holder |
| , public iunordered_set_index_aux<MapConfig>::index_t |
| { |
| /// @cond |
| typedef iunordered_set_index_aux<MapConfig> index_aux; |
| typedef typename index_aux::index_t index_type; |
| typedef typename MapConfig:: |
| intrusive_compare_key_type intrusive_compare_key_type; |
| typedef typename index_aux::equal_function equal_function; |
| typedef typename index_aux::hash_function hash_function; |
| typedef typename MapConfig::char_type char_type; |
| typedef typename |
| iunordered_set_index_aux<MapConfig>::allocator_type allocator_type; |
| typedef typename |
| iunordered_set_index_aux<MapConfig>::allocator_holder allocator_holder; |
| /// @endcond |
| |
| public: |
| typedef typename index_type::iterator iterator; |
| typedef typename index_type::const_iterator const_iterator; |
| typedef typename index_type::insert_commit_data insert_commit_data; |
| typedef typename index_type::value_type value_type; |
| typedef typename index_type::bucket_ptr bucket_ptr; |
| typedef typename index_type::bucket_type bucket_type; |
| typedef typename index_type::bucket_traits bucket_traits; |
| typedef typename index_type::size_type size_type; |
| |
| /// @cond |
| private: |
| typedef typename index_aux:: |
| segment_manager_base segment_manager_base; |
| |
| enum { InitBufferSize = 64}; |
| |
| static bucket_ptr create_buckets(allocator_type &alloc, std::size_t num) |
| { |
| num = index_type::suggested_upper_bucket_count(num); |
| bucket_ptr buckets = alloc.allocate(num); |
| bucket_ptr buckets_init = buckets; |
| for(std::size_t i = 0; i < num; ++i){ |
| new(get_pointer(buckets_init++))bucket_type(); |
| } |
| return buckets; |
| } |
| |
| static std::size_t shrink_buckets |
| ( bucket_ptr buckets, std::size_t old_size |
| , allocator_type &alloc, std::size_t new_size) |
| { |
| if(old_size <= new_size ) |
| return old_size; |
| std::size_t received_size; |
| if(!alloc.allocation_command |
| (boost::interprocess::try_shrink_in_place | boost::interprocess::nothrow_allocation, old_size, new_size, received_size, buckets).first){ |
| return old_size; |
| } |
| |
| for( bucket_type *p = detail::get_pointer(buckets) + received_size |
| , *pend = detail::get_pointer(buckets) + old_size |
| ; p != pend |
| ; ++p){ |
| p->~bucket_type(); |
| } |
| |
| bucket_ptr shunk_p = alloc.allocation_command |
| (boost::interprocess::shrink_in_place | boost::interprocess::nothrow_allocation, received_size, received_size, received_size, buckets).first; |
| BOOST_ASSERT(buckets == shunk_p); |
| |
| bucket_ptr buckets_init = buckets + received_size; |
| for(std::size_t i = 0; i < (old_size - received_size); ++i){ |
| get_pointer(buckets_init++)->~bucket_type(); |
| } |
| return received_size; |
| } |
| |
| static bucket_ptr expand_or_create_buckets |
| ( bucket_ptr old_buckets, const std::size_t old_num |
| , allocator_type &alloc, const std::size_t new_num) |
| { |
| std::size_t received_size; |
| std::pair<bucket_ptr, bool> ret = |
| alloc.allocation_command |
| (boost::interprocess::expand_fwd | boost::interprocess::allocate_new, new_num, new_num, received_size, old_buckets); |
| if(ret.first == old_buckets){ |
| bucket_ptr buckets_init = old_buckets + old_num; |
| for(std::size_t i = 0; i < (new_num - old_num); ++i){ |
| new(get_pointer(buckets_init++))bucket_type(); |
| } |
| } |
| else{ |
| bucket_ptr buckets_init = ret.first; |
| for(std::size_t i = 0; i < new_num; ++i){ |
| new(get_pointer(buckets_init++))bucket_type(); |
| } |
| } |
| |
| return ret.first; |
| } |
| |
| static void destroy_buckets |
| (allocator_type &alloc, bucket_ptr buckets, std::size_t num) |
| { |
| bucket_ptr buckets_destroy = buckets; |
| for(std::size_t i = 0; i < num; ++i){ |
| get_pointer(buckets_destroy++)->~bucket_type(); |
| } |
| alloc.deallocate(buckets, num); |
| } |
| |
| iunordered_set_index<MapConfig>* get_this_pointer() |
| { return this; } |
| |
| /// @endcond |
| |
| public: |
| //!Constructor. Takes a pointer to the |
| //!segment manager. Can throw |
| iunordered_set_index(segment_manager_base *mngr) |
| : allocator_holder(mngr) |
| , index_type(bucket_traits(&get_this_pointer()->init_bucket, 1)) |
| {} |
| |
| ~iunordered_set_index() |
| { |
| index_type::clear(); |
| if(index_type::bucket_pointer() != bucket_ptr(&this->init_bucket)){ |
| destroy_buckets(this->alloc, index_type::bucket_pointer(), index_type::bucket_count()); |
| } |
| } |
| |
| //!This reserves memory to optimize the insertion of n |
| //!elements in the index |
| void reserve(std::size_t new_n) |
| { |
| //Let's maintain a 1.0f load factor |
| size_type old_n = this->bucket_count(); |
| if(new_n <= old_n) |
| return; |
| bucket_ptr old_p = this->bucket_pointer(); |
| new_n = index_type::suggested_upper_bucket_count(new_n); |
| bucket_ptr new_p; |
| //This can throw |
| try{ |
| if(old_p != bucket_ptr(&this->init_bucket)) |
| new_p = expand_or_create_buckets(old_p, old_n, this->alloc, new_n); |
| else |
| new_p = create_buckets(this->alloc, new_n); |
| } |
| catch(...){ |
| return; |
| } |
| //Rehashing does not throw, since neither the hash nor the |
| //comparison function can throw |
| this->rehash(bucket_traits(new_p, new_n)); |
| if(new_p != old_p && old_p != bucket_ptr(&this->init_bucket)){ |
| destroy_buckets(this->alloc, old_p, old_n); |
| } |
| } |
| |
| //!This tries to free unused memory |
| //!previously allocated. |
| void shrink_to_fit() |
| { |
| size_type cur_size = this->size(); |
| size_type cur_count = this->bucket_count(); |
| bucket_ptr old_p = this->bucket_pointer(); |
| |
| if(!this->size() && old_p != bucket_ptr(&this->init_bucket)){ |
| this->rehash(bucket_traits(bucket_ptr(&this->init_bucket), 1)); |
| destroy_buckets(this->alloc, old_p, cur_count); |
| } |
| else{ |
| size_type sug_count = 0; //gcc warning |
| sug_count = index_type::suggested_upper_bucket_count(cur_size); |
| |
| if(sug_count >= cur_count) |
| return; |
| |
| try{ |
| shrink_buckets(old_p, cur_count, this->alloc, sug_count); |
| } |
| catch(...){ |
| return; |
| } |
| |
| //Rehashing does not throw, since neither the hash nor the |
| //comparison function can throw |
| this->rehash(bucket_traits(old_p, sug_count)); |
| } |
| } |
| |
| iterator find(const intrusive_compare_key_type &key) |
| { return index_type::find(key, hash_function(), equal_function()); } |
| |
| const_iterator find(const intrusive_compare_key_type &key) const |
| { return index_type::find(key, hash_function(), equal_function()); } |
| |
| std::pair<iterator, bool>insert_check |
| (const intrusive_compare_key_type &key, insert_commit_data &commit_data) |
| { return index_type::insert_check(key, hash_function(), equal_function(), commit_data); } |
| |
| iterator insert_commit(value_type &val, insert_commit_data &commit_data) |
| { |
| iterator it = index_type::insert_commit(val, commit_data); |
| size_type cur_size = this->size(); |
| if(cur_size > this->bucket_count()){ |
| try{ |
| this->reserve(cur_size); |
| } |
| catch(...){ |
| //Strong guarantee: if something goes wrong |
| //we should remove the insertion. |
| // |
| //We can use the iterator because the hash function |
| //can't throw and this means that "reserve" will |
| //throw only because of the memory allocation: |
| //the iterator has not been invalidated. |
| index_type::erase(it); |
| throw; |
| } |
| } |
| return it; |
| } |
| }; |
| |
| /// @cond |
| |
| //!Trait class to detect if an index is an intrusive |
| //!index |
| template<class MapConfig> |
| struct is_intrusive_index |
| <boost::interprocess::iunordered_set_index<MapConfig> > |
| { |
| enum{ value = true }; |
| }; |
| /// @endcond |
| |
| }} //namespace boost { namespace interprocess { |
| |
| #include <boost/interprocess/detail/config_end.hpp> |
| |
| #endif //#ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP |