1// Profiling vector 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 along
21// with this library; see the file COPYING3.  If not see
22// <http://www.gnu.org/licenses/>.
23
24/** @file profile/vector
25 *  This file is a GNU profile extension to the Standard C++ Library.
26 */
27
28#ifndef _GLIBCXX_PROFILE_VECTOR
29#define _GLIBCXX_PROFILE_VECTOR 1
30
31#include <vector>
32#include <utility>
33#include <profile/base.h>
34#include <profile/iterator_tracker.h>
35
36namespace std _GLIBCXX_VISIBILITY(default)
37{
38namespace __profile
39{
40  template<typename _Tp,
41	   typename _Allocator = std::allocator<_Tp> >
42    class vector
43    : public _GLIBCXX_STD_C::vector<_Tp, _Allocator>
44    {
45      typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base;
46
47      typedef typename _Base::iterator _Base_iterator;
48      typedef typename _Base::const_iterator _Base_const_iterator;
49
50#if __cplusplus >= 201103L
51      typedef __gnu_cxx::__alloc_traits<_Allocator>  _Alloc_traits;
52#endif
53
54    public:
55      typedef typename _Base::reference             reference;
56      typedef typename _Base::const_reference       const_reference;
57
58      typedef __iterator_tracker<_Base_iterator, vector>
59                                                    iterator;
60      typedef __iterator_tracker<_Base_const_iterator, vector>
61				                    const_iterator;
62
63      typedef typename _Base::size_type             size_type;
64      typedef typename _Base::difference_type       difference_type;
65
66      typedef _Tp				    value_type;
67      typedef _Allocator			    allocator_type;
68      typedef typename _Base::pointer               pointer;
69      typedef typename _Base::const_pointer         const_pointer;
70      typedef std::reverse_iterator<iterator>       reverse_iterator;
71      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
72
73      _Base&
74      _M_base() _GLIBCXX_NOEXCEPT { return *this; }
75
76      const _Base&
77      _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
78
79      // 23.2.4.1 construct/copy/destroy:
80
81      vector() _GLIBCXX_NOEXCEPT
82      : _Base()
83      {
84        __profcxx_vector_construct(this, this->capacity());
85        __profcxx_vector_construct2(this);
86      }
87
88      explicit
89      vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
90      : _Base(__a)
91      {
92        __profcxx_vector_construct(this, this->capacity());
93        __profcxx_vector_construct2(this);
94      }
95
96#if __cplusplus >= 201103L
97      explicit
98      vector(size_type __n, const _Allocator& __a = _Allocator())
99      : _Base(__n, __a)
100      {
101        __profcxx_vector_construct(this, this->capacity());
102        __profcxx_vector_construct2(this);
103      }
104
105      vector(size_type __n, const _Tp& __value,
106	     const _Allocator& __a = _Allocator())
107      :  _Base(__n, __value, __a)
108      {
109        __profcxx_vector_construct(this, this->capacity());
110        __profcxx_vector_construct2(this);
111      }
112#else
113      explicit
114      vector(size_type __n, const _Tp& __value = _Tp(),
115	     const _Allocator& __a = _Allocator())
116      : _Base(__n, __value, __a)
117      {
118        __profcxx_vector_construct(this, this->capacity());
119        __profcxx_vector_construct2(this);
120      }
121#endif
122
123#if __cplusplus >= 201103L
124      template<typename _InputIterator,
125	       typename = std::_RequireInputIter<_InputIterator>>
126#else
127      template<typename _InputIterator>
128#endif
129        vector(_InputIterator __first, _InputIterator __last,
130	       const _Allocator& __a = _Allocator())
131	: _Base(__first, __last, __a)
132        {
133	  __profcxx_vector_construct(this, this->capacity());
134	  __profcxx_vector_construct2(this);
135	}
136
137      vector(const vector& __x)
138      : _Base(__x)
139      {
140        __profcxx_vector_construct(this, this->capacity());
141        __profcxx_vector_construct2(this);
142      }
143
144      /// Construction from a release-mode vector
145      vector(const _Base& __x)
146      : _Base(__x)
147      {
148        __profcxx_vector_construct(this, this->capacity());
149        __profcxx_vector_construct2(this);
150      }
151
152#if __cplusplus >= 201103L
153      vector(vector&& __x) noexcept
154      : _Base(std::move(__x))
155      {
156        __profcxx_vector_construct(this, this->capacity());
157        __profcxx_vector_construct2(this);
158      }
159
160      vector(const _Base& __x, const _Allocator& __a)
161      : _Base(__x, __a)
162      {
163        __profcxx_vector_construct(this, this->capacity());
164        __profcxx_vector_construct2(this);
165      }
166
167      vector(vector&& __x, const _Allocator& __a)
168      : _Base(std::move(__x), __a)
169      {
170        __profcxx_vector_construct(this, this->capacity());
171        __profcxx_vector_construct2(this);
172      }
173
174      vector(initializer_list<value_type> __l,
175	     const allocator_type& __a = allocator_type())
176      : _Base(__l, __a) { }
177#endif
178
179      ~vector() _GLIBCXX_NOEXCEPT
180      {
181        __profcxx_vector_destruct(this, this->capacity(), this->size());
182        __profcxx_vector_destruct2(this);
183      }
184
185      vector&
186      operator=(const vector& __x)
187      {
188        static_cast<_Base&>(*this) = __x;
189        return *this;
190      }
191
192#if __cplusplus >= 201103L
193      vector&
194      operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
195      {
196	__profcxx_vector_destruct(this, this->capacity(), this->size());
197	__profcxx_vector_destruct2(this);
198	static_cast<_Base&>(*this) = std::move(__x);
199	return *this;
200      }
201
202      vector&
203      operator=(initializer_list<value_type> __l)
204      {
205	static_cast<_Base&>(*this) = __l;
206	return *this;
207      }
208#endif
209
210      using _Base::assign;
211      using _Base::get_allocator;
212
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      { return iterator(_Base::end(), this); }
226
227      const_iterator
228      end() const _GLIBCXX_NOEXCEPT
229      { return const_iterator(_Base::end(), this); }
230
231      reverse_iterator
232      rbegin() _GLIBCXX_NOEXCEPT
233      { return reverse_iterator(end()); }
234
235      const_reverse_iterator
236      rbegin() const _GLIBCXX_NOEXCEPT
237      { return const_reverse_iterator(end()); }
238
239      reverse_iterator
240      rend() _GLIBCXX_NOEXCEPT
241      { return reverse_iterator(begin()); }
242
243      const_reverse_iterator
244      rend() const _GLIBCXX_NOEXCEPT
245      { return const_reverse_iterator(begin()); }
246
247#if __cplusplus >= 201103L
248      const_iterator
249      cbegin() const noexcept
250      { return const_iterator(_Base::begin(), this); }
251
252      const_iterator
253      cend() const noexcept
254      { return const_iterator(_Base::end(), this); }
255
256      const_reverse_iterator
257      crbegin() const noexcept
258      { return const_reverse_iterator(end()); }
259
260      const_reverse_iterator
261      crend() const noexcept
262      { return const_reverse_iterator(begin()); }
263#endif
264
265      // 23.2.4.2 capacity:
266      using _Base::size;
267      using _Base::max_size;
268
269#if __cplusplus >= 201103L
270      void
271      resize(size_type __sz)
272      {
273        __profcxx_vector_invalid_operator(this);
274        _M_profile_resize(this, this->capacity(), __sz);
275        _Base::resize(__sz);
276      }
277
278      void
279      resize(size_type __sz, const _Tp& __c)
280      {
281        __profcxx_vector_invalid_operator(this);
282        _M_profile_resize(this, this->capacity(), __sz);
283        _Base::resize(__sz, __c);
284      }
285#else
286      void
287      resize(size_type __sz, _Tp __c = _Tp())
288      {
289        __profcxx_vector_invalid_operator(this);
290        _M_profile_resize(this, this->capacity(), __sz);
291        _Base::resize(__sz, __c);
292      }
293#endif
294
295#if __cplusplus >= 201103L
296      using _Base::shrink_to_fit;
297#endif
298
299      using _Base::empty;
300
301      // element access:
302      reference
303      operator[](size_type __n) _GLIBCXX_NOEXCEPT
304      {
305        __profcxx_vector_invalid_operator(this);
306        return _M_base()[__n];
307      }
308      const_reference
309      operator[](size_type __n) const _GLIBCXX_NOEXCEPT
310      {
311        __profcxx_vector_invalid_operator(this);
312        return _M_base()[__n];
313      }
314
315      using _Base::at;
316
317      reference
318      front() _GLIBCXX_NOEXCEPT
319      {
320        return _Base::front();
321      }
322
323      const_reference
324      front() const _GLIBCXX_NOEXCEPT
325      {
326	return _Base::front();
327      }
328
329      reference
330      back() _GLIBCXX_NOEXCEPT
331      {
332	return _Base::back();
333      }
334
335      const_reference
336      back() const _GLIBCXX_NOEXCEPT
337      {
338	return _Base::back();
339      }
340
341      // _GLIBCXX_RESOLVE_LIB_DEFECTS
342      // DR 464. Suggestion for new member functions in standard containers.
343      using _Base::data;
344
345      // 23.2.4.3 modifiers:
346      void
347      push_back(const _Tp& __x)
348      {
349        size_type __old_size = this->capacity();
350	_Base::push_back(__x);
351        _M_profile_resize(this, __old_size, this->capacity());
352      }
353
354#if __cplusplus >= 201103L
355      void
356      push_back(_Tp&& __x)
357      {
358        size_type __old_size = this->capacity();
359        _Base::push_back(std::move(__x));
360        _M_profile_resize(this, __old_size, this->capacity());
361      }
362
363#endif
364
365      iterator
366#if __cplusplus >= 201103L
367      insert(const_iterator __position, const _Tp& __x)
368#else
369      insert(iterator __position, const _Tp& __x)
370#endif
371      {
372        __profcxx_vector_insert(this, __position.base() - _Base::begin(),
373                                this->size());
374        size_type __old_size = this->capacity();
375	_Base_iterator __res = _Base::insert(__position.base(), __x);
376        _M_profile_resize(this, __old_size, this->capacity());
377	return iterator(__res, this);
378      }
379
380#if __cplusplus >= 201103L
381      iterator
382      insert(const_iterator __position, _Tp&& __x)
383      {
384        __profcxx_vector_insert(this, __position.base() - _Base::cbegin(),
385                                this->size());
386        size_type __old_size = this->capacity();
387	_Base_iterator __res = _Base::insert(__position.base(), __x);
388        _M_profile_resize(this, __old_size, this->capacity());
389	return iterator(__res, this);
390      }
391
392      template<typename... _Args>
393        iterator
394        emplace(const_iterator __position, _Args&&... __args)
395        {
396	  _Base_iterator __res = _Base::emplace(__position.base(),
397						std::forward<_Args>(__args)...);
398	  return iterator(__res, this);
399	}
400
401      iterator
402      insert(const_iterator __position, initializer_list<value_type> __l)
403      { return this->insert(__position, __l.begin(), __l.end()); }
404#endif
405
406#if __cplusplus >= 201103L
407      void
408      swap(vector&& __x)
409      {
410        _Base::swap(__x);
411      }
412#endif
413
414      void
415      swap(vector& __x)
416#if __cplusplus >= 201103L
417      noexcept(_Alloc_traits::_S_nothrow_swap())
418#endif
419      {
420        _Base::swap(__x);
421      }
422
423#if __cplusplus >= 201103L
424      iterator
425      insert(const_iterator __position, size_type __n, const _Tp& __x)
426      {
427        __profcxx_vector_insert(this, __position.base() - _Base::cbegin(),
428                                this->size());
429        size_type __old_size = this->capacity();
430        _Base_iterator __res = _Base::insert(__position, __n, __x);
431        _M_profile_resize(this, __old_size, this->capacity());
432	return iterator(__res, this);
433      }
434#else
435      void
436      insert(iterator __position, size_type __n, const _Tp& __x)
437      {
438        __profcxx_vector_insert(this, __position.base() - _Base::begin(),
439                                this->size());
440        size_type __old_size = this->capacity();
441        _Base::insert(__position, __n, __x);
442        _M_profile_resize(this, __old_size, this->capacity());
443      }
444#endif
445
446#if __cplusplus >= 201103L
447      template<typename _InputIterator,
448	       typename = std::_RequireInputIter<_InputIterator>>
449	iterator
450	insert(const_iterator __position,
451	       _InputIterator __first, _InputIterator __last)
452        {
453	  __profcxx_vector_insert(this, __position.base() - _Base::cbegin(),
454				  this->size());
455	  size_type __old_size = this->capacity();
456	  _Base_iterator __res = _Base::insert(__position, __first, __last);
457	  _M_profile_resize(this, __old_size, this->capacity());
458	  return iterator(__res, this);
459	}
460#else
461      template<typename _InputIterator>
462	void
463	insert(iterator __position,
464	       _InputIterator __first, _InputIterator __last)
465        {
466	  __profcxx_vector_insert(this, __position.base() - _Base::begin(),
467				  this->size());
468	  size_type __old_size = this->capacity();
469	  _Base::insert(__position, __first, __last);
470	  _M_profile_resize(this, __old_size, this->capacity());
471	}
472#endif
473
474      iterator
475#if __cplusplus >= 201103L
476      erase(const_iterator __position)
477#else
478      erase(iterator __position)
479#endif
480      {
481	_Base_iterator __res = _Base::erase(__position.base());
482	return iterator(__res, this);
483      }
484
485      iterator
486#if __cplusplus >= 201103L
487      erase(const_iterator __first, const_iterator __last)
488#else
489      erase(iterator __first, iterator __last)
490#endif
491      {
492	// _GLIBCXX_RESOLVE_LIB_DEFECTS
493	// 151. can't currently clear() empty container
494	_Base_iterator __res = _Base::erase(__first.base(), __last.base());
495	return iterator(__res, this);
496      }
497
498      void
499      clear() _GLIBCXX_NOEXCEPT
500      {
501        __profcxx_vector_destruct(this, this->capacity(), this->size());
502        __profcxx_vector_destruct2(this);
503        _Base::clear();
504      }
505
506      inline void _M_profile_find() const
507      {
508        __profcxx_vector_find(this, size());
509      }
510
511      inline void _M_profile_iterate(int __rewind = 0) const
512      {
513        __profcxx_vector_iterate(this);
514      }
515
516    private:
517      void _M_profile_resize(void* obj, size_type __old_size,
518                             size_type __new_size)
519      {
520        if (__old_size < __new_size) {
521          __profcxx_vector_resize(this, this->size(), __new_size);
522          __profcxx_vector_resize2(this, this->size(), __new_size);
523        }
524      }
525    };
526
527  template<typename _Tp, typename _Alloc>
528    inline bool
529    operator==(const vector<_Tp, _Alloc>& __lhs,
530           const vector<_Tp, _Alloc>& __rhs)
531    { return __lhs._M_base() == __rhs._M_base(); }
532
533  template<typename _Tp, typename _Alloc>
534    inline bool
535    operator!=(const vector<_Tp, _Alloc>& __lhs,
536           const vector<_Tp, _Alloc>& __rhs)
537    { return __lhs._M_base() != __rhs._M_base(); }
538
539  template<typename _Tp, typename _Alloc>
540    inline bool
541    operator<(const vector<_Tp, _Alloc>& __lhs,
542          const vector<_Tp, _Alloc>& __rhs)
543    { return __lhs._M_base() < __rhs._M_base(); }
544
545  template<typename _Tp, typename _Alloc>
546    inline bool
547    operator<=(const vector<_Tp, _Alloc>& __lhs,
548           const vector<_Tp, _Alloc>& __rhs)
549    { return __lhs._M_base() <= __rhs._M_base(); }
550
551  template<typename _Tp, typename _Alloc>
552    inline bool
553    operator>=(const vector<_Tp, _Alloc>& __lhs,
554           const vector<_Tp, _Alloc>& __rhs)
555    { return __lhs._M_base() >= __rhs._M_base(); }
556
557  template<typename _Tp, typename _Alloc>
558    inline bool
559    operator>(const vector<_Tp, _Alloc>& __lhs,
560          const vector<_Tp, _Alloc>& __rhs)
561    { return __lhs._M_base() > __rhs._M_base(); }
562
563  template<typename _Tp, typename _Alloc>
564    inline void
565    swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
566    { __lhs.swap(__rhs); }
567
568#if __cplusplus >= 201103L
569  template<typename _Tp, typename _Alloc>
570    inline void
571    swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs)
572    { __lhs.swap(__rhs); }
573
574  template<typename _Tp, typename _Alloc>
575    inline void
576    swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs)
577    { __lhs.swap(__rhs); }
578#endif
579
580} // namespace __profile
581
582#if __cplusplus >= 201103L
583  // DR 1182.
584  /// std::hash specialization for vector<bool>.
585  template<typename _Alloc>
586    struct hash<__profile::vector<bool, _Alloc>>
587    : public __hash_base<size_t, __profile::vector<bool, _Alloc>>
588    {
589      size_t
590      operator()(const __profile::vector<bool, _Alloc>& __b) const noexcept
591      { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()
592	  (__b._M_base()); }
593    };
594#endif
595
596} // namespace std
597
598#endif
599