1 // Profiling set implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2018 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 
35 namespace std _GLIBCXX_VISIBILITY(default)
36 {
37 namespace __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