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