boost/interprocess/indexes/iunordered_set_index.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/interprocess for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10
  11 #ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP
  12 #define BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP
  13
  14 #if defined(_MSC_VER)
  15 #  pragma once
  16 #endif
  17
  18 #include <boost/interprocess/detail/config_begin.hpp>
  19 #include <boost/interprocess/detail/workaround.hpp>
  20
  21 #include <functional>
  22 #include <utility>
  23
  24 #include <boost/interprocess/detail/utilities.hpp>
  25 #include <boost/interprocess/containers/vector.hpp>
  26 #include <boost/intrusive/unordered_set.hpp>
  27 #include <boost/interprocess/allocators/allocator.hpp>
  28
  29 //!\file
  30 //!Describes index adaptor of boost::intrusive::unordered_set container, to use it
  31 //!as name/shared memory index
  32
  33 namespace boost { namespace interprocess {
  34
  35 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
  36
  37 //!Helper class to define typedefs
  38 //!from IndexTraits
  39 template <class MapConfig>
  40 struct iunordered_set_index_aux
  41 {
  42    typedef typename
  43       MapConfig::segment_manager_base                 segment_manager_base;
  44
  45    typedef typename
  46       segment_manager_base::void_pointer              void_pointer;
  47
  48    typedef typename bi::make_unordered_set_base_hook
  49       < bi::void_pointer<void_pointer>
  50       >::type        derivation_hook;
  51
  52    typedef typename MapConfig::template
  53       intrusive_value_type<derivation_hook>::type     value_type;
  54
  55    typedef typename MapConfig::
  56       intrusive_compare_key_type                      intrusive_compare_key_type;
  57
  58    typedef std::equal_to<value_type>                  value_equal;
  59
  60    typedef typename MapConfig::char_type              char_type;
  61
  62    struct equal_function
  63    {
  64       bool operator()(const intrusive_compare_key_type &i, const value_type &b) const
  65       {
  66          return (i.m_len == b.name_length()) &&
  67                   (std::char_traits<char_type>::compare
  68                      (i.mp_str, b.name(), i.m_len) == 0);
  69       }
  70
  71       bool operator()(const value_type &b, const intrusive_compare_key_type &i) const
  72       {
  73          return (i.m_len == b.name_length()) &&
  74                   (std::char_traits<char_type>::compare
  75                      (i.mp_str, b.name(), i.m_len) == 0);
  76       }
  77
  78       bool operator()(const value_type &b1, const value_type &b2) const
  79       {
  80          return (b1.name_length() == b2.name_length()) &&
  81                   (std::char_traits<char_type>::compare
  82                      (b1.name(), b2.name(), b1.name_length()) == 0);
  83       }
  84    };
  85
  86     struct hash_function
  87       : std::unary_function<value_type, std::size_t>
  88     {
  89         std::size_t operator()(const value_type &val) const
  90         {
  91             const char_type *beg = ipcdetail::to_raw_pointer(val.name()),
  92                             *end = beg + val.name_length();
  93             return boost::hash_range(beg, end);
  94         }
  95
  96         std::size_t operator()(const intrusive_compare_key_type &i) const
  97         {
  98             const char_type *beg = i.mp_str,
  99                             *end = beg + i.m_len;
 100             return boost::hash_range(beg, end);
 101         }
 102     };
 103
 104    typedef typename bi::make_unordered_set
 105       < value_type
 106       , bi::hash<hash_function>
 107       , bi::equal<equal_function>
 108      , bi::size_type<typename segment_manager_base::size_type>
 109       >::type                                         index_t;
 110    typedef typename index_t::bucket_type              bucket_type;
 111    typedef allocator
 112       <bucket_type, segment_manager_base>             allocator_type;
 113
 114    struct allocator_holder
 115    {
 116       allocator_holder(segment_manager_base *mngr)
 117          :  alloc(mngr)
 118       {}
 119       allocator_type alloc;
 120       bucket_type init_bucket;
 121    };
 122 };
 123 #endif   //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
 124
 125 //!Index type based in boost::intrusive::set.
 126 //!Just derives from boost::intrusive::set
 127 //!and defines the interface needed by managed memory segments
 128 template <class MapConfig>
 129 class iunordered_set_index
 130       //Derive class from map specialization
 131    :  private iunordered_set_index_aux<MapConfig>::allocator_holder
 132    ,  public iunordered_set_index_aux<MapConfig>::index_t
 133 {
 134    #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
 135    typedef iunordered_set_index_aux<MapConfig>           index_aux;
 136    typedef typename index_aux::index_t                   index_type;
 137    typedef typename MapConfig::
 138       intrusive_compare_key_type                         intrusive_compare_key_type;
 139    typedef typename index_aux::equal_function            equal_function;
 140    typedef typename index_aux::hash_function             hash_function;
 141    typedef typename MapConfig::char_type                 char_type;
 142    typedef typename
 143       iunordered_set_index_aux<MapConfig>::allocator_type      allocator_type;
 144    typedef typename
 145       iunordered_set_index_aux<MapConfig>::allocator_holder    allocator_holder;
 146    #endif   //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
 147
 148    public:
 149    typedef typename index_type::iterator                 iterator;
 150    typedef typename index_type::const_iterator           const_iterator;
 151    typedef typename index_type::insert_commit_data       insert_commit_data;
 152    typedef typename index_type::value_type               value_type;
 153    typedef typename index_type::bucket_ptr               bucket_ptr;
 154    typedef typename index_type::bucket_type              bucket_type;
 155    typedef typename index_type::bucket_traits            bucket_traits;
 156    typedef typename index_type::size_type                size_type;
 157
 158    #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
 159    private:
 160    typedef typename index_aux::
 161       segment_manager_base             segment_manager_base;
 162
 163    static const std::size_t InitBufferSize = 64;
 164
 165    static bucket_ptr create_buckets(allocator_type &alloc, size_type num)
 166    {
 167       num = index_type::suggested_upper_bucket_count(num);
 168       bucket_ptr buckets = alloc.allocate(num);
 169       bucket_ptr buckets_init = buckets;
 170       for(size_type i = 0; i < num; ++i){
 171          new(to_raw_pointer(buckets_init++))bucket_type();
 172       }
 173       return buckets;
 174    }
 175
 176    static size_type shrink_buckets
 177       ( bucket_ptr buckets, size_type old_size
 178       , allocator_type &alloc, size_type new_size)
 179    {
 180       if(old_size <= new_size )
 181          return old_size;
 182       size_type received_size;
 183       if(!alloc.allocation_command
 184          (boost::interprocess::try_shrink_in_place | boost::interprocess::nothrow_allocation, old_size, new_size, received_size, buckets).first){
 185          return old_size;
 186       }
 187
 188       for( bucket_type *p = ipcdetail::to_raw_pointer(buckets) + received_size
 189          , *pend = ipcdetail::to_raw_pointer(buckets) + old_size
 190          ; p != pend
 191          ; ++p){
 192          p->~bucket_type();
 193       }
 194
 195       bucket_ptr shunk_p = alloc.allocation_command
 196          (boost::interprocess::shrink_in_place | boost::interprocess::nothrow_allocation, received_size, received_size, received_size, buckets).first;
 197       BOOST_ASSERT(buckets == shunk_p); (void)shunk_p;
 198
 199       bucket_ptr buckets_init = buckets + received_size;
 200       for(size_type i = 0; i < (old_size - received_size); ++i){
 201          to_raw_pointer(buckets_init++)->~bucket_type();
 202       }
 203       return received_size;
 204    }
 205
 206    static bucket_ptr expand_or_create_buckets
 207       ( bucket_ptr old_buckets, const size_type old_num
 208       , allocator_type &alloc,  const size_type new_num)
 209    {
 210       size_type received_size;
 211       std::pair<bucket_ptr, bool> ret =
 212          alloc.allocation_command
 213             (boost::interprocess::expand_fwd | boost::interprocess::allocate_new, new_num, new_num, received_size, old_buckets);
 214       if(ret.first == old_buckets){
 215          bucket_ptr buckets_init = old_buckets + old_num;
 216          for(size_type i = 0; i < (new_num - old_num); ++i){
 217             new(to_raw_pointer(buckets_init++))bucket_type();
 218          }
 219       }
 220       else{
 221          bucket_ptr buckets_init = ret.first;
 222          for(size_type i = 0; i < new_num; ++i){
 223             new(to_raw_pointer(buckets_init++))bucket_type();
 224          }
 225       }
 226
 227       return ret.first;
 228    }
 229
 230    static void destroy_buckets
 231       (allocator_type &alloc, bucket_ptr buckets, size_type num)
 232    {
 233       bucket_ptr buckets_destroy = buckets;
 234       for(size_type i = 0; i < num; ++i){
 235          to_raw_pointer(buckets_destroy++)->~bucket_type();
 236       }
 237       alloc.deallocate(buckets, num);
 238    }
 239
 240    iunordered_set_index<MapConfig>* get_this_pointer()
 241    {  return this;   }
 242
 243    #endif   //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
 244
 245    public:
 246    //!Constructor. Takes a pointer to the
 247    //!segment manager. Can throw
 248    iunordered_set_index(segment_manager_base *mngr)
 249       :  allocator_holder(mngr)
 250       ,  index_type(bucket_traits(&get_this_pointer()->init_bucket, 1))
 251    {}
 252
 253    ~iunordered_set_index()
 254    {
 255       index_type::clear();
 256       if(index_type::bucket_pointer() != bucket_ptr(&this->init_bucket)){
 257          destroy_buckets(this->alloc, index_type::bucket_pointer(), index_type::bucket_count());
 258       }
 259    }
 260
 261    //!This reserves memory to optimize the insertion of n
 262    //!elements in the index
 263    void reserve(size_type new_n)
 264    {
 265       //Let's maintain a 1.0f load factor
 266       size_type old_n  = this->bucket_count();
 267       if(new_n <= old_n)
 268          return;
 269       bucket_ptr old_p = this->bucket_pointer();
 270       new_n = index_type::suggested_upper_bucket_count(new_n);
 271       bucket_ptr new_p;
 272       //This can throw
 273       try{
 274          if(old_p != bucket_ptr(&this->init_bucket))
 275             new_p = expand_or_create_buckets(old_p, old_n, this->alloc, new_n);
 276          else
 277             new_p = create_buckets(this->alloc, new_n);
 278       }
 279       catch(...){
 280          return;
 281       }
 282       //Rehashing does not throw, since neither the hash nor the
 283       //comparison function can throw
 284       this->rehash(bucket_traits(new_p, new_n));
 285       if(new_p != old_p && old_p != bucket_ptr(&this->init_bucket)){
 286          destroy_buckets(this->alloc, old_p, old_n);
 287       }
 288    }
 289
 290    //!This tries to free unused memory
 291    //!previously allocated.
 292    void shrink_to_fit()
 293    {
 294       size_type cur_size   = this->size();
 295       size_type cur_count  = this->bucket_count();
 296       bucket_ptr old_p = this->bucket_pointer();
 297
 298       if(!this->size() && old_p != bucket_ptr(&this->init_bucket)){
 299          this->rehash(bucket_traits(bucket_ptr(&this->init_bucket), 1));
 300          destroy_buckets(this->alloc, old_p, cur_count);
 301       }
 302       else{
 303          size_type sug_count = 0; //gcc warning
 304          sug_count = index_type::suggested_upper_bucket_count(cur_size);
 305
 306          if(sug_count >= cur_count)
 307             return;
 308
 309          try{
 310             shrink_buckets(old_p, cur_count, this->alloc, sug_count);
 311          }
 312          catch(...){
 313             return;
 314          }
 315
 316          //Rehashing does not throw, since neither the hash nor the
 317          //comparison function can throw
 318          this->rehash(bucket_traits(old_p, sug_count));
 319       }
 320    }
 321
 322    iterator find(const intrusive_compare_key_type &key)
 323    {  return index_type::find(key, hash_function(), equal_function());  }
 324
 325    const_iterator find(const intrusive_compare_key_type &key) const
 326    {  return index_type::find(key, hash_function(), equal_function());  }
 327
 328    std::pair<iterator, bool>insert_check
 329       (const intrusive_compare_key_type &key, insert_commit_data &commit_data)
 330    {  return index_type::insert_check(key, hash_function(), equal_function(), commit_data); }
 331
 332    iterator insert_commit(value_type &val, insert_commit_data &commit_data)
 333    {
 334       iterator it = index_type::insert_commit(val, commit_data);
 335       size_type cur_size      = this->size();
 336       if(cur_size > this->bucket_count()){
 337          try{
 338             this->reserve(cur_size);
 339          }
 340          catch(...){
 341             //Strong guarantee: if something goes wrong
 342             //we should remove the insertion.
 343             //
 344             //We can use the iterator because the hash function
 345             //can't throw and this means that "reserve" will
 346             //throw only because of the memory allocation:
 347             //the iterator has not been invalidated.
 348             index_type::erase(it);
 349             throw;
 350          }
 351       }
 352       return it;
 353    }
 354 };
 355
 356 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
 357
 358 //!Trait class to detect if an index is an intrusive
 359 //!index
 360 template<class MapConfig>
 361 struct is_intrusive_index
 362    <boost::interprocess::iunordered_set_index<MapConfig> >
 363 {
 364    static const bool value = true;
 365 };
 366 #endif   //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
 367
 368 }}   //namespace boost { namespace interprocess {
 369
 370 #include <boost/interprocess/detail/config_end.hpp>
 371
 372 #endif   //#ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP