libstdc++
|
00001 // Profiling vector implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 // 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License along 00021 // with this library; see the file COPYING3. If not see 00022 // <http://www.gnu.org/licenses/>. 00023 00024 /** @file profile/vector 00025 * This file is a GNU profile extension to the Standard C++ Library. 00026 */ 00027 00028 #ifndef _GLIBCXX_PROFILE_VECTOR 00029 #define _GLIBCXX_PROFILE_VECTOR 1 00030 00031 #include <vector> 00032 #include <utility> 00033 #include <profile/base.h> 00034 #include <profile/iterator_tracker.h> 00035 00036 namespace std _GLIBCXX_VISIBILITY(default) 00037 { 00038 namespace __profile 00039 { 00040 template<typename _Vector> 00041 class _Vector_profile_pre 00042 { 00043 _Vector& 00044 _M_conjure() 00045 { return *static_cast<_Vector*>(this); } 00046 00047 public: 00048 #if __cplusplus >= 201103L 00049 _Vector_profile_pre() = default; 00050 _Vector_profile_pre(const _Vector_profile_pre&) = default; 00051 _Vector_profile_pre(_Vector_profile_pre&&) = default; 00052 00053 _Vector_profile_pre& 00054 operator=(const _Vector_profile_pre&) 00055 { _M_conjure()._M_profile_destruct(); } 00056 00057 _Vector_profile_pre& 00058 operator=(_Vector_profile_pre&&) noexcept 00059 { _M_conjure()._M_profile_destruct(); } 00060 #endif 00061 }; 00062 00063 template<typename _Vector> 00064 class _Vector_profile_post 00065 { 00066 _Vector& 00067 _M_conjure() 00068 { return *static_cast<_Vector*>(this); } 00069 00070 protected: 00071 __gnu_profile::__container_size_info* _M_size_info; 00072 __gnu_profile::__vector2list_info* _M_vect2list_info; 00073 00074 _Vector_profile_post() _GLIBCXX_NOEXCEPT 00075 { _M_profile_construct(); } 00076 00077 #if __cplusplus >= 201103L 00078 _Vector_profile_post(const _Vector_profile_post&) noexcept 00079 : _Vector_profile_post() { } 00080 _Vector_profile_post(_Vector_profile_post&& __other) noexcept 00081 : _Vector_profile_post() 00082 { _M_swap(__other); } 00083 00084 _Vector_profile_post& 00085 operator=(const _Vector_profile_post&) noexcept 00086 { _M_profile_construct(); } 00087 00088 _Vector_profile_post& 00089 operator=(_Vector_profile_post&& __other) noexcept 00090 { 00091 _M_swap(__other); 00092 __other._M_profile_construct(); 00093 } 00094 #endif 00095 00096 ~_Vector_profile_post() 00097 { _M_conjure()._M_profile_destruct(); } 00098 00099 public: 00100 void 00101 _M_profile_construct() _GLIBCXX_NOEXCEPT 00102 { 00103 _M_size_info = 00104 __profcxx_vector_size_construct(_M_conjure().capacity()); 00105 _M_vect2list_info = __profcxx_vector2list_construct(); 00106 } 00107 00108 void 00109 _M_profile_destruct() _GLIBCXX_NOEXCEPT 00110 { 00111 __profcxx_vector2list_destruct(_M_vect2list_info); 00112 _M_vect2list_info = 0; 00113 __profcxx_vector_size_destruct(_M_size_info, 00114 _M_conjure().capacity(), 00115 _M_conjure().size()); 00116 _M_size_info = 0; 00117 } 00118 00119 void 00120 _M_swap(_Vector_profile_post& __other) _GLIBCXX_NOEXCEPT 00121 { 00122 std::swap(_M_size_info, __other._M_size_info); 00123 std::swap(_M_vect2list_info, __other._M_vect2list_info); 00124 } 00125 }; 00126 00127 template<typename _Tp, 00128 typename _Allocator = std::allocator<_Tp> > 00129 class vector 00130 : public _Vector_profile_pre<vector<_Tp, _Allocator> >, 00131 public _GLIBCXX_STD_C::vector<_Tp, _Allocator>, 00132 public _Vector_profile_post<vector<_Tp, _Allocator> > 00133 { 00134 typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base; 00135 00136 typedef typename _Base::iterator _Base_iterator; 00137 typedef typename _Base::const_iterator _Base_const_iterator; 00138 00139 public: 00140 typedef typename _Base::reference reference; 00141 typedef typename _Base::const_reference const_reference; 00142 00143 typedef __iterator_tracker<_Base_iterator, vector> 00144 iterator; 00145 typedef __iterator_tracker<_Base_const_iterator, vector> 00146 const_iterator; 00147 00148 typedef typename _Base::size_type size_type; 00149 typedef typename _Base::difference_type difference_type; 00150 00151 typedef _Tp value_type; 00152 typedef _Allocator allocator_type; 00153 typedef typename _Base::pointer pointer; 00154 typedef typename _Base::const_pointer const_pointer; 00155 typedef std::reverse_iterator<iterator> reverse_iterator; 00156 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00157 00158 _Base& 00159 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00160 00161 const _Base& 00162 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00163 00164 // 23.2.4.1 construct/copy/destroy: 00165 00166 #if __cplusplus < 201103L 00167 vector() 00168 { } 00169 00170 vector(const vector& __x) 00171 : _Base(__x) { } 00172 #else 00173 vector() = default; 00174 vector(const vector&) = default; 00175 vector(vector&&) = default; 00176 #endif 00177 00178 explicit 00179 vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT 00180 : _Base(__a) { } 00181 00182 #if __cplusplus >= 201103L 00183 explicit 00184 vector(size_type __n, const _Allocator& __a = _Allocator()) 00185 : _Base(__n, __a) { } 00186 00187 vector(size_type __n, const _Tp& __value, 00188 const _Allocator& __a = _Allocator()) 00189 : _Base(__n, __value, __a) { } 00190 #else 00191 explicit 00192 vector(size_type __n, const _Tp& __value = _Tp(), 00193 const _Allocator& __a = _Allocator()) 00194 : _Base(__n, __value, __a) { } 00195 #endif 00196 00197 #if __cplusplus >= 201103L 00198 template<typename _InputIterator, 00199 typename = std::_RequireInputIter<_InputIterator>> 00200 #else 00201 template<typename _InputIterator> 00202 #endif 00203 vector(_InputIterator __first, _InputIterator __last, 00204 const _Allocator& __a = _Allocator()) 00205 : _Base(__first, __last, __a) { } 00206 00207 /// Construction from a normal-mode vector 00208 vector(const _Base& __x) 00209 : _Base(__x) { } 00210 00211 #if __cplusplus >= 201103L 00212 vector(const _Base& __x, const _Allocator& __a) 00213 : _Base(__x, __a) { } 00214 00215 vector(vector&& __x, const _Allocator& __a) 00216 : _Base(std::move(__x), __a) { } 00217 00218 vector(initializer_list<value_type> __l, 00219 const allocator_type& __a = allocator_type()) 00220 : _Base(__l, __a) { } 00221 #endif 00222 00223 #if __cplusplus < 201103L 00224 vector& 00225 operator=(const vector& __x) 00226 { 00227 this->_M_profile_destruct(); 00228 _M_base() = __x; 00229 this->_M_profile_construct(); 00230 return *this; 00231 } 00232 #else 00233 vector& 00234 operator=(const vector&) = default; 00235 00236 vector& 00237 operator=(vector&&) = default; 00238 00239 vector& 00240 operator=(initializer_list<value_type> __l) 00241 { 00242 this->_M_profile_destruct(); 00243 _M_base() = __l; 00244 this->_M_profile_construct(); 00245 return *this; 00246 } 00247 #endif 00248 00249 // iterators: 00250 iterator 00251 begin() _GLIBCXX_NOEXCEPT 00252 { return iterator(_Base::begin(), this); } 00253 00254 const_iterator 00255 begin() const _GLIBCXX_NOEXCEPT 00256 { return const_iterator(_Base::begin(), this); } 00257 00258 iterator 00259 end() _GLIBCXX_NOEXCEPT 00260 { return iterator(_Base::end(), this); } 00261 00262 const_iterator 00263 end() const _GLIBCXX_NOEXCEPT 00264 { return const_iterator(_Base::end(), this); } 00265 00266 reverse_iterator 00267 rbegin() _GLIBCXX_NOEXCEPT 00268 { return reverse_iterator(end()); } 00269 00270 const_reverse_iterator 00271 rbegin() const _GLIBCXX_NOEXCEPT 00272 { return const_reverse_iterator(end()); } 00273 00274 reverse_iterator 00275 rend() _GLIBCXX_NOEXCEPT 00276 { return reverse_iterator(begin()); } 00277 00278 const_reverse_iterator 00279 rend() const _GLIBCXX_NOEXCEPT 00280 { return const_reverse_iterator(begin()); } 00281 00282 #if __cplusplus >= 201103L 00283 const_iterator 00284 cbegin() const noexcept 00285 { return const_iterator(_Base::begin(), this); } 00286 00287 const_iterator 00288 cend() const noexcept 00289 { return const_iterator(_Base::end(), this); } 00290 00291 const_reverse_iterator 00292 crbegin() const noexcept 00293 { return const_reverse_iterator(end()); } 00294 00295 const_reverse_iterator 00296 crend() const noexcept 00297 { return const_reverse_iterator(begin()); } 00298 #endif 00299 00300 // 23.2.4.2 capacity: 00301 00302 #if __cplusplus >= 201103L 00303 void 00304 resize(size_type __sz) 00305 { 00306 __profcxx_vector2list_invalid_operator(this->_M_vect2list_info); 00307 _M_profile_resize(this->capacity(), __sz); 00308 _Base::resize(__sz); 00309 } 00310 00311 void 00312 resize(size_type __sz, const _Tp& __c) 00313 { 00314 __profcxx_vector2list_invalid_operator(this->_M_vect2list_info); 00315 _M_profile_resize(this->capacity(), __sz); 00316 _Base::resize(__sz, __c); 00317 } 00318 #else 00319 void 00320 resize(size_type __sz, _Tp __c = _Tp()) 00321 { 00322 __profcxx_vector2list_invalid_operator(this->_M_vect2list_info); 00323 _M_profile_resize(this->capacity(), __sz); 00324 _Base::resize(__sz, __c); 00325 } 00326 #endif 00327 00328 // element access: 00329 reference 00330 operator[](size_type __n) _GLIBCXX_NOEXCEPT 00331 { 00332 __profcxx_vector2list_invalid_operator(this->_M_vect2list_info); 00333 return _M_base()[__n]; 00334 } 00335 const_reference 00336 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 00337 { 00338 __profcxx_vector2list_invalid_operator(this->_M_vect2list_info); 00339 return _M_base()[__n]; 00340 } 00341 00342 // 23.2.4.3 modifiers: 00343 void 00344 push_back(const _Tp& __x) 00345 { 00346 size_type __old_size = this->capacity(); 00347 _Base::push_back(__x); 00348 _M_profile_resize(__old_size, this->capacity()); 00349 } 00350 00351 #if __cplusplus >= 201103L 00352 void 00353 push_back(_Tp&& __x) 00354 { 00355 size_type __old_size = this->capacity(); 00356 _Base::push_back(std::move(__x)); 00357 _M_profile_resize(__old_size, this->capacity()); 00358 } 00359 00360 #endif 00361 00362 iterator 00363 #if __cplusplus >= 201103L 00364 insert(const_iterator __pos, const _Tp& __x) 00365 #else 00366 insert(iterator __pos, const _Tp& __x) 00367 #endif 00368 { 00369 __profcxx_vector2list_insert(this->_M_vect2list_info, 00370 __pos.base() - _Base::begin(), 00371 this->size()); 00372 size_type __old_size = this->capacity(); 00373 _Base_iterator __res = _Base::insert(__pos.base(), __x); 00374 _M_profile_resize(__old_size, this->capacity()); 00375 return iterator(__res, this); 00376 } 00377 00378 #if __cplusplus >= 201103L 00379 iterator 00380 insert(const_iterator __pos, _Tp&& __x) 00381 { 00382 __profcxx_vector2list_insert(this->_M_vect2list_info, 00383 __pos.base() - _Base::cbegin(), 00384 this->size()); 00385 size_type __old_size = this->capacity(); 00386 _Base_iterator __res = _Base::insert(__pos.base(), __x); 00387 _M_profile_resize(__old_size, this->capacity()); 00388 return iterator(__res, this); 00389 } 00390 00391 template<typename... _Args> 00392 iterator 00393 emplace(const_iterator __pos, _Args&&... __args) 00394 { 00395 _Base_iterator __res = _Base::emplace(__pos.base(), 00396 std::forward<_Args>(__args)...); 00397 return iterator(__res, this); 00398 } 00399 00400 iterator 00401 insert(const_iterator __pos, initializer_list<value_type> __l) 00402 { return this->insert(__pos, __l.begin(), __l.end()); } 00403 #endif 00404 00405 void 00406 swap(vector& __x) 00407 #if __cplusplus >= 201103L 00408 noexcept( noexcept(declval<_Base>().swap(__x)) ) 00409 #endif 00410 { 00411 _Base::swap(__x); 00412 this->_M_swap(__x); 00413 } 00414 00415 #if __cplusplus >= 201103L 00416 iterator 00417 insert(const_iterator __pos, size_type __n, const _Tp& __x) 00418 { 00419 __profcxx_vector2list_insert(this->_M_vect2list_info, 00420 __pos.base() - _Base::cbegin(), 00421 this->size()); 00422 size_type __old_size = this->capacity(); 00423 _Base_iterator __res = _Base::insert(__pos, __n, __x); 00424 _M_profile_resize(__old_size, this->capacity()); 00425 return iterator(__res, this); 00426 } 00427 #else 00428 void 00429 insert(iterator __pos, size_type __n, const _Tp& __x) 00430 { 00431 __profcxx_vector2list_insert(this->_M_vect2list_info, 00432 __pos.base() - _Base::begin(), 00433 this->size()); 00434 size_type __old_size = this->capacity(); 00435 _Base::insert(__pos, __n, __x); 00436 _M_profile_resize(__old_size, this->capacity()); 00437 } 00438 #endif 00439 00440 #if __cplusplus >= 201103L 00441 template<typename _InputIterator, 00442 typename = std::_RequireInputIter<_InputIterator>> 00443 iterator 00444 insert(const_iterator __pos, 00445 _InputIterator __first, _InputIterator __last) 00446 { 00447 __profcxx_vector2list_insert(this->_M_vect2list_info, 00448 __pos.base() - _Base::cbegin(), 00449 this->size()); 00450 size_type __old_size = this->capacity(); 00451 _Base_iterator __res = _Base::insert(__pos, __first, __last); 00452 _M_profile_resize(__old_size, this->capacity()); 00453 return iterator(__res, this); 00454 } 00455 #else 00456 template<typename _InputIterator> 00457 void 00458 insert(iterator __pos, 00459 _InputIterator __first, _InputIterator __last) 00460 { 00461 __profcxx_vector2list_insert(this->_M_vect2list_info, 00462 __pos.base() - _Base::begin(), 00463 this->size()); 00464 size_type __old_size = this->capacity(); 00465 _Base::insert(__pos, __first, __last); 00466 _M_profile_resize(__old_size, this->capacity()); 00467 } 00468 #endif 00469 00470 iterator 00471 #if __cplusplus >= 201103L 00472 erase(const_iterator __pos) 00473 #else 00474 erase(iterator __pos) 00475 #endif 00476 { return iterator(_Base::erase(__pos.base()), this); } 00477 00478 iterator 00479 #if __cplusplus >= 201103L 00480 erase(const_iterator __first, const_iterator __last) 00481 #else 00482 erase(iterator __first, iterator __last) 00483 #endif 00484 { return iterator(_Base::erase(__first.base(), __last.base()), this); } 00485 00486 void 00487 clear() _GLIBCXX_NOEXCEPT 00488 { 00489 this->_M_profile_destruct(); 00490 _Base::clear(); 00491 this->_M_profile_construct(); 00492 } 00493 00494 inline void 00495 _M_profile_iterate(int __rewind = 0) const 00496 { __profcxx_vector2list_iterate(this->_M_vect2list_info, __rewind); } 00497 00498 private: 00499 void _M_profile_resize(size_type __old_size, size_type __new_size) 00500 { 00501 if (__old_size < __new_size) 00502 { 00503 __profcxx_vector_size_resize(this->_M_size_info, 00504 this->size(), __new_size); 00505 __profcxx_vector2list_resize(this->_M_vect2list_info, 00506 this->size(), __new_size); 00507 } 00508 } 00509 }; 00510 00511 template<typename _Tp, typename _Alloc> 00512 inline bool 00513 operator==(const vector<_Tp, _Alloc>& __lhs, 00514 const vector<_Tp, _Alloc>& __rhs) 00515 { return __lhs._M_base() == __rhs._M_base(); } 00516 00517 template<typename _Tp, typename _Alloc> 00518 inline bool 00519 operator!=(const vector<_Tp, _Alloc>& __lhs, 00520 const vector<_Tp, _Alloc>& __rhs) 00521 { return __lhs._M_base() != __rhs._M_base(); } 00522 00523 template<typename _Tp, typename _Alloc> 00524 inline bool 00525 operator<(const vector<_Tp, _Alloc>& __lhs, 00526 const vector<_Tp, _Alloc>& __rhs) 00527 { return __lhs._M_base() < __rhs._M_base(); } 00528 00529 template<typename _Tp, typename _Alloc> 00530 inline bool 00531 operator<=(const vector<_Tp, _Alloc>& __lhs, 00532 const vector<_Tp, _Alloc>& __rhs) 00533 { return __lhs._M_base() <= __rhs._M_base(); } 00534 00535 template<typename _Tp, typename _Alloc> 00536 inline bool 00537 operator>=(const vector<_Tp, _Alloc>& __lhs, 00538 const vector<_Tp, _Alloc>& __rhs) 00539 { return __lhs._M_base() >= __rhs._M_base(); } 00540 00541 template<typename _Tp, typename _Alloc> 00542 inline bool 00543 operator>(const vector<_Tp, _Alloc>& __lhs, 00544 const vector<_Tp, _Alloc>& __rhs) 00545 { return __lhs._M_base() > __rhs._M_base(); } 00546 00547 template<typename _Tp, typename _Alloc> 00548 inline void 00549 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 00550 { __lhs.swap(__rhs); } 00551 00552 #if __cplusplus >= 201103L 00553 template<typename _Tp, typename _Alloc> 00554 inline void 00555 swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs) 00556 { __lhs.swap(__rhs); } 00557 00558 template<typename _Tp, typename _Alloc> 00559 inline void 00560 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs) 00561 { __lhs.swap(__rhs); } 00562 #endif 00563 00564 } // namespace __profile 00565 00566 #if __cplusplus >= 201103L 00567 // DR 1182. 00568 /// std::hash specialization for vector<bool>. 00569 template<typename _Alloc> 00570 struct hash<__profile::vector<bool, _Alloc>> 00571 : public __hash_base<size_t, __profile::vector<bool, _Alloc>> 00572 { 00573 size_t 00574 operator()(const __profile::vector<bool, _Alloc>& __b) const noexcept 00575 { 00576 return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b._M_base()); 00577 } 00578 }; 00579 #endif 00580 00581 } // namespace std 00582 00583 #endif