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
20namespace 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> extractor;
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 extractor;
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 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

source code of boost/boost/unordered/detail/unique.hpp