1// Debugging map implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009
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 3, 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// Under Section 7 of GPL version 3, you are granted additional
18// permissions described in the GCC Runtime Library Exception, version
19// 3.1, as published by the Free Software Foundation.
20
21// You should have received a copy of the GNU General Public License and
22// a copy of the GCC Runtime Library Exception along with this program;
23// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24// <http://www.gnu.org/licenses/>.
25
26/** @file debug/map.h
27 *  This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30#ifndef _GLIBCXX_DEBUG_MAP_H
31#define _GLIBCXX_DEBUG_MAP_H 1
32
33#include <debug/safe_sequence.h>
34#include <debug/safe_iterator.h>
35#include <utility>
36
37namespace std
38{
39namespace __debug
40{
41  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
42	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
43    class map
44    : public _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator>,
45      public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> >
46    {
47      typedef _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator> _Base;
48      typedef __gnu_debug::_Safe_sequence<map> _Safe_base;
49
50    public:
51      // types:
52      typedef _Key                                  key_type;
53      typedef _Tp                                   mapped_type;
54      typedef std::pair<const _Key, _Tp>            value_type;
55      typedef _Compare                              key_compare;
56      typedef _Allocator                            allocator_type;
57      typedef typename _Base::reference             reference;
58      typedef typename _Base::const_reference       const_reference;
59
60      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map>
61                                                    iterator;
62      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map>
63                                                    const_iterator;
64
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 std::reverse_iterator<iterator>       reverse_iterator;
70      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
71
72      using _Base::value_compare;
73
74      // 23.3.1.1 construct/copy/destroy:
75      explicit map(const _Compare& __comp = _Compare(),
76		   const _Allocator& __a = _Allocator())
77      : _Base(__comp, __a) { }
78
79      template<typename _InputIterator>
80        map(_InputIterator __first, _InputIterator __last,
81	    const _Compare& __comp = _Compare(),
82	    const _Allocator& __a = _Allocator())
83	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
84		__comp, __a), _Safe_base() { }
85
86      map(const map& __x)
87      : _Base(__x), _Safe_base() { }
88
89      map(const _Base& __x)
90      : _Base(__x), _Safe_base() { }
91
92#ifdef __GXX_EXPERIMENTAL_CXX0X__
93      map(map&& __x)
94      : _Base(std::forward<map>(__x)), _Safe_base()
95      { this->_M_swap(__x); }
96
97      map(initializer_list<value_type> __l,
98	  const _Compare& __c = _Compare(),
99	  const allocator_type& __a = allocator_type())
100      : _Base(__l, __c, __a), _Safe_base() { }
101#endif
102
103      ~map() { }
104
105      map&
106      operator=(const map& __x)
107      {
108	*static_cast<_Base*>(this) = __x;
109	this->_M_invalidate_all();
110	return *this;
111      }
112
113#ifdef __GXX_EXPERIMENTAL_CXX0X__
114      map&
115      operator=(map&& __x)
116      {
117        // NB: DR 675.
118	clear();
119	swap(__x);
120	return *this;
121      }
122
123      map&
124      operator=(initializer_list<value_type> __l)
125      {
126	this->clear();
127	this->insert(__l);
128	return *this;
129      }
130#endif
131
132      // _GLIBCXX_RESOLVE_LIB_DEFECTS
133      // 133. map missing get_allocator()
134      using _Base::get_allocator;
135
136      // iterators:
137      iterator
138      begin()
139      { return iterator(_Base::begin(), this); }
140
141      const_iterator
142      begin() const
143      { return const_iterator(_Base::begin(), this); }
144
145      iterator
146      end()
147      { return iterator(_Base::end(), this); }
148
149      const_iterator
150      end() const
151      { return const_iterator(_Base::end(), this); }
152
153      reverse_iterator
154      rbegin()
155      { return reverse_iterator(end()); }
156
157      const_reverse_iterator
158      rbegin() const
159      { return const_reverse_iterator(end()); }
160
161      reverse_iterator
162      rend()
163      { return reverse_iterator(begin()); }
164
165      const_reverse_iterator
166      rend() const
167      { return const_reverse_iterator(begin()); }
168
169#ifdef __GXX_EXPERIMENTAL_CXX0X__
170      const_iterator
171      cbegin() const
172      { return const_iterator(_Base::begin(), this); }
173
174      const_iterator
175      cend() const
176      { return const_iterator(_Base::end(), this); }
177
178      const_reverse_iterator
179      crbegin() const
180      { return const_reverse_iterator(end()); }
181
182      const_reverse_iterator
183      crend() const
184      { return const_reverse_iterator(begin()); }
185#endif
186
187      // capacity:
188      using _Base::empty;
189      using _Base::size;
190      using _Base::max_size;
191
192      // 23.3.1.2 element access:
193      using _Base::operator[];
194
195      // _GLIBCXX_RESOLVE_LIB_DEFECTS
196      // DR 464. Suggestion for new member functions in standard containers.
197      using _Base::at;
198
199      // modifiers:
200      std::pair<iterator, bool>
201      insert(const value_type& __x)
202      {
203	typedef typename _Base::iterator _Base_iterator;
204	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
205	return std::pair<iterator, bool>(iterator(__res.first, this),
206					 __res.second);
207      }
208
209#ifdef __GXX_EXPERIMENTAL_CXX0X__
210      void
211      insert(std::initializer_list<value_type> __list)
212      { _Base::insert(__list); }
213#endif
214
215      iterator
216      insert(iterator __position, const value_type& __x)
217      {
218	__glibcxx_check_insert(__position);
219	return iterator(_Base::insert(__position.base(), __x), this);
220      }
221
222      template<typename _InputIterator>
223        void
224        insert(_InputIterator __first, _InputIterator __last)
225        {
226	  __glibcxx_check_valid_range(__first, __last);
227	  _Base::insert(__first, __last);
228	}
229
230      void
231      erase(iterator __position)
232      {
233	__glibcxx_check_erase(__position);
234	__position._M_invalidate();
235	_Base::erase(__position.base());
236      }
237
238      size_type
239      erase(const key_type& __x)
240      {
241	iterator __victim = find(__x);
242	if (__victim == end())
243	  return 0;
244	else
245	{
246	  __victim._M_invalidate();
247	  _Base::erase(__victim.base());
248	  return 1;
249	}
250      }
251
252      void
253      erase(iterator __first, iterator __last)
254      {
255	// _GLIBCXX_RESOLVE_LIB_DEFECTS
256	// 151. can't currently clear() empty container
257	__glibcxx_check_erase_range(__first, __last);
258	while (__first != __last)
259	  this->erase(__first++);
260      }
261
262      void
263#ifdef __GXX_EXPERIMENTAL_CXX0X__
264      swap(map&& __x)
265#else
266      swap(map& __x)
267#endif
268      {
269	_Base::swap(__x);
270	this->_M_swap(__x);
271      }
272
273      void
274      clear()
275      { this->erase(begin(), end()); }
276
277      // observers:
278      using _Base::key_comp;
279      using _Base::value_comp;
280
281      // 23.3.1.3 map operations:
282      iterator
283      find(const key_type& __x)
284      { return iterator(_Base::find(__x), this); }
285
286      const_iterator
287      find(const key_type& __x) const
288      { return const_iterator(_Base::find(__x), this); }
289
290      using _Base::count;
291
292      iterator
293      lower_bound(const key_type& __x)
294      { return iterator(_Base::lower_bound(__x), this); }
295
296      const_iterator
297      lower_bound(const key_type& __x) const
298      { return const_iterator(_Base::lower_bound(__x), this); }
299
300      iterator
301      upper_bound(const key_type& __x)
302      { return iterator(_Base::upper_bound(__x), this); }
303
304      const_iterator
305      upper_bound(const key_type& __x) const
306      { return const_iterator(_Base::upper_bound(__x), this); }
307
308      std::pair<iterator,iterator>
309      equal_range(const key_type& __x)
310      {
311	typedef typename _Base::iterator _Base_iterator;
312	std::pair<_Base_iterator, _Base_iterator> __res =
313	_Base::equal_range(__x);
314	return std::make_pair(iterator(__res.first, this),
315			      iterator(__res.second, this));
316      }
317
318      std::pair<const_iterator,const_iterator>
319      equal_range(const key_type& __x) const
320      {
321	typedef typename _Base::const_iterator _Base_const_iterator;
322	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
323	_Base::equal_range(__x);
324	return std::make_pair(const_iterator(__res.first, this),
325			      const_iterator(__res.second, this));
326      }
327
328      _Base&
329      _M_base() { return *this; }
330
331      const _Base&
332      _M_base() const { return *this; }
333
334    private:
335      void
336      _M_invalidate_all()
337      {
338	typedef typename _Base::const_iterator _Base_const_iterator;
339	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
340	this->_M_invalidate_if(_Not_equal(_M_base().end()));
341      }
342    };
343
344  template<typename _Key, typename _Tp,
345	   typename _Compare, typename _Allocator>
346    inline bool
347    operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
348	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
349    { return __lhs._M_base() == __rhs._M_base(); }
350
351  template<typename _Key, typename _Tp,
352	   typename _Compare, typename _Allocator>
353    inline bool
354    operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
355	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
356    { return __lhs._M_base() != __rhs._M_base(); }
357
358  template<typename _Key, typename _Tp,
359	   typename _Compare, typename _Allocator>
360    inline bool
361    operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
362	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
363    { return __lhs._M_base() < __rhs._M_base(); }
364
365  template<typename _Key, typename _Tp,
366	   typename _Compare, typename _Allocator>
367    inline bool
368    operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
369	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
370    { return __lhs._M_base() <= __rhs._M_base(); }
371
372  template<typename _Key, typename _Tp,
373	   typename _Compare, typename _Allocator>
374    inline bool
375    operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
376	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
377    { return __lhs._M_base() >= __rhs._M_base(); }
378
379  template<typename _Key, typename _Tp,
380	   typename _Compare, typename _Allocator>
381    inline bool
382    operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
383	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
384    { return __lhs._M_base() > __rhs._M_base(); }
385
386  template<typename _Key, typename _Tp,
387	   typename _Compare, typename _Allocator>
388    inline void
389    swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
390	 map<_Key, _Tp, _Compare, _Allocator>& __rhs)
391    { __lhs.swap(__rhs); }
392
393#ifdef __GXX_EXPERIMENTAL_CXX0X__
394  template<typename _Key, typename _Tp,
395	   typename _Compare, typename _Allocator>
396    inline void
397    swap(map<_Key, _Tp, _Compare, _Allocator>&& __lhs,
398	 map<_Key, _Tp, _Compare, _Allocator>& __rhs)
399    { __lhs.swap(__rhs); }
400
401  template<typename _Key, typename _Tp,
402	   typename _Compare, typename _Allocator>
403    inline void
404    swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
405	 map<_Key, _Tp, _Compare, _Allocator>&& __rhs)
406    { __lhs.swap(__rhs); }
407#endif
408
409} // namespace __debug
410} // namespace std
411
412#endif
413