1// Debugging multimap implementation -*- C++ -*-
2
3// Copyright (C) 2003-2013 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/multimap.h
26 *  This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_MULTIMAP_H
30#define _GLIBCXX_DEBUG_MULTIMAP_H 1
31
32#include <debug/safe_sequence.h>
33#include <debug/safe_iterator.h>
34#include <utility>
35
36namespace std _GLIBCXX_VISIBILITY(default)
37{
38namespace __debug
39{
40  /// Class std::multimap with safety/checking/debug instrumentation.
41  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
42	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
43    class multimap
44    : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>,
45      public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp,
46						  _Compare, _Allocator> >
47    {
48      typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
49
50      typedef typename _Base::const_iterator _Base_const_iterator;
51      typedef typename _Base::iterator _Base_iterator;
52      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
53    public:
54      // types:
55      typedef _Key				     key_type;
56      typedef _Tp				     mapped_type;
57      typedef std::pair<const _Key, _Tp>             value_type;
58      typedef _Compare                               key_compare;
59      typedef _Allocator                             allocator_type;
60      typedef typename _Base::reference              reference;
61      typedef typename _Base::const_reference        const_reference;
62
63      typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
64                                                     iterator;
65      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
66                                           multimap> const_iterator;
67
68      typedef typename _Base::size_type              size_type;
69      typedef typename _Base::difference_type        difference_type;
70      typedef typename _Base::pointer                pointer;
71      typedef typename _Base::const_pointer          const_pointer;
72      typedef std::reverse_iterator<iterator>        reverse_iterator;
73      typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
74
75      // 23.3.1.1 construct/copy/destroy:
76      explicit multimap(const _Compare& __comp = _Compare(),
77			const _Allocator& __a = _Allocator())
78      : _Base(__comp, __a) { }
79
80      template<typename _InputIterator>
81      multimap(_InputIterator __first, _InputIterator __last,
82	       const _Compare& __comp = _Compare(),
83	       const _Allocator& __a = _Allocator())
84	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
85								     __last)),
86		__gnu_debug::__base(__last),
87	      __comp, __a) { }
88
89      multimap(const multimap& __x)
90      : _Base(__x) { }
91
92      multimap(const _Base& __x)
93      : _Base(__x) { }
94
95#if __cplusplus >= 201103L
96      multimap(multimap&& __x)
97      noexcept(is_nothrow_copy_constructible<_Compare>::value)
98      : _Base(std::move(__x))
99      { this->_M_swap(__x); }
100
101      multimap(initializer_list<value_type> __l,
102	       const _Compare& __c = _Compare(),
103	       const allocator_type& __a = allocator_type())
104      : _Base(__l, __c, __a) { }
105#endif
106
107      ~multimap() _GLIBCXX_NOEXCEPT { }
108
109      multimap&
110      operator=(const multimap& __x)
111      {
112	*static_cast<_Base*>(this) = __x;
113	this->_M_invalidate_all();
114	return *this;
115      }
116
117#if __cplusplus >= 201103L
118      multimap&
119      operator=(multimap&& __x)
120      {
121	// NB: DR 1204.
122	// NB: DR 675.
123	__glibcxx_check_self_move_assign(__x);
124	clear();
125	swap(__x);
126	return *this;
127      }
128
129      multimap&
130      operator=(initializer_list<value_type> __l)
131      {
132	this->clear();
133	this->insert(__l);
134	return *this;
135      }
136#endif
137
138      using _Base::get_allocator;
139
140      // iterators:
141      iterator
142      begin() _GLIBCXX_NOEXCEPT
143      { return iterator(_Base::begin(), this); }
144
145      const_iterator
146      begin() const _GLIBCXX_NOEXCEPT
147      { return const_iterator(_Base::begin(), this); }
148
149      iterator
150      end() _GLIBCXX_NOEXCEPT
151      { return iterator(_Base::end(), this); }
152
153      const_iterator
154      end() const _GLIBCXX_NOEXCEPT
155      { return const_iterator(_Base::end(), this); }
156
157      reverse_iterator
158      rbegin() _GLIBCXX_NOEXCEPT
159      { return reverse_iterator(end()); }
160
161      const_reverse_iterator
162      rbegin() const _GLIBCXX_NOEXCEPT
163      { return const_reverse_iterator(end()); }
164
165      reverse_iterator
166      rend() _GLIBCXX_NOEXCEPT
167      { return reverse_iterator(begin()); }
168
169      const_reverse_iterator
170      rend() const _GLIBCXX_NOEXCEPT
171      { return const_reverse_iterator(begin()); }
172
173#if __cplusplus >= 201103L
174      const_iterator
175      cbegin() const noexcept
176      { return const_iterator(_Base::begin(), this); }
177
178      const_iterator
179      cend() const noexcept
180      { return const_iterator(_Base::end(), this); }
181
182      const_reverse_iterator
183      crbegin() const noexcept
184      { return const_reverse_iterator(end()); }
185
186      const_reverse_iterator
187      crend() const noexcept
188      { return const_reverse_iterator(begin()); }
189#endif
190
191      // capacity:
192      using _Base::empty;
193      using _Base::size;
194      using _Base::max_size;
195
196      // modifiers:
197#if __cplusplus >= 201103L
198      template<typename... _Args>
199	iterator
200	emplace(_Args&&... __args)
201	{
202	  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
203	}
204
205      template<typename... _Args>
206	iterator
207	emplace_hint(const_iterator __pos, _Args&&... __args)
208	{
209	  __glibcxx_check_insert(__pos);
210	  return iterator(_Base::emplace_hint(__pos.base(),
211					      std::forward<_Args>(__args)...),
212			  this);
213	}
214#endif
215
216      iterator
217      insert(const value_type& __x)
218      { return iterator(_Base::insert(__x), this); }
219
220#if __cplusplus >= 201103L
221      template<typename _Pair, typename = typename
222	       std::enable_if<std::is_constructible<value_type,
223						    _Pair&&>::value>::type>
224        iterator
225        insert(_Pair&& __x)
226        { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); }
227#endif
228
229#if __cplusplus >= 201103L
230      void
231      insert(std::initializer_list<value_type> __list)
232      { _Base::insert(__list); }
233#endif
234
235      iterator
236#if __cplusplus >= 201103L
237      insert(const_iterator __position, const value_type& __x)
238#else
239      insert(iterator __position, const value_type& __x)
240#endif
241      {
242	__glibcxx_check_insert(__position);
243	return iterator(_Base::insert(__position.base(), __x), this);
244      }
245
246#if __cplusplus >= 201103L
247      template<typename _Pair, typename = typename
248	       std::enable_if<std::is_constructible<value_type,
249						    _Pair&&>::value>::type>
250        iterator
251        insert(const_iterator __position, _Pair&& __x)
252        {
253	  __glibcxx_check_insert(__position);
254	  return iterator(_Base::insert(__position.base(),
255					std::forward<_Pair>(__x)), this);
256	}
257#endif
258
259      template<typename _InputIterator>
260        void
261        insert(_InputIterator __first, _InputIterator __last)
262        {
263	  __glibcxx_check_valid_range(__first, __last);
264	  _Base::insert(__gnu_debug::__base(__first),
265			__gnu_debug::__base(__last));
266	}
267
268#if __cplusplus >= 201103L
269      iterator
270      erase(const_iterator __position)
271      {
272	__glibcxx_check_erase(__position);
273	this->_M_invalidate_if(_Equal(__position.base()));
274	return iterator(_Base::erase(__position.base()), this);
275      }
276
277      iterator
278      erase(iterator __position)
279      { return erase(const_iterator(__position)); }
280#else
281      void
282      erase(iterator __position)
283      {
284	__glibcxx_check_erase(__position);
285	this->_M_invalidate_if(_Equal(__position.base()));
286	_Base::erase(__position.base());
287      }
288#endif
289
290      size_type
291      erase(const key_type& __x)
292      {
293	std::pair<_Base_iterator, _Base_iterator> __victims =
294	  _Base::equal_range(__x);
295	size_type __count = 0;
296	_Base_iterator __victim = __victims.first;
297	while (__victim !=  __victims.second)
298	  {
299	    this->_M_invalidate_if(_Equal(__victim));
300	    _Base::erase(__victim++);
301	    ++__count;
302	  }
303	return __count;
304      }
305
306#if __cplusplus >= 201103L
307      iterator
308      erase(const_iterator __first, const_iterator __last)
309      {
310	// _GLIBCXX_RESOLVE_LIB_DEFECTS
311	// 151. can't currently clear() empty container
312	__glibcxx_check_erase_range(__first, __last);
313	for (_Base_const_iterator __victim = __first.base();
314	     __victim != __last.base(); ++__victim)
315	  {
316	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
317				  _M_message(__gnu_debug::__msg_valid_range)
318				  ._M_iterator(__first, "first")
319				  ._M_iterator(__last, "last"));
320	    this->_M_invalidate_if(_Equal(__victim));
321	  }
322	return iterator(_Base::erase(__first.base(), __last.base()), this);
323      }
324#else
325      void
326      erase(iterator __first, iterator __last)
327      {
328	// _GLIBCXX_RESOLVE_LIB_DEFECTS
329	// 151. can't currently clear() empty container
330	__glibcxx_check_erase_range(__first, __last);
331	for (_Base_iterator __victim = __first.base();
332	     __victim != __last.base(); ++__victim)
333	  {
334	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
335				  _M_message(__gnu_debug::__msg_valid_range)
336				  ._M_iterator(__first, "first")
337				  ._M_iterator(__last, "last"));
338	    this->_M_invalidate_if(_Equal(__victim));
339	  }
340	_Base::erase(__first.base(), __last.base());
341      }
342#endif
343
344      void
345      swap(multimap& __x)
346      {
347	_Base::swap(__x);
348	this->_M_swap(__x);
349      }
350
351      void
352      clear() _GLIBCXX_NOEXCEPT
353      {
354	this->_M_invalidate_all();
355	_Base::clear();
356      }
357
358      // observers:
359      using _Base::key_comp;
360      using _Base::value_comp;
361
362      // 23.3.1.3 multimap operations:
363      iterator
364      find(const key_type& __x)
365      { return iterator(_Base::find(__x), this); }
366
367      const_iterator
368      find(const key_type& __x) const
369      { return const_iterator(_Base::find(__x), this); }
370
371      using _Base::count;
372
373      iterator
374      lower_bound(const key_type& __x)
375      { return iterator(_Base::lower_bound(__x), this); }
376
377      const_iterator
378      lower_bound(const key_type& __x) const
379      { return const_iterator(_Base::lower_bound(__x), this); }
380
381      iterator
382      upper_bound(const key_type& __x)
383      { return iterator(_Base::upper_bound(__x), this); }
384
385      const_iterator
386      upper_bound(const key_type& __x) const
387      { return const_iterator(_Base::upper_bound(__x), this); }
388
389      std::pair<iterator,iterator>
390      equal_range(const key_type& __x)
391      {
392	std::pair<_Base_iterator, _Base_iterator> __res =
393	_Base::equal_range(__x);
394	return std::make_pair(iterator(__res.first, this),
395			      iterator(__res.second, this));
396      }
397
398      std::pair<const_iterator,const_iterator>
399      equal_range(const key_type& __x) const
400      {
401	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
402	  _Base::equal_range(__x);
403	return std::make_pair(const_iterator(__res.first, this),
404			      const_iterator(__res.second, this));
405      }
406
407      _Base&
408      _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
409
410      const _Base&
411      _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
412
413    private:
414      void
415      _M_invalidate_all()
416      {
417	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
418	this->_M_invalidate_if(_Not_equal(_Base::end()));
419      }
420    };
421
422  template<typename _Key, typename _Tp,
423	   typename _Compare, typename _Allocator>
424    inline bool
425    operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
426	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
427    { return __lhs._M_base() == __rhs._M_base(); }
428
429  template<typename _Key, typename _Tp,
430	   typename _Compare, typename _Allocator>
431    inline bool
432    operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
433	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
434    { return __lhs._M_base() != __rhs._M_base(); }
435
436  template<typename _Key, typename _Tp,
437	   typename _Compare, typename _Allocator>
438    inline bool
439    operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
440	      const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
441    { return __lhs._M_base() < __rhs._M_base(); }
442
443  template<typename _Key, typename _Tp,
444	   typename _Compare, typename _Allocator>
445    inline bool
446    operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
447	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
448    { return __lhs._M_base() <= __rhs._M_base(); }
449
450  template<typename _Key, typename _Tp,
451	   typename _Compare, typename _Allocator>
452    inline bool
453    operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
454	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
455    { return __lhs._M_base() >= __rhs._M_base(); }
456
457  template<typename _Key, typename _Tp,
458	   typename _Compare, typename _Allocator>
459    inline bool
460    operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
461	      const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
462    { return __lhs._M_base() > __rhs._M_base(); }
463
464  template<typename _Key, typename _Tp,
465	   typename _Compare, typename _Allocator>
466    inline void
467    swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
468	 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
469    { __lhs.swap(__rhs); }
470
471} // namespace __debug
472} // namespace std
473
474#endif
475