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 38 template <class Slist> 39 struct bucket_impl : public Slist 40 { 41 typedef Slist slist_type; bucket_implboost::intrusive::bucket_impl42 BOOST_INTRUSIVE_FORCEINLINE bucket_impl() 43 {} 44 bucket_implboost::intrusive::bucket_impl45 BOOST_INTRUSIVE_FORCEINLINE bucket_impl(const bucket_impl &) 46 {} 47 ~bucket_implboost::intrusive::bucket_impl48 BOOST_INTRUSIVE_FORCEINLINE ~bucket_impl() 49 { 50 //This bucket is still being used! 51 BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty()); 52 } 53 operator =boost::intrusive::bucket_impl54 BOOST_INTRUSIVE_FORCEINLINE bucket_impl &operator=(const bucket_impl&) 55 { 56 //This bucket is still in use! 57 BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty()); 58 return *this; 59 } 60 }; 61 62 template<class Slist> 63 struct bucket_traits_impl 64 { 65 private: 66 BOOST_COPYABLE_AND_MOVABLE(bucket_traits_impl) 67 68 public: 69 /// @cond 70 71 typedef typename pointer_traits 72 <typename Slist::pointer>::template rebind_pointer 73 < bucket_impl<Slist> >::type bucket_ptr; 74 typedef Slist slist; 75 typedef typename Slist::size_type size_type; 76 /// @endcond 77 bucket_traits_implboost::intrusive::bucket_traits_impl78 BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl(bucket_ptr buckets, size_type len) 79 : buckets_(buckets), buckets_len_(len) 80 {} 81 bucket_traits_implboost::intrusive::bucket_traits_impl82 BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl(const bucket_traits_impl &x) 83 : buckets_(x.buckets_), buckets_len_(x.buckets_len_) 84 {} 85 bucket_traits_implboost::intrusive::bucket_traits_impl86 BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl(BOOST_RV_REF(bucket_traits_impl) x) 87 : buckets_(x.buckets_), buckets_len_(x.buckets_len_) 88 { x.buckets_ = bucket_ptr(); x.buckets_len_ = 0; } 89 operator =boost::intrusive::bucket_traits_impl90 BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl& operator=(BOOST_RV_REF(bucket_traits_impl) x) 91 { 92 buckets_ = x.buckets_; buckets_len_ = x.buckets_len_; 93 x.buckets_ = bucket_ptr(); x.buckets_len_ = 0; return *this; 94 } 95 operator =boost::intrusive::bucket_traits_impl96 BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl& operator=(BOOST_COPY_ASSIGN_REF(bucket_traits_impl) x) 97 { 98 buckets_ = x.buckets_; buckets_len_ = x.buckets_len_; return *this; 99 } 100 bucket_beginboost::intrusive::bucket_traits_impl101 BOOST_INTRUSIVE_FORCEINLINE const bucket_ptr &bucket_begin() const 102 { return buckets_; } 103 bucket_countboost::intrusive::bucket_traits_impl104 BOOST_INTRUSIVE_FORCEINLINE size_type bucket_count() const 105 { return buckets_len_; } 106 107 private: 108 bucket_ptr buckets_; 109 size_type buckets_len_; 110 }; 111 112 template <class NodeTraits> 113 struct hash_reduced_slist_node_traits 114 { 115 template <class U> static detail::no_type test(...); 116 template <class U> static detail::yes_type test(typename U::reduced_slist_node_traits*); 117 static const bool value = sizeof(test<NodeTraits>(0)) == sizeof(detail::yes_type); 118 }; 119 120 template <class NodeTraits> 121 struct apply_reduced_slist_node_traits 122 { 123 typedef typename NodeTraits::reduced_slist_node_traits type; 124 }; 125 126 template <class NodeTraits> 127 struct reduced_slist_node_traits 128 { 129 typedef typename detail::eval_if_c 130 < hash_reduced_slist_node_traits<NodeTraits>::value 131 , apply_reduced_slist_node_traits<NodeTraits> 132 , detail::identity<NodeTraits> 133 >::type type; 134 }; 135 136 template<class NodeTraits> 137 struct get_slist_impl 138 { 139 typedef trivial_value_traits<NodeTraits, normal_link> trivial_traits; 140 141 //Reducing symbol length 142 struct type : make_slist 143 < typename NodeTraits::node 144 , boost::intrusive::value_traits<trivial_traits> 145 , boost::intrusive::constant_time_size<false> 146 , boost::intrusive::size_type<std::size_t> 147 >::type 148 {}; 149 }; 150 151 template<class BucketValueTraits, bool IsConst> 152 class hashtable_iterator 153 { 154 typedef typename BucketValueTraits::value_traits value_traits; 155 typedef typename BucketValueTraits::bucket_traits bucket_traits; 156 157 typedef iiterator< value_traits, IsConst 158 , std::forward_iterator_tag> types_t; 159 public: 160 typedef typename types_t::iterator_type::difference_type difference_type; 161 typedef typename types_t::iterator_type::value_type value_type; 162 typedef typename types_t::iterator_type::pointer pointer; 163 typedef typename types_t::iterator_type::reference reference; 164 typedef typename types_t::iterator_type::iterator_category iterator_category; 165 166 private: 167 typedef typename value_traits::node_traits node_traits; 168 typedef typename node_traits::node_ptr node_ptr; 169 typedef typename get_slist_impl 170 < typename reduced_slist_node_traits 171 <node_traits>::type >::type slist_impl; 172 typedef typename slist_impl::iterator siterator; 173 typedef typename slist_impl::const_iterator const_siterator; 174 typedef bucket_impl<slist_impl> bucket_type; 175 176 typedef typename pointer_traits 177 <pointer>::template rebind_pointer 178 < const BucketValueTraits >::type const_bucketvaltraits_ptr; 179 typedef typename slist_impl::size_type size_type; 180 class nat; 181 typedef typename 182 detail::if_c< IsConst 183 , hashtable_iterator<BucketValueTraits, false> 184 , nat>::type nonconst_iterator; 185 downcast_bucket(typename bucket_type::node_ptr p)186 BOOST_INTRUSIVE_FORCEINLINE static node_ptr downcast_bucket(typename bucket_type::node_ptr p) 187 { 188 return pointer_traits<node_ptr>:: 189 pointer_to(static_cast<typename node_traits::node&>(*p)); 190 } 191 192 public: 193 hashtable_iterator()194 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator () 195 : slist_it_() //Value initialization to achieve "null iterators" (N3644) 196 {} 197 hashtable_iterator(siterator ptr,const BucketValueTraits * cont)198 BOOST_INTRUSIVE_FORCEINLINE explicit hashtable_iterator(siterator ptr, const BucketValueTraits *cont) 199 : slist_it_ (ptr) 200 , traitsptr_ (cont ? pointer_traits<const_bucketvaltraits_ptr>::pointer_to(*cont) : const_bucketvaltraits_ptr() ) 201 {} 202 hashtable_iterator(const hashtable_iterator & other)203 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator(const hashtable_iterator &other) 204 : slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits()) 205 {} 206 hashtable_iterator(const nonconst_iterator & other)207 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator(const nonconst_iterator &other) 208 : slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits()) 209 {} 210 slist_it() const211 BOOST_INTRUSIVE_FORCEINLINE const siterator &slist_it() const 212 { return slist_it_; } 213 unconst() const214 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator<BucketValueTraits, false> unconst() const 215 { return hashtable_iterator<BucketValueTraits, false>(this->slist_it(), this->get_bucket_value_traits()); } 216 operator ++()217 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator& operator++() 218 { this->increment(); return *this; } 219 operator =(const hashtable_iterator & other)220 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator &operator=(const hashtable_iterator &other) 221 { slist_it_ = other.slist_it(); traitsptr_ = other.get_bucket_value_traits(); return *this; } 222 operator ++(int)223 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator operator++(int) 224 { 225 hashtable_iterator result (*this); 226 this->increment(); 227 return result; 228 } 229 operator ==(const hashtable_iterator & i,const hashtable_iterator & i2)230 BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2) 231 { return i.slist_it_ == i2.slist_it_; } 232 operator !=(const hashtable_iterator & i,const hashtable_iterator & i2)233 BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2) 234 { return !(i == i2); } 235 operator *() const236 BOOST_INTRUSIVE_FORCEINLINE reference operator*() const 237 { return *this->operator ->(); } 238 operator ->() const239 BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const 240 { 241 return this->priv_value_traits().to_value_ptr 242 (downcast_bucket(slist_it_.pointed_node())); 243 } 244 get_bucket_value_traits() const245 BOOST_INTRUSIVE_FORCEINLINE const const_bucketvaltraits_ptr &get_bucket_value_traits() const 246 { return traitsptr_; } 247 priv_value_traits() const248 BOOST_INTRUSIVE_FORCEINLINE const value_traits &priv_value_traits() const 249 { return traitsptr_->priv_value_traits(); } 250 priv_bucket_traits() const251 BOOST_INTRUSIVE_FORCEINLINE const bucket_traits &priv_bucket_traits() const 252 { return traitsptr_->priv_bucket_traits(); } 253 254 private: increment()255 void increment() 256 { 257 const bucket_traits &rbuck_traits = this->priv_bucket_traits(); 258 bucket_type* const buckets = boost::movelib::to_raw_pointer(rbuck_traits.bucket_begin()); 259 const size_type buckets_len = rbuck_traits.bucket_count(); 260 261 ++slist_it_; 262 const typename slist_impl::node_ptr n = slist_it_.pointed_node(); 263 const siterator first_bucket_bbegin = buckets->end(); 264 if(first_bucket_bbegin.pointed_node() <= n && n <= buckets[buckets_len-1].cend().pointed_node()){ 265 //If one-past the node is inside the bucket then look for the next non-empty bucket 266 //1. get the bucket_impl from the iterator 267 const bucket_type &b = static_cast<const bucket_type&> 268 (bucket_type::slist_type::container_from_end_iterator(slist_it_)); 269 270 //2. Now just calculate the index b has in the bucket array 271 size_type n_bucket = static_cast<size_type>(&b - buckets); 272 273 //3. Iterate until a non-empty bucket is found 274 do{ 275 if (++n_bucket >= buckets_len){ //bucket overflow, return end() iterator 276 slist_it_ = buckets->before_begin(); 277 return; 278 } 279 } 280 while (buckets[n_bucket].empty()); 281 slist_it_ = buckets[n_bucket].begin(); 282 } 283 else{ 284 //++slist_it_ yield to a valid object 285 } 286 } 287 288 siterator slist_it_; 289 const_bucketvaltraits_ptr traitsptr_; 290 }; 291 292 } //namespace intrusive { 293 } //namespace boost { 294 295 #endif 296