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