1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
26 /** @file debug/unordered_set
27 * This file is a GNU debug extension to the Standard C++ Library.
30 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
31 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
34 # include <bits/c++0x_warning.h>
36 # include <unordered_set>
38 #include <debug/safe_unordered_container.h>
39 #include <debug/safe_iterator.h>
40 #include <debug/safe_local_iterator.h>
42 namespace std _GLIBCXX_VISIBILITY(default)
46 /// Class std::unordered_set with safety/checking/debug instrumentation.
47 template<typename _Value,
48 typename _Hash = std::hash<_Value>,
49 typename _Pred = std::equal_to<_Value>,
50 typename _Alloc = std::allocator<_Value> >
52 : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>,
53 public __gnu_debug::_Safe_unordered_container<unordered_set<_Value, _Hash,
56 typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash,
58 typedef __gnu_debug::_Safe_unordered_container<unordered_set> _Safe_base;
59 typedef typename _Base::const_iterator _Base_const_iterator;
60 typedef typename _Base::iterator _Base_iterator;
61 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
62 typedef typename _Base::local_iterator _Base_local_iterator;
65 typedef typename _Base::size_type size_type;
66 typedef typename _Base::hasher hasher;
67 typedef typename _Base::key_equal key_equal;
68 typedef typename _Base::allocator_type allocator_type;
70 typedef typename _Base::key_type key_type;
71 typedef typename _Base::value_type value_type;
73 typedef __gnu_debug::_Safe_iterator<_Base_iterator,
74 unordered_set> iterator;
75 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
76 unordered_set> const_iterator;
77 typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
78 unordered_set> local_iterator;
79 typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
80 unordered_set> const_local_iterator;
83 unordered_set(size_type __n = 10,
84 const hasher& __hf = hasher(),
85 const key_equal& __eql = key_equal(),
86 const allocator_type& __a = allocator_type())
87 : _Base(__n, __hf, __eql, __a) { }
89 template<typename _InputIterator>
90 unordered_set(_InputIterator __first, _InputIterator __last,
92 const hasher& __hf = hasher(),
93 const key_equal& __eql = key_equal(),
94 const allocator_type& __a = allocator_type())
95 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
97 __gnu_debug::__base(__last), __n,
100 unordered_set(const unordered_set& __x)
103 unordered_set(const _Base& __x)
106 unordered_set(unordered_set&& __x)
107 : _Base(std::move(__x)) { }
109 unordered_set(initializer_list<value_type> __l,
111 const hasher& __hf = hasher(),
112 const key_equal& __eql = key_equal(),
113 const allocator_type& __a = allocator_type())
114 : _Base(__l, __n, __hf, __eql, __a) { }
116 ~unordered_set() noexcept { }
119 operator=(const unordered_set& __x)
121 *static_cast<_Base*>(this) = __x;
122 this->_M_invalidate_all();
127 operator=(unordered_set&& __x)
137 operator=(initializer_list<value_type> __l)
145 swap(unordered_set& __x)
148 _Safe_base::_M_swap(__x);
155 this->_M_invalidate_all();
160 { return iterator(_Base::begin(), this); }
163 begin() const noexcept
164 { return const_iterator(_Base::begin(), this); }
168 { return iterator(_Base::end(), this); }
172 { return const_iterator(_Base::end(), this); }
175 cbegin() const noexcept
176 { return const_iterator(_Base::begin(), this); }
179 cend() const noexcept
180 { return const_iterator(_Base::end(), this); }
185 { return local_iterator(_Base::begin(__b), __b, this); }
189 { return local_iterator(_Base::end(__b), __b, this); }
192 begin(size_type __b) const
193 { return const_local_iterator(_Base::begin(__b), __b, this); }
196 end(size_type __b) const
197 { return const_local_iterator(_Base::end(__b), __b, this); }
200 cbegin(size_type __b) const
201 { return const_local_iterator(_Base::cbegin(__b), __b, this); }
204 cend(size_type __b) const
205 { return const_local_iterator(_Base::cend(__b), __b, this); }
207 std::pair<iterator, bool>
208 insert(const value_type& __obj)
210 size_type __bucket_count = this->bucket_count();
211 typedef std::pair<_Base_iterator, bool> __pair_type;
212 __pair_type __res = _Base::insert(__obj);
213 _M_check_rehashed(__bucket_count);
214 return std::make_pair(iterator(__res.first, this), __res.second);
218 insert(const_iterator __hint, const value_type& __obj)
220 __glibcxx_check_insert(__hint);
221 size_type __bucket_count = this->bucket_count();
222 _Base_iterator __it = _Base::insert(__hint.base(), __obj);
223 _M_check_rehashed(__bucket_count);
224 return iterator(__it, this);
227 std::pair<iterator, bool>
228 insert(value_type&& __obj)
230 size_type __bucket_count = this->bucket_count();
231 typedef std::pair<typename _Base::iterator, bool> __pair_type;
232 __pair_type __res = _Base::insert(std::move(__obj));
233 _M_check_rehashed(__bucket_count);
234 return std::make_pair(iterator(__res.first, this), __res.second);
238 insert(const_iterator __hint, value_type&& __obj)
240 __glibcxx_check_insert(__hint);
241 size_type __bucket_count = this->bucket_count();
242 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
243 _M_check_rehashed(__bucket_count);
244 return iterator(__it, this);
248 insert(std::initializer_list<value_type> __l)
250 size_type __bucket_count = this->bucket_count();
252 _M_check_rehashed(__bucket_count);
255 template<typename _InputIterator>
257 insert(_InputIterator __first, _InputIterator __last)
259 __glibcxx_check_valid_range(__first, __last);
260 size_type __bucket_count = this->bucket_count();
261 _Base::insert(__gnu_debug::__base(__first),
262 __gnu_debug::__base(__last));
263 _M_check_rehashed(__bucket_count);
267 find(const key_type& __key)
268 { return iterator(_Base::find(__key), this); }
271 find(const key_type& __key) const
272 { return const_iterator(_Base::find(__key), this); }
274 std::pair<iterator, iterator>
275 equal_range(const key_type& __key)
277 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
278 __pair_type __res = _Base::equal_range(__key);
279 return std::make_pair(iterator(__res.first, this),
280 iterator(__res.second, this));
283 std::pair<const_iterator, const_iterator>
284 equal_range(const key_type& __key) const
286 std::pair<_Base_const_iterator, _Base_const_iterator>
287 __res = _Base::equal_range(__key);
288 return std::make_pair(const_iterator(__res.first, this),
289 const_iterator(__res.second, this));
293 erase(const key_type& __key)
296 _Base_iterator __victim(_Base::find(__key));
297 if (__victim != _Base::end())
299 this->_M_invalidate_if(
300 [__victim](_Base_const_iterator __it)
301 { return __it == __victim; });
302 _Base_local_iterator __local_victim = _S_to_local(__victim);
303 this->_M_invalidate_local_if(
304 [__local_victim](_Base_const_local_iterator __it)
305 { return __it == __local_victim; });
306 size_type __bucket_count = this->bucket_count();
307 _Base::erase(__victim);
308 _M_check_rehashed(__bucket_count);
315 erase(const_iterator __it)
317 __glibcxx_check_erase(__it);
318 _Base_const_iterator __victim = __it.base();
319 this->_M_invalidate_if(
320 [__victim](_Base_const_iterator __it)
321 { return __it == __victim; });
322 _Base_const_local_iterator __local_victim = _S_to_local(__victim);
323 this->_M_invalidate_local_if(
324 [__local_victim](_Base_const_local_iterator __it)
325 { return __it == __local_victim; });
326 size_type __bucket_count = this->bucket_count();
327 _Base_iterator __next = _Base::erase(__it.base());
328 _M_check_rehashed(__bucket_count);
329 return iterator(__next, this);
334 { return erase(const_iterator(__it)); }
337 erase(const_iterator __first, const_iterator __last)
339 __glibcxx_check_erase_range(__first, __last);
340 for (_Base_const_iterator __tmp = __first.base();
341 __tmp != __last.base(); ++__tmp)
343 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
344 _M_message(__gnu_debug::__msg_valid_range)
345 ._M_iterator(__first, "first")
346 ._M_iterator(__last, "last"));
347 this->_M_invalidate_if(
348 [__tmp](_Base_const_iterator __it)
349 { return __it == __tmp; });
350 _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
351 this->_M_invalidate_local_if(
352 [__local_tmp](_Base_const_local_iterator __it)
353 { return __it == __local_tmp; });
355 size_type __bucket_count = this->bucket_count();
356 _Base_iterator __next = _Base::erase(__first.base(),
358 _M_check_rehashed(__bucket_count);
359 return iterator(__next, this);
363 _M_base() noexcept { return *this; }
366 _M_base() const noexcept { return *this; }
370 _M_invalidate_locals()
372 _Base_local_iterator __local_end = _Base::end(0);
373 this->_M_invalidate_local_if(
374 [__local_end](_Base_const_local_iterator __it)
375 { return __it != __local_end; });
381 _Base_iterator __end = _Base::end();
382 this->_M_invalidate_if(
383 [__end](_Base_const_iterator __it)
384 { return __it != __end; });
385 _M_invalidate_locals();
389 _M_check_rehashed(size_type __prev_count)
391 if (__prev_count != this->bucket_count())
392 _M_invalidate_locals();
395 static _Base_local_iterator
396 _S_to_local(_Base_iterator __it)
397 { return _Base_local_iterator(__it._M_cur); }
399 static _Base_const_local_iterator
400 _S_to_local(_Base_const_iterator __it)
401 { return _Base_const_local_iterator(__it._M_cur); }
404 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
406 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
407 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
410 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
412 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
413 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
414 { return __x._M_equal(__y); }
416 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
418 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
419 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
420 { return !(__x == __y); }
423 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
424 template<typename _Value,
425 typename _Hash = std::hash<_Value>,
426 typename _Pred = std::equal_to<_Value>,
427 typename _Alloc = std::allocator<_Value> >
428 class unordered_multiset
429 : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
430 public __gnu_debug::_Safe_unordered_container<
431 unordered_multiset<_Value, _Hash, _Pred, _Alloc> >
433 typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
434 _Pred, _Alloc> _Base;
435 typedef __gnu_debug::_Safe_unordered_container<unordered_multiset>
437 typedef typename _Base::const_iterator _Base_const_iterator;
438 typedef typename _Base::iterator _Base_iterator;
439 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
440 typedef typename _Base::local_iterator _Base_local_iterator;
443 typedef typename _Base::size_type size_type;
444 typedef typename _Base::hasher hasher;
445 typedef typename _Base::key_equal key_equal;
446 typedef typename _Base::allocator_type allocator_type;
448 typedef typename _Base::key_type key_type;
449 typedef typename _Base::value_type value_type;
451 typedef __gnu_debug::_Safe_iterator<_Base_iterator,
452 unordered_multiset> iterator;
453 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
454 unordered_multiset> const_iterator;
455 typedef __gnu_debug::_Safe_local_iterator<
456 _Base_local_iterator, unordered_multiset> local_iterator;
457 typedef __gnu_debug::_Safe_local_iterator<
458 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
461 unordered_multiset(size_type __n = 10,
462 const hasher& __hf = hasher(),
463 const key_equal& __eql = key_equal(),
464 const allocator_type& __a = allocator_type())
465 : _Base(__n, __hf, __eql, __a) { }
467 template<typename _InputIterator>
468 unordered_multiset(_InputIterator __first, _InputIterator __last,
470 const hasher& __hf = hasher(),
471 const key_equal& __eql = key_equal(),
472 const allocator_type& __a = allocator_type())
473 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
475 __gnu_debug::__base(__last), __n,
476 __hf, __eql, __a) { }
478 unordered_multiset(const unordered_multiset& __x)
481 unordered_multiset(const _Base& __x)
484 unordered_multiset(unordered_multiset&& __x)
485 : _Base(std::move(__x)) { }
487 unordered_multiset(initializer_list<value_type> __l,
489 const hasher& __hf = hasher(),
490 const key_equal& __eql = key_equal(),
491 const allocator_type& __a = allocator_type())
492 : _Base(__l, __n, __hf, __eql, __a) { }
494 ~unordered_multiset() noexcept { }
497 operator=(const unordered_multiset& __x)
499 *static_cast<_Base*>(this) = __x;
500 this->_M_invalidate_all();
505 operator=(unordered_multiset&& __x)
515 operator=(initializer_list<value_type> __l)
523 swap(unordered_multiset& __x)
526 _Safe_base::_M_swap(__x);
533 this->_M_invalidate_all();
538 { return iterator(_Base::begin(), this); }
541 begin() const noexcept
542 { return const_iterator(_Base::begin(), this); }
546 { return iterator(_Base::end(), this); }
550 { return const_iterator(_Base::end(), this); }
553 cbegin() const noexcept
554 { return const_iterator(_Base::begin(), this); }
557 cend() const noexcept
558 { return const_iterator(_Base::end(), this); }
563 { return local_iterator(_Base::begin(__b), __b, this); }
567 { return local_iterator(_Base::end(__b), __b, this); }
570 begin(size_type __b) const
571 { return const_local_iterator(_Base::begin(__b), __b, this); }
574 end(size_type __b) const
575 { return const_local_iterator(_Base::end(__b), __b, this); }
578 cbegin(size_type __b) const
579 { return const_local_iterator(_Base::cbegin(__b), __b, this); }
582 cend(size_type __b) const
583 { return const_local_iterator(_Base::cend(__b), __b, this); }
586 insert(const value_type& __obj)
588 size_type __bucket_count = this->bucket_count();
589 _Base_iterator __it = _Base::insert(__obj);
590 _M_check_rehashed(__bucket_count);
591 return iterator(__it, this);
595 insert(const_iterator __hint, const value_type& __obj)
597 __glibcxx_check_insert(__hint);
598 size_type __bucket_count = this->bucket_count();
599 _Base_iterator __it = _Base::insert(__hint.base(), __obj);
600 _M_check_rehashed(__bucket_count);
601 return iterator(__it, this);
605 insert(value_type&& __obj)
607 size_type __bucket_count = this->bucket_count();
608 _Base_iterator __it = _Base::insert(std::move(__obj));
609 _M_check_rehashed(__bucket_count);
610 return iterator(__it, this);
614 insert(const_iterator __hint, value_type&& __obj)
616 __glibcxx_check_insert(__hint);
617 size_type __bucket_count = this->bucket_count();
618 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
619 _M_check_rehashed(__bucket_count);
620 return iterator(__it, this);
624 insert(std::initializer_list<value_type> __l)
626 size_type __bucket_count = this->bucket_count();
628 _M_check_rehashed(__bucket_count);
631 template<typename _InputIterator>
633 insert(_InputIterator __first, _InputIterator __last)
635 __glibcxx_check_valid_range(__first, __last);
636 size_type __bucket_count = this->bucket_count();
637 _Base::insert(__gnu_debug::__base(__first),
638 __gnu_debug::__base(__last));
639 _M_check_rehashed(__bucket_count);
643 find(const key_type& __key)
644 { return iterator(_Base::find(__key), this); }
647 find(const key_type& __key) const
648 { return const_iterator(_Base::find(__key), this); }
650 std::pair<iterator, iterator>
651 equal_range(const key_type& __key)
653 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
654 __pair_type __res = _Base::equal_range(__key);
655 return std::make_pair(iterator(__res.first, this),
656 iterator(__res.second, this));
659 std::pair<const_iterator, const_iterator>
660 equal_range(const key_type& __key) const
662 std::pair<_Base_const_iterator, _Base_const_iterator>
663 __res = _Base::equal_range(__key);
664 return std::make_pair(const_iterator(__res.first, this),
665 const_iterator(__res.second, this));
669 erase(const key_type& __key)
672 std::pair<_Base_iterator, _Base_iterator> __pair =
673 _Base::equal_range(__key);
674 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
676 this->_M_invalidate_if([__victim](_Base_const_iterator __it)
677 { return __it == __victim; });
678 _Base_local_iterator __local_victim = _S_to_local(__victim);
679 this->_M_invalidate_local_if(
680 [__local_victim](_Base_const_local_iterator __it)
681 { return __it == __local_victim; });
682 _Base::erase(__victim++);
689 erase(const_iterator __it)
691 __glibcxx_check_erase(__it);
692 _Base_const_iterator __victim = __it.base();
693 this->_M_invalidate_if([__victim](_Base_const_iterator __it)
694 { return __it == __victim; });
695 _Base_const_local_iterator __local_victim = _S_to_local(__victim);
696 this->_M_invalidate_local_if(
697 [__local_victim](_Base_const_local_iterator __it)
698 { return __it == __local_victim; });
699 return iterator(_Base::erase(__it.base()), this);
704 { return erase(const_iterator(__it)); }
707 erase(const_iterator __first, const_iterator __last)
709 __glibcxx_check_erase_range(__first, __last);
710 for (_Base_const_iterator __tmp = __first.base();
711 __tmp != __last.base(); ++__tmp)
713 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
714 _M_message(__gnu_debug::__msg_valid_range)
715 ._M_iterator(__first, "first")
716 ._M_iterator(__last, "last"));
717 this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
718 { return __it == __tmp; });
719 _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
720 this->_M_invalidate_local_if(
721 [__local_tmp](_Base_const_local_iterator __it)
722 { return __it == __local_tmp; });
724 return iterator(_Base::erase(__first.base(),
725 __last.base()), this);
729 _M_base() noexcept { return *this; }
732 _M_base() const noexcept { return *this; }
736 _M_invalidate_locals()
738 _Base_local_iterator __local_end = _Base::end(0);
739 this->_M_invalidate_local_if(
740 [__local_end](_Base_const_local_iterator __it)
741 { return __it != __local_end; });
747 _Base_iterator __end = _Base::end();
748 this->_M_invalidate_if([__end](_Base_const_iterator __it)
749 { return __it != __end; });
750 _M_invalidate_locals();
754 _M_check_rehashed(size_type __prev_count)
756 if (__prev_count != this->bucket_count())
757 _M_invalidate_locals();
760 static _Base_local_iterator
761 _S_to_local(_Base_iterator __it)
762 { return _Base_local_iterator(__it._M_cur); }
764 static _Base_const_local_iterator
765 _S_to_local(_Base_const_iterator __it)
766 { return _Base_const_local_iterator(__it._M_cur); }
769 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
771 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
772 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
775 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
777 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
778 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
779 { return __x._M_equal(__y); }
781 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
783 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
784 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
785 { return !(__x == __y); }
787 } // namespace __debug
790 #endif // __GXX_EXPERIMENTAL_CXX0X__