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