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