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