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