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