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