interprocess/indexes/iunordered_set_index.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/interprocess for documentation.
0008 //
0009 //////////////////////////////////////////////////////////////////////////////
0010
0011 #ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP
0012 #define BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP
0013
0014 #ifndef BOOST_CONFIG_HPP
0015 #  include <boost/config.hpp>
0016 #endif
0017 0018 ">#
0019 #if defined(BOOST_HAS_PRAGMA_ONCE)
0020 #  pragma once
0021 #endif
0022
0023 #include <boost/interprocess/detail/config_begin.hpp>
0024 #include <boost/interprocess/detail/workaround.hpp>
0025
0026 #include <boost/interprocess/detail/utilities.hpp>
0027 #include <boost/interprocess/allocators/allocator.hpp>
0028 #include <boost/container/vector.hpp>
0029 #include <boost/intrusive/unordered_set.hpp>
0030 #include <boost/intrusive/detail/minimal_pair_header.hpp>
0031 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>   //std::less
0032 #include <boost/container/detail/minimal_char_traits_header.hpp>  //std::char_traits
0033 #include <boost/container/detail/placement_new.hpp>
0034 #include <boost/intrusive/detail/hash.hpp>
0035
0036 //!\file
0037 //!Describes index adaptor of boost::intrusive::unordered_set container, to use it
0038 //!as name/shared memory index
0039
0040 namespace boost { namespace interprocess {
0041
0042 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
0043
0044 //!Helper class to define typedefs
0045 //!from IndexTraits
0046 template <class MapConfig>
0047 struct iunordered_set_index_aux
0048 {
0049    typedef typename
0050       MapConfig::segment_manager_base                 segment_manager_base;
0051
0052    typedef typename
0053       segment_manager_base::void_pointer              void_pointer;
0054
0055    typedef typename bi::make_unordered_set_base_hook
0056       < bi::void_pointer<void_pointer>
0057       >::type        derivation_hook;
0058
0059    typedef typename MapConfig::template
0060       intrusive_value_type<derivation_hook>::type     value_type;
0061
0062    typedef typename MapConfig::compare_key_type       compare_key_type;
0063
0064    typedef std::equal_to<value_type>                  value_equal;
0065
0066    typedef typename MapConfig::char_type              char_type;
0067
0068    struct equal_function
0069    {
0070       bool operator()(const compare_key_type&i, const value_type &b) const
0071       {
0072          return (i.m_len == b.name_length()) &&
0073                   (std::char_traits<char_type>::compare
0074                      (i.mp_str, b.name(), i.m_len) == 0);
0075       }
0076
0077       bool operator()(const value_type &b, const compare_key_type&i) const
0078       {
0079          return (i.m_len == b.name_length()) &&
0080                   (std::char_traits<char_type>::compare
0081                      (i.mp_str, b.name(), i.m_len) == 0);
0082       }
0083
0084       bool operator()(const value_type &b1, const value_type &b2) const
0085       {
0086          return (b1.name_length() == b2.name_length()) &&
0087                   (std::char_traits<char_type>::compare
0088                      (b1.name(), b2.name(), b1.name_length()) == 0);
0089       }
0090    };
0091
0092    struct hash_function
0093    {
0094       typedef value_type argument_type;
0095       typedef std::size_t result_type;
0096
0097       std::size_t hash_char_range(const char_type* beg, const char_type* end) const
0098       {
0099          std::size_t seed = 0;
0100          while (beg != end) {
0101             boost::intrusive::detail::hash_combine_size_t(seed, boost::intrusive::detail::internal_hash_functor<char_type>()(*beg));
0102             ++beg;
0103          }
0104          return seed;
0105       }
0106
0107       std::size_t operator()(const value_type &val) const
0108       {
0109          const char_type* beg = ipcdetail::to_raw_pointer(val.name()),
0110                         * end = beg + val.name_length();
0111          return hash_char_range(beg, end);
0112       }
0113
0114       std::size_t operator()(const compare_key_type&i) const
0115       {
0116          const char_type *beg = i.mp_str,
0117                          *end = beg + i.m_len;
0118          return hash_char_range(beg, end);
0119       }
0120    };
0121
0122    typedef typename bi::make_unordered_set
0123       < value_type
0124       , bi::hash<hash_function>
0125       , bi::equal<equal_function>
0126      , bi::size_type<typename segment_manager_base::size_type>
0127       >::type                                         index_t;
0128    typedef typename index_t::bucket_type              bucket_type;
0129    typedef allocator
0130       <bucket_type, segment_manager_base>             allocator_type;
0131
0132    struct allocator_holder
0133    {
0134       allocator_holder(segment_manager_base *mngr)
0135          :  alloc(mngr)
0136       {}
0137       allocator_type alloc;
0138       bucket_type init_bucket;
0139    };
0140 };
0141 #endif   //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
0142
0143 //!Index type based in boost::intrusive::set.
0144 //!Just derives from boost::intrusive::set
0145 //!and defines the interface needed by managed memory segments
0146 template <class MapConfig>
0147 class iunordered_set_index
0148       //Derive class from map specialization
0149    :  private iunordered_set_index_aux<MapConfig>::allocator_holder
0150    ,  private iunordered_set_index_aux<MapConfig>::index_t
0151 {
0152    #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
0153    typedef iunordered_set_index_aux<MapConfig>           index_aux;
0154    typedef typename index_aux::index_t                   index_type;
0155    typedef typename index_aux::equal_function            equal_function;
0156    typedef typename index_aux::hash_function             hash_function;
0157    typedef typename MapConfig::char_type                 char_type;
0158    typedef typename
0159       iunordered_set_index_aux<MapConfig>::allocator_type      allocator_type;
0160    typedef typename
0161       iunordered_set_index_aux<MapConfig>::allocator_holder    allocator_holder;
0162    public:
0163    typedef typename MapConfig::compare_key_type          compare_key_type;
0164    #endif   //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
0165
0166    public:
0167    typedef typename index_type::iterator                 iterator;
0168    typedef typename index_type::const_iterator           const_iterator;
0169    typedef typename index_type::insert_commit_data       insert_commit_data;
0170    typedef typename index_type::value_type               value_type;
0171    typedef typename index_type::bucket_ptr               bucket_ptr;
0172    typedef typename index_type::bucket_type              bucket_type;
0173    typedef typename index_type::bucket_traits            bucket_traits;
0174    typedef typename index_type::size_type                size_type;
0175    typedef typename index_type::difference_type          difference_type;
0176    typedef value_type                                    index_data_t;
0177
0178    #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
0179    private:
0180    typedef typename index_aux::
0181       segment_manager_base             segment_manager_base;
0182
0183    static const std::size_t InitBufferSize = 64;
0184
0185    static bucket_ptr create_buckets(allocator_type &alloc, size_type num)
0186    {
0187       num = index_type::suggested_upper_bucket_count(num);
0188       bucket_ptr buckets = alloc.allocate(num);
0189       bucket_ptr buckets_init = buckets;
0190       for(size_type i = 0; i < num; ++i){
0191          ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type();
0192       }
0193       return buckets;
0194    }
0195
0196    static size_type shrink_buckets
0197       ( bucket_ptr buckets, size_type old_size
0198       , allocator_type &alloc, size_type new_size)
0199    {
0200       if(old_size <= new_size )
0201          return old_size;
0202       size_type received_size = new_size;
0203       if(!alloc.allocation_command
0204          (boost::interprocess::try_shrink_in_place | boost::interprocess::nothrow_allocation, old_size, received_size, buckets)){
0205          return old_size;
0206       }
0207
0208       for( bucket_type *p = ipcdetail::to_raw_pointer(buckets) + received_size
0209          , *pend = ipcdetail::to_raw_pointer(buckets) + old_size
0210          ; p != pend
0211          ; ++p){
0212          p->~bucket_type();
0213       }
0214
0215       bucket_ptr shunk_p = alloc.allocation_command
0216          (boost::interprocess::shrink_in_place | boost::interprocess::nothrow_allocation, received_size, received_size, buckets);
0217       BOOST_ASSERT(buckets == shunk_p); (void)shunk_p;
0218
0219       bucket_ptr buckets_init = buckets + difference_type(received_size);
0220       for(size_type i = 0; i < (old_size - received_size); ++i){
0221          to_raw_pointer(buckets_init++)->~bucket_type();
0222       }
0223       return received_size;
0224    }
0225
0226    static bucket_ptr expand_or_create_buckets
0227       ( bucket_ptr old_buckets, const size_type old_num
0228       , allocator_type &alloc,  const size_type new_num)
0229    {
0230       size_type received_size = new_num;
0231       bucket_ptr reuse(old_buckets);
0232       bucket_ptr ret = alloc.allocation_command
0233             (boost::interprocess::expand_fwd | boost::interprocess::allocate_new, new_num, received_size, reuse);
0234       if(ret == old_buckets){
0235          bucket_ptr buckets_init = old_buckets + difference_type(old_num);
0236          for(size_type i = 0; i < (new_num - old_num); ++i){
0237             ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type();
0238          }
0239       }
0240       else{
0241          bucket_ptr buckets_init = ret;
0242          for(size_type i = 0; i < new_num; ++i){
0243             ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type();
0244          }
0245       }
0246       return ret;
0247    }
0248
0249    static void destroy_buckets
0250       (allocator_type &alloc, bucket_ptr buckets, size_type num)
0251    {
0252       bucket_ptr buckets_destroy = buckets;
0253       for(size_type i = 0; i < num; ++i){
0254          to_raw_pointer(buckets_destroy++)->~bucket_type();
0255       }
0256       alloc.deallocate(buckets, num);
0257    }
0258
0259    iunordered_set_index<MapConfig>* get_this_pointer()
0260    {  return this;   }
0261
0262    #endif   //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
0263
0264    public:
0265    using index_type::begin;
0266    using index_type::end;
0267    using index_type::size;
0268    using index_type::erase;
0269
0270    //!Constructor. Takes a pointer to the
0271    //!segment manager. Can throw
0272    iunordered_set_index(segment_manager_base *mngr)
0273       :  allocator_holder(mngr)
0274       ,  index_type(bucket_traits(&get_this_pointer()->init_bucket, 1))
0275    {}
0276
0277    ~iunordered_set_index()
0278    {
0279       index_type::clear();
0280       if(index_type::bucket_pointer() != bucket_ptr(&this->init_bucket)){
0281          destroy_buckets(this->alloc, index_type::bucket_pointer(), index_type::bucket_count());
0282       }
0283    }
0284
0285    //!This reserves memory to optimize the insertion of n
0286    //!elements in the index
0287    void reserve(size_type new_n)
0288    {
0289       //Let's maintain a 1.0f load factor
0290       size_type old_n  = this->bucket_count();
0291       if(new_n <= old_n)
0292          return;
0293       bucket_ptr old_p = this->bucket_pointer();
0294       new_n = index_type::suggested_upper_bucket_count(new_n);
0295       bucket_ptr new_p;
0296       //This can throw
0297       BOOST_INTERPROCESS_TRY{
0298          if(old_p != bucket_ptr(&this->init_bucket))
0299             new_p = expand_or_create_buckets(old_p, old_n, this->alloc, new_n);
0300          else
0301             new_p = create_buckets(this->alloc, new_n);
0302       }
0303       BOOST_INTERPROCESS_CATCH(...){
0304          return;
0305       } BOOST_INTERPROCESS_CATCH_END
0306       //Rehashing does not throw, since neither the hash nor the
0307       //comparison function can throw
0308       this->rehash(bucket_traits(new_p, new_n));
0309       if(new_p != old_p && old_p != bucket_ptr(&this->init_bucket)){
0310          destroy_buckets(this->alloc, old_p, old_n);
0311       }
0312    }
0313
0314    //!This tries to free unused memory
0315    //!previously allocated.
0316    void shrink_to_fit()
0317    {
0318       size_type cur_size   = this->size();
0319       size_type cur_count  = this->bucket_count();
0320       bucket_ptr old_p = this->bucket_pointer();
0321
0322       if(!this->size() && old_p != bucket_ptr(&this->init_bucket)){
0323          this->rehash(bucket_traits(bucket_ptr(&this->init_bucket), 1));
0324          destroy_buckets(this->alloc, old_p, cur_count);
0325       }
0326       else{
0327          size_type sug_count = 0; //gcc warning
0328          sug_count = index_type::suggested_upper_bucket_count(cur_size);
0329
0330          if(sug_count >= cur_count)
0331             return;
0332
0333          BOOST_INTERPROCESS_TRY{
0334             shrink_buckets(old_p, cur_count, this->alloc, sug_count);
0335          }
0336          BOOST_INTERPROCESS_CATCH(...){
0337             return;
0338          } BOOST_INTERPROCESS_CATCH_END
0339
0340          //Rehashing does not throw, since neither the hash nor the
0341          //comparison function can throw
0342          this->rehash(bucket_traits(old_p, sug_count));
0343       }
0344    }
0345
0346    iterator find(const compare_key_type&key)
0347    {  return index_type::find(key, hash_function(), equal_function());  }
0348
0349    const_iterator find(const compare_key_type&key) const
0350    {  return index_type::find(key, hash_function(), equal_function());  }
0351
0352    std::pair<iterator, bool>insert_check
0353       (const compare_key_type&key, insert_commit_data &commit_data)
0354    {  return index_type::insert_check(key, hash_function(), equal_function(), commit_data); }
0355
0356    iterator insert_commit
0357       (const compare_key_type &, void *, index_data_t &val, insert_commit_data& commit_data)
0358    {
0359       iterator it = index_type::insert_commit(val, commit_data);
0360       size_type cur_size      = this->size();
0361       if(cur_size > this->bucket_count()){
0362          BOOST_INTERPROCESS_TRY{
0363             this->reserve(cur_size);
0364          }
0365          BOOST_INTERPROCESS_CATCH(...){
0366             //Strong guarantee: if something goes wrong
0367             //we should remove the insertion.
0368             //
0369             //We can use the iterator because the hash function
0370             //can't throw and this means that "reserve" will
0371             //throw only because of the memory allocation:
0372             //the iterator has not been invalidated.
0373             index_type::erase(it);
0374             BOOST_INTERPROCESS_RETHROW
0375          } BOOST_INTERPROCESS_CATCH_END
0376       }
0377       return it;
0378    }
0379 };
0380
0381 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
0382
0383 //!Trait class to detect if an index is an intrusive
0384 //!index
0385 template<class MapConfig>
0386 struct is_intrusive_index
0387    <boost::interprocess::iunordered_set_index<MapConfig> >
0388 {
0389    static const bool value = true;
0390 };
0391 #endif   //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
0392
0393 }}   //namespace boost { namespace interprocess {
0394
0395 #include <boost/interprocess/detail/config_end.hpp>
0396
0397 #endif   //#ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP