intrusive/detail/hashtable_node.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga  2007-2014
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/intrusive for documentation.
0010 //
0011 /////////////////////////////////////////////////////////////////////////////
0012
0013 #ifndef BOOST_INTRUSIVE_HASHTABLE_NODE_HPP
0014 #define BOOST_INTRUSIVE_HASHTABLE_NODE_HPP
0015
0016 #ifndef BOOST_CONFIG_HPP
0017 #  include <boost/config.hpp>
0018 #endif
0019
0020 #if defined(BOOST_HAS_PRAGMA_ONCE)
0021 #  pragma once
0022 #endif
0023
0024 #include <boost/intrusive/detail/workaround.hpp>
0025 #include <boost/intrusive/detail/assert.hpp>
0026 #include <boost/intrusive/pointer_traits.hpp>
0027 #include <boost/intrusive/detail/mpl.hpp>
0028 #include <boost/intrusive/trivial_value_traits.hpp>
0029 #include <boost/intrusive/detail/common_slist_algorithms.hpp>
0030 #include <boost/intrusive/detail/iiterator.hpp>
0031 #include <boost/intrusive/detail/slist_iterator.hpp>
0032 #include <boost/move/detail/to_raw_pointer.hpp>
0033 #include <cstddef>
0034 #include <climits>
0035 #include <boost/move/core.hpp>
0036
0037
0038 namespace boost {
0039 namespace intrusive {
0040
0041 template <class NodeTraits>
0042 struct bucket_impl
0043    : public NodeTraits::node
0044 {
0045    public:
0046    typedef NodeTraits node_traits;
0047
0048    private:
0049    typedef typename node_traits::node_ptr          node_ptr;
0050    typedef typename node_traits::const_node_ptr    const_node_ptr;
0051
0052    typedef detail::common_slist_algorithms<NodeTraits> algo_t;
0053
0054    public:
0055    BOOST_INTRUSIVE_FORCEINLINE bucket_impl()
0056    {}
0057
0058    BOOST_INTRUSIVE_FORCEINLINE bucket_impl(const bucket_impl &)
0059    {}
0060
0061    BOOST_INTRUSIVE_FORCEINLINE ~bucket_impl()
0062    {}
0063
0064    BOOST_INTRUSIVE_FORCEINLINE bucket_impl &operator=(const bucket_impl&)
0065    {  return *this;  }
0066
0067    BOOST_INTRUSIVE_FORCEINLINE node_ptr get_node_ptr()
0068    {  return pointer_traits<node_ptr>::pointer_to(*this);  }
0069
0070    BOOST_INTRUSIVE_FORCEINLINE const_node_ptr get_node_ptr() const
0071    {  return pointer_traits<const_node_ptr>::pointer_to(*this);  }
0072
0073    BOOST_INTRUSIVE_FORCEINLINE node_ptr begin_ptr()
0074    {  return node_traits::get_next(get_node_ptr());  }
0075 };
0076
0077
0078
0079 template <class NodeTraits>
0080 struct hash_reduced_slist_node_traits
0081 {
0082    template <class U> static detail::no_type test(...);
0083    template <class U> static detail::yes_type test(typename U::reduced_slist_node_traits*);
0084    static const bool value = sizeof(test<NodeTraits>(0)) == sizeof(detail::yes_type);
0085 };
0086
0087 template <class NodeTraits>
0088 struct apply_reduced_slist_node_traits
0089 {
0090    typedef typename NodeTraits::reduced_slist_node_traits type;
0091 };
0092
0093 template <class NodeTraits>
0094 struct reduced_slist_node_traits
0095 {
0096    typedef typename detail::eval_if_c
0097       < hash_reduced_slist_node_traits<NodeTraits>::value
0098       , apply_reduced_slist_node_traits<NodeTraits>
0099       , detail::identity<NodeTraits>
0100       >::type type;
0101 };
0102
0103 template<class BucketValueTraits, bool LinearBuckets, bool IsConst>
0104 class hashtable_iterator
0105 {
0106    typedef typename BucketValueTraits::value_traits            value_traits;
0107    typedef typename BucketValueTraits::bucket_traits           bucket_traits;
0108
0109    typedef iiterator< value_traits, IsConst
0110                     , std::forward_iterator_tag>   types_t;
0111    public:
0112    typedef typename types_t::iterator_type::difference_type    difference_type;
0113    typedef typename types_t::iterator_type::value_type         value_type;
0114    typedef typename types_t::iterator_type::pointer            pointer;
0115    typedef typename types_t::iterator_type::reference          reference;
0116    typedef typename types_t::iterator_type::iterator_category  iterator_category;
0117
0118    private:
0119    typedef typename value_traits::node_traits                  node_traits;
0120    typedef typename node_traits::node_ptr                      node_ptr;
0121    typedef typename BucketValueTraits::bucket_type             bucket_type;
0122    typedef typename bucket_type::node_traits                   slist_node_traits;
0123    typedef typename slist_node_traits::node_ptr                slist_node_ptr;
0124    typedef trivial_value_traits
0125       <slist_node_traits, normal_link>                         slist_value_traits;
0126    typedef slist_iterator<slist_value_traits, false>           siterator;
0127    typedef slist_iterator<slist_value_traits, true>            const_siterator;
0128    typedef circular_slist_algorithms<slist_node_traits>        slist_node_algorithms;
0129
0130    typedef typename pointer_traits
0131       <pointer>::template rebind_pointer
0132          < const BucketValueTraits >::type                     const_bucketvaltraits_ptr;
0133    class nat;
0134    typedef typename
0135       detail::if_c< IsConst
0136                   , hashtable_iterator<BucketValueTraits, LinearBuckets, false>
0137                   , nat>::type                                 nonconst_iterator;
0138
0139    BOOST_INTRUSIVE_FORCEINLINE static node_ptr downcast_bucket(typename bucket_type::node_traits::node_ptr p)
0140    {
0141       return pointer_traits<node_ptr>::
0142          pointer_to(static_cast<typename node_traits::node&>(*p));
0143    }
0144
0145    public:
0146
0147    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator ()
0148       : slist_it_()  //Value initialization to achieve "null iterators" (N3644)
0149    {}
0150
0151    BOOST_INTRUSIVE_FORCEINLINE explicit hashtable_iterator(siterator ptr, const BucketValueTraits *cont)
0152       : slist_it_ (ptr)
0153       , traitsptr_ (cont ? pointer_traits<const_bucketvaltraits_ptr>::pointer_to(*cont) : const_bucketvaltraits_ptr() )
0154    {}
0155
0156    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator(const hashtable_iterator &other)
0157       :  slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits())
0158    {}
0159
0160    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator(const nonconst_iterator &other)
0161       :  slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits())
0162    {}
0163
0164    BOOST_INTRUSIVE_FORCEINLINE const siterator &slist_it() const
0165    { return slist_it_; }
0166
0167    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator<BucketValueTraits, LinearBuckets, false> unconst() const
0168    {  return hashtable_iterator<BucketValueTraits, LinearBuckets, false>(this->slist_it(), this->get_bucket_value_traits());   }
0169
0170    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator& operator++()
0171    {  this->increment();   return *this;   }
0172
0173    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator &operator=(const hashtable_iterator &other)
0174    {  slist_it_ = other.slist_it(); traitsptr_ = other.get_bucket_value_traits();   return *this;  }
0175
0176    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator operator++(int)
0177    {
0178       hashtable_iterator result (*this);
0179       this->increment();
0180       return result;
0181    }
0182
0183    BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2)
0184    { return i.slist_it_ == i2.slist_it_; }
0185
0186    BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2)
0187    { return !(i == i2); }
0188
0189    BOOST_INTRUSIVE_FORCEINLINE reference operator*() const
0190    { return *this->operator ->(); }
0191
0192    BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const
0193    {
0194       return this->priv_value_traits().to_value_ptr
0195          (downcast_bucket(slist_it_.pointed_node()));
0196    }
0197
0198    BOOST_INTRUSIVE_FORCEINLINE const_bucketvaltraits_ptr get_bucket_value_traits() const
0199    {  return traitsptr_;  }
0200
0201    BOOST_INTRUSIVE_FORCEINLINE const value_traits &priv_value_traits() const
0202    {  return traitsptr_->priv_value_traits();  }
0203
0204    private:
0205
0206    void increment()
0207    {
0208       bucket_type* const buckets = boost::movelib::to_raw_pointer(traitsptr_->priv_bucket_traits().bucket_begin());
0209       const std::size_t buckets_len = traitsptr_->priv_bucket_traits().bucket_count();
0210
0211       ++slist_it_;
0212       const slist_node_ptr n = slist_it_.pointed_node();
0213       const siterator first_bucket_bbegin(buckets->get_node_ptr());
0214       if(first_bucket_bbegin.pointed_node() <= n && n <= buckets[buckets_len-1].get_node_ptr()){
0215          //If one-past the node is inside the bucket then look for the next non-empty bucket
0216          //1. get the bucket_impl from the iterator
0217          const bucket_type &b = static_cast<const bucket_type&>(*n);
0218
0219          //2. Now just calculate the index b has in the bucket array
0220          std::size_t n_bucket = static_cast<std::size_t>(&b - buckets);
0221
0222          //3. Iterate until a non-empty bucket is found
0223          slist_node_ptr bucket_nodeptr = buckets->get_node_ptr();
0224          do{
0225             if (++n_bucket >= buckets_len){  //bucket overflow, return end() iterator
0226                slist_it_ = first_bucket_bbegin;
0227                return;
0228             }
0229             bucket_nodeptr = buckets[n_bucket].get_node_ptr();
0230          }
0231          while (slist_node_algorithms::is_empty(bucket_nodeptr));
0232          slist_it_ = siterator(bucket_nodeptr);
0233          ++slist_it_;
0234       }
0235       else{
0236          //++slist_it_ yield to a valid object
0237       }
0238    }
0239
0240    siterator                  slist_it_;
0241    const_bucketvaltraits_ptr  traitsptr_;
0242 };
0243
0244 template<class BucketValueTraits, bool IsConst>
0245 class hashtable_iterator<BucketValueTraits, true, IsConst>
0246 {
0247    typedef typename BucketValueTraits::value_traits            value_traits;
0248    typedef typename BucketValueTraits::bucket_traits           bucket_traits;
0249
0250    typedef iiterator< value_traits, IsConst
0251                     , std::forward_iterator_tag>   types_t;
0252    public:
0253    typedef typename types_t::iterator_type::difference_type    difference_type;
0254    typedef typename types_t::iterator_type::value_type         value_type;
0255    typedef typename types_t::iterator_type::pointer            pointer;
0256    typedef typename types_t::iterator_type::reference          reference;
0257    typedef typename types_t::iterator_type::iterator_category  iterator_category;
0258
0259    private:
0260    typedef typename value_traits::node_traits                  node_traits;
0261    typedef typename node_traits::node_ptr                      node_ptr;
0262    typedef typename BucketValueTraits::bucket_type             bucket_type;
0263    typedef typename BucketValueTraits::bucket_ptr              bucket_ptr;
0264    typedef typename bucket_type::node_traits                   slist_node_traits;
0265    typedef linear_slist_algorithms<slist_node_traits>          slist_node_algorithms;
0266    typedef typename slist_node_traits::node_ptr                slist_node_ptr;
0267    typedef trivial_value_traits
0268       <slist_node_traits, normal_link>                         slist_value_traits;
0269    typedef slist_iterator<slist_value_traits, false>           siterator;
0270    typedef slist_iterator<slist_value_traits, true>            const_siterator;
0271
0272    static const bool stateful_value_traits =
0273       detail::is_stateful_value_traits<value_traits>::value;
0274
0275    typedef typename pointer_traits
0276       <pointer>::template rebind_pointer
0277          < const value_traits >::type                          const_value_traits_ptr;
0278    class nat;
0279    typedef typename
0280       detail::if_c< IsConst
0281                   , hashtable_iterator<BucketValueTraits, true, false>
0282                   , nat>::type                                 nonconst_iterator;
0283
0284    BOOST_INTRUSIVE_FORCEINLINE static node_ptr downcast_bucket(slist_node_ptr p)
0285    {
0286       return pointer_traits<node_ptr>::
0287          pointer_to(static_cast<typename node_traits::node&>(*p));
0288    }
0289
0290    public:
0291
0292    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator ()
0293       : slist_it_()  //Value initialization to achieve "null iterators" (N3644)
0294       , members_()
0295    {}
0296
0297    BOOST_INTRUSIVE_FORCEINLINE explicit hashtable_iterator(siterator ptr, bucket_ptr bp, const_value_traits_ptr traits_ptr)
0298       : slist_it_ (ptr)
0299       , members_ (bp, traits_ptr)
0300    {}
0301
0302    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator(const hashtable_iterator &other)
0303       :  slist_it_(other.slist_it()), members_(other.get_bucket_ptr(), other.get_value_traits())
0304    {}
0305
0306    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator(const nonconst_iterator &other)
0307       :  slist_it_(other.slist_it()), members_(other.get_bucket_ptr(), other.get_value_traits())
0308    {}
0309
0310    BOOST_INTRUSIVE_FORCEINLINE const siterator &slist_it() const
0311    { return slist_it_; }
0312
0313    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator<BucketValueTraits, true, false> unconst() const
0314    {  return hashtable_iterator<BucketValueTraits, true, false>(this->slist_it(), members_.nodeptr_, members_.get_ptr());   }
0315
0316    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator& operator++()
0317    {  this->increment();   return *this;   }
0318
0319    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator &operator=(const hashtable_iterator &other)
0320    {  slist_it_ = other.slist_it(); members_ = other.members_;  return *this;  }
0321
0322    BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator operator++(int)
0323    {
0324       hashtable_iterator result (*this);
0325       this->increment();
0326       return result;
0327    }
0328
0329    BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2)
0330    { return i.slist_it_ == i2.slist_it_; }
0331
0332    BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2)
0333    { return i.slist_it_ != i2.slist_it_; }
0334
0335    BOOST_INTRUSIVE_FORCEINLINE reference operator*() const
0336    { return *this->operator ->(); }
0337
0338    BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const
0339    { return this->operator_arrow(detail::bool_<stateful_value_traits>()); }
0340
0341    BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr get_value_traits() const
0342    {  return members_.get_ptr(); }
0343
0344    BOOST_INTRUSIVE_FORCEINLINE bucket_ptr get_bucket_ptr() const
0345    {  return members_.nodeptr_; }
0346
0347    private:
0348
0349    BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::false_) const
0350    { return value_traits::to_value_ptr(downcast_bucket(slist_it_.pointed_node())); }
0351
0352    BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::true_) const
0353    { return this->get_value_traits()->to_value_ptr(downcast_bucket(slist_it_.pointed_node())); }
0354
0355    void increment()
0356    {
0357       ++slist_it_;
0358       if (slist_it_ == siterator()){
0359          slist_node_ptr bucket_nodeptr;
0360          do {
0361             ++members_.nodeptr_;
0362              bucket_nodeptr = members_.nodeptr_->get_node_ptr();
0363          }while(slist_node_algorithms::is_empty(bucket_nodeptr));
0364          slist_it_ = siterator(slist_node_traits::get_next(bucket_nodeptr));
0365       }
0366    }
0367
0368    siterator   slist_it_;
0369    iiterator_members<bucket_ptr, const_value_traits_ptr, stateful_value_traits> members_;
0370 };
0371
0372 }  //namespace intrusive {
0373 }  //namespace boost {
0374
0375 #endif