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