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