1// Debugging hash_multimap implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2005, 2006
4// Free Software Foundation, Inc.
5//
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 2, or (at your option)
10// any later version.
11
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.
16
17// You should have received a copy of the GNU General Public License along
18// with this library; see the file COPYING.  If not, write to the Free
19// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20// USA.
21
22// As a special exception, you may use this file as part of a free software
23// library without restriction.  Specifically, if other files instantiate
24// templates or use macros or inline functions from this file, or you compile
25// this file and link it with other files to produce an executable, this
26// file does not by itself cause the resulting executable to be covered by
27// the GNU General Public License.  This exception does not however
28// invalidate any other reasons why the executable file might be covered by
29// the GNU General Public License.
30
31/** @file debug/hash_multimap.h
32 *  This file is a GNU debug extension to the Standard C++ Library.
33 */
34
35#ifndef _GLIBCXX_DEBUG_HASH_MULTIMAP_H
36#define _GLIBCXX_DEBUG_HASH_MULTIMAP_H 1
37
38#include <debug/safe_sequence.h>
39#include <debug/safe_iterator.h>
40
41namespace __gnu_cxx
42{
43namespace __debug
44{
45  template<typename _Value, typename _Tp,
46	   typename _HashFcn  = __gnu_cxx::hash<_Value>,
47	   typename _EqualKey = std::equal_to<_Value>,
48	   typename _Alloc =  std::allocator<_Value> >
49    class hash_multimap
50    : public _GLIBCXX_EXT::hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>,
51      public __gnu_debug::_Safe_sequence<hash_multimap<_Value, _Tp, _HashFcn,
52						       _EqualKey, _Alloc> >
53    {
54      typedef _GLIBCXX_EXT::hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>
55							_Base;
56      typedef __gnu_debug::_Safe_sequence<hash_multimap> _Safe_base;
57
58  public:
59      typedef typename _Base::key_type			key_type;
60      typedef typename _Base::data_type			data_type;
61      typedef typename _Base::mapped_type		mapped_type;
62      typedef typename _Base::value_type		value_type;
63      typedef typename _Base::hasher			hasher;
64      typedef typename _Base::key_equal			key_equal;
65      typedef typename _Base::size_type			size_type;
66      typedef typename _Base::difference_type		difference_type;
67      typedef typename _Base::pointer			pointer;
68      typedef typename _Base::const_pointer		const_pointer;
69      typedef typename _Base::reference			reference;
70      typedef typename _Base::const_reference		const_reference;
71
72      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
73					  hash_multimap> iterator;
74      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
75					  hash_multimap> const_iterator;
76
77      typedef typename _Base::allocator_type              allocator_type;
78
79      using _Base::hash_funct;
80      using _Base::key_eq;
81      using _Base::get_allocator;
82
83      hash_multimap() { }
84
85      explicit hash_multimap(size_type __n) : _Base(__n) { }
86
87      hash_multimap(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
88
89      hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
90		    const allocator_type& __a = allocator_type())
91      : _Base(__n, __hf, __eql, __a) { }
92
93      template<typename _InputIterator>
94        hash_multimap(_InputIterator __f, _InputIterator __l)
95	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
96
97      template<typename _InputIterator>
98        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
99        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
100
101      template<typename _InputIterator>
102        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
103		      const hasher& __hf)
104	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
105
106      template<typename _InputIterator>
107        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
108		      const hasher& __hf, const key_equal& __eql,
109		      const allocator_type& __a = allocator_type())
110	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
111		__eql, __a) { }
112
113      using _Base::size;
114      using _Base::max_size;
115      using _Base::empty;
116
117      void
118      swap(hash_multimap& __x)
119      {
120	_Base::swap(__x);
121	this->_M_swap(__x);
122      }
123
124      iterator
125      begin() { return iterator(_Base::begin(), this); }
126
127      iterator
128      end()   { return iterator(_Base::end(),   this); }
129
130      const_iterator
131      begin() const
132      { return const_iterator(_Base::begin(), this); }
133
134      const_iterator
135      end() const
136      { return const_iterator(_Base::end(),   this); }
137
138      iterator
139      insert(const value_type& __obj)
140      { return iterator(_Base::insert(__obj), this); }
141
142      template <typename _InputIterator>
143        void
144        insert(_InputIterator __first, _InputIterator __last)
145        {
146	  __glibcxx_check_valid_range(__first, __last);
147	  _Base::insert(__first.base(), __last.base());
148	}
149
150      iterator
151      insert_noresize(const value_type& __obj)
152      { return iterator(_Base::insert_noresize(__obj), this); }
153
154      iterator
155      find(const key_type& __key)
156      { return iterator(_Base::find(__key), this); }
157
158      const_iterator
159      find(const key_type& __key) const
160      { return const_iterator(_Base::find(__key), this); }
161
162      using _Base::count;
163
164      std::pair<iterator, iterator>
165      equal_range(const key_type& __key)
166      {
167	typedef typename _Base::iterator _Base_iterator;
168	std::pair<_Base_iterator, _Base_iterator> __res =
169	                                             _Base::equal_range(__key);
170	return std::make_pair(iterator(__res.first, this),
171			      iterator(__res.second, this));
172      }
173
174      std::pair<const_iterator, const_iterator>
175      equal_range(const key_type& __key) const
176      {
177	typedef typename _Base::const_iterator _Base_iterator;
178	std::pair<_Base_iterator, _Base_iterator> __res =
179        _Base::equal_range(__key);
180	return std::make_pair(const_iterator(__res.first, this),
181			      const_iterator(__res.second, this));
182      }
183
184      size_type
185      erase(const key_type& __key)
186      {
187	std::pair<iterator, iterator> __victims = this->equal_range(__key);
188	std::size_t __num_victims = 0;
189	while (__victims.first != __victims.second)
190	{
191	  this->erase(__victims.first++);
192	  ++__num_victims;
193	}
194	return __num_victims;
195      }
196
197      void
198      erase(iterator __it)
199      {
200	__glibcxx_check_erase(__it);
201	__it._M_invalidate();
202	_Base::erase(__it.base());
203      }
204
205      void
206      erase(iterator __first, iterator __last)
207      {
208	__glibcxx_check_erase_range(__first, __last);
209	for (iterator __tmp = __first; __tmp != __last;)
210	{
211	  iterator __victim = __tmp++;
212	  __victim._M_invalidate();
213	}
214	_Base::erase(__first.base(), __last.base());
215      }
216
217      void
218      clear()
219      {
220	_Base::clear();
221	this->_M_invalidate_all();
222      }
223
224      using _Base::resize;
225      using _Base::bucket_count;
226      using _Base::max_bucket_count;
227      using _Base::elems_in_bucket;
228
229      _Base&
230      _M_base()       { return *this; }
231
232      const _Base&
233      _M_base() const { return *this; }
234
235    private:
236      void
237      _M_invalidate_all()
238      {
239	typedef typename _Base::const_iterator _Base_const_iterator;
240	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
241	this->_M_invalidate_if(_Not_equal(_M_base().end()));
242      }
243    };
244
245  template<typename _Value, typename _Tp, typename _HashFcn,
246	   typename _EqualKey, typename _Alloc>
247    inline bool
248    operator==(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
249	       const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
250    { return __x._M_base() == __y._M_base(); }
251
252  template<typename _Value, typename _Tp, typename _HashFcn,
253	   typename _EqualKey, typename _Alloc>
254    inline bool
255    operator!=(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
256	       const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
257    { return __x._M_base() != __y._M_base(); }
258
259  template<typename _Value, typename _Tp, typename _HashFcn,
260	   typename _EqualKey, typename _Alloc>
261    inline void
262    swap(hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
263	 hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
264    { __x.swap(__y); }
265} // namespace __debug
266} // namespace __gnu_cxx
267
268#endif
269