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
35namespace boost {
36namespace intrusive {
37namespace detail {
38
39template <class Slist>
40struct bucket_impl : public Slist
41{
42 typedef Slist slist_type;
43 BOOST_INTRUSIVE_FORCEINLINE bucket_impl()
44 {}
45
46 BOOST_INTRUSIVE_FORCEINLINE bucket_impl(const bucket_impl &)
47 {}
48
49 BOOST_INTRUSIVE_FORCEINLINE ~bucket_impl()
50 {
51 //This bucket is still being used!
52 BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty());
53 }
54
55 BOOST_INTRUSIVE_FORCEINLINE bucket_impl &operator=(const bucket_impl&)
56 {
57 //This bucket is still in use!
58 BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty());
59 return *this;
60 }
61};
62
63template<class Slist>
64struct 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
79 BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl(bucket_ptr buckets, size_type len)
80 : buckets_(buckets), buckets_len_(len)
81 {}
82
83 BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl(const bucket_traits_impl &x)
84 : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
85 {}
86
87 BOOST_INTRUSIVE_FORCEINLINE 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
91 BOOST_INTRUSIVE_FORCEINLINE 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
97 BOOST_INTRUSIVE_FORCEINLINE 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
102 BOOST_INTRUSIVE_FORCEINLINE const bucket_ptr &bucket_begin() const
103 { return buckets_; }
104
105 BOOST_INTRUSIVE_FORCEINLINE size_type bucket_count() const
106 { return buckets_len_; }
107
108 private:
109 bucket_ptr buckets_;
110 size_type buckets_len_;
111};
112
113template <class NodeTraits>
114struct 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
121template <class NodeTraits>
122struct apply_reduced_slist_node_traits
123{
124 typedef typename NodeTraits::reduced_slist_node_traits type;
125};
126
127template <class NodeTraits>
128struct 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
137template<class NodeTraits>
138struct 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
154template<class BucketValueTraits, bool IsConst>
155class 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_type::difference_type difference_type;
164 typedef typename types_t::iterator_type::value_type value_type;
165 typedef typename types_t::iterator_type::pointer pointer;
166 typedef typename types_t::iterator_type::reference reference;
167 typedef typename types_t::iterator_type::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
184 BOOST_INTRUSIVE_FORCEINLINE 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
192 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator ()
193 : slist_it_() //Value initialization to achieve "null iterators" (N3644)
194 {}
195
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
201 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator(const hashtable_iterator<BucketValueTraits, false> &other)
202 : slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits())
203 {}
204
205 BOOST_INTRUSIVE_FORCEINLINE const siterator &slist_it() const
206 { return slist_it_; }
207
208 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator<BucketValueTraits, false> unconst() const
209 { return hashtable_iterator<BucketValueTraits, false>(this->slist_it(), this->get_bucket_value_traits()); }
210
211 BOOST_INTRUSIVE_FORCEINLINE hashtable_iterator& operator++()
212 { this->increment(); return *this; }
213
214 hashtable_iterator operator++(int)
215 {
216 hashtable_iterator result (*this);
217 this->increment();
218 return result;
219 }
220
221 BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2)
222 { return i.slist_it_ == i2.slist_it_; }
223
224 BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2)
225 { return !(i == i2); }
226
227 BOOST_INTRUSIVE_FORCEINLINE reference operator*() const
228 { return *this->operator ->(); }
229
230 BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const
231 {
232 return this->priv_value_traits().to_value_ptr
233 (downcast_bucket(slist_it_.pointed_node()));
234 }
235
236 BOOST_INTRUSIVE_FORCEINLINE const const_bucketvaltraits_ptr &get_bucket_value_traits() const
237 { return traitsptr_; }
238
239 BOOST_INTRUSIVE_FORCEINLINE const value_traits &priv_value_traits() const
240 { return traitsptr_->priv_value_traits(); }
241
242 BOOST_INTRUSIVE_FORCEINLINE const bucket_traits &priv_bucket_traits() const
243 { return traitsptr_->priv_bucket_traits(); }
244
245 private:
246 void increment()
247 {
248 const bucket_traits &rbuck_traits = this->priv_bucket_traits();
249 bucket_type* const buckets = boost::movelib::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