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