// Debugging unordered_map/unordered_multimap implementation -*- C++ -*-// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010// Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library. This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation; either version 3, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the// GNU General Public License for more details.// Under Section 7 of GPL version 3, you are granted additional// permissions described in the GCC Runtime Library Exception, version// 3.1, as published by the Free Software Foundation.// You should have received a copy of the GNU General Public License and// a copy of the GCC Runtime Library Exception along with this program;// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see// <http://www.gnu.org/licenses/>./** @file debug/unordered_map* This file is a GNU debug extension to the Standard C++ Library.*/#ifndef _GLIBCXX_DEBUG_UNORDERED_MAP#define _GLIBCXX_DEBUG_UNORDERED_MAP 1#ifndef __GXX_EXPERIMENTAL_CXX0X__# include <bits/c++0x_warning.h>#else# include <unordered_map>#include <debug/safe_sequence.h>#include <debug/safe_iterator.h>namespace std _GLIBCXX_VISIBILITY(default){namespace __debug{/// Class std::unordered_map with safety/checking/debug instrumentation.template<typename _Key, typename _Tp,typename _Hash = std::hash<_Key>,typename _Pred = std::equal_to<_Key>,typename _Alloc = std::allocator<_Key> >class unordered_map: public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,_Pred, _Alloc> >{typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,_Pred, _Alloc> _Base;typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base;typedef typename _Base::const_iterator _Base_const_iterator;typedef typename _Base::iterator _Base_iterator;typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;public:typedef typename _Base::size_type size_type;typedef typename _Base::hasher hasher;typedef typename _Base::key_equal key_equal;typedef typename _Base::allocator_type allocator_type;typedef typename _Base::key_type key_type;typedef typename _Base::value_type value_type;typedef __gnu_debug::_Safe_iterator<_Base_iterator,unordered_map> iterator;typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,unordered_map> const_iterator;explicitunordered_map(size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__n, __hf, __eql, __a) { }template<typename _InputIterator>unordered_map(_InputIterator __first, _InputIterator __last,size_type __n = 0,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,__last)),__gnu_debug::__base(__last), __n,__hf, __eql, __a), _Safe_base() { }unordered_map(const unordered_map& __x): _Base(__x), _Safe_base() { }unordered_map(const _Base& __x): _Base(__x), _Safe_base() { }unordered_map(unordered_map&& __x): _Base(std::move(__x)), _Safe_base() { }unordered_map(initializer_list<value_type> __l,size_type __n = 0,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }unordered_map&operator=(const unordered_map& __x){*static_cast<_Base*>(this) = __x;this->_M_invalidate_all();return *this;}unordered_map&operator=(unordered_map&& __x){// NB: DR 1204.// NB: DR 675.clear();swap(__x);return *this;}unordered_map&operator=(initializer_list<value_type> __l){this->clear();this->insert(__l);return *this;}voidswap(unordered_map& __x){_Base::swap(__x);_Safe_base::_M_swap(__x);}voidclear(){_Base::clear();this->_M_invalidate_all();}iteratorbegin(){ return iterator(_Base::begin(), this); }const_iteratorbegin() const{ return const_iterator(_Base::begin(), this); }iteratorend(){ return iterator(_Base::end(), this); }const_iteratorend() const{ return const_iterator(_Base::end(), this); }const_iteratorcbegin() const{ return const_iterator(_Base::begin(), this); }const_iteratorcend() const{ return const_iterator(_Base::end(), this); }// local versionsusing _Base::begin;using _Base::end;using _Base::cbegin;using _Base::cend;std::pair<iterator, bool>insert(const value_type& __obj){std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);return std::make_pair(iterator(__res.first, this), __res.second);}iteratorinsert(const_iterator __hint, const value_type& __obj){__glibcxx_check_insert(__hint);return iterator(_Base::insert(__hint.base(), __obj), this);}template<typename _Pair, typename = typenamestd::enable_if<std::is_convertible<_Pair,value_type>::value>::type>std::pair<iterator, bool>insert(_Pair&& __obj){std::pair<_Base_iterator, bool> __res =_Base::insert(std::forward<_Pair>(__obj));return std::make_pair(iterator(__res.first, this), __res.second);}template<typename _Pair, typename = typenamestd::enable_if<std::is_convertible<_Pair,value_type>::value>::type>iteratorinsert(const_iterator __hint, _Pair&& __obj){__glibcxx_check_insert(__hint);return iterator(_Base::insert(__hint.base(),std::forward<_Pair>(__obj)),this);}voidinsert(std::initializer_list<value_type> __l){ _Base::insert(__l); }template<typename _InputIterator>voidinsert(_InputIterator __first, _InputIterator __last){__glibcxx_check_valid_range(__first, __last);_Base::insert(__gnu_debug::__base(__first),__gnu_debug::__base(__last));}iteratorfind(const key_type& __key){ return iterator(_Base::find(__key), this); }const_iteratorfind(const key_type& __key) const{ return const_iterator(_Base::find(__key), this); }std::pair<iterator, iterator>equal_range(const key_type& __key){std::pair<_Base_iterator, _Base_iterator> __res =_Base::equal_range(__key);return std::make_pair(iterator(__res.first, this),iterator(__res.second, this));}std::pair<const_iterator, const_iterator>equal_range(const key_type& __key) const{std::pair<_Base_const_iterator, _Base_const_iterator> __res =_Base::equal_range(__key);return std::make_pair(const_iterator(__res.first, this),const_iterator(__res.second, this));}size_typeerase(const key_type& __key){size_type __ret(0);_Base_iterator __victim(_Base::find(__key));if (__victim != _Base::end()){this->_M_invalidate_if(_Equal(__victim));_Base::erase(__victim);__ret = 1;}return __ret;}iteratorerase(const_iterator __it){__glibcxx_check_erase(__it);this->_M_invalidate_if(_Equal(__it.base()));return iterator(_Base::erase(__it.base()), this);}iteratorerase(iterator __it){ return erase(const_iterator(__it)); }iteratorerase(const_iterator __first, const_iterator __last){__glibcxx_check_erase_range(__first, __last);for (_Base_const_iterator __tmp = __first.base();__tmp != __last.base(); ++__tmp){_GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),_M_message(__gnu_debug::__msg_valid_range)._M_iterator(__first, "first")._M_iterator(__last, "last"));this->_M_invalidate_if(_Equal(__tmp));}return iterator(_Base::erase(__first.base(),__last.base()), this);}_Base&_M_base() { return *this; }const _Base&_M_base() const { return *this; }private:void_M_invalidate_all(){typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;this->_M_invalidate_if(_Not_equal(_Base::end()));}};template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline voidswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ __x.swap(__y); }template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline booloperator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ return __x._M_equal(__y); }template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline booloperator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ return !(__x == __y); }/// Class std::unordered_multimap with safety/checking/debug instrumentation.template<typename _Key, typename _Tp,typename _Hash = std::hash<_Key>,typename _Pred = std::equal_to<_Key>,typename _Alloc = std::allocator<_Key> >class unordered_multimap: public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,_Pred, _Alloc>,public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,_Pred, _Alloc> >{typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,_Pred, _Alloc> _Base;typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;typedef typename _Base::const_iterator _Base_const_iterator;typedef typename _Base::iterator _Base_iterator;typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;public:typedef typename _Base::size_type size_type;typedef typename _Base::hasher hasher;typedef typename _Base::key_equal key_equal;typedef typename _Base::allocator_type allocator_type;typedef typename _Base::key_type key_type;typedef typename _Base::value_type value_type;typedef __gnu_debug::_Safe_iterator<_Base_iterator,unordered_multimap> iterator;typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,unordered_multimap> const_iterator;explicitunordered_multimap(size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__n, __hf, __eql, __a) { }template<typename _InputIterator>unordered_multimap(_InputIterator __first, _InputIterator __last,size_type __n = 0,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,__last)),__gnu_debug::__base(__last), __n,__hf, __eql, __a), _Safe_base() { }unordered_multimap(const unordered_multimap& __x): _Base(__x), _Safe_base() { }unordered_multimap(const _Base& __x): _Base(__x), _Safe_base() { }unordered_multimap(unordered_multimap&& __x): _Base(std::move(__x)), _Safe_base() { }unordered_multimap(initializer_list<value_type> __l,size_type __n = 0,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }unordered_multimap&operator=(const unordered_multimap& __x){*static_cast<_Base*>(this) = __x;this->_M_invalidate_all();return *this;}unordered_multimap&operator=(unordered_multimap&& __x){// NB: DR 1204.// NB: DR 675.clear();swap(__x);return *this;}unordered_multimap&operator=(initializer_list<value_type> __l){this->clear();this->insert(__l);return *this;}voidswap(unordered_multimap& __x){_Base::swap(__x);_Safe_base::_M_swap(__x);}voidclear(){_Base::clear();this->_M_invalidate_all();}iteratorbegin(){ return iterator(_Base::begin(), this); }const_iteratorbegin() const{ return const_iterator(_Base::begin(), this); }iteratorend(){ return iterator(_Base::end(), this); }const_iteratorend() const{ return const_iterator(_Base::end(), this); }const_iteratorcbegin() const{ return const_iterator(_Base::begin(), this); }const_iteratorcend() const{ return const_iterator(_Base::end(), this); }// local versionsusing _Base::begin;using _Base::end;using _Base::cbegin;using _Base::cend;iteratorinsert(const value_type& __obj){ return iterator(_Base::insert(__obj), this); }iteratorinsert(const_iterator __hint, const value_type& __obj){__glibcxx_check_insert(__hint);return iterator(_Base::insert(__hint.base(), __obj), this);}template<typename _Pair, typename = typenamestd::enable_if<std::is_convertible<_Pair,value_type>::value>::type>iteratorinsert(_Pair&& __obj){ return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }template<typename _Pair, typename = typenamestd::enable_if<std::is_convertible<_Pair,value_type>::value>::type>iteratorinsert(const_iterator __hint, _Pair&& __obj){__glibcxx_check_insert(__hint);return iterator(_Base::insert(__hint.base(),std::forward<_Pair>(__obj)),this);}voidinsert(std::initializer_list<value_type> __l){ _Base::insert(__l); }template<typename _InputIterator>voidinsert(_InputIterator __first, _InputIterator __last){__glibcxx_check_valid_range(__first, __last);_Base::insert(__gnu_debug::__base(__first),__gnu_debug::__base(__last));}iteratorfind(const key_type& __key){ return iterator(_Base::find(__key), this); }const_iteratorfind(const key_type& __key) const{ return const_iterator(_Base::find(__key), this); }std::pair<iterator, iterator>equal_range(const key_type& __key){std::pair<_Base_iterator, _Base_iterator> __res =_Base::equal_range(__key);return std::make_pair(iterator(__res.first, this),iterator(__res.second, this));}std::pair<const_iterator, const_iterator>equal_range(const key_type& __key) const{std::pair<_Base_const_iterator, _Base_const_iterator> __res =_Base::equal_range(__key);return std::make_pair(const_iterator(__res.first, this),const_iterator(__res.second, this));}size_typeerase(const key_type& __key){size_type __ret(0);std::pair<_Base_iterator, _Base_iterator> __pair =_Base::equal_range(__key);for (_Base_iterator __victim = __pair.first; __victim != __pair.second;){this->_M_invalidate_if(_Equal(__victim));_Base::erase(__victim++);++__ret;}return __ret;}iteratorerase(const_iterator __it){__glibcxx_check_erase(__it);this->_M_invalidate_if(_Equal(__it.base()));return iterator(_Base::erase(__it.base()), this);}iteratorerase(iterator __it){ return erase(const_iterator(__it)); }iteratorerase(const_iterator __first, const_iterator __last){__glibcxx_check_erase_range(__first, __last);for (_Base_const_iterator __tmp = __first.base();__tmp != __last.base(); ++__tmp){_GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),_M_message(__gnu_debug::__msg_valid_range)._M_iterator(__first, "first")._M_iterator(__last, "last"));this->_M_invalidate_if(_Equal(__tmp));}return iterator(_Base::erase(__first.base(),__last.base()), this);}_Base&_M_base() { return *this; }const _Base&_M_base() const { return *this; }private:void_M_invalidate_all(){typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;this->_M_invalidate_if(_Not_equal(_Base::end()));}};template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline voidswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ __x.swap(__y); }template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline booloperator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ return __x._M_equal(__y); }template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline booloperator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ return !(__x == __y); }} // namespace __debug} // namespace std#endif // __GXX_EXPERIMENTAL_CXX0X__#endif