1// Profiling set implementation -*- C++ -*-
2
3// Copyright (C) 2009-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 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#if __cplusplus >= 201103L
227	noexcept( noexcept(declval<_Base>().swap(__x)) )
228#endif
229      {
230	_Base::swap(__x);
231	this->_M_swap(__x);
232      }
233
234      // modifiers:
235#if __cplusplus >= 201103L
236      template<typename... _Args>
237	std::pair<iterator, bool>
238	emplace(_Args&&... __args)
239	{
240	  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
241	  auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...);
242	  return std::make_pair(iterator(__base_ret.first, this),
243				__base_ret.second);
244	}
245
246      template<typename... _Args>
247	iterator
248	emplace_hint(const_iterator __pos, _Args&&... __args)
249	{
250	  auto size_before = this->size();
251	  auto __res
252	    = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
253	  __profcxx_map2umap_insert(this->_M_map2umap_info,
254		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
255	  return iterator(__res, this);
256	}
257#endif
258
259      std::pair<iterator, bool>
260      insert(const value_type& __x)
261      {
262	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
263	std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x);
264	return std::make_pair(iterator(__base_ret.first, this),
265			      __base_ret.second);
266      }
267
268#if __cplusplus >= 201103L
269      std::pair<iterator, bool>
270      insert(value_type&& __x)
271      {
272	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
273	std::pair<_Base_iterator, bool> __base_ret
274	  = _Base::insert(std::move(__x));
275	return std::make_pair(iterator(__base_ret.first, this),
276			      __base_ret.second);
277      }
278#endif
279
280      iterator
281      insert(const_iterator __pos, const value_type& __x)
282      {
283	size_type size_before = this->size();
284	_Base_iterator __res = _Base::insert(__pos.base(), __x);
285	__profcxx_map2umap_insert(this->_M_map2umap_info,
286		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
287	return iterator(__res, this);
288      }
289
290#if __cplusplus >= 201103L
291      iterator
292      insert(const_iterator __pos, value_type&& __x)
293      { return iterator(_Base::insert(__pos.base(), std::move(__x)), this); }
294#endif
295
296      template<typename _InputIterator>
297	void
298	insert(_InputIterator __first, _InputIterator __last)
299	{
300	  for (; __first != __last; ++__first)
301	    insert(*__first);
302	}
303
304#if __cplusplus >= 201103L
305      void
306      insert(initializer_list<value_type> __l)
307      { insert(__l.begin(), __l.end()); }
308#endif
309
310#if __cplusplus >= 201103L
311      iterator
312      erase(const_iterator __pos)
313      {
314	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
315	return iterator(_Base::erase(__pos.base()), this);
316      }
317#else
318      void
319      erase(iterator __pos)
320      {
321	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
322	_Base::erase(__pos.base());
323      }
324#endif
325
326      size_type
327      erase(const key_type& __x)
328      {
329	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
330	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
331	return _Base::erase(__x);
332      }
333
334#if __cplusplus >= 201103L
335      iterator
336      erase(const_iterator __first, const_iterator __last)
337      {
338	if (__first != __last)
339	  {
340	    iterator __ret;
341	    for (; __first != __last;)
342	      __ret = erase(__first++);
343	    return __ret;
344	  }
345
346	return iterator(_Base::erase(__first.base(), __last.base()), this);
347      }
348#else
349      void
350      erase(iterator __first, iterator __last)
351      {
352	for (; __first != __last;)
353	     erase(__first++);
354      }
355#endif
356
357      void
358      clear() _GLIBCXX_NOEXCEPT
359      {
360	this->_M_profile_destruct();
361	_Base::clear();
362	this->_M_profile_construct();
363      }
364
365      size_type
366      count(const key_type& __x) const
367      {
368	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
369	return _Base::count(__x);
370      }
371
372      // set operations:
373      iterator
374      find(const key_type& __x)
375      {
376	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
377	return iterator(_Base::find(__x), this);
378      }
379
380      const_iterator
381      find(const key_type& __x) const
382      {
383	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
384	return const_iterator(_Base::find(__x), this);
385      }
386
387      iterator
388      lower_bound(const key_type& __x)
389      {
390	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
391	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
392	return iterator(_Base::lower_bound(__x), this);
393      }
394
395      const_iterator
396      lower_bound(const key_type& __x) const
397      {
398	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
399	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
400	return const_iterator(_Base::lower_bound(__x), this);
401      }
402
403      iterator
404      upper_bound(const key_type& __x)
405      {
406	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
407	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
408	return iterator(_Base::upper_bound(__x), this);
409      }
410
411      const_iterator
412      upper_bound(const key_type& __x) const
413      {
414	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
415	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
416	return const_iterator(_Base::upper_bound(__x), this);
417      }
418
419      std::pair<iterator, iterator>
420      equal_range(const key_type& __x)
421      {
422	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
423	std::pair<_Base_iterator, _Base_iterator> __base_ret
424	  = _Base::equal_range(__x);
425	return std::make_pair(iterator(__base_ret.first, this),
426			      iterator(__base_ret.second, this));
427      }
428
429      std::pair<const_iterator, const_iterator>
430      equal_range(const key_type& __x) const
431      {
432	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
433	std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
434	  = _Base::equal_range(__x);
435	return std::make_pair(const_iterator(__base_ret.first, this),
436			      const_iterator(__base_ret.second, this));
437      }
438
439      _Base&
440      _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
441
442      const _Base&
443      _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
444
445    private:
446      /** If hint is used we consider that the map and unordered_map
447       * operations have equivalent insertion cost so we do not update metrics
448       * about it.
449       * Note that to find out if hint has been used is libstdc++
450       * implementation dependent.
451       */
452      bool
453      _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
454      {
455	return (__hint == __res
456		|| (__hint == _M_base().end() && ++__res == _M_base().end())
457		|| (__hint != _M_base().end() && (++__hint == __res
458						  || ++__res == --__hint)));
459      }
460
461      template<typename _K1, typename _C1, typename _A1>
462	friend bool
463	operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
464
465      template<typename _K1, typename _C1, typename _A1>
466	friend bool
467	operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
468    };
469
470  template<typename _Key, typename _Compare, typename _Allocator>
471    inline bool
472    operator==(const set<_Key, _Compare, _Allocator>& __lhs,
473	       const set<_Key, _Compare, _Allocator>& __rhs)
474    {
475      __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
476      __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
477      return __lhs._M_base() == __rhs._M_base();
478    }
479
480  template<typename _Key, typename _Compare, typename _Allocator>
481    inline bool
482    operator<(const set<_Key, _Compare, _Allocator>& __lhs,
483	      const set<_Key, _Compare, _Allocator>& __rhs)
484    {
485      __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
486      __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
487      return __lhs._M_base() < __rhs._M_base();
488    }
489
490  template<typename _Key, typename _Compare, typename _Allocator>
491    inline bool
492    operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
493	       const set<_Key, _Compare, _Allocator>& __rhs)
494    { return !(__lhs == __rhs); }
495
496  template<typename _Key, typename _Compare, typename _Allocator>
497    inline bool
498    operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
499	       const set<_Key, _Compare, _Allocator>& __rhs)
500    { return !(__rhs < __lhs); }
501
502  template<typename _Key, typename _Compare, typename _Allocator>
503    inline bool
504    operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
505	       const set<_Key, _Compare, _Allocator>& __rhs)
506    { return !(__lhs < __rhs); }
507
508  template<typename _Key, typename _Compare, typename _Allocator>
509    inline bool
510    operator>(const set<_Key, _Compare, _Allocator>& __lhs,
511	      const set<_Key, _Compare, _Allocator>& __rhs)
512    { return __rhs < __lhs; }
513
514  template<typename _Key, typename _Compare, typename _Allocator>
515    void
516    swap(set<_Key, _Compare, _Allocator>& __x,
517	 set<_Key, _Compare, _Allocator>& __y)
518    { return __x.swap(__y); }
519
520} // namespace __profile
521} // namespace std
522
523#endif
524