]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. | |
3 | // Copyright (C) 2005-2011 Daniel James | |
4 | // Distributed under the Boost Software License, Version 1.0. (See accompanying | |
5 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | #ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED | |
8 | #define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED | |
9 | ||
10 | #include <boost/config.hpp> | |
11 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
12 | #pragma once | |
13 | #endif | |
14 | ||
15 | #include <boost/unordered/detail/extract_key.hpp> | |
16 | #include <boost/throw_exception.hpp> | |
17 | #include <stdexcept> | |
18 | ||
19 | namespace boost { namespace unordered { namespace detail { | |
20 | ||
21 | template <typename A, typename T> struct unique_node; | |
22 | template <typename T> struct ptr_node; | |
23 | template <typename Types> struct table_impl; | |
24 | ||
25 | template <typename A, typename T> | |
26 | struct unique_node : | |
27 | boost::unordered::detail::value_base<T> | |
28 | { | |
29 | typedef typename ::boost::unordered::detail::rebind_wrap< | |
30 | A, unique_node<A, T> >::type allocator; | |
31 | typedef typename ::boost::unordered::detail:: | |
32 | allocator_traits<allocator>::pointer node_pointer; | |
33 | typedef node_pointer link_pointer; | |
34 | ||
35 | link_pointer next_; | |
36 | std::size_t hash_; | |
37 | ||
38 | unique_node() : | |
39 | next_(), | |
40 | hash_(0) | |
41 | {} | |
42 | ||
43 | void init(node_pointer) | |
44 | { | |
45 | } | |
46 | ||
47 | private: | |
48 | unique_node& operator=(unique_node const&); | |
49 | }; | |
50 | ||
51 | template <typename T> | |
52 | struct ptr_node : | |
53 | boost::unordered::detail::ptr_bucket | |
54 | { | |
55 | typedef T value_type; | |
56 | typedef boost::unordered::detail::ptr_bucket bucket_base; | |
57 | typedef ptr_node<T>* node_pointer; | |
58 | typedef ptr_bucket* link_pointer; | |
59 | ||
60 | std::size_t hash_; | |
61 | boost::unordered::detail::value_base<T> value_base_; | |
62 | ||
63 | ptr_node() : | |
64 | bucket_base(), | |
65 | hash_(0) | |
66 | {} | |
67 | ||
68 | void init(node_pointer) | |
69 | { | |
70 | } | |
71 | ||
72 | void* address() { return value_base_.address(); } | |
73 | value_type& value() { return value_base_.value(); } | |
74 | value_type* value_ptr() { return value_base_.value_ptr(); } | |
75 | ||
76 | private: | |
77 | ptr_node& operator=(ptr_node const&); | |
78 | }; | |
79 | ||
80 | // If the allocator uses raw pointers use ptr_node | |
81 | // Otherwise use node. | |
82 | ||
83 | template <typename A, typename T, typename NodePtr, typename BucketPtr> | |
84 | struct pick_node2 | |
85 | { | |
86 | typedef boost::unordered::detail::unique_node<A, T> node; | |
87 | ||
88 | typedef typename boost::unordered::detail::allocator_traits< | |
89 | typename boost::unordered::detail::rebind_wrap<A, node>::type | |
90 | >::pointer node_pointer; | |
91 | ||
92 | typedef boost::unordered::detail::bucket<node_pointer> bucket; | |
93 | typedef node_pointer link_pointer; | |
94 | }; | |
95 | ||
96 | template <typename A, typename T> | |
97 | struct pick_node2<A, T, | |
98 | boost::unordered::detail::ptr_node<T>*, | |
99 | boost::unordered::detail::ptr_bucket*> | |
100 | { | |
101 | typedef boost::unordered::detail::ptr_node<T> node; | |
102 | typedef boost::unordered::detail::ptr_bucket bucket; | |
103 | typedef bucket* link_pointer; | |
104 | }; | |
105 | ||
106 | template <typename A, typename T> | |
107 | struct pick_node | |
108 | { | |
109 | typedef typename boost::remove_const<T>::type nonconst; | |
110 | ||
111 | typedef boost::unordered::detail::allocator_traits< | |
112 | typename boost::unordered::detail::rebind_wrap<A, | |
113 | boost::unordered::detail::ptr_node<nonconst> >::type | |
114 | > tentative_node_traits; | |
115 | ||
116 | typedef boost::unordered::detail::allocator_traits< | |
117 | typename boost::unordered::detail::rebind_wrap<A, | |
118 | boost::unordered::detail::ptr_bucket >::type | |
119 | > tentative_bucket_traits; | |
120 | ||
121 | typedef pick_node2<A, nonconst, | |
122 | typename tentative_node_traits::pointer, | |
123 | typename tentative_bucket_traits::pointer> pick; | |
124 | ||
125 | typedef typename pick::node node; | |
126 | typedef typename pick::bucket bucket; | |
127 | typedef typename pick::link_pointer link_pointer; | |
128 | }; | |
129 | ||
130 | template <typename Types> | |
131 | struct table_impl : boost::unordered::detail::table<Types> | |
132 | { | |
133 | typedef boost::unordered::detail::table<Types> table; | |
134 | typedef typename table::value_type value_type; | |
135 | typedef typename table::bucket bucket; | |
136 | typedef typename table::policy policy; | |
137 | typedef typename table::node_pointer node_pointer; | |
138 | typedef typename table::node_allocator node_allocator; | |
139 | typedef typename table::node_allocator_traits node_allocator_traits; | |
140 | typedef typename table::bucket_pointer bucket_pointer; | |
141 | typedef typename table::link_pointer link_pointer; | |
142 | typedef typename table::hasher hasher; | |
143 | typedef typename table::key_equal key_equal; | |
144 | typedef typename table::key_type key_type; | |
145 | typedef typename table::node_constructor node_constructor; | |
146 | typedef typename table::node_tmp node_tmp; | |
147 | typedef typename table::extractor extractor; | |
148 | typedef typename table::iterator iterator; | |
149 | typedef typename table::c_iterator c_iterator; | |
150 | ||
151 | typedef std::pair<iterator, bool> emplace_return; | |
152 | ||
153 | // Constructors | |
154 | ||
155 | table_impl(std::size_t n, | |
156 | hasher const& hf, | |
157 | key_equal const& eq, | |
158 | node_allocator const& a) | |
159 | : table(n, hf, eq, a) | |
160 | {} | |
161 | ||
162 | table_impl(table_impl const& x) | |
163 | : table(x, node_allocator_traits:: | |
164 | select_on_container_copy_construction(x.node_alloc())) | |
165 | { | |
166 | this->init(x); | |
167 | } | |
168 | ||
169 | table_impl(table_impl const& x, | |
170 | node_allocator const& a) | |
171 | : table(x, a) | |
172 | { | |
173 | this->init(x); | |
174 | } | |
175 | ||
176 | table_impl(table_impl& x, | |
177 | boost::unordered::detail::move_tag m) | |
178 | : table(x, m) | |
179 | {} | |
180 | ||
181 | table_impl(table_impl& x, | |
182 | node_allocator const& a, | |
183 | boost::unordered::detail::move_tag m) | |
184 | : table(x, a, m) | |
185 | { | |
186 | this->move_init(x); | |
187 | } | |
188 | ||
189 | // Node functions. | |
190 | ||
191 | static inline node_pointer next_node(link_pointer n) { | |
192 | return static_cast<node_pointer>(n->next_); | |
193 | } | |
194 | ||
195 | // Accessors | |
196 | ||
197 | template <class Key, class Pred> | |
198 | node_pointer find_node_impl( | |
199 | std::size_t key_hash, | |
200 | Key const& k, | |
201 | Pred const& eq) const | |
202 | { | |
203 | std::size_t bucket_index = this->hash_to_bucket(key_hash); | |
204 | node_pointer n = this->begin(bucket_index); | |
205 | ||
206 | for (;;) | |
207 | { | |
208 | if (!n) return n; | |
209 | ||
210 | std::size_t node_hash = n->hash_; | |
211 | if (key_hash == node_hash) | |
212 | { | |
213 | if (eq(k, this->get_key(n->value()))) | |
214 | return n; | |
215 | } | |
216 | else | |
217 | { | |
218 | if (this->hash_to_bucket(node_hash) != bucket_index) | |
219 | return node_pointer(); | |
220 | } | |
221 | ||
222 | n = next_node(n); | |
223 | } | |
224 | } | |
225 | ||
226 | std::size_t count(key_type const& k) const | |
227 | { | |
228 | return this->find_node(k) ? 1 : 0; | |
229 | } | |
230 | ||
231 | value_type& at(key_type const& k) const | |
232 | { | |
233 | if (this->size_) { | |
234 | node_pointer n = this->find_node(k); | |
235 | if (n) return n->value(); | |
236 | } | |
237 | ||
238 | boost::throw_exception( | |
239 | std::out_of_range("Unable to find key in unordered_map.")); | |
240 | } | |
241 | ||
242 | std::pair<iterator, iterator> | |
243 | equal_range(key_type const& k) const | |
244 | { | |
245 | node_pointer n = this->find_node(k); | |
246 | return std::make_pair(iterator(n), iterator(n ? next_node(n) : n)); | |
247 | } | |
248 | ||
249 | // equals | |
250 | ||
251 | bool equals(table_impl const& other) const | |
252 | { | |
253 | if(this->size_ != other.size_) return false; | |
254 | ||
255 | for(node_pointer n1 = this->begin(); n1; n1 = next_node(n1)) | |
256 | { | |
257 | node_pointer n2 = other.find_node(other.get_key(n1->value())); | |
258 | ||
259 | if (!n2 || n1->value() != n2->value()) | |
260 | return false; | |
261 | } | |
262 | ||
263 | return true; | |
264 | } | |
265 | ||
266 | // Emplace/Insert | |
267 | ||
268 | inline node_pointer add_node( | |
269 | node_pointer n, | |
270 | std::size_t key_hash) | |
271 | { | |
272 | n->hash_ = key_hash; | |
273 | ||
274 | bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash)); | |
275 | ||
276 | if (!b->next_) | |
277 | { | |
278 | link_pointer start_node = this->get_previous_start(); | |
279 | ||
280 | if (start_node->next_) { | |
281 | this->get_bucket(this->hash_to_bucket( | |
282 | next_node(start_node)->hash_) | |
283 | )->next_ = n; | |
284 | } | |
285 | ||
286 | b->next_ = start_node; | |
287 | n->next_ = start_node->next_; | |
288 | start_node->next_ = n; | |
289 | } | |
290 | else | |
291 | { | |
292 | n->next_ = b->next_->next_; | |
293 | b->next_->next_ = n; | |
294 | } | |
295 | ||
296 | ++this->size_; | |
297 | return n; | |
298 | } | |
299 | ||
300 | inline node_pointer resize_and_add_node(node_pointer n, std::size_t key_hash) | |
301 | { | |
302 | node_tmp b(n, this->node_alloc()); | |
303 | this->reserve_for_insert(this->size_ + 1); | |
304 | return this->add_node(b.release(), key_hash); | |
305 | } | |
306 | ||
307 | value_type& operator[](key_type const& k) | |
308 | { | |
309 | std::size_t key_hash = this->hash(k); | |
310 | node_pointer pos = this->find_node(key_hash, k); | |
311 | if (pos) { | |
312 | return pos->value(); | |
313 | } | |
314 | else { | |
315 | return this->resize_and_add_node( | |
316 | boost::unordered::detail::func::construct_node_pair(this->node_alloc(), k), | |
317 | key_hash)->value(); | |
318 | } | |
319 | } | |
320 | ||
321 | #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) | |
322 | # if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
323 | emplace_return emplace(boost::unordered::detail::emplace_args1< | |
324 | boost::unordered::detail::please_ignore_this_overload> const&) | |
325 | { | |
326 | BOOST_ASSERT(false); | |
327 | return emplace_return(iterator(), false); | |
328 | } | |
329 | ||
330 | iterator emplace_hint(c_iterator, | |
331 | boost::unordered::detail::emplace_args1< | |
332 | boost::unordered::detail::please_ignore_this_overload> const&) | |
333 | { | |
334 | BOOST_ASSERT(false); | |
335 | return iterator(); | |
336 | } | |
337 | # else | |
338 | emplace_return emplace( | |
339 | boost::unordered::detail::please_ignore_this_overload const&) | |
340 | { | |
341 | BOOST_ASSERT(false); | |
342 | return emplace_return(iterator(), false); | |
343 | } | |
344 | ||
345 | iterator emplace_hint(c_iterator, | |
346 | boost::unordered::detail::please_ignore_this_overload const&) | |
347 | { | |
348 | BOOST_ASSERT(false); | |
349 | return iterator(); | |
350 | } | |
351 | # endif | |
352 | #endif | |
353 | ||
354 | template <BOOST_UNORDERED_EMPLACE_TEMPLATE> | |
355 | emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS) | |
356 | { | |
357 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
358 | return emplace_impl( | |
359 | extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD), | |
360 | BOOST_UNORDERED_EMPLACE_FORWARD); | |
361 | #else | |
362 | return emplace_impl( | |
363 | extractor::extract(args.a0, args.a1), | |
364 | BOOST_UNORDERED_EMPLACE_FORWARD); | |
365 | #endif | |
366 | } | |
367 | ||
368 | template <BOOST_UNORDERED_EMPLACE_TEMPLATE> | |
369 | iterator emplace_hint(c_iterator hint, | |
370 | BOOST_UNORDERED_EMPLACE_ARGS) | |
371 | { | |
372 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
373 | return emplace_hint_impl(hint, | |
374 | extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD), | |
375 | BOOST_UNORDERED_EMPLACE_FORWARD); | |
376 | #else | |
377 | return emplace_hint_impl(hint, | |
378 | extractor::extract(args.a0, args.a1), | |
379 | BOOST_UNORDERED_EMPLACE_FORWARD); | |
380 | #endif | |
381 | } | |
382 | ||
383 | #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
384 | template <typename A0> | |
385 | emplace_return emplace( | |
386 | boost::unordered::detail::emplace_args1<A0> const& args) | |
387 | { | |
388 | return emplace_impl(extractor::extract(args.a0), args); | |
389 | } | |
390 | ||
391 | template <typename A0> | |
392 | iterator emplace_hint(c_iterator hint, | |
393 | boost::unordered::detail::emplace_args1<A0> const& args) | |
394 | { | |
395 | return emplace_hint_impl(hint, extractor::extract(args.a0), args); | |
396 | } | |
397 | #endif | |
398 | ||
399 | template <BOOST_UNORDERED_EMPLACE_TEMPLATE> | |
400 | iterator emplace_hint_impl(c_iterator hint, key_type const& k, | |
401 | BOOST_UNORDERED_EMPLACE_ARGS) | |
402 | { | |
403 | if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) { | |
404 | return iterator(hint.node_); | |
405 | } | |
406 | else { | |
407 | return emplace_impl(k, BOOST_UNORDERED_EMPLACE_FORWARD).first; | |
408 | } | |
409 | } | |
410 | ||
411 | template <BOOST_UNORDERED_EMPLACE_TEMPLATE> | |
412 | emplace_return emplace_impl(key_type const& k, | |
413 | BOOST_UNORDERED_EMPLACE_ARGS) | |
414 | { | |
415 | std::size_t key_hash = this->hash(k); | |
416 | node_pointer pos = this->find_node(key_hash, k); | |
417 | if (pos) { | |
418 | return emplace_return(iterator(pos), false); | |
419 | } | |
420 | else { | |
421 | return emplace_return( | |
422 | iterator(this->resize_and_add_node( | |
423 | boost::unordered::detail::func::construct_node_from_args( | |
424 | this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), | |
425 | key_hash)), | |
426 | true); | |
427 | } | |
428 | } | |
429 | ||
430 | template <BOOST_UNORDERED_EMPLACE_TEMPLATE> | |
431 | iterator emplace_hint_impl(c_iterator hint, no_key, | |
432 | BOOST_UNORDERED_EMPLACE_ARGS) | |
433 | { | |
434 | node_tmp b( | |
435 | boost::unordered::detail::func::construct_node_from_args( | |
436 | this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), | |
437 | this->node_alloc()); | |
438 | key_type const& k = this->get_key(b.node_->value()); | |
439 | if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) { | |
440 | return iterator(hint.node_); | |
441 | } | |
442 | std::size_t key_hash = this->hash(k); | |
443 | node_pointer pos = this->find_node(key_hash, k); | |
444 | if (pos) { | |
445 | return iterator(pos); | |
446 | } | |
447 | else { | |
448 | return iterator(this->resize_and_add_node(b.release(), key_hash)); | |
449 | } | |
450 | } | |
451 | ||
452 | template <BOOST_UNORDERED_EMPLACE_TEMPLATE> | |
453 | emplace_return emplace_impl(no_key, BOOST_UNORDERED_EMPLACE_ARGS) | |
454 | { | |
455 | node_tmp b( | |
456 | boost::unordered::detail::func::construct_node_from_args( | |
457 | this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), | |
458 | this->node_alloc()); | |
459 | key_type const& k = this->get_key(b.node_->value()); | |
460 | std::size_t key_hash = this->hash(k); | |
461 | node_pointer pos = this->find_node(key_hash, k); | |
462 | if (pos) { | |
463 | return emplace_return(iterator(pos), false); | |
464 | } | |
465 | else { | |
466 | return emplace_return( | |
467 | iterator(this->resize_and_add_node(b.release(), key_hash)), | |
468 | true); | |
469 | } | |
470 | } | |
471 | ||
472 | //////////////////////////////////////////////////////////////////////// | |
473 | // Insert range methods | |
474 | // | |
475 | // if hash function throws, or inserting > 1 element, basic exception | |
476 | // safety strong otherwise | |
477 | ||
478 | template <class InputIt> | |
479 | void insert_range(InputIt i, InputIt j) | |
480 | { | |
481 | if(i != j) | |
482 | return insert_range_impl(extractor::extract(*i), i, j); | |
483 | } | |
484 | ||
485 | template <class InputIt> | |
486 | void insert_range_impl(key_type const& k, InputIt i, InputIt j) | |
487 | { | |
488 | insert_range_impl2(k, i, j); | |
489 | ||
490 | while(++i != j) { | |
491 | // Note: can't use get_key as '*i' might not be value_type - it | |
492 | // could be a pair with first_types as key_type without const or | |
493 | // a different second_type. | |
494 | // | |
495 | // TODO: Might be worth storing the value_type instead of the | |
496 | // key here. Could be more efficient if '*i' is expensive. Could | |
497 | // be less efficient if copying the full value_type is | |
498 | // expensive. | |
499 | insert_range_impl2(extractor::extract(*i), i, j); | |
500 | } | |
501 | } | |
502 | ||
503 | template <class InputIt> | |
504 | void insert_range_impl2(key_type const& k, InputIt i, InputIt j) | |
505 | { | |
506 | // No side effects in this initial code | |
507 | std::size_t key_hash = this->hash(k); | |
508 | node_pointer pos = this->find_node(key_hash, k); | |
509 | ||
510 | if (!pos) { | |
511 | node_tmp b( | |
512 | boost::unordered::detail::func::construct_node(this->node_alloc(), *i), | |
513 | this->node_alloc()); | |
514 | if(this->size_ + 1 > this->max_load_) | |
515 | this->reserve_for_insert(this->size_ + | |
516 | boost::unordered::detail::insert_size(i, j)); | |
517 | this->add_node(b.release(), key_hash); | |
518 | } | |
519 | } | |
520 | ||
521 | template <class InputIt> | |
522 | void insert_range_impl(no_key, InputIt i, InputIt j) | |
523 | { | |
524 | node_constructor a(this->node_alloc()); | |
525 | ||
526 | do { | |
527 | if (!a.node_) { a.create_node(); } | |
528 | boost::unordered::detail::func::call_construct( | |
529 | a.alloc_, a.node_->value_ptr(), *i); | |
530 | node_tmp b(a.release(), a.alloc_); | |
531 | ||
532 | key_type const& k = this->get_key(b.node_->value()); | |
533 | std::size_t key_hash = this->hash(k); | |
534 | node_pointer pos = this->find_node(key_hash, k); | |
535 | ||
536 | if (pos) { | |
537 | a.reclaim(b.release()); | |
538 | } | |
539 | else { | |
540 | // reserve has basic exception safety if the hash function | |
541 | // throws, strong otherwise. | |
542 | this->reserve_for_insert(this->size_ + 1); | |
543 | this->add_node(b.release(), key_hash); | |
544 | } | |
545 | } while(++i != j); | |
546 | } | |
547 | ||
548 | //////////////////////////////////////////////////////////////////////// | |
549 | // Erase | |
550 | // | |
551 | // no throw | |
552 | ||
553 | std::size_t erase_key(key_type const& k) | |
554 | { | |
555 | if(!this->size_) return 0; | |
556 | ||
557 | std::size_t key_hash = this->hash(k); | |
558 | std::size_t bucket_index = this->hash_to_bucket(key_hash); | |
559 | link_pointer prev = this->get_previous_start(bucket_index); | |
560 | if (!prev) return 0; | |
561 | ||
562 | for (;;) | |
563 | { | |
564 | if (!prev->next_) return 0; | |
565 | std::size_t node_hash = next_node(prev)->hash_; | |
566 | if (this->hash_to_bucket(node_hash) != bucket_index) | |
567 | return 0; | |
568 | if (node_hash == key_hash && | |
569 | this->key_eq()(k, this->get_key( | |
570 | next_node(prev)->value()))) | |
571 | break; | |
572 | prev = prev->next_; | |
573 | } | |
574 | ||
575 | link_pointer end = next_node(prev)->next_; | |
576 | ||
577 | std::size_t deleted_count = this->delete_nodes(prev, end); | |
578 | this->fix_bucket(bucket_index, prev); | |
579 | return deleted_count; | |
580 | } | |
581 | ||
582 | iterator erase(c_iterator r) | |
583 | { | |
584 | BOOST_ASSERT(r.node_); | |
585 | node_pointer next = next_node(r.node_); | |
586 | erase_nodes(r.node_, next); | |
587 | return iterator(next); | |
588 | } | |
589 | ||
590 | iterator erase_range(c_iterator r1, c_iterator r2) | |
591 | { | |
592 | if (r1 == r2) return iterator(r2.node_); | |
593 | erase_nodes(r1.node_, r2.node_); | |
594 | return iterator(r2.node_); | |
595 | } | |
596 | ||
597 | void erase_nodes(node_pointer i, node_pointer j) | |
598 | { | |
599 | std::size_t bucket_index = this->hash_to_bucket(i->hash_); | |
600 | ||
601 | // Find the node before i. | |
602 | link_pointer prev = this->get_previous_start(bucket_index); | |
603 | while(prev->next_ != i) prev = prev->next_; | |
604 | ||
605 | // Delete the nodes. | |
606 | do { | |
607 | this->delete_node(prev); | |
608 | bucket_index = this->fix_bucket(bucket_index, prev); | |
609 | } while (prev->next_ != j); | |
610 | } | |
611 | ||
612 | //////////////////////////////////////////////////////////////////////// | |
613 | // fill_buckets | |
614 | ||
615 | void copy_buckets(table const& src) { | |
616 | this->create_buckets(this->bucket_count_); | |
617 | ||
618 | for(node_pointer n = src.begin(); n; n = next_node(n)) { | |
619 | this->add_node( | |
620 | boost::unordered::detail::func::construct_node( | |
621 | this->node_alloc(), n->value()), n->hash_); | |
622 | } | |
623 | } | |
624 | ||
625 | void move_buckets(table const& src) { | |
626 | this->create_buckets(this->bucket_count_); | |
627 | ||
628 | for(node_pointer n = src.begin(); n; n = next_node(n)) { | |
629 | this->add_node( | |
630 | boost::unordered::detail::func::construct_node( | |
631 | this->node_alloc(), boost::move(n->value())), n->hash_); | |
632 | } | |
633 | } | |
634 | ||
635 | void assign_buckets(table const& src) | |
636 | { | |
637 | node_holder<node_allocator> holder(*this); | |
638 | for(node_pointer n = src.begin(); n; n = next_node(n)) { | |
639 | this->add_node(holder.copy_of(n->value()), n->hash_); | |
640 | } | |
641 | } | |
642 | ||
643 | void move_assign_buckets(table& src) | |
644 | { | |
645 | node_holder<node_allocator> holder(*this); | |
646 | for(node_pointer n = src.begin(); n; n = next_node(n)) { | |
647 | this->add_node(holder.move_copy_of(n->value()), n->hash_); | |
648 | } | |
649 | } | |
650 | ||
651 | // strong otherwise exception safety | |
652 | void rehash_impl(std::size_t num_buckets) | |
653 | { | |
654 | BOOST_ASSERT(this->buckets_); | |
655 | ||
656 | this->create_buckets(num_buckets); | |
657 | link_pointer prev = this->get_previous_start(); | |
658 | while (prev->next_) | |
659 | prev = place_in_bucket(*this, prev); | |
660 | } | |
661 | ||
662 | // Iterate through the nodes placing them in the correct buckets. | |
663 | // pre: prev->next_ is not null. | |
664 | static link_pointer place_in_bucket(table& dst, link_pointer prev) | |
665 | { | |
666 | node_pointer n = next_node(prev); | |
667 | bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(n->hash_)); | |
668 | ||
669 | if (!b->next_) { | |
670 | b->next_ = prev; | |
671 | return n; | |
672 | } | |
673 | else { | |
674 | prev->next_ = n->next_; | |
675 | n->next_ = b->next_->next_; | |
676 | b->next_->next_ = n; | |
677 | return prev; | |
678 | } | |
679 | } | |
680 | }; | |
681 | }}} | |
682 | ||
683 | #endif |