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