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

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