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