libstdc++
profile/list
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 
36 namespace std _GLIBCXX_VISIBILITY(default)
37 {
38 namespace __profile
39 {
40  /** @brief List wrapper with performance instrumentation. */
41 template<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