1 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 2 3 // Copyright (C) 2009-2014 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 // 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License along 21 // with this library; see the file COPYING3. If not see 22 // <http://www.gnu.org/licenses/>. 23 24 /** @file profile/unordered_map 25 * This file is a GNU profile extension to the Standard C++ Library. 26 */ 27 28 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP 29 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1 30 31 #if __cplusplus < 201103L 32 # include <bits/c++0x_warning.h> 33 #else 34 # include <unordered_map> 35 36 #include <profile/base.h> 37 #include <profile/unordered_base.h> 38 39 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 40 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 41 42 namespace std _GLIBCXX_VISIBILITY(default) 43 { 44 namespace __profile 45 { 46 /// Class std::unordered_map wrapper with performance instrumentation. 47 template<typename _Key, typename _Tp, 48 typename _Hash = std::hash<_Key>, 49 typename _Pred = std::equal_to<_Key>, 50 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 51 class unordered_map 52 : public _GLIBCXX_STD_BASE, 53 public _Unordered_profile<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 54 true> 55 { 56 typedef typename _GLIBCXX_STD_BASE _Base; 57 58 _Base& 59 _M_base() noexcept { return *this; } 60 61 const _Base& 62 _M_base() const noexcept { return *this; } 63 64 public: 65 typedef typename _Base::size_type size_type; 66 typedef typename _Base::hasher hasher; 67 typedef typename _Base::key_equal key_equal; 68 typedef typename _Base::allocator_type allocator_type; 69 typedef typename _Base::key_type key_type; 70 typedef typename _Base::value_type value_type; 71 typedef typename _Base::difference_type difference_type; 72 typedef typename _Base::reference reference; 73 typedef typename _Base::const_reference const_reference; 74 typedef typename _Base::mapped_type mapped_type; 75 76 typedef typename _Base::iterator iterator; 77 typedef typename _Base::const_iterator const_iterator; 78 79 explicit 80 unordered_map(size_type __n = 10, 81 const hasher& __hf = hasher(), 82 const key_equal& __eql = key_equal(), 83 const allocator_type& __a = allocator_type()) 84 : _Base(__n, __hf, __eql, __a) 85 { } 86 87 template<typename _InputIterator> 88 unordered_map(_InputIterator __f, _InputIterator __l, 89 size_type __n = 0, 90 const hasher& __hf = hasher(), 91 const key_equal& __eql = key_equal(), 92 const allocator_type& __a = allocator_type()) 93 : _Base(__f, __l, __n, __hf, __eql, __a) 94 { } 95 96 unordered_map(const unordered_map&) = default; 97 98 unordered_map(const _Base& __x) 99 : _Base(__x) 100 { } 101 102 unordered_map(unordered_map&&) = default; 103 104 explicit 105 unordered_map(const allocator_type& __a) 106 : _Base(__a) 107 { } 108 109 unordered_map(const unordered_map& __umap, 110 const allocator_type& __a) 111 : _Base(__umap, __a) 112 { } 113 114 unordered_map(unordered_map&& __umap, 115 const allocator_type& __a) 116 : _Base(std::move(__umap._M_base()), __a) 117 { } 118 119 unordered_map(initializer_list<value_type> __l, 120 size_type __n = 0, 121 const hasher& __hf = hasher(), 122 const key_equal& __eql = key_equal(), 123 const allocator_type& __a = allocator_type()) 124 : _Base(__l, __n, __hf, __eql, __a) 125 { } 126 127 unordered_map& 128 operator=(const unordered_map&) = default; 129 130 unordered_map& 131 operator=(unordered_map&&) = default; 132 133 unordered_map& 134 operator=(initializer_list<value_type> __l) 135 { 136 _M_base() = __l; 137 return *this; 138 } 139 140 void 141 clear() noexcept 142 { 143 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 144 _Base::size()); 145 this->_M_profile_destruct(); 146 _Base::clear(); 147 } 148 149 template<typename... _Args> 150 std::pair<iterator, bool> 151 emplace(_Args&&... __args) 152 { 153 size_type __old_size = _Base::bucket_count(); 154 std::pair<iterator, bool> __res 155 = _Base::emplace(std::forward<_Args>(__args)...); 156 _M_profile_resize(__old_size); 157 return __res; 158 } 159 160 template<typename... _Args> 161 iterator 162 emplace_hint(const_iterator __it, _Args&&... __args) 163 { 164 size_type __old_size = _Base::bucket_count(); 165 iterator __res 166 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 167 _M_profile_resize(__old_size); 168 return __res; 169 } 170 171 void 172 insert(std::initializer_list<value_type> __l) 173 { 174 size_type __old_size = _Base::bucket_count(); 175 _Base::insert(__l); 176 _M_profile_resize(__old_size); 177 } 178 179 std::pair<iterator, bool> 180 insert(const value_type& __obj) 181 { 182 size_type __old_size = _Base::bucket_count(); 183 std::pair<iterator, bool> __res = _Base::insert(__obj); 184 _M_profile_resize(__old_size); 185 return __res; 186 } 187 188 iterator 189 insert(const_iterator __iter, const value_type& __v) 190 { 191 size_type __old_size = _Base::bucket_count(); 192 iterator __res = _Base::insert(__iter, __v); 193 _M_profile_resize(__old_size); 194 return __res; 195 } 196 197 template<typename _Pair, typename = typename 198 std::enable_if<std::is_constructible<value_type, 199 _Pair&&>::value>::type> 200 std::pair<iterator, bool> 201 insert(_Pair&& __obj) 202 { 203 size_type __old_size = _Base::bucket_count(); 204 std::pair<iterator, bool> __res 205 = _Base::insert(std::forward<_Pair>(__obj)); 206 _M_profile_resize(__old_size); 207 return __res; 208 } 209 210 template<typename _Pair, typename = typename 211 std::enable_if<std::is_constructible<value_type, 212 _Pair&&>::value>::type> 213 iterator 214 insert(const_iterator __iter, _Pair&& __v) 215 { 216 size_type __old_size = _Base::bucket_count(); 217 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 218 _M_profile_resize(__old_size); 219 return __res; 220 } 221 222 template<typename _InputIter> 223 void 224 insert(_InputIter __first, _InputIter __last) 225 { 226 size_type __old_size = _Base::bucket_count(); 227 _Base::insert(__first, __last); 228 _M_profile_resize(__old_size); 229 } 230 231 // operator[] 232 mapped_type& 233 operator[](const _Key& __k) 234 { 235 size_type __old_size = _Base::bucket_count(); 236 mapped_type& __res = _M_base()[__k]; 237 _M_profile_resize(__old_size); 238 return __res; 239 } 240 241 mapped_type& 242 operator[](_Key&& __k) 243 { 244 size_type __old_size = _Base::bucket_count(); 245 mapped_type& __res = _M_base()[std::move(__k)]; 246 _M_profile_resize(__old_size); 247 return __res; 248 } 249 250 void 251 swap(unordered_map& __x) 252 noexcept( noexcept(__x._M_base().swap(__x)) ) 253 { _Base::swap(__x._M_base()); } 254 255 void rehash(size_type __n) 256 { 257 size_type __old_size = _Base::bucket_count(); 258 _Base::rehash(__n); 259 _M_profile_resize(__old_size); 260 } 261 262 private: 263 void 264 _M_profile_resize(size_type __old_size) 265 { 266 size_type __new_size = _Base::bucket_count(); 267 if (__old_size != __new_size) 268 __profcxx_hashtable_resize(this, __old_size, __new_size); 269 } 270 }; 271 272 template<typename _Key, typename _Tp, typename _Hash, 273 typename _Pred, typename _Alloc> 274 inline void 275 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 276 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 277 { __x.swap(__y); } 278 279 template<typename _Key, typename _Tp, typename _Hash, 280 typename _Pred, typename _Alloc> 281 inline bool 282 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 283 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 284 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 285 286 template<typename _Key, typename _Tp, typename _Hash, 287 typename _Pred, typename _Alloc> 288 inline bool 289 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 290 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 291 { return !(__x == __y); } 292 293 #undef _GLIBCXX_BASE 294 #undef _GLIBCXX_STD_BASE 295 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 296 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 297 298 /// Class std::unordered_multimap wrapper with performance instrumentation. 299 template<typename _Key, typename _Tp, 300 typename _Hash = std::hash<_Key>, 301 typename _Pred = std::equal_to<_Key>, 302 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 303 class unordered_multimap 304 : public _GLIBCXX_STD_BASE, 305 public _Unordered_profile<unordered_multimap<_Key, _Tp, 306 _Hash, _Pred, _Alloc>, 307 false> 308 { 309 typedef typename _GLIBCXX_STD_BASE _Base; 310 311 _Base& 312 _M_base() noexcept { return *this; } 313 314 const _Base& 315 _M_base() const noexcept { return *this; } 316 317 public: 318 typedef typename _Base::size_type size_type; 319 typedef typename _Base::hasher hasher; 320 typedef typename _Base::key_equal key_equal; 321 typedef typename _Base::allocator_type allocator_type; 322 typedef typename _Base::key_type key_type; 323 typedef typename _Base::value_type value_type; 324 typedef typename _Base::difference_type difference_type; 325 typedef typename _Base::reference reference; 326 typedef typename _Base::const_reference const_reference; 327 328 typedef typename _Base::iterator iterator; 329 typedef typename _Base::const_iterator const_iterator; 330 331 explicit 332 unordered_multimap(size_type __n = 10, 333 const hasher& __hf = hasher(), 334 const key_equal& __eql = key_equal(), 335 const allocator_type& __a = allocator_type()) 336 : _Base(__n, __hf, __eql, __a) 337 { } 338 339 template<typename _InputIterator> 340 unordered_multimap(_InputIterator __f, _InputIterator __l, 341 size_type __n = 0, 342 const hasher& __hf = hasher(), 343 const key_equal& __eql = key_equal(), 344 const allocator_type& __a = allocator_type()) 345 : _Base(__f, __l, __n, __hf, __eql, __a) 346 { } 347 348 unordered_multimap(const unordered_multimap&) = default; 349 350 unordered_multimap(const _Base& __x) 351 : _Base(__x) 352 { } 353 354 unordered_multimap(unordered_multimap&&) = default; 355 356 explicit 357 unordered_multimap(const allocator_type& __a) 358 : _Base(__a) 359 { } 360 361 unordered_multimap(const unordered_multimap& __ummap, 362 const allocator_type& __a) 363 : _Base(__ummap._M_base(), __a) 364 { } 365 366 unordered_multimap(unordered_multimap&& __ummap, 367 const allocator_type& __a) 368 : _Base(std::move(__ummap._M_base()), __a) 369 { } 370 371 unordered_multimap(initializer_list<value_type> __l, 372 size_type __n = 0, 373 const hasher& __hf = hasher(), 374 const key_equal& __eql = key_equal(), 375 const allocator_type& __a = allocator_type()) 376 : _Base(__l, __n, __hf, __eql, __a) 377 { } 378 379 unordered_multimap& 380 operator=(const unordered_multimap&) = default; 381 382 unordered_multimap& 383 operator=(unordered_multimap&&) = default; 384 385 unordered_multimap& 386 operator=(initializer_list<value_type> __l) 387 { 388 _M_base() = __l; 389 return *this; 390 } 391 392 void 393 clear() noexcept 394 { 395 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 396 _Base::size()); 397 this->_M_profile_destruct(); 398 _Base::clear(); 399 } 400 401 template<typename... _Args> 402 iterator 403 emplace(_Args&&... __args) 404 { 405 size_type __old_size = _Base::bucket_count(); 406 iterator __res 407 = _Base::emplace(std::forward<_Args>(__args)...); 408 _M_profile_resize(__old_size); 409 return __res; 410 } 411 412 template<typename... _Args> 413 iterator 414 emplace_hint(const_iterator __it, _Args&&... __args) 415 { 416 size_type __old_size = _Base::bucket_count(); 417 iterator __res 418 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 419 _M_profile_resize(__old_size); 420 return __res; 421 } 422 423 void 424 insert(std::initializer_list<value_type> __l) 425 { 426 size_type __old_size = _Base::bucket_count(); 427 _Base::insert(__l); 428 _M_profile_resize(__old_size); 429 } 430 431 iterator 432 insert(const value_type& __obj) 433 { 434 size_type __old_size = _Base::bucket_count(); 435 iterator __res = _Base::insert(__obj); 436 _M_profile_resize(__old_size); 437 return __res; 438 } 439 440 iterator 441 insert(const_iterator __iter, const value_type& __v) 442 { 443 size_type __old_size = _Base::bucket_count(); 444 iterator __res = _Base::insert(__iter, __v); 445 _M_profile_resize(__old_size); 446 return __res; 447 } 448 449 template<typename _Pair, typename = typename 450 std::enable_if<std::is_constructible<value_type, 451 _Pair&&>::value>::type> 452 iterator 453 insert(_Pair&& __obj) 454 { 455 size_type __old_size = _Base::bucket_count(); 456 iterator __res = _Base::insert(std::forward<_Pair>(__obj)); 457 _M_profile_resize(__old_size); 458 return __res; 459 } 460 461 template<typename _Pair, typename = typename 462 std::enable_if<std::is_constructible<value_type, 463 _Pair&&>::value>::type> 464 iterator 465 insert(const_iterator __iter, _Pair&& __v) 466 { 467 size_type __old_size = _Base::bucket_count(); 468 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 469 _M_profile_resize(__old_size); 470 return __res; 471 } 472 473 template<typename _InputIter> 474 void 475 insert(_InputIter __first, _InputIter __last) 476 { 477 size_type __old_size = _Base::bucket_count(); 478 _Base::insert(__first, __last); 479 _M_profile_resize(__old_size); 480 } 481 482 void 483 swap(unordered_multimap& __x) 484 noexcept( noexcept(__x._M_base().swap(__x)) ) 485 { _Base::swap(__x._M_base()); } 486 487 void 488 rehash(size_type __n) 489 { 490 size_type __old_size = _Base::bucket_count(); 491 _Base::rehash(__n); 492 _M_profile_resize(__old_size); 493 } 494 495 private: 496 void 497 _M_profile_resize(size_type __old_size) 498 { 499 size_type __new_size = _Base::bucket_count(); 500 if (__old_size != __new_size) 501 __profcxx_hashtable_resize(this, __old_size, __new_size); 502 } 503 }; 504 505 template<typename _Key, typename _Tp, typename _Hash, 506 typename _Pred, typename _Alloc> 507 inline void 508 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 509 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 510 { __x.swap(__y); } 511 512 template<typename _Key, typename _Tp, typename _Hash, 513 typename _Pred, typename _Alloc> 514 inline bool 515 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 516 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 517 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 518 519 template<typename _Key, typename _Tp, typename _Hash, 520 typename _Pred, typename _Alloc> 521 inline bool 522 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 523 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 524 { return !(__x == __y); } 525 526 } // namespace __profile 527 } // namespace std 528 529 #undef _GLIBCXX_BASE 530 #undef _GLIBCXX_STD_BASE 531 532 #endif // C++11 533 534 #endif 535
