ceph/src/boost/libs/intrusive/include/boost/intrusive/detail/hashtable_node.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2014
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef BOOST_INTRUSIVE_HASHTABLE_NODE_HPP
  14 #define BOOST_INTRUSIVE_HASHTABLE_NODE_HPP
  15
  16 #ifndef BOOST_CONFIG_HPP
  17 #  include <boost/config.hpp>
  18 #endif
  19
  20 #if defined(BOOST_HAS_PRAGMA_ONCE)
  21 #  pragma once
  22 #endif
  23
  24 #include <boost/intrusive/detail/workaround.hpp>
  25 #include <boost/intrusive/detail/assert.hpp>
  26 #include <boost/intrusive/pointer_traits.hpp>
  27 #include <boost/intrusive/detail/mpl.hpp>
  28 #include <boost/intrusive/trivial_value_traits.hpp>
  29 #include <boost/intrusive/slist.hpp> //make_slist
  30 #include <cstddef>
  31 #include <climits>
  32 #include <boost/move/core.hpp>
  33
  34
  35 namespace boost {
  36 namespace intrusive {
  37 namespace detail {
  38
  39 template <class Slist>
  40 struct bucket_impl : public Slist
  41 {
  42    typedef Slist slist_type;
  43    bucket_impl()
  44    {}
  45
  46    bucket_impl(const bucket_impl &)
  47    {}
  48
  49    ~bucket_impl()
  50    {
  51       //This bucket is still being used!
  52       BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty());
  53    }
  54
  55    bucket_impl &operator=(const bucket_impl&)
  56    {
  57       //This bucket is still in use!
  58       BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty());
  59       //Slist::clear();
  60       return *this;
  61    }
  62 };
  63
  64 template<class Slist>
  65 struct bucket_traits_impl
  66 {
  67    private:
  68    BOOST_COPYABLE_AND_MOVABLE(bucket_traits_impl)
  69
  70    public:
  71    /// @cond
  72
  73    typedef typename pointer_traits
  74       <typename Slist::pointer>::template rebind_pointer
  75          < bucket_impl<Slist> >::type                                bucket_ptr;
  76    typedef Slist slist;
  77    typedef typename Slist::size_type size_type;
  78    /// @endcond
  79
  80    bucket_traits_impl(bucket_ptr buckets, size_type len)
  81       :  buckets_(buckets), buckets_len_(len)
  82    {}
  83
  84    bucket_traits_impl(const bucket_traits_impl &x)
  85       : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
  86    {}
  87
  88    bucket_traits_impl(BOOST_RV_REF(bucket_traits_impl) x)
  89       : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
  90    {  x.buckets_ = bucket_ptr();   x.buckets_len_ = 0;  }
  91
  92    bucket_traits_impl& operator=(BOOST_RV_REF(bucket_traits_impl) x)
  93    {
  94       buckets_ = x.buckets_; buckets_len_ = x.buckets_len_;
  95       x.buckets_ = bucket_ptr();   x.buckets_len_ = 0; return *this;
  96    }
  97
  98    bucket_traits_impl& operator=(BOOST_COPY_ASSIGN_REF(bucket_traits_impl) x)
  99    {
 100       buckets_ = x.buckets_;  buckets_len_ = x.buckets_len_; return *this;
 101    }
 102
 103    BOOST_INTRUSIVE_FORCEINLINE const bucket_ptr &bucket_begin() const
 104    {  return buckets_;  }
 105
 106    BOOST_INTRUSIVE_FORCEINLINE size_type  bucket_count() const
 107    {  return buckets_len_;  }
 108
 109    private:
 110    bucket_ptr  buckets_;
 111    size_type   buckets_len_;
 112 };
 113
 114 template <class NodeTraits>
 115 struct hash_reduced_slist_node_traits
 116 {
 117    template <class U> static detail::no_type test(...);
 118    template <class U> static detail::yes_type test(typename U::reduced_slist_node_traits*);
 119    static const bool value = sizeof(test<NodeTraits>(0)) == sizeof(detail::yes_type);
 120 };
 121
 122 template <class NodeTraits>
 123 struct apply_reduced_slist_node_traits
 124 {
 125    typedef typename NodeTraits::reduced_slist_node_traits type;
 126 };
 127
 128 template <class NodeTraits>
 129 struct reduced_slist_node_traits
 130 {
 131    typedef typename detail::eval_if_c
 132       < hash_reduced_slist_node_traits<NodeTraits>::value
 133       , apply_reduced_slist_node_traits<NodeTraits>
 134       , detail::identity<NodeTraits>
 135       >::type type;
 136 };
 137
 138 template<class NodeTraits>
 139 struct get_slist_impl
 140 {
 141    typedef trivial_value_traits<NodeTraits, normal_link> trivial_traits;
 142
 143    //Reducing symbol length
 144    struct type : make_slist
 145       < typename NodeTraits::node
 146       , boost::intrusive::value_traits<trivial_traits>
 147       , boost::intrusive::constant_time_size<false>
 148       , boost::intrusive::size_type<std::size_t>
 149       >::type
 150    {};
 151 };
 152
 153 }  //namespace detail {
 154
 155 template<class BucketValueTraits, bool IsConst>
 156 class hashtable_iterator
 157 {
 158    typedef typename BucketValueTraits::value_traits            value_traits;
 159    typedef typename BucketValueTraits::bucket_traits           bucket_traits;
 160
 161    typedef iiterator< value_traits, IsConst
 162                     , std::forward_iterator_tag>   types_t;
 163    public:
 164    typedef typename types_t::iterator_type::difference_type    difference_type;
 165    typedef typename types_t::iterator_type::value_type         value_type;
 166    typedef typename types_t::iterator_type::pointer            pointer;
 167    typedef typename types_t::iterator_type::reference          reference;
 168    typedef typename types_t::iterator_type::iterator_category  iterator_category;
 169
 170    private:
 171    typedef typename value_traits::node_traits                  node_traits;
 172    typedef typename node_traits::node_ptr                      node_ptr;
 173    typedef typename detail::get_slist_impl
 174       < typename detail::reduced_slist_node_traits
 175          <node_traits>::type >::type                           slist_impl;
 176    typedef typename slist_impl::iterator                       siterator;
 177    typedef typename slist_impl::const_iterator                 const_siterator;
 178    typedef detail::bucket_impl<slist_impl>                     bucket_type;
 179
 180    typedef typename pointer_traits
 181       <pointer>::template rebind_pointer
 182          < const BucketValueTraits >::type                     const_bucketvaltraits_ptr;
 183    typedef typename slist_impl::size_type                      size_type;
 184
 185    static node_ptr downcast_bucket(typename bucket_type::node_ptr p)
 186    {
 187       return pointer_traits<node_ptr>::
 188          pointer_to(static_cast<typename node_traits::node&>(*p));
 189    }
 190
 191    public:
 192
 193    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator ()
 194       : slist_it_()  //Value initialization to achieve "null iterators" (N3644)
 195    {}
 196
 197    explicit hashtable_iterator(siterator ptr, const BucketValueTraits *cont)
 198       : slist_it_ (ptr)
 199       , traitsptr_ (cont ? pointer_traits<const_bucketvaltraits_ptr>::pointer_to(*cont) : const_bucketvaltraits_ptr() )
 200    {}
 201
 202    hashtable_iterator(const hashtable_iterator<BucketValueTraits, false> &other)
 203       :  slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits())
 204    {}
 205
 206    BOOST_INTRUSIVE_FORCEINLINE const siterator &slist_it() const
 207    { return slist_it_; }
 208
 209    hashtable_iterator<BucketValueTraits, false> unconst() const
 210    {  return hashtable_iterator<BucketValueTraits, false>(this->slist_it(), this->get_bucket_value_traits());   }
 211
 212    hashtable_iterator& operator++()
 213    {  this->increment();   return *this;   }
 214
 215    hashtable_iterator operator++(int)
 216    {
 217       hashtable_iterator result (*this);
 218       this->increment();
 219       return result;
 220    }
 221
 222    BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2)
 223    { return i.slist_it_ == i2.slist_it_; }
 224
 225    BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2)
 226    { return !(i == i2); }
 227
 228    BOOST_INTRUSIVE_FORCEINLINE reference operator*() const
 229    { return *this->operator ->(); }
 230
 231    BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const
 232    {
 233       return this->priv_value_traits().to_value_ptr
 234          (downcast_bucket(slist_it_.pointed_node()));
 235    }
 236
 237    BOOST_INTRUSIVE_FORCEINLINE const const_bucketvaltraits_ptr &get_bucket_value_traits() const
 238    {  return traitsptr_;  }
 239
 240    BOOST_INTRUSIVE_FORCEINLINE const value_traits &priv_value_traits() const
 241    {  return traitsptr_->priv_value_traits();  }
 242
 243    BOOST_INTRUSIVE_FORCEINLINE const bucket_traits &priv_bucket_traits() const
 244    {  return traitsptr_->priv_bucket_traits();  }
 245
 246    private:
 247    void increment()
 248    {
 249       const bucket_traits &rbuck_traits = this->priv_bucket_traits();
 250       bucket_type* const buckets = boost::intrusive::detail::to_raw_pointer(rbuck_traits.bucket_begin());
 251       const size_type buckets_len = rbuck_traits.bucket_count();
 252
 253       ++slist_it_;
 254       const typename slist_impl::node_ptr n = slist_it_.pointed_node();
 255       const siterator first_bucket_bbegin = buckets->end();
 256       if(first_bucket_bbegin.pointed_node() <= n && n <= buckets[buckets_len-1].cend().pointed_node()){
 257          //If one-past the node is inside the bucket then look for the next non-empty bucket
 258          //1. get the bucket_impl from the iterator
 259          const bucket_type &b = static_cast<const bucket_type&>
 260             (bucket_type::slist_type::container_from_end_iterator(slist_it_));
 261
 262          //2. Now just calculate the index b has in the bucket array
 263          size_type n_bucket = static_cast<size_type>(&b - buckets);
 264
 265          //3. Iterate until a non-empty bucket is found
 266          do{
 267             if (++n_bucket >= buckets_len){  //bucket overflow, return end() iterator
 268                slist_it_ = buckets->before_begin();
 269                return;
 270             }
 271          }
 272          while (buckets[n_bucket].empty());
 273          slist_it_ = buckets[n_bucket].begin();
 274       }
 275       else{
 276          //++slist_it_ yield to a valid object
 277       }
 278    }
 279
 280    siterator                  slist_it_;
 281    const_bucketvaltraits_ptr  traitsptr_;
 282 };
 283
 284 }  //namespace intrusive {
 285 }  //namespace boost {
 286
 287 #endif