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