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