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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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 
37 namespace __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