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