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/detail/common_slist_algorithms.hpp>
30#include <boost/intrusive/detail/iiterator.hpp>
31#include <boost/intrusive/detail/slist_iterator.hpp>
32#include <boost/move/detail/to_raw_pointer.hpp>
33#include <cstddef>
34#include <climits>
35#include <boost/move/core.hpp>
36
37
38namespace boost {
39namespace intrusive {
40
41template <class NodeTraits>
42struct bucket_impl
43 : public NodeTraits::node
44{
45 public:
46 typedef NodeTraits node_traits;
47
48 private:
49 typedef typename node_traits::node_ptr node_ptr;
50 typedef typename node_traits::const_node_ptr const_node_ptr;
51
52 typedef detail::common_slist_algorithms<NodeTraits> algo_t;
53
54 public:
55 inline bucket_impl()
56 {}
57
58 inline bucket_impl(const bucket_impl &)
59 {}
60
61 inline ~bucket_impl()
62 {}
63
64 inline bucket_impl &operator=(const bucket_impl&)
65 { return *this; }
66
67 inline node_ptr get_node_ptr()
68 { return pointer_traits<node_ptr>::pointer_to(*this); }
69
70 inline const_node_ptr get_node_ptr() const
71 { return pointer_traits<const_node_ptr>::pointer_to(*this); }
72
73 inline node_ptr begin_ptr()
74 { return node_traits::get_next(get_node_ptr()); }
75};
76
77
78
79template <class NodeTraits>
80struct hash_reduced_slist_node_traits
81{
82 template <class U> static detail::no_type test(...);
83 template <class U> static detail::yes_type test(typename U::reduced_slist_node_traits*);
84 static const bool value = sizeof(test<NodeTraits>(0)) == sizeof(detail::yes_type);
85};
86
87template <class NodeTraits>
88struct apply_reduced_slist_node_traits
89{
90 typedef typename NodeTraits::reduced_slist_node_traits type;
91};
92
93template <class NodeTraits>
94struct reduced_slist_node_traits
95{
96 typedef typename detail::eval_if_c
97 < hash_reduced_slist_node_traits<NodeTraits>::value
98 , apply_reduced_slist_node_traits<NodeTraits>
99 , detail::identity<NodeTraits>
100 >::type type;
101};
102
103template<class BucketValueTraits, bool LinearBuckets, bool IsConst>
104class hashtable_iterator
105{
106 typedef typename BucketValueTraits::value_traits value_traits;
107 typedef typename BucketValueTraits::bucket_traits bucket_traits;
108
109 typedef iiterator< value_traits, IsConst
110 , std::forward_iterator_tag> types_t;
111 public:
112 typedef typename types_t::iterator_type::difference_type difference_type;
113 typedef typename types_t::iterator_type::value_type value_type;
114 typedef typename types_t::iterator_type::pointer pointer;
115 typedef typename types_t::iterator_type::reference reference;
116 typedef typename types_t::iterator_type::iterator_category iterator_category;
117
118 private:
119 typedef typename value_traits::node_traits node_traits;
120 typedef typename node_traits::node_ptr node_ptr;
121 typedef typename BucketValueTraits::bucket_type bucket_type;
122 typedef typename bucket_type::node_traits slist_node_traits;
123 typedef typename slist_node_traits::node_ptr slist_node_ptr;
124 typedef trivial_value_traits
125 <slist_node_traits, normal_link> slist_value_traits;
126 typedef slist_iterator<slist_value_traits, false> siterator;
127 typedef slist_iterator<slist_value_traits, true> const_siterator;
128 typedef circular_slist_algorithms<slist_node_traits> slist_node_algorithms;
129
130 typedef typename pointer_traits
131 <pointer>::template rebind_pointer
132 < const BucketValueTraits >::type const_bucketvaltraits_ptr;
133 class nat;
134 typedef typename
135 detail::if_c< IsConst
136 , hashtable_iterator<BucketValueTraits, LinearBuckets, false>
137 , nat>::type nonconst_iterator;
138
139 inline static node_ptr downcast_bucket(typename bucket_type::node_traits::node_ptr p)
140 {
141 return pointer_traits<node_ptr>::
142 pointer_to(static_cast<typename node_traits::node&>(*p));
143 }
144
145 public:
146
147 inline hashtable_iterator ()
148 : slist_it_() //Value initialization to achieve "null iterators" (N3644)
149 {}
150
151 inline explicit hashtable_iterator(siterator ptr, const BucketValueTraits *cont)
152 : slist_it_ (ptr)
153 , traitsptr_ (cont ? pointer_traits<const_bucketvaltraits_ptr>::pointer_to(*cont) : const_bucketvaltraits_ptr() )
154 {}
155
156 inline hashtable_iterator(const hashtable_iterator &other)
157 : slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits())
158 {}
159
160 inline hashtable_iterator(const nonconst_iterator &other)
161 : slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits())
162 {}
163
164 inline const siterator &slist_it() const
165 { return slist_it_; }
166
167 inline hashtable_iterator<BucketValueTraits, LinearBuckets, false> unconst() const
168 { return hashtable_iterator<BucketValueTraits, LinearBuckets, false>(this->slist_it(), this->get_bucket_value_traits()); }
169
170 inline hashtable_iterator& operator++()
171 { this->increment(); return *this; }
172
173 inline hashtable_iterator &operator=(const hashtable_iterator &other)
174 { slist_it_ = other.slist_it(); traitsptr_ = other.get_bucket_value_traits(); return *this; }
175
176 inline hashtable_iterator operator++(int)
177 {
178 hashtable_iterator result (*this);
179 this->increment();
180 return result;
181 }
182
183 inline friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2)
184 { return i.slist_it_ == i2.slist_it_; }
185
186 inline friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2)
187 { return !(i == i2); }
188
189 inline reference operator*() const
190 { return *this->operator ->(); }
191
192 inline pointer operator->() const
193 {
194 return this->priv_value_traits().to_value_ptr
195 (downcast_bucket(p: slist_it_.pointed_node()));
196 }
197
198 inline const_bucketvaltraits_ptr get_bucket_value_traits() const
199 { return traitsptr_; }
200
201 inline const value_traits &priv_value_traits() const
202 { return traitsptr_->priv_value_traits(); }
203
204 private:
205
206 void increment()
207 {
208 bucket_type* const buckets = boost::movelib::to_raw_pointer(traitsptr_->priv_bucket_traits().bucket_begin());
209 const std::size_t buckets_len = traitsptr_->priv_bucket_traits().bucket_count();
210
211 ++slist_it_;
212 const slist_node_ptr n = slist_it_.pointed_node();
213 const siterator first_bucket_bbegin(buckets->get_node_ptr());
214 if(first_bucket_bbegin.pointed_node() <= n && n <= buckets[buckets_len-1].get_node_ptr()){
215 //If one-past the node is inside the bucket then look for the next non-empty bucket
216 //1. get the bucket_impl from the iterator
217 const bucket_type &b = static_cast<const bucket_type&>(*n);
218
219 //2. Now just calculate the index b has in the bucket array
220 std::size_t n_bucket = static_cast<std::size_t>(&b - buckets);
221
222 //3. Iterate until a non-empty bucket is found
223 slist_node_ptr bucket_nodeptr = buckets->get_node_ptr();
224 do{
225 if (++n_bucket >= buckets_len){ //bucket overflow, return end() iterator
226 slist_it_ = first_bucket_bbegin;
227 return;
228 }
229 bucket_nodeptr = buckets[n_bucket].get_node_ptr();
230 }
231 while (slist_node_algorithms::is_empty(bucket_nodeptr));
232 slist_it_ = siterator(bucket_nodeptr);
233 ++slist_it_;
234 }
235 else{
236 //++slist_it_ yield to a valid object
237 }
238 }
239
240 siterator slist_it_;
241 const_bucketvaltraits_ptr traitsptr_;
242};
243
244template<class BucketValueTraits, bool IsConst>
245class hashtable_iterator<BucketValueTraits, true, IsConst>
246{
247 typedef typename BucketValueTraits::value_traits value_traits;
248 typedef typename BucketValueTraits::bucket_traits bucket_traits;
249
250 typedef iiterator< value_traits, IsConst
251 , std::forward_iterator_tag> types_t;
252 public:
253 typedef typename types_t::iterator_type::difference_type difference_type;
254 typedef typename types_t::iterator_type::value_type value_type;
255 typedef typename types_t::iterator_type::pointer pointer;
256 typedef typename types_t::iterator_type::reference reference;
257 typedef typename types_t::iterator_type::iterator_category iterator_category;
258
259 private:
260 typedef typename value_traits::node_traits node_traits;
261 typedef typename node_traits::node_ptr node_ptr;
262 typedef typename BucketValueTraits::bucket_type bucket_type;
263 typedef typename BucketValueTraits::bucket_ptr bucket_ptr;
264 typedef typename bucket_type::node_traits slist_node_traits;
265 typedef linear_slist_algorithms<slist_node_traits> slist_node_algorithms;
266 typedef typename slist_node_traits::node_ptr slist_node_ptr;
267 typedef trivial_value_traits
268 <slist_node_traits, normal_link> slist_value_traits;
269 typedef slist_iterator<slist_value_traits, false> siterator;
270 typedef slist_iterator<slist_value_traits, true> const_siterator;
271
272 static const bool stateful_value_traits =
273 detail::is_stateful_value_traits<value_traits>::value;
274
275 typedef typename pointer_traits
276 <pointer>::template rebind_pointer
277 < const value_traits >::type const_value_traits_ptr;
278 class nat;
279 typedef typename
280 detail::if_c< IsConst
281 , hashtable_iterator<BucketValueTraits, true, false>
282 , nat>::type nonconst_iterator;
283
284 inline static node_ptr downcast_bucket(slist_node_ptr p)
285 {
286 return pointer_traits<node_ptr>::
287 pointer_to(static_cast<typename node_traits::node&>(*p));
288 }
289
290 public:
291
292 inline hashtable_iterator ()
293 : slist_it_() //Value initialization to achieve "null iterators" (N3644)
294 , members_()
295 {}
296
297 inline explicit hashtable_iterator(siterator ptr, bucket_ptr bp, const_value_traits_ptr traits_ptr)
298 : slist_it_ (ptr)
299 , members_ (bp, traits_ptr)
300 {}
301
302 inline hashtable_iterator(const hashtable_iterator &other)
303 : slist_it_(other.slist_it()), members_(other.get_bucket_ptr(), other.get_value_traits())
304 {}
305
306 inline hashtable_iterator(const nonconst_iterator &other)
307 : slist_it_(other.slist_it()), members_(other.get_bucket_ptr(), other.get_value_traits())
308 {}
309
310 inline const siterator &slist_it() const
311 { return slist_it_; }
312
313 inline hashtable_iterator<BucketValueTraits, true, false> unconst() const
314 { return hashtable_iterator<BucketValueTraits, true, false>(this->slist_it(), members_.nodeptr_, members_.get_ptr()); }
315
316 inline hashtable_iterator& operator++()
317 { this->increment(); return *this; }
318
319 inline hashtable_iterator &operator=(const hashtable_iterator &other)
320 { slist_it_ = other.slist_it(); members_ = other.members_; return *this; }
321
322 inline hashtable_iterator operator++(int)
323 {
324 hashtable_iterator result (*this);
325 this->increment();
326 return result;
327 }
328
329 inline friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2)
330 { return i.slist_it_ == i2.slist_it_; }
331
332 inline friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2)
333 { return i.slist_it_ != i2.slist_it_; }
334
335 inline reference operator*() const
336 { return *this->operator ->(); }
337
338 inline pointer operator->() const
339 { return this->operator_arrow(detail::bool_<stateful_value_traits>()); }
340
341 inline const_value_traits_ptr get_value_traits() const
342 { return members_.get_ptr(); }
343
344 inline bucket_ptr get_bucket_ptr() const
345 { return members_.nodeptr_; }
346
347 private:
348
349 inline pointer operator_arrow(detail::false_) const
350 { return value_traits::to_value_ptr(downcast_bucket(p: slist_it_.pointed_node())); }
351
352 inline pointer operator_arrow(detail::true_) const
353 { return this->get_value_traits()->to_value_ptr(downcast_bucket(p: slist_it_.pointed_node())); }
354
355 void increment()
356 {
357 ++slist_it_;
358 if (slist_it_ == siterator()){
359 slist_node_ptr bucket_nodeptr;
360 do {
361 ++members_.nodeptr_;
362 bucket_nodeptr = members_.nodeptr_->get_node_ptr();
363 }while(slist_node_algorithms::is_empty(bucket_nodeptr));
364 slist_it_ = siterator(slist_node_traits::get_next(bucket_nodeptr));
365 }
366 }
367
368 siterator slist_it_;
369 iiterator_members<bucket_ptr, const_value_traits_ptr, stateful_value_traits> members_;
370};
371
372} //namespace intrusive {
373} //namespace boost {
374
375#endif
376

source code of boost/libs/intrusive/include/boost/intrusive/detail/hashtable_node.hpp