1// Profiling map implementation -*- C++ -*-
2
3// Copyright (C) 2009-2019 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 along
21// with this library; see the file COPYING3.  If not see
22// <http://www.gnu.org/licenses/>.
23
24/** @file profile/map.h
25 *  This file is a GNU profile extension to the Standard C++ Library.
26 */
27
28#ifndef _GLIBCXX_PROFILE_MAP_H
29#define _GLIBCXX_PROFILE_MAP_H 1
30
31#include <profile/base.h>
32#include <profile/ordered_base.h>
33
34namespace std _GLIBCXX_VISIBILITY(default)
35{
36namespace __profile
37{
38  /// Class std::map wrapper with performance instrumentation.
39  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
40	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
41    class map
42    : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>,
43      public _Ordered_profile<map<_Key, _Tp, _Compare, _Allocator> >
44    {
45      typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
46
47      typedef typename _Base::iterator			_Base_iterator;
48      typedef typename _Base::const_iterator		_Base_const_iterator;
49
50    public:
51      // types:
52      typedef _Key					key_type;
53      typedef _Tp					mapped_type;
54      typedef typename _Base::value_type		value_type;
55      typedef _Compare					key_compare;
56      typedef typename _Base::reference			reference;
57      typedef typename _Base::const_reference		const_reference;
58
59      typedef __iterator_tracker<_Base_iterator, map>	iterator;
60      typedef __iterator_tracker<_Base_const_iterator,
61				 map>			const_iterator;
62      typedef std::reverse_iterator<iterator>		reverse_iterator;
63      typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
64
65      typedef typename _Base::size_type			size_type;
66      typedef typename _Base::difference_type		difference_type;
67
68      // 23.3.1.1 construct/copy/destroy:
69
70#if __cplusplus < 201103L
71      map()
72      : _Base() { }
73      map(const map& __x)
74	: _Base(__x) { }
75      ~map()
76      { }
77#else
78      map() = default;
79      map(const map&) = default;
80      map(map&&) = default;
81      ~map() = default;
82#endif
83
84      explicit
85      map(const _Compare& __comp,
86	  const _Allocator& __a = _Allocator())
87      : _Base(__comp, __a) { }
88
89#if __cplusplus >= 201103L
90      template<typename _InputIterator,
91	       typename = std::_RequireInputIter<_InputIterator>>
92#else
93      template<typename _InputIterator>
94#endif
95	map(_InputIterator __first, _InputIterator __last,
96	    const _Compare& __comp = _Compare(),
97	    const _Allocator& __a = _Allocator())
98	: _Base(__first, __last, __comp, __a) { }
99
100      map(const _Base& __x)
101      : _Base(__x) { }
102
103#if __cplusplus >= 201103L
104      map(initializer_list<value_type> __l,
105	  const _Compare& __c = _Compare(),
106	  const _Allocator& __a = _Allocator())
107      : _Base(__l, __c, __a) { }
108
109      explicit
110      map(const _Allocator& __a)
111      : _Base(__a) { }
112
113      map(const map& __x, const _Allocator& __a)
114      : _Base(__x, __a) { }
115
116      map(map&& __x, const _Allocator& __a)
117      noexcept( noexcept(_Base(std::move(__x), __a)) )
118      : _Base(std::move(__x), __a) { }
119
120      map(initializer_list<value_type> __l, const _Allocator& __a)
121      : _Base(__l, __a) { }
122
123      template<typename _InputIterator>
124	map(_InputIterator __first, _InputIterator __last,
125	    const _Allocator& __a)
126	: _Base(__first, __last, __a) { }
127#endif
128
129#if __cplusplus < 201103L
130      map&
131      operator=(const map& __x)
132      {
133	this->_M_profile_destruct();
134	_M_base() = __x;
135	this->_M_profile_construct();
136	return *this;
137      }
138#else
139      map&
140      operator=(const map&) = default;
141
142      map&
143      operator=(map&&) = default;
144
145      map&
146      operator=(initializer_list<value_type> __l)
147      {
148	this->_M_profile_destruct();
149	_M_base() = __l;
150	this->_M_profile_construct();
151	return *this;
152      }
153#endif
154
155      // iterators
156      iterator
157      begin() _GLIBCXX_NOEXCEPT
158      { return iterator(_Base::begin(), this); }
159
160      const_iterator
161      begin() const _GLIBCXX_NOEXCEPT
162      { return const_iterator(_Base::begin(), this); }
163
164      iterator
165      end() _GLIBCXX_NOEXCEPT
166      { return iterator(_Base::end(), this); }
167
168      const_iterator
169      end() const _GLIBCXX_NOEXCEPT
170      { return const_iterator(_Base::end(), this); }
171
172#if __cplusplus >= 201103L
173      const_iterator
174      cbegin() const noexcept
175      { return const_iterator(_Base::cbegin(), this); }
176
177      const_iterator
178      cend() const noexcept
179      { return const_iterator(_Base::cend(), this); }
180#endif
181
182      reverse_iterator
183      rbegin() _GLIBCXX_NOEXCEPT
184      {
185	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
186	return reverse_iterator(end());
187      }
188
189      const_reverse_iterator
190      rbegin() const _GLIBCXX_NOEXCEPT
191      {
192	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
193	return const_reverse_iterator(end());
194      }
195
196      reverse_iterator
197      rend() _GLIBCXX_NOEXCEPT
198      {
199	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
200	return reverse_iterator(begin());
201      }
202
203      const_reverse_iterator
204      rend() const _GLIBCXX_NOEXCEPT
205      {
206	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
207	return const_reverse_iterator(begin());
208      }
209
210#if __cplusplus >= 201103L
211      const_reverse_iterator
212      crbegin() const noexcept
213      {
214	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
215	return const_reverse_iterator(cend());
216      }
217
218      const_reverse_iterator
219      crend() const noexcept
220      {
221	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
222	return const_reverse_iterator(cbegin());
223      }
224#endif
225
226      // 23.3.1.2 element access:
227      mapped_type&
228      operator[](const key_type& __k)
229      {
230	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
231	return _Base::operator[](__k);
232      }
233
234#if __cplusplus >= 201103L
235      mapped_type&
236      operator[](key_type&& __k)
237      {
238	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
239	return _Base::operator[](std::move(__k));
240      }
241#endif
242
243      mapped_type&
244      at(const key_type& __k)
245      {
246	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
247	return _Base::at(__k);
248      }
249
250      const mapped_type&
251      at(const key_type& __k) const
252      {
253	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
254	return _Base::at(__k);
255      }
256
257      // modifiers:
258#if __cplusplus >= 201103L
259      template<typename... _Args>
260	std::pair<iterator, bool>
261	emplace(_Args&&... __args)
262	{
263	  // The cost is the same whether or not the element is inserted so we
264	  // always report insertion of 1 element.
265	  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
266	  auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...);
267	  return std::make_pair(iterator(__base_ret.first, this),
268				__base_ret.second);
269	}
270
271      template<typename... _Args>
272	iterator
273	emplace_hint(const_iterator __pos, _Args&&... __args)
274	{
275	  auto size_before = this->size();
276	  auto __res
277	    = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
278	  __profcxx_map2umap_insert(this->_M_map2umap_info,
279		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
280	  return iterator(__res, this);
281	}
282#endif
283
284      std::pair<iterator, bool>
285      insert(const value_type& __x)
286      {
287	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
288	std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x);
289	return std::make_pair(iterator(__base_ret.first, this),
290			      __base_ret.second);
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	std::pair<iterator, bool>
298	insert(_Pair&& __x)
299	{
300	  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
301	  auto __base_ret= _Base::insert(std::forward<_Pair>(__x));
302	  return std::make_pair(iterator(__base_ret.first, this),
303				__base_ret.second);
304	}
305#endif
306
307#if __cplusplus >= 201103L
308      void
309      insert(std::initializer_list<value_type> __list)
310      { insert(__list.begin(), __list.end()); }
311#endif
312
313      iterator
314#if __cplusplus >= 201103L
315      insert(const_iterator __pos, const value_type& __x)
316#else
317      insert(iterator __pos, const value_type& __x)
318#endif
319      {
320	size_type size_before = this->size();
321	_Base_iterator __res = _Base::insert(__pos.base(), __x);
322
323	__profcxx_map2umap_insert(this->_M_map2umap_info,
324		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
325	return iterator(__res, this);
326      }
327
328#if __cplusplus >= 201103L
329      template<typename _Pair, typename = typename
330	       std::enable_if<std::is_constructible<value_type,
331						    _Pair&&>::value>::type>
332	iterator
333	insert(const_iterator __pos, _Pair&& __x)
334	{
335	  size_type size_before = this->size();
336	  auto __res = _Base::insert(__pos.base(), std::forward<_Pair>(__x));
337
338	  __profcxx_map2umap_insert(this->_M_map2umap_info,
339		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
340	  return iterator(__res, this);
341      }
342#endif
343
344      template<typename _InputIterator>
345	void
346	insert(_InputIterator __first, _InputIterator __last)
347	{
348	  for (; __first != __last; ++__first)
349	    insert(*__first);
350	}
351
352#if __cplusplus >= 201103L
353      iterator
354      erase(const_iterator __pos)
355      {
356	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
357	return iterator(_Base::erase(__pos.base()), this);
358      }
359
360      iterator
361      erase(iterator __pos)
362      {
363	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
364	return iterator(_Base::erase(__pos.base()), this);
365      }
366#else
367      void
368      erase(iterator __pos)
369      {
370	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
371	_Base::erase(__pos.base());
372      }
373#endif
374
375      size_type
376      erase(const key_type& __x)
377      {
378	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
379	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
380	return _Base::erase(__x);
381      }
382
383#if __cplusplus >= 201103L
384      iterator
385      erase(const_iterator __first, const_iterator __last)
386      {
387	if (__first != __last)
388	  {
389	    iterator __ret;
390	    for (; __first != __last;)
391	      __ret = erase(__first++);
392	    return __ret;
393	  }
394	else
395	  return iterator(_Base::erase(__first.base(), __last.base()), this);
396      }
397#else
398      void
399      erase(iterator __first, iterator __last)
400      {
401	for (; __first != __last;)
402	  erase(__first++);
403      }
404#endif
405
406      void
407      swap(map& __x)
408      _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
409      {
410	_Base::swap(__x);
411	this->_M_swap(__x);
412      }
413
414      void
415      clear() _GLIBCXX_NOEXCEPT
416      {
417	this->_M_profile_destruct();
418	_Base::clear();
419	this->_M_profile_construct();
420      }
421
422      // 23.3.1.3 map operations:
423      iterator
424      find(const key_type& __x)
425      {
426	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
427	return iterator(_Base::find(__x), this);
428      }
429
430#if __cplusplus > 201103L
431      template<typename _Kt,
432	       typename _Req =
433		 typename __has_is_transparent<_Compare, _Kt>::type>
434	iterator
435	find(const _Kt& __x)
436	{
437	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
438	  return { _Base::find(__x), this };
439	}
440#endif
441
442      const_iterator
443      find(const key_type& __x) const
444      {
445	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
446	return const_iterator(_Base::find(__x), this);
447      }
448
449#if __cplusplus > 201103L
450      template<typename _Kt,
451	       typename _Req =
452		 typename __has_is_transparent<_Compare, _Kt>::type>
453	const_iterator
454	find(const _Kt& __x) const
455	{
456	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
457	  return { _Base::find(__x), this };
458	}
459#endif
460
461      size_type
462      count(const key_type& __x) const
463      {
464	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
465	return _Base::count(__x);
466      }
467
468#if __cplusplus > 201103L
469      template<typename _Kt,
470	       typename _Req =
471		 typename __has_is_transparent<_Compare, _Kt>::type>
472	size_type
473	count(const _Kt& __x) const
474	{
475	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
476	  return _Base::count(__x);
477	}
478#endif
479
480      iterator
481      lower_bound(const key_type& __x)
482      {
483	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
484	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
485	return iterator(_Base::lower_bound(__x), this);
486      }
487
488#if __cplusplus > 201103L
489      template<typename _Kt,
490	       typename _Req =
491		 typename __has_is_transparent<_Compare, _Kt>::type>
492	iterator
493	lower_bound(const _Kt& __x)
494	{
495	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
496	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
497	  return { _Base::lower_bound(__x), this };
498	}
499#endif
500
501      const_iterator
502      lower_bound(const key_type& __x) const
503      {
504	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
505	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
506	return const_iterator(_Base::lower_bound(__x), this);
507      }
508
509#if __cplusplus > 201103L
510      template<typename _Kt,
511	       typename _Req =
512		 typename __has_is_transparent<_Compare, _Kt>::type>
513	const_iterator
514	lower_bound(const _Kt& __x) const
515	{
516	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
517	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
518	  return { _Base::lower_bound(__x), this };
519	}
520#endif
521
522      iterator
523      upper_bound(const key_type& __x)
524      {
525	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
526	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
527	return iterator(_Base::upper_bound(__x), this);
528      }
529
530#if __cplusplus > 201103L
531      template<typename _Kt,
532	       typename _Req =
533		 typename __has_is_transparent<_Compare, _Kt>::type>
534	iterator
535	upper_bound(const _Kt& __x)
536	{
537	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
538	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
539	  return { _Base::upper_bound(__x), this };
540	}
541#endif
542
543      const_iterator
544      upper_bound(const key_type& __x) const
545      {
546	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
547	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
548	return const_iterator(_Base::upper_bound(__x), this);
549      }
550
551#if __cplusplus > 201103L
552      template<typename _Kt,
553	       typename _Req =
554		 typename __has_is_transparent<_Compare, _Kt>::type>
555	const_iterator
556	upper_bound(const _Kt& __x) const
557	{
558	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
559	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
560	  return { _Base::upper_bound(__x), this };
561	}
562#endif
563
564      std::pair<iterator,iterator>
565      equal_range(const key_type& __x)
566      {
567	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
568	std::pair<_Base_iterator, _Base_iterator> __base_ret
569	  = _Base::equal_range(__x);
570	return std::make_pair(iterator(__base_ret.first, this),
571			      iterator(__base_ret.second, this));
572      }
573
574#if __cplusplus > 201103L
575      template<typename _Kt,
576	       typename _Req =
577		 typename __has_is_transparent<_Compare, _Kt>::type>
578	std::pair<iterator, iterator>
579	equal_range(const _Kt& __x)
580	{
581	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
582	  auto __res = _Base::equal_range(__x);
583	  return { { __res.first, this }, { __res.second, this } };
584	}
585#endif
586
587      std::pair<const_iterator,const_iterator>
588      equal_range(const key_type& __x) const
589      {
590	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
591	std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
592	  = _Base::equal_range(__x);
593	return std::make_pair(const_iterator(__base_ret.first, this),
594			      const_iterator(__base_ret.second, this));
595      }
596
597#if __cplusplus > 201103L
598      template<typename _Kt,
599	       typename _Req =
600		 typename __has_is_transparent<_Compare, _Kt>::type>
601	std::pair<const_iterator, const_iterator>
602	equal_range(const _Kt& __x) const
603	{
604	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
605	  auto __res = _Base::equal_range(__x);
606	  return { { __res.first, this }, { __res.second, this } };
607	}
608#endif
609
610      _Base&
611      _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
612
613      const _Base&
614      _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
615
616    private:
617      /** If hint is used we consider that the map and unordered_map
618       * operations have equivalent insertion cost so we do not update metrics
619       * about it.
620       * Note that to find out if hint has been used is libstdc++
621       * implementation dependent.
622       */
623      bool
624      _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
625      {
626	return (__hint == __res
627		|| (__hint == _M_base().end() && ++__res == _M_base().end())
628		|| (__hint != _M_base().end() && (++__hint == __res
629						  || ++__res == --__hint)));
630      }
631
632
633      template<typename _K1, typename _T1, typename _C1, typename _A1>
634        friend bool
635        operator==(const map<_K1, _T1, _C1, _A1>&,
636		   const map<_K1, _T1, _C1, _A1>&);
637
638      template<typename _K1, typename _T1, typename _C1, typename _A1>
639        friend bool
640        operator<(const map<_K1, _T1, _C1, _A1>&,
641		  const map<_K1, _T1, _C1, _A1>&);
642    };
643
644  template<typename _Key, typename _Tp,
645	   typename _Compare, typename _Allocator>
646    inline bool
647    operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
648	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
649    {
650      __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
651      __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
652      return __lhs._M_base() == __rhs._M_base();
653    }
654
655  template<typename _Key, typename _Tp,
656	   typename _Compare, typename _Allocator>
657    inline bool
658    operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
659	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
660    {
661      __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
662      __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
663      return __lhs._M_base() < __rhs._M_base();
664    }
665
666  template<typename _Key, typename _Tp,
667	   typename _Compare, typename _Allocator>
668    inline bool
669    operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
670	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
671    { return !(__lhs == __rhs); }
672
673  template<typename _Key, typename _Tp,
674	   typename _Compare, typename _Allocator>
675    inline bool
676    operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
677	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
678    { return !(__rhs < __lhs); }
679
680  template<typename _Key, typename _Tp,
681	   typename _Compare, typename _Allocator>
682    inline bool
683    operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
684	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
685    { return !(__lhs < __rhs); }
686
687  template<typename _Key, typename _Tp,
688	   typename _Compare, typename _Allocator>
689    inline bool
690    operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
691	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
692    { return __rhs < __lhs; }
693
694  template<typename _Key, typename _Tp,
695	   typename _Compare, typename _Allocator>
696    inline void
697    swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
698	 map<_Key, _Tp, _Compare, _Allocator>& __rhs)
699    _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
700    { __lhs.swap(__rhs); }
701
702} // namespace __profile
703} // namespace std
704
705#endif
706