1// Debugging hash_map implementation -*- C++ -*-
2
3// Copyright (C) 2003
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#ifndef _GLIBCXX_DEBUG_HASH_MAP_H
32#define _GLIBCXX_DEBUG_HASH_MAP_H 1
33
34#include <debug/safe_sequence.h>
35#include <debug/safe_iterator.h>
36
37namespace __gnu_debug_def
38{
39  template<typename _Value, typename _Tp,
40	   typename _HashFcn  = __gnu_cxx::hash<_Value>,
41	   typename _EqualKey = std::equal_to<_Value>,
42	   typename _Alloc = std::allocator<_Value> >
43    class hash_map
44    : public __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>,
45      public __gnu_debug::_Safe_sequence<hash_map<_Value, _Tp, _HashFcn,
46						 _EqualKey, _Alloc> >
47    {
48      typedef __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>
49      							_Base;
50      typedef __gnu_debug::_Safe_sequence<hash_map> 	_Safe_base;
51
52    public:
53      typedef typename _Base::key_type        key_type;
54      typedef typename _Base::data_type       data_type;
55      typedef typename _Base::mapped_type     mapped_type;
56      typedef typename _Base::value_type      value_type;
57      typedef typename _Base::hasher          hasher;
58      typedef typename _Base::key_equal       key_equal;
59      typedef typename _Base::size_type       size_type;
60      typedef typename _Base::difference_type difference_type;
61      typedef typename _Base::pointer         pointer;
62      typedef typename _Base::const_pointer   const_pointer;
63      typedef typename _Base::reference       reference;
64      typedef typename _Base::const_reference const_reference;
65
66      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, hash_map>
67					      iterator;
68      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
69					  hash_map>
70					      const_iterator;
71
72      typedef typename _Base::allocator_type  allocator_type;
73
74      using _Base::hash_funct;
75      using _Base::key_eq;
76      using _Base::get_allocator;
77
78      hash_map() { }
79
80      explicit hash_map(size_type __n) : _Base(__n) { }
81
82      hash_map(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
83
84      hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
85	       const allocator_type& __a = allocator_type())
86      : _Base(__n, __hf, __eql, __a) { }
87
88      template<typename _InputIterator>
89        hash_map(_InputIterator __f, _InputIterator __l)
90        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
91
92      template<typename _InputIterator>
93        hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
94	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
95
96      template<typename _InputIterator>
97        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
98		 const hasher& __hf)
99        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
100
101      template<typename _InputIterator>
102        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
103		 const hasher& __hf, const key_equal& __eql,
104		 const allocator_type& __a = allocator_type())
105	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
106		__eql, __a) { }
107
108      hash_map(const _Base& __x) : _Base(__x), _Safe_base() { }
109
110      using _Base::size;
111      using _Base::max_size;
112      using _Base::empty;
113
114      void
115      swap(hash_map& __x)
116      {
117	_Base::swap(__x);
118	this->_M_swap(__x);
119      }
120
121      iterator
122      begin() { return iterator(_Base::begin(), this); }
123
124      iterator
125      end() { return iterator(_Base::end(),   this); }
126
127      const_iterator
128      begin() const
129      { return const_iterator(_Base::begin(), this); }
130
131      const_iterator
132      end() const
133      { return const_iterator(_Base::end(),   this); }
134
135      std::pair<iterator, bool>
136      insert(const value_type& __obj)
137      {
138	std::pair<typename _Base::iterator, bool> __res = _Base::insert(__obj);
139	return std::make_pair(iterator(__res.first, this), __res.second);
140      }
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
151      std::pair<iterator, bool>
152      insert_noresize(const value_type& __obj)
153      {
154	std::pair<typename _Base::iterator, bool> __res =
155	                                        _Base::insert_noresize(__obj);
156	return std::make_pair(iterator(__res.first, this), __res.second);
157      }
158
159      iterator
160      find(const key_type& __key)
161      { return iterator(_Base::find(__key), this); }
162
163      const_iterator
164      find(const key_type& __key) const
165      { return const_iterator(_Base::find(__key), this); }
166
167      using _Base::operator[];
168      using _Base::count;
169
170      std::pair<iterator, iterator>
171      equal_range(const key_type& __key)
172      {
173	typedef typename _Base::iterator _Base_iterator;
174	std::pair<_Base_iterator, _Base_iterator> __res =
175	                  _Base::equal_range(__key);
176	return std::make_pair(iterator(__res.first, this),
177			      iterator(__res.second, this));
178      }
179
180      std::pair<const_iterator, const_iterator>
181      equal_range(const key_type& __key) const
182      {
183	typedef typename _Base::const_iterator _Base_iterator;
184	std::pair<_Base_iterator, _Base_iterator> __res =
185	_Base::equal_range(__key);
186	return std::make_pair(const_iterator(__res.first, this),
187			      const_iterator(__res.second, this));
188      }
189
190      size_type
191      erase(const key_type& __key)
192      {
193	iterator __victim(_Base::find(__key), this);
194	if (__victim != end())
195	  return this->erase(__victim), 1;
196	else
197	  return 0;
198      }
199
200      void
201      erase(iterator __it)
202      {
203	__glibcxx_check_erase(__it);
204	__it._M_invalidate();
205	_Base::erase(__it.base());
206      }
207
208      void
209      erase(iterator __first, iterator __last)
210      {
211	__glibcxx_check_erase_range(__first, __last);
212	for (iterator __tmp = __first; __tmp != __last;)
213	{
214	  iterator __victim = __tmp++;
215	  __victim._M_invalidate();
216	}
217	_Base::erase(__first.base(), __last.base());
218      }
219
220      void
221      clear()
222      {
223	_Base::clear();
224	this->_M_invalidate_all();
225      }
226
227      using _Base::resize;
228      using _Base::bucket_count;
229      using _Base::max_bucket_count;
230      using _Base::elems_in_bucket;
231
232      _Base&
233      _M_base()       { return *this; }
234
235      const _Base&
236      _M_base() const { return *this; }
237
238    private:
239      void
240      _M_invalidate_all()
241      {
242	typedef typename _Base::const_iterator _Base_const_iterator;
243	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
244	this->_M_invalidate_if(_Not_equal(_M_base().end()));
245      }
246    };
247
248  template<typename _Value, typename _Tp, typename _HashFcn,
249	   typename _EqualKey, typename _Alloc>
250    inline bool
251    operator==(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
252	       const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
253    { return __x._M_base() == __y._M_base(); }
254
255  template<typename _Value, typename _Tp, typename _HashFcn,
256	   typename _EqualKey, typename _Alloc>
257    inline bool
258    operator!=(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
259	       const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
260    { return __x._M_base() != __y._M_base(); }
261
262  template<typename _Value, typename _Tp, typename _HashFcn,
263	   typename _EqualKey, typename _Alloc>
264    inline void
265    swap(hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
266	 hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
267    { __x.swap(__y); }
268} // namespace __gnu_debug_def
269
270#endif
271