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