1// Debugging map implementation -*- C++ -*-
2
3// Copyright (C) 2003-2015 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file debug/map.h
26 *  This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_MAP_H
30#define _GLIBCXX_DEBUG_MAP_H 1
31
32#include <debug/safe_sequence.h>
33#include <debug/safe_container.h>
34#include <debug/safe_iterator.h>
35#include <utility>
36
37namespace std _GLIBCXX_VISIBILITY(default)
38{
39namespace __debug
40{
41  /// Class std::map with safety/checking/debug instrumentation.
42  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
43	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
44    class map
45    : public __gnu_debug::_Safe_container<
46	map<_Key, _Tp, _Compare, _Allocator>, _Allocator,
47	__gnu_debug::_Safe_node_sequence>,
48      public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
49    {
50      typedef _GLIBCXX_STD_C::map<
51	_Key, _Tp, _Compare, _Allocator>			_Base;
52      typedef __gnu_debug::_Safe_container<
53	map, _Allocator, __gnu_debug::_Safe_node_sequence>	_Safe;
54
55      typedef typename _Base::const_iterator	_Base_const_iterator;
56      typedef typename _Base::iterator		_Base_iterator;
57      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
58
59    public:
60      // types:
61      typedef _Key					key_type;
62      typedef _Tp					mapped_type;
63      typedef std::pair<const _Key, _Tp>		value_type;
64      typedef _Compare					key_compare;
65      typedef _Allocator				allocator_type;
66      typedef typename _Base::reference			reference;
67      typedef typename _Base::const_reference		const_reference;
68
69      typedef __gnu_debug::_Safe_iterator<_Base_iterator, map>
70							iterator;
71      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map>
72							const_iterator;
73
74      typedef typename _Base::size_type			size_type;
75      typedef typename _Base::difference_type		difference_type;
76      typedef typename _Base::pointer			pointer;
77      typedef typename _Base::const_pointer		const_pointer;
78      typedef std::reverse_iterator<iterator>		reverse_iterator;
79      typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
80
81      // 23.3.1.1 construct/copy/destroy:
82
83#if __cplusplus < 201103L
84      map() : _Base() { }
85
86      map(const map& __x)
87      : _Base(__x) { }
88
89      ~map() { }
90#else
91      map() = default;
92      map(const map&) = default;
93      map(map&&) = default;
94
95      map(initializer_list<value_type> __l,
96	  const _Compare& __c = _Compare(),
97	  const allocator_type& __a = allocator_type())
98      : _Base(__l, __c, __a) { }
99
100      explicit
101      map(const allocator_type& __a)
102      : _Base(__a) { }
103
104      map(const map& __m, const allocator_type& __a)
105      : _Base(__m, __a) { }
106
107      map(map&& __m, const allocator_type& __a)
108      : _Safe(std::move(__m._M_safe()), __a),
109	_Base(std::move(__m._M_base()), __a) { }
110
111      map(initializer_list<value_type> __l, const allocator_type& __a)
112      : _Base(__l, __a) { }
113
114      template<typename _InputIterator>
115	map(_InputIterator __first, _InputIterator __last,
116	    const allocator_type& __a)
117	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
118								     __last)),
119		__gnu_debug::__base(__last), __a)
120	{ }
121
122      ~map() = default;
123#endif
124
125      map(const _Base& __x)
126      : _Base(__x) { }
127
128      explicit map(const _Compare& __comp,
129		   const _Allocator& __a = _Allocator())
130      : _Base(__comp, __a) { }
131
132      template<typename _InputIterator>
133	map(_InputIterator __first, _InputIterator __last,
134	    const _Compare& __comp = _Compare(),
135	    const _Allocator& __a = _Allocator())
136	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
137								     __last)),
138		__gnu_debug::__base(__last),
139		__comp, __a) { }
140
141#if __cplusplus < 201103L
142      map&
143      operator=(const map& __x)
144      {
145	this->_M_safe() = __x;
146	_M_base() = __x;
147	return *this;
148      }
149#else
150      map&
151      operator=(const map&) = default;
152
153      map&
154      operator=(map&&) = default;
155
156      map&
157      operator=(initializer_list<value_type> __l)
158      {
159	_M_base() = __l;
160	this->_M_invalidate_all();
161	return *this;
162      }
163#endif
164
165      // _GLIBCXX_RESOLVE_LIB_DEFECTS
166      // 133. map missing get_allocator()
167      using _Base::get_allocator;
168
169      // iterators:
170      iterator
171      begin() _GLIBCXX_NOEXCEPT
172      { return iterator(_Base::begin(), this); }
173
174      const_iterator
175      begin() const _GLIBCXX_NOEXCEPT
176      { return const_iterator(_Base::begin(), this); }
177
178      iterator
179      end() _GLIBCXX_NOEXCEPT
180      { return iterator(_Base::end(), this); }
181
182      const_iterator
183      end() const _GLIBCXX_NOEXCEPT
184      { return const_iterator(_Base::end(), this); }
185
186      reverse_iterator
187      rbegin() _GLIBCXX_NOEXCEPT
188      { return reverse_iterator(end()); }
189
190      const_reverse_iterator
191      rbegin() const _GLIBCXX_NOEXCEPT
192      { return const_reverse_iterator(end()); }
193
194      reverse_iterator
195      rend() _GLIBCXX_NOEXCEPT
196      { return reverse_iterator(begin()); }
197
198      const_reverse_iterator
199      rend() const _GLIBCXX_NOEXCEPT
200      { return const_reverse_iterator(begin()); }
201
202#if __cplusplus >= 201103L
203      const_iterator
204      cbegin() const noexcept
205      { return const_iterator(_Base::begin(), this); }
206
207      const_iterator
208      cend() const noexcept
209      { return const_iterator(_Base::end(), this); }
210
211      const_reverse_iterator
212      crbegin() const noexcept
213      { return const_reverse_iterator(end()); }
214
215      const_reverse_iterator
216      crend() const noexcept
217      { return const_reverse_iterator(begin()); }
218#endif
219
220      // capacity:
221      using _Base::empty;
222      using _Base::size;
223      using _Base::max_size;
224
225      // 23.3.1.2 element access:
226      using _Base::operator[];
227
228      // _GLIBCXX_RESOLVE_LIB_DEFECTS
229      // DR 464. Suggestion for new member functions in standard containers.
230      using _Base::at;
231
232      // modifiers:
233#if __cplusplus >= 201103L
234      template<typename... _Args>
235	std::pair<iterator, bool>
236	emplace(_Args&&... __args)
237	{
238	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
239	  return std::pair<iterator, bool>(iterator(__res.first, this),
240					   __res.second);
241	}
242
243      template<typename... _Args>
244	iterator
245	emplace_hint(const_iterator __pos, _Args&&... __args)
246	{
247	  __glibcxx_check_insert(__pos);
248	  return iterator(_Base::emplace_hint(__pos.base(),
249					      std::forward<_Args>(__args)...),
250			  this);
251	}
252#endif
253
254      std::pair<iterator, bool>
255      insert(const value_type& __x)
256      {
257	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
258	return std::pair<iterator, bool>(iterator(__res.first, this),
259					 __res.second);
260      }
261
262#if __cplusplus >= 201103L
263      template<typename _Pair, typename = typename
264	       std::enable_if<std::is_constructible<value_type,
265						    _Pair&&>::value>::type>
266	std::pair<iterator, bool>
267	insert(_Pair&& __x)
268	{
269	  std::pair<_Base_iterator, bool> __res
270	    = _Base::insert(std::forward<_Pair>(__x));
271	  return std::pair<iterator, bool>(iterator(__res.first, this),
272					   __res.second);
273	}
274#endif
275
276#if __cplusplus >= 201103L
277      void
278      insert(std::initializer_list<value_type> __list)
279      { _Base::insert(__list); }
280#endif
281
282      iterator
283#if __cplusplus >= 201103L
284      insert(const_iterator __position, const value_type& __x)
285#else
286      insert(iterator __position, const value_type& __x)
287#endif
288      {
289	__glibcxx_check_insert(__position);
290	return iterator(_Base::insert(__position.base(), __x), this);
291      }
292
293#if __cplusplus >= 201103L
294      template<typename _Pair, typename = typename
295	       std::enable_if<std::is_constructible<value_type,
296						    _Pair&&>::value>::type>
297	iterator
298	insert(const_iterator __position, _Pair&& __x)
299	{
300	  __glibcxx_check_insert(__position);
301	  return iterator(_Base::insert(__position.base(),
302					std::forward<_Pair>(__x)), this);
303	}
304#endif
305
306      template<typename _InputIterator>
307	void
308	insert(_InputIterator __first, _InputIterator __last)
309	{
310	  __glibcxx_check_valid_range(__first, __last);
311	  _Base::insert(__gnu_debug::__base(__first),
312			__gnu_debug::__base(__last));
313	}
314
315#if __cplusplus >= 201103L
316      iterator
317      erase(const_iterator __position)
318      {
319	__glibcxx_check_erase(__position);
320	this->_M_invalidate_if(_Equal(__position.base()));
321	return iterator(_Base::erase(__position.base()), this);
322      }
323
324      iterator
325      erase(iterator __position)
326      { return erase(const_iterator(__position)); }
327#else
328      void
329      erase(iterator __position)
330      {
331	__glibcxx_check_erase(__position);
332	this->_M_invalidate_if(_Equal(__position.base()));
333	_Base::erase(__position.base());
334      }
335#endif
336
337      size_type
338      erase(const key_type& __x)
339      {
340	_Base_iterator __victim = _Base::find(__x);
341	if (__victim == _Base::end())
342	  return 0;
343	else
344	  {
345	    this->_M_invalidate_if(_Equal(__victim));
346	    _Base::erase(__victim);
347	    return 1;
348	  }
349      }
350
351#if __cplusplus >= 201103L
352      iterator
353      erase(const_iterator __first, const_iterator __last)
354      {
355	// _GLIBCXX_RESOLVE_LIB_DEFECTS
356	// 151. can't currently clear() empty container
357	__glibcxx_check_erase_range(__first, __last);
358	for (_Base_const_iterator __victim = __first.base();
359	     __victim != __last.base(); ++__victim)
360	  {
361	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
362				  _M_message(__gnu_debug::__msg_valid_range)
363				  ._M_iterator(__first, "first")
364				  ._M_iterator(__last, "last"));
365	    this->_M_invalidate_if(_Equal(__victim));
366	  }
367	return iterator(_Base::erase(__first.base(), __last.base()), this);
368      }
369#else
370      void
371      erase(iterator __first, iterator __last)
372      {
373	// _GLIBCXX_RESOLVE_LIB_DEFECTS
374	// 151. can't currently clear() empty container
375	__glibcxx_check_erase_range(__first, __last);
376	for (_Base_iterator __victim = __first.base();
377	     __victim != __last.base(); ++__victim)
378	  {
379	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
380				  _M_message(__gnu_debug::__msg_valid_range)
381				  ._M_iterator(__first, "first")
382				  ._M_iterator(__last, "last"));
383	    this->_M_invalidate_if(_Equal(__victim));
384	  }
385	_Base::erase(__first.base(), __last.base());
386      }
387#endif
388
389      void
390      swap(map& __x)
391#if __cplusplus >= 201103L
392	noexcept( noexcept(declval<_Base>().swap(__x)) )
393#endif
394      {
395	_Safe::_M_swap(__x);
396	_Base::swap(__x);
397      }
398
399      void
400      clear() _GLIBCXX_NOEXCEPT
401      {
402	this->_M_invalidate_all();
403	_Base::clear();
404      }
405
406      // observers:
407      using _Base::key_comp;
408      using _Base::value_comp;
409
410      // 23.3.1.3 map operations:
411      iterator
412      find(const key_type& __x)
413      { return iterator(_Base::find(__x), this); }
414
415      const_iterator
416      find(const key_type& __x) const
417      { return const_iterator(_Base::find(__x), this); }
418
419      using _Base::count;
420
421      iterator
422      lower_bound(const key_type& __x)
423      { return iterator(_Base::lower_bound(__x), this); }
424
425      const_iterator
426      lower_bound(const key_type& __x) const
427      { return const_iterator(_Base::lower_bound(__x), this); }
428
429      iterator
430      upper_bound(const key_type& __x)
431      { return iterator(_Base::upper_bound(__x), this); }
432
433      const_iterator
434      upper_bound(const key_type& __x) const
435      { return const_iterator(_Base::upper_bound(__x), this); }
436
437      std::pair<iterator,iterator>
438      equal_range(const key_type& __x)
439      {
440	std::pair<_Base_iterator, _Base_iterator> __res =
441	_Base::equal_range(__x);
442	return std::make_pair(iterator(__res.first, this),
443			      iterator(__res.second, this));
444      }
445
446      std::pair<const_iterator,const_iterator>
447      equal_range(const key_type& __x) const
448      {
449	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
450	_Base::equal_range(__x);
451	return std::make_pair(const_iterator(__res.first, this),
452			      const_iterator(__res.second, this));
453      }
454
455      _Base&
456      _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
457
458      const _Base&
459      _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
460    };
461
462  template<typename _Key, typename _Tp,
463	   typename _Compare, typename _Allocator>
464    inline bool
465    operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
466	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
467    { return __lhs._M_base() == __rhs._M_base(); }
468
469  template<typename _Key, typename _Tp,
470	   typename _Compare, typename _Allocator>
471    inline bool
472    operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
473	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
474    { return __lhs._M_base() != __rhs._M_base(); }
475
476  template<typename _Key, typename _Tp,
477	   typename _Compare, typename _Allocator>
478    inline bool
479    operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
480	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
481    { return __lhs._M_base() < __rhs._M_base(); }
482
483  template<typename _Key, typename _Tp,
484	   typename _Compare, typename _Allocator>
485    inline bool
486    operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
487	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
488    { return __lhs._M_base() <= __rhs._M_base(); }
489
490  template<typename _Key, typename _Tp,
491	   typename _Compare, typename _Allocator>
492    inline bool
493    operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
494	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
495    { return __lhs._M_base() >= __rhs._M_base(); }
496
497  template<typename _Key, typename _Tp,
498	   typename _Compare, typename _Allocator>
499    inline bool
500    operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
501	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
502    { return __lhs._M_base() > __rhs._M_base(); }
503
504  template<typename _Key, typename _Tp,
505	   typename _Compare, typename _Allocator>
506    inline void
507    swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
508	 map<_Key, _Tp, _Compare, _Allocator>& __rhs)
509    { __lhs.swap(__rhs); }
510
511} // namespace __debug
512} // namespace std
513
514#endif
515