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 | |
18 | namespace 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> ; |
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 | ; |
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 ; |
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 | |