1132720Skan// Debugging hash_multimap implementation -*- C++ -*-
2132720Skan
3169691Skan// Copyright (C) 2003, 2005, 2006
4132720Skan// Free Software Foundation, Inc.
5132720Skan//
6132720Skan// This file is part of the GNU ISO C++ Library.  This library is free
7132720Skan// software; you can redistribute it and/or modify it under the
8132720Skan// terms of the GNU General Public License as published by the
9132720Skan// Free Software Foundation; either version 2, or (at your option)
10132720Skan// any later version.
11132720Skan
12132720Skan// This library is distributed in the hope that it will be useful,
13132720Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of
14132720Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15132720Skan// GNU General Public License for more details.
16132720Skan
17132720Skan// You should have received a copy of the GNU General Public License along
18132720Skan// with this library; see the file COPYING.  If not, write to the Free
19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20132720Skan// USA.
21132720Skan
22132720Skan// As a special exception, you may use this file as part of a free software
23132720Skan// library without restriction.  Specifically, if other files instantiate
24132720Skan// templates or use macros or inline functions from this file, or you compile
25132720Skan// this file and link it with other files to produce an executable, this
26132720Skan// file does not by itself cause the resulting executable to be covered by
27132720Skan// the GNU General Public License.  This exception does not however
28132720Skan// invalidate any other reasons why the executable file might be covered by
29132720Skan// the GNU General Public License.
30132720Skan
31169691Skan/** @file debug/hash_multimap.h
32169691Skan *  This file is a GNU debug extension to the Standard C++ Library.
33169691Skan */
34169691Skan
35132720Skan#ifndef _GLIBCXX_DEBUG_HASH_MULTIMAP_H
36132720Skan#define _GLIBCXX_DEBUG_HASH_MULTIMAP_H 1
37132720Skan
38132720Skan#include <debug/safe_sequence.h>
39132720Skan#include <debug/safe_iterator.h>
40132720Skan
41169691Skannamespace __gnu_cxx
42132720Skan{
43169691Skannamespace __debug
44169691Skan{
45132720Skan  template<typename _Value, typename _Tp,
46132720Skan	   typename _HashFcn  = __gnu_cxx::hash<_Value>,
47132720Skan	   typename _EqualKey = std::equal_to<_Value>,
48132720Skan	   typename _Alloc =  std::allocator<_Value> >
49132720Skan    class hash_multimap
50169691Skan    : public _GLIBCXX_EXT::hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>,
51132720Skan      public __gnu_debug::_Safe_sequence<hash_multimap<_Value, _Tp, _HashFcn,
52132720Skan						       _EqualKey, _Alloc> >
53132720Skan    {
54169691Skan      typedef _GLIBCXX_EXT::hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>
55132720Skan							_Base;
56132720Skan      typedef __gnu_debug::_Safe_sequence<hash_multimap> _Safe_base;
57132720Skan
58132720Skan  public:
59132720Skan      typedef typename _Base::key_type			key_type;
60132720Skan      typedef typename _Base::data_type			data_type;
61132720Skan      typedef typename _Base::mapped_type		mapped_type;
62132720Skan      typedef typename _Base::value_type		value_type;
63132720Skan      typedef typename _Base::hasher			hasher;
64132720Skan      typedef typename _Base::key_equal			key_equal;
65132720Skan      typedef typename _Base::size_type			size_type;
66132720Skan      typedef typename _Base::difference_type		difference_type;
67132720Skan      typedef typename _Base::pointer			pointer;
68132720Skan      typedef typename _Base::const_pointer		const_pointer;
69132720Skan      typedef typename _Base::reference			reference;
70132720Skan      typedef typename _Base::const_reference		const_reference;
71132720Skan
72132720Skan      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
73132720Skan					  hash_multimap> iterator;
74132720Skan      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
75132720Skan					  hash_multimap> const_iterator;
76132720Skan
77132720Skan      typedef typename _Base::allocator_type              allocator_type;
78132720Skan
79132720Skan      using _Base::hash_funct;
80132720Skan      using _Base::key_eq;
81132720Skan      using _Base::get_allocator;
82132720Skan
83132720Skan      hash_multimap() { }
84132720Skan
85132720Skan      explicit hash_multimap(size_type __n) : _Base(__n) { }
86132720Skan
87132720Skan      hash_multimap(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
88132720Skan
89132720Skan      hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
90132720Skan		    const allocator_type& __a = allocator_type())
91132720Skan      : _Base(__n, __hf, __eql, __a) { }
92132720Skan
93132720Skan      template<typename _InputIterator>
94132720Skan        hash_multimap(_InputIterator __f, _InputIterator __l)
95132720Skan	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
96132720Skan
97132720Skan      template<typename _InputIterator>
98132720Skan        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
99132720Skan        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
100132720Skan
101132720Skan      template<typename _InputIterator>
102132720Skan        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
103132720Skan		      const hasher& __hf)
104132720Skan	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
105132720Skan
106132720Skan      template<typename _InputIterator>
107132720Skan        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
108132720Skan		      const hasher& __hf, const key_equal& __eql,
109132720Skan		      const allocator_type& __a = allocator_type())
110132720Skan	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
111132720Skan		__eql, __a) { }
112132720Skan
113132720Skan      using _Base::size;
114132720Skan      using _Base::max_size;
115132720Skan      using _Base::empty;
116132720Skan
117132720Skan      void
118132720Skan      swap(hash_multimap& __x)
119132720Skan      {
120132720Skan	_Base::swap(__x);
121132720Skan	this->_M_swap(__x);
122132720Skan      }
123132720Skan
124132720Skan      iterator
125132720Skan      begin() { return iterator(_Base::begin(), this); }
126132720Skan
127132720Skan      iterator
128132720Skan      end()   { return iterator(_Base::end(),   this); }
129132720Skan
130132720Skan      const_iterator
131132720Skan      begin() const
132132720Skan      { return const_iterator(_Base::begin(), this); }
133132720Skan
134132720Skan      const_iterator
135132720Skan      end() const
136132720Skan      { return const_iterator(_Base::end(),   this); }
137132720Skan
138132720Skan      iterator
139132720Skan      insert(const value_type& __obj)
140132720Skan      { return iterator(_Base::insert(__obj), this); }
141132720Skan
142132720Skan      template <typename _InputIterator>
143132720Skan        void
144132720Skan        insert(_InputIterator __first, _InputIterator __last)
145132720Skan        {
146132720Skan	  __glibcxx_check_valid_range(__first, __last);
147132720Skan	  _Base::insert(__first.base(), __last.base());
148132720Skan	}
149132720Skan
150132720Skan      iterator
151132720Skan      insert_noresize(const value_type& __obj)
152132720Skan      { return iterator(_Base::insert_noresize(__obj), this); }
153132720Skan
154132720Skan      iterator
155132720Skan      find(const key_type& __key)
156132720Skan      { return iterator(_Base::find(__key), this); }
157132720Skan
158132720Skan      const_iterator
159132720Skan      find(const key_type& __key) const
160132720Skan      { return const_iterator(_Base::find(__key), this); }
161132720Skan
162132720Skan      using _Base::count;
163132720Skan
164132720Skan      std::pair<iterator, iterator>
165132720Skan      equal_range(const key_type& __key)
166132720Skan      {
167132720Skan	typedef typename _Base::iterator _Base_iterator;
168132720Skan	std::pair<_Base_iterator, _Base_iterator> __res =
169132720Skan	                                             _Base::equal_range(__key);
170132720Skan	return std::make_pair(iterator(__res.first, this),
171132720Skan			      iterator(__res.second, this));
172132720Skan      }
173132720Skan
174132720Skan      std::pair<const_iterator, const_iterator>
175132720Skan      equal_range(const key_type& __key) const
176132720Skan      {
177132720Skan	typedef typename _Base::const_iterator _Base_iterator;
178132720Skan	std::pair<_Base_iterator, _Base_iterator> __res =
179132720Skan        _Base::equal_range(__key);
180132720Skan	return std::make_pair(const_iterator(__res.first, this),
181132720Skan			      const_iterator(__res.second, this));
182132720Skan      }
183132720Skan
184132720Skan      size_type
185132720Skan      erase(const key_type& __key)
186132720Skan      {
187132720Skan	std::pair<iterator, iterator> __victims = this->equal_range(__key);
188169691Skan	std::size_t __num_victims = 0;
189132720Skan	while (__victims.first != __victims.second)
190132720Skan	{
191132720Skan	  this->erase(__victims.first++);
192132720Skan	  ++__num_victims;
193132720Skan	}
194132720Skan	return __num_victims;
195132720Skan      }
196132720Skan
197132720Skan      void
198132720Skan      erase(iterator __it)
199132720Skan      {
200132720Skan	__glibcxx_check_erase(__it);
201132720Skan	__it._M_invalidate();
202132720Skan	_Base::erase(__it.base());
203132720Skan      }
204132720Skan
205132720Skan      void
206132720Skan      erase(iterator __first, iterator __last)
207132720Skan      {
208132720Skan	__glibcxx_check_erase_range(__first, __last);
209132720Skan	for (iterator __tmp = __first; __tmp != __last;)
210132720Skan	{
211132720Skan	  iterator __victim = __tmp++;
212132720Skan	  __victim._M_invalidate();
213132720Skan	}
214132720Skan	_Base::erase(__first.base(), __last.base());
215132720Skan      }
216132720Skan
217132720Skan      void
218132720Skan      clear()
219132720Skan      {
220132720Skan	_Base::clear();
221132720Skan	this->_M_invalidate_all();
222132720Skan      }
223132720Skan
224132720Skan      using _Base::resize;
225132720Skan      using _Base::bucket_count;
226132720Skan      using _Base::max_bucket_count;
227132720Skan      using _Base::elems_in_bucket;
228132720Skan
229132720Skan      _Base&
230132720Skan      _M_base()       { return *this; }
231132720Skan
232132720Skan      const _Base&
233132720Skan      _M_base() const { return *this; }
234132720Skan
235132720Skan    private:
236132720Skan      void
237132720Skan      _M_invalidate_all()
238132720Skan      {
239132720Skan	typedef typename _Base::const_iterator _Base_const_iterator;
240132720Skan	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
241132720Skan	this->_M_invalidate_if(_Not_equal(_M_base().end()));
242132720Skan      }
243132720Skan    };
244132720Skan
245132720Skan  template<typename _Value, typename _Tp, typename _HashFcn,
246132720Skan	   typename _EqualKey, typename _Alloc>
247132720Skan    inline bool
248132720Skan    operator==(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
249132720Skan	       const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
250132720Skan    { return __x._M_base() == __y._M_base(); }
251132720Skan
252132720Skan  template<typename _Value, typename _Tp, typename _HashFcn,
253132720Skan	   typename _EqualKey, typename _Alloc>
254132720Skan    inline bool
255132720Skan    operator!=(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
256132720Skan	       const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
257132720Skan    { return __x._M_base() != __y._M_base(); }
258132720Skan
259132720Skan  template<typename _Value, typename _Tp, typename _HashFcn,
260132720Skan	   typename _EqualKey, typename _Alloc>
261132720Skan    inline void
262132720Skan    swap(hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
263132720Skan	 hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
264132720Skan    { __x.swap(__y); }
265169691Skan} // namespace __debug
266169691Skan} // namespace __gnu_cxx
267132720Skan
268132720Skan#endif
269