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
42namespace std
43{
44namespace __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