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