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