libstdc++
|
00001 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009-2013 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 unordered_map(initializer_list<value_type> __l, 00105 size_type __n = 0, 00106 const hasher& __hf = hasher(), 00107 const key_equal& __eql = key_equal(), 00108 const allocator_type& __a = allocator_type()) 00109 : _Base(__l, __n, __hf, __eql, __a) 00110 { } 00111 00112 unordered_map& 00113 operator=(const unordered_map&) = default; 00114 00115 unordered_map& 00116 operator=(unordered_map&&) = default; 00117 00118 unordered_map& 00119 operator=(initializer_list<value_type> __l) 00120 { 00121 _M_base() = __l; 00122 return *this; 00123 } 00124 00125 void 00126 clear() noexcept 00127 { 00128 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 00129 _Base::size()); 00130 this->_M_profile_destruct(); 00131 _Base::clear(); 00132 } 00133 00134 template<typename... _Args> 00135 std::pair<iterator, bool> 00136 emplace(_Args&&... __args) 00137 { 00138 size_type __old_size = _Base::bucket_count(); 00139 std::pair<iterator, bool> __res 00140 = _Base::emplace(std::forward<_Args>(__args)...); 00141 _M_profile_resize(__old_size); 00142 return __res; 00143 } 00144 00145 template<typename... _Args> 00146 iterator 00147 emplace_hint(const_iterator __it, _Args&&... __args) 00148 { 00149 size_type __old_size = _Base::bucket_count(); 00150 iterator __res 00151 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00152 _M_profile_resize(__old_size); 00153 return __res; 00154 } 00155 00156 void 00157 insert(std::initializer_list<value_type> __l) 00158 { 00159 size_type __old_size = _Base::bucket_count(); 00160 _Base::insert(__l); 00161 _M_profile_resize(__old_size); 00162 } 00163 00164 std::pair<iterator, bool> 00165 insert(const value_type& __obj) 00166 { 00167 size_type __old_size = _Base::bucket_count(); 00168 std::pair<iterator, bool> __res = _Base::insert(__obj); 00169 _M_profile_resize(__old_size); 00170 return __res; 00171 } 00172 00173 iterator 00174 insert(const_iterator __iter, const value_type& __v) 00175 { 00176 size_type __old_size = _Base::bucket_count(); 00177 iterator __res = _Base::insert(__iter, __v); 00178 _M_profile_resize(__old_size); 00179 return __res; 00180 } 00181 00182 template<typename _Pair, typename = typename 00183 std::enable_if<std::is_constructible<value_type, 00184 _Pair&&>::value>::type> 00185 std::pair<iterator, bool> 00186 insert(_Pair&& __obj) 00187 { 00188 size_type __old_size = _Base::bucket_count(); 00189 std::pair<iterator, bool> __res 00190 = _Base::insert(std::forward<_Pair>(__obj)); 00191 _M_profile_resize(__old_size); 00192 return __res; 00193 } 00194 00195 template<typename _Pair, typename = typename 00196 std::enable_if<std::is_constructible<value_type, 00197 _Pair&&>::value>::type> 00198 iterator 00199 insert(const_iterator __iter, _Pair&& __v) 00200 { 00201 size_type __old_size = _Base::bucket_count(); 00202 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 00203 _M_profile_resize(__old_size); 00204 return __res; 00205 } 00206 00207 template<typename _InputIter> 00208 void 00209 insert(_InputIter __first, _InputIter __last) 00210 { 00211 size_type __old_size = _Base::bucket_count(); 00212 _Base::insert(__first, __last); 00213 _M_profile_resize(__old_size); 00214 } 00215 00216 // operator[] 00217 mapped_type& 00218 operator[](const _Key& __k) 00219 { 00220 size_type __old_size = _Base::bucket_count(); 00221 mapped_type& __res = _M_base()[__k]; 00222 _M_profile_resize(__old_size); 00223 return __res; 00224 } 00225 00226 mapped_type& 00227 operator[](_Key&& __k) 00228 { 00229 size_type __old_size = _Base::bucket_count(); 00230 mapped_type& __res = _M_base()[std::move(__k)]; 00231 _M_profile_resize(__old_size); 00232 return __res; 00233 } 00234 00235 void 00236 swap(unordered_map& __x) 00237 { _Base::swap(__x._M_base()); } 00238 00239 void rehash(size_type __n) 00240 { 00241 size_type __old_size = _Base::bucket_count(); 00242 _Base::rehash(__n); 00243 _M_profile_resize(__old_size); 00244 } 00245 00246 private: 00247 void 00248 _M_profile_resize(size_type __old_size) 00249 { 00250 size_type __new_size = _Base::bucket_count(); 00251 if (__old_size != __new_size) 00252 __profcxx_hashtable_resize(this, __old_size, __new_size); 00253 } 00254 }; 00255 00256 template<typename _Key, typename _Tp, typename _Hash, 00257 typename _Pred, typename _Alloc> 00258 inline void 00259 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00260 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00261 { __x.swap(__y); } 00262 00263 template<typename _Key, typename _Tp, typename _Hash, 00264 typename _Pred, typename _Alloc> 00265 inline bool 00266 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00267 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00268 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00269 00270 template<typename _Key, typename _Tp, typename _Hash, 00271 typename _Pred, typename _Alloc> 00272 inline bool 00273 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00274 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00275 { return !(__x == __y); } 00276 00277 #undef _GLIBCXX_BASE 00278 #undef _GLIBCXX_STD_BASE 00279 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 00280 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 00281 00282 /// Class std::unordered_multimap wrapper with performance instrumentation. 00283 template<typename _Key, typename _Tp, 00284 typename _Hash = std::hash<_Key>, 00285 typename _Pred = std::equal_to<_Key>, 00286 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00287 class unordered_multimap 00288 : public _GLIBCXX_STD_BASE, 00289 public _Unordered_profile<unordered_multimap<_Key, _Tp, 00290 _Hash, _Pred, _Alloc>, 00291 false> 00292 { 00293 typedef typename _GLIBCXX_STD_BASE _Base; 00294 00295 _Base& 00296 _M_base() noexcept { return *this; } 00297 00298 const _Base& 00299 _M_base() const noexcept { return *this; } 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_multimap(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 00323 template<typename _InputIterator> 00324 unordered_multimap(_InputIterator __f, _InputIterator __l, 00325 size_type __n = 0, 00326 const hasher& __hf = hasher(), 00327 const key_equal& __eql = key_equal(), 00328 const allocator_type& __a = allocator_type()) 00329 : _Base(__f, __l, __n, __hf, __eql, __a) 00330 { } 00331 00332 unordered_multimap(const unordered_multimap&) = default; 00333 00334 unordered_multimap(const _Base& __x) 00335 : _Base(__x) 00336 { } 00337 00338 unordered_multimap(unordered_multimap&&) = default; 00339 00340 unordered_multimap(initializer_list<value_type> __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(__l, __n, __hf, __eql, __a) 00346 { } 00347 00348 unordered_multimap& 00349 operator=(const unordered_multimap&) = default; 00350 00351 unordered_multimap& 00352 operator=(unordered_multimap&&) = default; 00353 00354 unordered_multimap& 00355 operator=(initializer_list<value_type> __l) 00356 { 00357 _M_base() = __l; 00358 return *this; 00359 } 00360 00361 void 00362 clear() noexcept 00363 { 00364 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 00365 _Base::size()); 00366 this->_M_profile_destruct(); 00367 _Base::clear(); 00368 } 00369 00370 template<typename... _Args> 00371 iterator 00372 emplace(_Args&&... __args) 00373 { 00374 size_type __old_size = _Base::bucket_count(); 00375 iterator __res 00376 = _Base::emplace(std::forward<_Args>(__args)...); 00377 _M_profile_resize(__old_size); 00378 return __res; 00379 } 00380 00381 template<typename... _Args> 00382 iterator 00383 emplace_hint(const_iterator __it, _Args&&... __args) 00384 { 00385 size_type __old_size = _Base::bucket_count(); 00386 iterator __res 00387 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00388 _M_profile_resize(__old_size); 00389 return __res; 00390 } 00391 00392 void 00393 insert(std::initializer_list<value_type> __l) 00394 { 00395 size_type __old_size = _Base::bucket_count(); 00396 _Base::insert(__l); 00397 _M_profile_resize(__old_size); 00398 } 00399 00400 iterator 00401 insert(const value_type& __obj) 00402 { 00403 size_type __old_size = _Base::bucket_count(); 00404 iterator __res = _Base::insert(__obj); 00405 _M_profile_resize(__old_size); 00406 return __res; 00407 } 00408 00409 iterator 00410 insert(const_iterator __iter, const value_type& __v) 00411 { 00412 size_type __old_size = _Base::bucket_count(); 00413 iterator __res = _Base::insert(__iter, __v); 00414 _M_profile_resize(__old_size); 00415 return __res; 00416 } 00417 00418 template<typename _Pair, typename = typename 00419 std::enable_if<std::is_constructible<value_type, 00420 _Pair&&>::value>::type> 00421 iterator 00422 insert(_Pair&& __obj) 00423 { 00424 size_type __old_size = _Base::bucket_count(); 00425 iterator __res = _Base::insert(std::forward<_Pair>(__obj)); 00426 _M_profile_resize(__old_size); 00427 return __res; 00428 } 00429 00430 template<typename _Pair, typename = typename 00431 std::enable_if<std::is_constructible<value_type, 00432 _Pair&&>::value>::type> 00433 iterator 00434 insert(const_iterator __iter, _Pair&& __v) 00435 { 00436 size_type __old_size = _Base::bucket_count(); 00437 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 00438 _M_profile_resize(__old_size); 00439 return __res; 00440 } 00441 00442 template<typename _InputIter> 00443 void 00444 insert(_InputIter __first, _InputIter __last) 00445 { 00446 size_type __old_size = _Base::bucket_count(); 00447 _Base::insert(__first, __last); 00448 _M_profile_resize(__old_size); 00449 } 00450 00451 void 00452 swap(unordered_multimap& __x) 00453 { _Base::swap(__x._M_base()); } 00454 00455 void 00456 rehash(size_type __n) 00457 { 00458 size_type __old_size = _Base::bucket_count(); 00459 _Base::rehash(__n); 00460 _M_profile_resize(__old_size); 00461 } 00462 00463 private: 00464 void 00465 _M_profile_resize(size_type __old_size) 00466 { 00467 size_type __new_size = _Base::bucket_count(); 00468 if (__old_size != __new_size) 00469 __profcxx_hashtable_resize(this, __old_size, __new_size); 00470 } 00471 }; 00472 00473 template<typename _Key, typename _Tp, typename _Hash, 00474 typename _Pred, typename _Alloc> 00475 inline void 00476 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00477 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00478 { __x.swap(__y); } 00479 00480 template<typename _Key, typename _Tp, typename _Hash, 00481 typename _Pred, typename _Alloc> 00482 inline bool 00483 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00484 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00485 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00486 00487 template<typename _Key, typename _Tp, typename _Hash, 00488 typename _Pred, typename _Alloc> 00489 inline bool 00490 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00491 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00492 { return !(__x == __y); } 00493 00494 } // namespace __profile 00495 } // namespace std 00496 00497 #undef _GLIBCXX_BASE 00498 #undef _GLIBCXX_STD_BASE 00499 00500 #endif // C++11 00501 00502 #endif