1 // Debugging map implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004, 2005
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/map.h
32  *  This file is a GNU debug extension to the Standard C++ Library.
33  */
34 
35 #ifndef _GLIBCXX_DEBUG_MAP_H
36 #define _GLIBCXX_DEBUG_MAP_H 1
37 
38 #include <debug/safe_sequence.h>
39 #include <debug/safe_iterator.h>
40 #include <utility>
41 
42 namespace std
43 {
44 namespace __debug
45 {
46   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
47 	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
48     class map
49     : public _GLIBCXX_STD::map<_Key, _Tp, _Compare, _Allocator>,
50       public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> >
51     {
52       typedef _GLIBCXX_STD::map<_Key, _Tp, _Compare, _Allocator> _Base;
53       typedef __gnu_debug::_Safe_sequence<map> _Safe_base;
54 
55     public:
56       // types:
57       typedef _Key                                  key_type;
58       typedef _Tp                                   mapped_type;
59       typedef std::pair<const _Key, _Tp>            value_type;
60       typedef _Compare                              key_compare;
61       typedef _Allocator                            allocator_type;
62       typedef typename _Base::reference             reference;
63       typedef typename _Base::const_reference       const_reference;
64 
65       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map>
66                                                     iterator;
67       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map>
68                                                     const_iterator;
69 
70       typedef typename _Base::size_type             size_type;
71       typedef typename _Base::difference_type       difference_type;
72       typedef typename _Base::pointer               pointer;
73       typedef typename _Base::const_pointer         const_pointer;
74       typedef std::reverse_iterator<iterator>       reverse_iterator;
75       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
76 
77       // 23.3.1.1 construct/copy/destroy:
78       explicit map(const _Compare& __comp = _Compare(),
79 		   const _Allocator& __a = _Allocator())
80       : _Base(__comp, __a) { }
81 
82       template<typename _InputIterator>
83         map(_InputIterator __first, _InputIterator __last,
84 	    const _Compare& __comp = _Compare(),
85 	    const _Allocator& __a = _Allocator())
86 	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
87 		__comp, __a), _Safe_base() { }
88 
89       map(const map<_Key,_Tp,_Compare,_Allocator>& __x)
90       : _Base(__x), _Safe_base() { }
91 
92       map(const _Base& __x) : _Base(__x), _Safe_base() { }
93 
94       ~map() { }
95 
96       map<_Key,_Tp,_Compare,_Allocator>&
97       operator=(const map<_Key,_Tp,_Compare,_Allocator>& __x)
98       {
99 	*static_cast<_Base*>(this) = __x;
100 	this->_M_invalidate_all();
101 	return *this;
102       }
103 
104       // _GLIBCXX_RESOLVE_LIB_DEFECTS
105       // 133. map missing get_allocator()
106       using _Base::get_allocator;
107 
108       // iterators:
109       iterator
110       begin()
111       { return iterator(_Base::begin(), this); }
112 
113       const_iterator
114       begin() const
115       { return const_iterator(_Base::begin(), this); }
116 
117       iterator
118       end()
119       { return iterator(_Base::end(), this); }
120 
121       const_iterator
122       end() const
123       { return const_iterator(_Base::end(), this); }
124 
125       reverse_iterator
126       rbegin()
127       { return reverse_iterator(end()); }
128 
129       const_reverse_iterator
130       rbegin() const
131       { return const_reverse_iterator(end()); }
132 
133       reverse_iterator
134       rend()
135       { return reverse_iterator(begin()); }
136 
137       const_reverse_iterator
138       rend() const
139       { return const_reverse_iterator(begin()); }
140 
141       // capacity:
142       using _Base::empty;
143       using _Base::size;
144       using _Base::max_size;
145 
146       // 23.3.1.2 element access:
147       using _Base::operator[];
148 
149       // _GLIBCXX_RESOLVE_LIB_DEFECTS
150       // DR 464. Suggestion for new member functions in standard containers.
151       using _Base::at;
152 
153       // modifiers:
154       std::pair<iterator, bool>
155       insert(const value_type& __x)
156       {
157 	typedef typename _Base::iterator _Base_iterator;
158 	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
159 	return std::pair<iterator, bool>(iterator(__res.first, this),
160 					 __res.second);
161       }
162 
163       iterator
164       insert(iterator __position, const value_type& __x)
165       {
166 	__glibcxx_check_insert(__position);
167 	return iterator(_Base::insert(__position.base(), __x), this);
168       }
169 
170       template<typename _InputIterator>
171         void
172         insert(_InputIterator __first, _InputIterator __last)
173         {
174 	  __glibcxx_check_valid_range(__first, __last);
175 	  _Base::insert(__first, __last);
176 	}
177 
178       void
179       erase(iterator __position)
180       {
181 	__glibcxx_check_erase(__position);
182 	__position._M_invalidate();
183 	_Base::erase(__position.base());
184       }
185 
186       size_type
187       erase(const key_type& __x)
188       {
189 	iterator __victim = find(__x);
190 	if (__victim == end())
191 	  return 0;
192 	else
193 	{
194 	  __victim._M_invalidate();
195 	  _Base::erase(__victim.base());
196 	  return 1;
197 	}
198       }
199 
200       void
201       erase(iterator __first, iterator __last)
202       {
203 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
204 	// 151. can't currently clear() empty container
205 	__glibcxx_check_erase_range(__first, __last);
206 	while (__first != __last)
207 	  this->erase(__first++);
208       }
209 
210       void
211       swap(map<_Key,_Tp,_Compare,_Allocator>& __x)
212       {
213 	_Base::swap(__x);
214 	this->_M_swap(__x);
215       }
216 
217       void
218       clear()
219       { this->erase(begin(), end()); }
220 
221       // observers:
222       using _Base::key_comp;
223       using _Base::value_comp;
224 
225       // 23.3.1.3 map operations:
226       iterator
227       find(const key_type& __x)
228       { return iterator(_Base::find(__x), this); }
229 
230       const_iterator
231       find(const key_type& __x) const
232       { return const_iterator(_Base::find(__x), this); }
233 
234       using _Base::count;
235 
236       iterator
237       lower_bound(const key_type& __x)
238       { return iterator(_Base::lower_bound(__x), this); }
239 
240       const_iterator
241       lower_bound(const key_type& __x) const
242       { return const_iterator(_Base::lower_bound(__x), this); }
243 
244       iterator
245       upper_bound(const key_type& __x)
246       { return iterator(_Base::upper_bound(__x), this); }
247 
248       const_iterator
249       upper_bound(const key_type& __x) const
250       { return const_iterator(_Base::upper_bound(__x), this); }
251 
252       std::pair<iterator,iterator>
253       equal_range(const key_type& __x)
254       {
255 	typedef typename _Base::iterator _Base_iterator;
256 	std::pair<_Base_iterator, _Base_iterator> __res =
257 	_Base::equal_range(__x);
258 	return std::make_pair(iterator(__res.first, this),
259 			      iterator(__res.second, this));
260       }
261 
262       std::pair<const_iterator,const_iterator>
263       equal_range(const key_type& __x) const
264       {
265 	typedef typename _Base::const_iterator _Base_const_iterator;
266 	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
267 	_Base::equal_range(__x);
268 	return std::make_pair(const_iterator(__res.first, this),
269 			      const_iterator(__res.second, this));
270       }
271 
272       _Base&
273       _M_base() { return *this; }
274 
275       const _Base&
276       _M_base() const { return *this; }
277 
278     private:
279       void
280       _M_invalidate_all()
281       {
282 	typedef typename _Base::const_iterator _Base_const_iterator;
283 	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
284 	this->_M_invalidate_if(_Not_equal(_M_base().end()));
285       }
286     };
287 
288   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
289     inline bool
290     operator==(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
291 	       const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
292     { return __lhs._M_base() == __rhs._M_base(); }
293 
294   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
295     inline bool
296     operator!=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
297 	       const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
298     { return __lhs._M_base() != __rhs._M_base(); }
299 
300   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
301     inline bool
302     operator<(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
303 	      const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
304     { return __lhs._M_base() < __rhs._M_base(); }
305 
306   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
307     inline bool
308     operator<=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
309 	       const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
310     { return __lhs._M_base() <= __rhs._M_base(); }
311 
312   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
313     inline bool
314     operator>=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
315 	       const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
316     { return __lhs._M_base() >= __rhs._M_base(); }
317 
318   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
319     inline bool
320     operator>(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
321 	      const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
322     { return __lhs._M_base() > __rhs._M_base(); }
323 
324   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
325     inline void
326     swap(map<_Key,_Tp,_Compare,_Allocator>& __lhs,
327 	 map<_Key,_Tp,_Compare,_Allocator>& __rhs)
328     { __lhs.swap(__rhs); }
329 } // namespace __debug
330 } // namespace std
331 
332 #endif
333