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