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