1// Debugging hash_map 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_map.h
32 *  This file is a GNU debug extension to the Standard C++ Library.
33 */
34
35#ifndef _GLIBCXX_DEBUG_HASH_MAP_H
36#define _GLIBCXX_DEBUG_HASH_MAP_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_map
50    : public _GLIBCXX_EXT::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>,
51      public __gnu_debug::_Safe_sequence<hash_map<_Value, _Tp, _HashFcn,
52						 _EqualKey, _Alloc> >
53    {
54      typedef _GLIBCXX_EXT::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>
55      							_Base;
56      typedef __gnu_debug::_Safe_sequence<hash_map> 	_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, hash_map>
73					      iterator;
74      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
75					  hash_map>
76					      const_iterator;
77
78      typedef typename _Base::allocator_type  allocator_type;
79
80      using _Base::hash_funct;
81      using _Base::key_eq;
82      using _Base::get_allocator;
83
84      hash_map() { }
85
86      explicit hash_map(size_type __n) : _Base(__n) { }
87
88      hash_map(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
89
90      hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
91	       const allocator_type& __a = allocator_type())
92      : _Base(__n, __hf, __eql, __a) { }
93
94      template<typename _InputIterator>
95        hash_map(_InputIterator __f, _InputIterator __l)
96        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
97
98      template<typename _InputIterator>
99        hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
100	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
101
102      template<typename _InputIterator>
103        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
104		 const hasher& __hf)
105        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
106
107      template<typename _InputIterator>
108        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
109		 const hasher& __hf, const key_equal& __eql,
110		 const allocator_type& __a = allocator_type())
111	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
112		__eql, __a) { }
113
114      hash_map(const _Base& __x) : _Base(__x), _Safe_base() { }
115
116      using _Base::size;
117      using _Base::max_size;
118      using _Base::empty;
119
120      void
121      swap(hash_map& __x)
122      {
123	_Base::swap(__x);
124	this->_M_swap(__x);
125      }
126
127      iterator
128      begin() { return iterator(_Base::begin(), this); }
129
130      iterator
131      end() { return iterator(_Base::end(),   this); }
132
133      const_iterator
134      begin() const
135      { return const_iterator(_Base::begin(), this); }
136
137      const_iterator
138      end() const
139      { return const_iterator(_Base::end(),   this); }
140
141      std::pair<iterator, bool>
142      insert(const value_type& __obj)
143      {
144	std::pair<typename _Base::iterator, bool> __res = _Base::insert(__obj);
145	return std::make_pair(iterator(__res.first, this), __res.second);
146      }
147
148      void
149      insert(const value_type* __first, const value_type* __last)
150      {
151	__glibcxx_check_valid_range(__first, __last);
152	_Base::insert(__first, __last);
153      }
154
155     template<typename _InputIterator>
156        void
157        insert(_InputIterator __first, _InputIterator __last)
158        {
159	  __glibcxx_check_valid_range(__first, __last);
160	  _Base::insert(__first.base(), __last.base());
161	}
162
163
164      std::pair<iterator, bool>
165      insert_noresize(const value_type& __obj)
166      {
167	std::pair<typename _Base::iterator, bool> __res =
168	                                        _Base::insert_noresize(__obj);
169	return std::make_pair(iterator(__res.first, this), __res.second);
170      }
171
172      iterator
173      find(const key_type& __key)
174      { return iterator(_Base::find(__key), this); }
175
176      const_iterator
177      find(const key_type& __key) const
178      { return const_iterator(_Base::find(__key), this); }
179
180      using _Base::operator[];
181      using _Base::count;
182
183      std::pair<iterator, iterator>
184      equal_range(const key_type& __key)
185      {
186	typedef typename _Base::iterator _Base_iterator;
187	std::pair<_Base_iterator, _Base_iterator> __res =
188	                  _Base::equal_range(__key);
189	return std::make_pair(iterator(__res.first, this),
190			      iterator(__res.second, this));
191      }
192
193      std::pair<const_iterator, const_iterator>
194      equal_range(const key_type& __key) const
195      {
196	typedef typename _Base::const_iterator _Base_iterator;
197	std::pair<_Base_iterator, _Base_iterator> __res =
198	_Base::equal_range(__key);
199	return std::make_pair(const_iterator(__res.first, this),
200			      const_iterator(__res.second, this));
201      }
202
203      size_type
204      erase(const key_type& __key)
205      {
206	iterator __victim(_Base::find(__key), this);
207	if (__victim != end())
208	  return this->erase(__victim), 1;
209	else
210	  return 0;
211      }
212
213      void
214      erase(iterator __it)
215      {
216	__glibcxx_check_erase(__it);
217	__it._M_invalidate();
218	_Base::erase(__it.base());
219      }
220
221      void
222      erase(iterator __first, iterator __last)
223      {
224	__glibcxx_check_erase_range(__first, __last);
225	for (iterator __tmp = __first; __tmp != __last;)
226	{
227	  iterator __victim = __tmp++;
228	  __victim._M_invalidate();
229	}
230	_Base::erase(__first.base(), __last.base());
231      }
232
233      void
234      clear()
235      {
236	_Base::clear();
237	this->_M_invalidate_all();
238      }
239
240      using _Base::resize;
241      using _Base::bucket_count;
242      using _Base::max_bucket_count;
243      using _Base::elems_in_bucket;
244
245      _Base&
246      _M_base()       { return *this; }
247
248      const _Base&
249      _M_base() const { return *this; }
250
251    private:
252      void
253      _M_invalidate_all()
254      {
255	typedef typename _Base::const_iterator _Base_const_iterator;
256	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
257	this->_M_invalidate_if(_Not_equal(_M_base().end()));
258      }
259    };
260
261  template<typename _Value, typename _Tp, typename _HashFcn,
262	   typename _EqualKey, typename _Alloc>
263    inline bool
264    operator==(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
265	       const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
266    { return __x._M_base() == __y._M_base(); }
267
268  template<typename _Value, typename _Tp, typename _HashFcn,
269	   typename _EqualKey, typename _Alloc>
270    inline bool
271    operator!=(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
272	       const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
273    { return __x._M_base() != __y._M_base(); }
274
275  template<typename _Value, typename _Tp, typename _HashFcn,
276	   typename _EqualKey, typename _Alloc>
277    inline void
278    swap(hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
279	 hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
280    { __x.swap(__y); }
281} // namespace __debug
282} // namespace __gnu_cxx
283
284#endif
285