libstdc++
|
00001 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009-2014 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/unordered_set 00025 * This file is a GNU profile extension to the Standard C++ Library. 00026 */ 00027 00028 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET 00029 #define _GLIBCXX_PROFILE_UNORDERED_SET 1 00030 00031 #if __cplusplus < 201103L 00032 # include <bits/c++0x_warning.h> 00033 #else 00034 # include <unordered_set> 00035 00036 #include <profile/base.h> 00037 #include <profile/unordered_base.h> 00038 00039 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc> 00040 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 00041 00042 namespace std _GLIBCXX_VISIBILITY(default) 00043 { 00044 namespace __profile 00045 { 00046 /** @brief Unordered_set wrapper with performance instrumentation. */ 00047 template<typename _Key, 00048 typename _Hash = std::hash<_Key>, 00049 typename _Pred = std::equal_to<_Key>, 00050 typename _Alloc = std::allocator<_Key> > 00051 class unordered_set 00052 : public _GLIBCXX_STD_BASE, 00053 public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>, 00054 true> 00055 { 00056 typedef _GLIBCXX_STD_BASE _Base; 00057 00058 _Base& 00059 _M_base() noexcept { return *this; } 00060 00061 const _Base& 00062 _M_base() const noexcept { return *this; } 00063 00064 public: 00065 typedef typename _Base::size_type size_type; 00066 typedef typename _Base::hasher hasher; 00067 typedef typename _Base::key_equal key_equal; 00068 typedef typename _Base::allocator_type allocator_type; 00069 typedef typename _Base::key_type key_type; 00070 typedef typename _Base::value_type value_type; 00071 typedef typename _Base::difference_type difference_type; 00072 typedef typename _Base::reference reference; 00073 typedef typename _Base::const_reference const_reference; 00074 00075 typedef typename _Base::iterator iterator; 00076 typedef typename _Base::const_iterator const_iterator; 00077 00078 explicit 00079 unordered_set(size_type __n = 10, 00080 const hasher& __hf = hasher(), 00081 const key_equal& __eql = key_equal(), 00082 const allocator_type& __a = allocator_type()) 00083 : _Base(__n, __hf, __eql, __a) 00084 { } 00085 00086 template<typename _InputIterator> 00087 unordered_set(_InputIterator __f, _InputIterator __l, 00088 size_type __n = 0, 00089 const hasher& __hf = hasher(), 00090 const key_equal& __eql = key_equal(), 00091 const allocator_type& __a = allocator_type()) 00092 : _Base(__f, __l, __n, __hf, __eql, __a) 00093 { } 00094 00095 unordered_set(const unordered_set&) = default; 00096 00097 unordered_set(const _Base& __x) 00098 : _Base(__x) 00099 { } 00100 00101 unordered_set(unordered_set&&) = default; 00102 00103 explicit 00104 unordered_set(const allocator_type& __a) 00105 : _Base(__a) 00106 { } 00107 00108 unordered_set(const unordered_set& __uset, 00109 const allocator_type& __a) 00110 : _Base(__uset._M_base(), __a) 00111 { } 00112 00113 unordered_set(unordered_set&& __uset, 00114 const allocator_type& __a) 00115 : _Base(std::move(__uset._M_base()), __a) 00116 { } 00117 00118 unordered_set(initializer_list<value_type> __l, 00119 size_type __n = 0, 00120 const hasher& __hf = hasher(), 00121 const key_equal& __eql = key_equal(), 00122 const allocator_type& __a = allocator_type()) 00123 : _Base(__l, __n, __hf, __eql, __a) 00124 { } 00125 00126 unordered_set& 00127 operator=(const unordered_set&) = default; 00128 00129 unordered_set& 00130 operator=(unordered_set&&) = default; 00131 00132 unordered_set& 00133 operator=(initializer_list<value_type> __l) 00134 { 00135 _M_base() = __l; 00136 return *this; 00137 } 00138 00139 void 00140 swap(unordered_set& __x) 00141 noexcept( noexcept(__x._M_base().swap(__x)) ) 00142 { _Base::swap(__x); } 00143 00144 void 00145 clear() noexcept 00146 { 00147 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 00148 _Base::size()); 00149 this->_M_profile_destruct(); 00150 _Base::clear(); 00151 } 00152 00153 template<typename... _Args> 00154 std::pair<iterator, bool> 00155 emplace(_Args&&... __args) 00156 { 00157 size_type __old_size = _Base::bucket_count(); 00158 std::pair<iterator, bool> __res 00159 = _Base::emplace(std::forward<_Args>(__args)...); 00160 _M_profile_resize(__old_size); 00161 return __res; 00162 } 00163 00164 template<typename... _Args> 00165 iterator 00166 emplace_hint(const_iterator __it, _Args&&... __args) 00167 { 00168 size_type __old_size = _Base::bucket_count(); 00169 iterator __res 00170 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00171 _M_profile_resize(__old_size); 00172 return __res; 00173 } 00174 00175 void 00176 insert(std::initializer_list<value_type> __l) 00177 { 00178 size_type __old_size = _Base::bucket_count(); 00179 _Base::insert(__l); 00180 _M_profile_resize(__old_size); 00181 } 00182 00183 std::pair<iterator, bool> 00184 insert(const value_type& __obj) 00185 { 00186 size_type __old_size = _Base::bucket_count(); 00187 std::pair<iterator, bool> __res = _Base::insert(__obj); 00188 _M_profile_resize(__old_size); 00189 return __res; 00190 } 00191 00192 iterator 00193 insert(const_iterator __iter, const value_type& __v) 00194 { 00195 size_type __old_size = _Base::bucket_count(); 00196 iterator __res = _Base::insert(__iter, __v); 00197 _M_profile_resize(__old_size); 00198 return __res; 00199 } 00200 00201 std::pair<iterator, bool> 00202 insert(value_type&& __obj) 00203 { 00204 size_type __old_size = _Base::bucket_count(); 00205 std::pair<iterator, bool> __res = _Base::insert(std::move(__obj)); 00206 _M_profile_resize(__old_size); 00207 return __res; 00208 } 00209 00210 iterator 00211 insert(const_iterator __iter, value_type&& __v) 00212 { 00213 size_type __old_size = _Base::bucket_count(); 00214 iterator __res = _Base::insert(__iter, std::move(__v)); 00215 _M_profile_resize(__old_size); 00216 return __res; 00217 } 00218 00219 template<typename _InputIter> 00220 void 00221 insert(_InputIter __first, _InputIter __last) 00222 { 00223 size_type __old_size = _Base::bucket_count(); 00224 _Base::insert(__first, __last); 00225 _M_profile_resize(__old_size); 00226 } 00227 00228 void 00229 rehash(size_type __n) 00230 { 00231 size_type __old_size = _Base::bucket_count(); 00232 _Base::rehash(__n); 00233 _M_profile_resize(__old_size); 00234 } 00235 00236 private: 00237 void 00238 _M_profile_resize(size_type __old_size) 00239 { 00240 size_type __new_size = _Base::bucket_count(); 00241 if (__old_size != __new_size) 00242 __profcxx_hashtable_resize(this, __old_size, __new_size); 00243 } 00244 }; 00245 00246 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 00247 inline void 00248 swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 00249 unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 00250 { __x.swap(__y); } 00251 00252 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 00253 inline bool 00254 operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 00255 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 00256 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00257 00258 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 00259 inline bool 00260 operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 00261 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 00262 { return !(__x == __y); } 00263 00264 #undef _GLIBCXX_BASE 00265 #undef _GLIBCXX_STD_BASE 00266 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 00267 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc> 00268 00269 /** @brief Unordered_multiset wrapper with performance instrumentation. */ 00270 template<typename _Value, 00271 typename _Hash = std::hash<_Value>, 00272 typename _Pred = std::equal_to<_Value>, 00273 typename _Alloc = std::allocator<_Value> > 00274 class unordered_multiset 00275 : public _GLIBCXX_STD_BASE, 00276 public _Unordered_profile<unordered_multiset<_Value, 00277 _Hash, _Pred, _Alloc>, 00278 false> 00279 { 00280 typedef _GLIBCXX_STD_BASE _Base; 00281 00282 _Base& 00283 _M_base() noexcept { return *this; } 00284 00285 const _Base& 00286 _M_base() const noexcept { return *this; } 00287 00288 public: 00289 typedef typename _Base::size_type size_type; 00290 typedef typename _Base::hasher hasher; 00291 typedef typename _Base::key_equal key_equal; 00292 typedef typename _Base::allocator_type allocator_type; 00293 typedef typename _Base::key_type key_type; 00294 typedef typename _Base::value_type value_type; 00295 typedef typename _Base::difference_type difference_type; 00296 typedef typename _Base::reference reference; 00297 typedef typename _Base::const_reference const_reference; 00298 00299 typedef typename _Base::iterator iterator; 00300 typedef typename _Base::const_iterator const_iterator; 00301 00302 explicit 00303 unordered_multiset(size_type __n = 10, 00304 const hasher& __hf = hasher(), 00305 const key_equal& __eql = key_equal(), 00306 const allocator_type& __a = allocator_type()) 00307 : _Base(__n, __hf, __eql, __a) 00308 { } 00309 00310 template<typename _InputIterator> 00311 unordered_multiset(_InputIterator __f, _InputIterator __l, 00312 size_type __n = 0, 00313 const hasher& __hf = hasher(), 00314 const key_equal& __eql = key_equal(), 00315 const allocator_type& __a = allocator_type()) 00316 : _Base(__f, __l, __n, __hf, __eql, __a) 00317 { } 00318 00319 unordered_multiset(const unordered_multiset&) = default; 00320 00321 unordered_multiset(const _Base& __x) 00322 : _Base(__x) 00323 { } 00324 00325 unordered_multiset(unordered_multiset&&) = default; 00326 00327 explicit 00328 unordered_multiset(const allocator_type& __a) 00329 : _Base(__a) 00330 { } 00331 00332 unordered_multiset(const unordered_multiset& __umset, 00333 const allocator_type& __a) 00334 : _Base(__umset._M_base(), __a) 00335 { } 00336 00337 unordered_multiset(unordered_multiset&& __umset, 00338 const allocator_type& __a) 00339 : _Base(std::move(__umset._M_base()), __a) 00340 { } 00341 00342 unordered_multiset(initializer_list<value_type> __l, 00343 size_type __n = 0, 00344 const hasher& __hf = hasher(), 00345 const key_equal& __eql = key_equal(), 00346 const allocator_type& __a = allocator_type()) 00347 : _Base(__l, __n, __hf, __eql, __a) 00348 { } 00349 00350 unordered_multiset& 00351 operator=(const unordered_multiset&) = default; 00352 00353 unordered_multiset& 00354 operator=(unordered_multiset&&) = default; 00355 00356 unordered_multiset& 00357 operator=(initializer_list<value_type> __l) 00358 { 00359 _M_base() = __l; 00360 return *this; 00361 } 00362 00363 void 00364 swap(unordered_multiset& __x) 00365 noexcept( noexcept(__x._M_base().swap(__x)) ) 00366 { _Base::swap(__x); } 00367 00368 void 00369 clear() noexcept 00370 { 00371 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 00372 _Base::size()); 00373 this->_M_profile_destruct(); 00374 _Base::clear(); 00375 } 00376 00377 template<typename... _Args> 00378 iterator 00379 emplace(_Args&&... __args) 00380 { 00381 size_type __old_size = _Base::bucket_count(); 00382 iterator __res = _Base::emplace(std::forward<_Args>(__args)...); 00383 _M_profile_resize(__old_size); 00384 return __res; 00385 } 00386 00387 template<typename... _Args> 00388 iterator 00389 emplace_hint(const_iterator __it, _Args&&... __args) 00390 { 00391 size_type __old_size = _Base::bucket_count(); 00392 iterator __res 00393 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00394 _M_profile_resize(__old_size); 00395 return __res; 00396 } 00397 00398 void 00399 insert(std::initializer_list<value_type> __l) 00400 { 00401 size_type __old_size = _Base::bucket_count(); 00402 _Base::insert(__l); 00403 _M_profile_resize(__old_size); 00404 } 00405 00406 iterator 00407 insert(const value_type& __obj) 00408 { 00409 size_type __old_size = _Base::bucket_count(); 00410 iterator __res = _Base::insert(__obj); 00411 _M_profile_resize(__old_size); 00412 return __res; 00413 } 00414 00415 iterator 00416 insert(const_iterator __iter, const value_type& __v) 00417 { 00418 size_type __old_size = _Base::bucket_count(); 00419 iterator __res = _Base::insert(__iter, __v); 00420 _M_profile_resize(__old_size); 00421 return __res; 00422 } 00423 00424 iterator 00425 insert(value_type&& __obj) 00426 { 00427 size_type __old_size = _Base::bucket_count(); 00428 iterator __res = _Base::insert(std::move(__obj)); 00429 _M_profile_resize(__old_size); 00430 return __res; 00431 } 00432 00433 iterator 00434 insert(const_iterator __iter, value_type&& __v) 00435 { 00436 size_type __old_size = _Base::bucket_count(); 00437 iterator __res = _Base::insert(__iter, std::move(__v)); 00438 _M_profile_resize(__old_size); 00439 return __res; 00440 } 00441 00442 template<typename _InputIter> 00443 void 00444 insert(_InputIter __first, _InputIter __last) 00445 { 00446 size_type __old_size = _Base::bucket_count(); 00447 _Base::insert(__first, __last); 00448 _M_profile_resize(__old_size); 00449 } 00450 00451 void 00452 rehash(size_type __n) 00453 { 00454 size_type __old_size = _Base::bucket_count(); 00455 _Base::rehash(__n); 00456 _M_profile_resize(__old_size); 00457 } 00458 00459 private: 00460 void 00461 _M_profile_resize(size_type __old_size) 00462 { 00463 size_type __new_size = _Base::bucket_count(); 00464 if (__old_size != __new_size) 00465 __profcxx_hashtable_resize(this, __old_size, __new_size); 00466 } 00467 }; 00468 00469 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00470 inline void 00471 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00472 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00473 { __x.swap(__y); } 00474 00475 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00476 inline bool 00477 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00478 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00479 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00480 00481 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00482 inline bool 00483 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00484 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00485 { return !(__x == __y); } 00486 00487 } // namespace __profile 00488 } // namespace std 00489 00490 #undef _GLIBCXX_BASE 00491 #undef _GLIBCXX_STD_BASE 00492 00493 #endif // C++11 00494 00495 #endif