1// Profiling list 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/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#endif
149
150      explicit
151      list(const _Allocator& __a) _GLIBCXX_NOEXCEPT
152      : _Base(__a) { }
153
154#if __cplusplus >= 201103L
155      explicit
156      list(size_type __n)
157      : _Base(__n) { }
158
159      list(size_type __n, const _Tp& __value,
160	   const _Allocator& __a = _Allocator())
161      : _Base(__n, __value, __a) { }
162#else
163      explicit
164      list(size_type __n, const _Tp& __value = _Tp(),
165	   const _Allocator& __a = _Allocator())
166      : _Base(__n, __value, __a) { }
167#endif
168
169#if __cplusplus >= 201103L
170      template<typename _InputIterator,
171	       typename = std::_RequireInputIter<_InputIterator>>
172#else
173      template<class _InputIterator>
174#endif
175      list(_InputIterator __first, _InputIterator __last,
176	   const _Allocator& __a = _Allocator())
177      : _Base(__first, __last, __a) { }
178
179      list(const _Base& __x)
180      : _Base(__x) { }
181
182#if __cplusplus < 201103L
183      list&
184      operator=(const list& __x)
185      {
186	this->_M_profile_destruct();
187	_M_base() = __x;
188	this->_M_profile_construct();
189	return *this;
190      }
191#else
192      list&
193      operator=(const list&) = default;
194
195      list&
196      operator=(list&&) = default;
197
198      list&
199      operator=(initializer_list<value_type> __l)
200      {
201	this->_M_profile_destruct();
202	_M_base() = __l;
203	this->_M_profile_construct();
204	return *this;
205      }
206#endif
207
208      // iterators:
209      iterator
210      begin() _GLIBCXX_NOEXCEPT
211      { return iterator(_Base::begin(), this); }
212
213      const_iterator
214      begin() const _GLIBCXX_NOEXCEPT
215      { return const_iterator(_Base::begin(), this); }
216
217      iterator
218      end() _GLIBCXX_NOEXCEPT
219      {
220	__profcxx_list2slist_rewind(this->_M_list2slist_info);
221	return iterator(_Base::end(), this);
222      }
223
224      const_iterator
225      end() const _GLIBCXX_NOEXCEPT
226      {
227	__profcxx_list2slist_rewind(this->_M_list2slist_info);
228	return const_iterator(_Base::end(), this);
229      }
230
231      reverse_iterator
232      rbegin() _GLIBCXX_NOEXCEPT
233      {
234	__profcxx_list2slist_rewind(this->_M_list2slist_info);
235	return reverse_iterator(end());
236      }
237
238      const_reverse_iterator
239      rbegin() const _GLIBCXX_NOEXCEPT
240      {
241	__profcxx_list2slist_rewind(this->_M_list2slist_info);
242	return const_reverse_iterator(end());
243      }
244
245      reverse_iterator
246      rend() _GLIBCXX_NOEXCEPT
247      { return reverse_iterator(begin()); }
248
249      const_reverse_iterator
250      rend() const _GLIBCXX_NOEXCEPT
251      { return const_reverse_iterator(begin()); }
252
253#if __cplusplus >= 201103L
254      const_iterator
255      cbegin() const noexcept
256      { return const_iterator(_Base::cbegin(), this); }
257
258      const_iterator
259      cend() const noexcept
260      { return const_iterator(_Base::cend(), this); }
261
262      const_reverse_iterator
263      crbegin() const noexcept
264      { return const_reverse_iterator(end()); }
265
266      const_reverse_iterator
267      crend() const noexcept
268      { return const_reverse_iterator(begin()); }
269#endif
270
271      // 23.2.2.2 capacity:
272      reference
273      back() _GLIBCXX_NOEXCEPT
274      {
275	__profcxx_list2slist_rewind(this->_M_list2slist_info);
276	return _Base::back();
277      }
278
279      const_reference
280      back() const _GLIBCXX_NOEXCEPT
281      {
282	__profcxx_list2slist_rewind(this->_M_list2slist_info);
283	return _Base::back();
284      }
285
286      // 23.2.2.3 modifiers:
287      void
288      push_front(const value_type& __x)
289      {
290	__profcxx_list2vector_invalid_operator(this->_M_list2vector_info);
291	__profcxx_list2slist_operation(this->_M_list2slist_info);
292	_Base::push_front(__x);
293      }
294
295      void
296      pop_front() _GLIBCXX_NOEXCEPT
297      {
298	__profcxx_list2slist_operation(this->_M_list2slist_info);
299	_Base::pop_front();
300      }
301
302      void
303      pop_back() _GLIBCXX_NOEXCEPT
304      {
305	_Base::pop_back();
306	__profcxx_list2slist_rewind(this->_M_list2slist_info);
307      }
308
309#if __cplusplus >= 201103L
310      template<typename... _Args>
311	iterator
312	emplace(const_iterator __position, _Args&&... __args)
313	{
314	  return iterator(_Base::emplace(__position.base(),
315					 std::forward<_Args>(__args)...),
316			  this);
317	}
318#endif
319
320      iterator
321#if __cplusplus >= 201103L
322      insert(const_iterator __pos, const _Tp& __x)
323#else
324      insert(iterator __pos, const _Tp& __x)
325#endif
326      {
327	_M_profile_insert(__pos, this->size());
328	return iterator(_Base::insert(__pos.base(), __x), this);
329      }
330
331#if __cplusplus >= 201103L
332      iterator
333      insert(const_iterator __pos, _Tp&& __x)
334      {
335	_M_profile_insert(__pos, this->size());
336	return iterator(_Base::emplace(__pos.base(), std::move(__x)),
337			this);
338      }
339
340      iterator
341      insert(const_iterator __pos, initializer_list<value_type> __l)
342      {
343	_M_profile_insert(__pos, this->size());
344	return iterator(_Base::insert(__pos.base(), __l), this);
345      }
346#endif
347
348#if __cplusplus >= 201103L
349      iterator
350      insert(const_iterator __pos, size_type __n, const _Tp& __x)
351      {
352	_M_profile_insert(__pos, this->size());
353	return iterator(_Base::insert(__pos.base(), __n, __x), this);
354      }
355#else
356      void
357      insert(iterator __pos, size_type __n, const _Tp& __x)
358      {
359	_M_profile_insert(__pos, this->size());
360	_Base::insert(__pos.base(), __n, __x);
361      }
362#endif
363
364#if __cplusplus >= 201103L
365      template<typename _InputIterator,
366	       typename = std::_RequireInputIter<_InputIterator>>
367	iterator
368	insert(const_iterator __pos, _InputIterator __first,
369	       _InputIterator __last)
370	{
371	  _M_profile_insert(__pos, this->size());
372	  return iterator(_Base::insert(__pos.base(), __first, __last),
373			  this);
374	}
375#else
376      template<class _InputIterator>
377	void
378	insert(iterator __pos, _InputIterator __first,
379	       _InputIterator __last)
380	{
381	  _M_profile_insert(__pos, this->size());
382	  _Base::insert(__pos.base(), __first, __last);
383	}
384#endif
385
386      iterator
387#if __cplusplus >= 201103L
388      erase(const_iterator __pos) noexcept
389#else
390      erase(iterator __pos)
391#endif
392      {	return iterator(_Base::erase(__pos.base()), this); }
393
394      iterator
395#if __cplusplus >= 201103L
396      erase(const_iterator __pos, const_iterator __last) noexcept
397#else
398      erase(iterator __pos, iterator __last)
399#endif
400      {
401	// _GLIBCXX_RESOLVE_LIB_DEFECTS
402	// 151. can't currently clear() empty container
403	return iterator(_Base::erase(__pos.base(), __last.base()), this);
404      }
405
406      void
407      swap(list& __x)
408#if __cplusplus >= 201103L
409	noexcept( noexcept(declval<_Base>().swap(__x)) )
410#endif
411      {
412	_Base::swap(__x);
413	this->_M_swap(__x);
414      }
415
416      void
417      clear() _GLIBCXX_NOEXCEPT
418      {
419	this->_M_profile_destruct();
420	_Base::clear();
421	this->_M_profile_construct();
422      }
423
424      // 23.2.2.4 list operations:
425      void
426#if __cplusplus >= 201103L
427      splice(const_iterator __pos, list&& __x) noexcept
428#else
429      splice(iterator __pos, list& __x)
430#endif
431      { this->splice(__pos, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); }
432
433#if __cplusplus >= 201103L
434      void
435      splice(const_iterator __pos, list& __x) noexcept
436      { this->splice(__pos, std::move(__x)); }
437
438      void
439      splice(const_iterator __pos, list& __x, const_iterator __i)
440      { this->splice(__pos, std::move(__x), __i); }
441#endif
442
443      void
444#if __cplusplus >= 201103L
445      splice(const_iterator __pos, list&& __x, const_iterator __i) noexcept
446#else
447      splice(iterator __pos, list& __x, iterator __i)
448#endif
449      {
450	// We used to perform the splice_alloc check:  not anymore, redundant
451	// after implementing the relevant bits of N1599.
452
453	// _GLIBCXX_RESOLVE_LIB_DEFECTS
454	_Base::splice(__pos.base(), _GLIBCXX_MOVE(__x._M_base()),
455		      __i.base());
456      }
457
458      void
459#if __cplusplus >= 201103L
460      splice(const_iterator __pos, list&& __x, const_iterator __first,
461	     const_iterator __last) noexcept
462#else
463      splice(iterator __pos, list& __x, iterator __first,
464	     iterator __last)
465#endif
466      {
467	_Base::splice(__pos.base(), _GLIBCXX_MOVE(__x._M_base()),
468		      __first.base(), __last.base());
469      }
470
471#if __cplusplus >= 201103L
472      void
473      splice(const_iterator __pos, list& __x,
474	     const_iterator __first, const_iterator __last) noexcept
475      { this->splice(__pos, std::move(__x), __first, __last); }
476#endif
477
478      void
479      remove(const _Tp& __value)
480      {
481	for (iterator __x = begin(); __x != end(); )
482	  {
483	    if (*__x == __value)
484	      __x = erase(__x);
485	    else
486	      ++__x;
487	  }
488      }
489
490      template<class _Predicate>
491	void
492	remove_if(_Predicate __pred)
493	{
494	  for (iterator __x = begin(); __x != end(); )
495	    {
496	      __profcxx_list2slist_operation(this->_M_list2slist_info);
497	      if (__pred(*__x))
498		__x = erase(__x);
499	      else
500		++__x;
501	    }
502	}
503
504      void
505      unique()
506      {
507	iterator __first = begin();
508	iterator __last = end();
509	if (__first == __last)
510	  return;
511	iterator __next = __first;
512	while (++__next != __last)
513	  {
514	    __profcxx_list2slist_operation(this->_M_list2slist_info);
515	    if (*__first == *__next)
516	      erase(__next);
517	    else
518	      __first = __next;
519	    __next = __first;
520	  }
521      }
522
523      template<class _BinaryPredicate>
524	void
525	unique(_BinaryPredicate __binary_pred)
526	{
527	  iterator __first = begin();
528	  iterator __last = end();
529	  if (__first == __last)
530	    return;
531	  iterator __next = __first;
532	  while (++__next != __last)
533	    {
534	      __profcxx_list2slist_operation(this->_M_list2slist_info);
535	      if (__binary_pred(*__first, *__next))
536		erase(__next);
537	      else
538		__first = __next;
539	      __next = __first;
540	    }
541	}
542
543      void
544#if __cplusplus >= 201103L
545      merge(list&& __x)
546#else
547      merge(list& __x)
548#endif
549      { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); }
550
551#if __cplusplus >= 201103L
552      void
553      merge(list& __x)
554      { this->merge(std::move(__x)); }
555#endif
556
557      template<class _Compare>
558	void
559#if __cplusplus >= 201103L
560	merge(list&& __x, _Compare __comp)
561#else
562	merge(list& __x, _Compare __comp)
563#endif
564	{ _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); }
565
566#if __cplusplus >= 201103L
567      template<typename _Compare>
568	void
569	merge(list& __x, _Compare __comp)
570	{ this->merge(std::move(__x), __comp); }
571#endif
572
573      _Base&
574      _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
575
576      const _Base&
577      _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
578
579      void _M_profile_iterate(int __rewind = 0) const
580      {
581	__profcxx_list2slist_operation(this->_M_list2slist_info);
582	__profcxx_list2vector_iterate(this->_M_list2vector_info, __rewind);
583	if (__rewind)
584	  __profcxx_list2slist_rewind(this->_M_list2slist_info);
585      }
586
587    private:
588      size_type
589      _M_profile_insert(const_iterator __pos, size_type __size)
590      {
591	size_type __shift = 0;
592	typename _Base::const_iterator __it = __pos.base();
593	for (; __it != _Base::end(); ++__it)
594	  __shift++;
595	__profcxx_list2slist_rewind(this->_M_list2slist_info);
596	__profcxx_list2slist_operation(this->_M_list2slist_info);
597	__profcxx_list2vector_insert(this->_M_list2vector_info, __shift, __size);
598      }
599    };
600
601  template<typename _Tp, typename _Alloc>
602    inline bool
603    operator==(const list<_Tp, _Alloc>& __lhs,
604	       const list<_Tp, _Alloc>& __rhs)
605    { return __lhs._M_base() == __rhs._M_base(); }
606
607  template<typename _Tp, typename _Alloc>
608    inline bool
609    operator!=(const list<_Tp, _Alloc>& __lhs,
610	       const list<_Tp, _Alloc>& __rhs)
611    { return __lhs._M_base() != __rhs._M_base(); }
612
613  template<typename _Tp, typename _Alloc>
614    inline bool
615    operator<(const list<_Tp, _Alloc>& __lhs,
616	      const list<_Tp, _Alloc>& __rhs)
617    { return __lhs._M_base() < __rhs._M_base(); }
618
619  template<typename _Tp, typename _Alloc>
620    inline bool
621    operator<=(const list<_Tp, _Alloc>& __lhs,
622	       const list<_Tp, _Alloc>& __rhs)
623    { return __lhs._M_base() <= __rhs._M_base(); }
624
625  template<typename _Tp, typename _Alloc>
626    inline bool
627    operator>=(const list<_Tp, _Alloc>& __lhs,
628	       const list<_Tp, _Alloc>& __rhs)
629    { return __lhs._M_base() >= __rhs._M_base(); }
630
631  template<typename _Tp, typename _Alloc>
632    inline bool
633    operator>(const list<_Tp, _Alloc>& __lhs,
634	      const list<_Tp, _Alloc>& __rhs)
635    { return __lhs._M_base() > __rhs._M_base(); }
636
637  template<typename _Tp, typename _Alloc>
638    inline void
639    swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
640    { __lhs.swap(__rhs); }
641
642} // namespace __profile
643} // namespace std
644
645#endif
646