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