1// Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 2 3// Copyright (C) 2009, 2010 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 2, 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// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/** @file profile/unordered_map 31 * This file is a GNU profile extension to the Standard C++ Library. 32 */ 33 34#ifndef _GLIBCXX_PROFILE_UNORDERED_MAP 35#define _GLIBCXX_PROFILE_UNORDERED_MAP 1 36 37#ifndef __GXX_EXPERIMENTAL_CXX0X__ 38# include <bits/c++0x_warning.h> 39#else 40# include <unordered_map> 41 42#include <profile/base.h> 43 44#define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 45#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE 46 47namespace std 48{ 49namespace __profile 50{ 51 /// Class std::unordered_map wrapper with performance instrumentation. 52 template<typename _Key, typename _Tp, 53 typename _Hash = std::hash<_Key>, 54 typename _Pred = std::equal_to<_Key>, 55 typename _Alloc = std::allocator<_Key> > 56 class unordered_map 57 : public _GLIBCXX_STD_BASE 58 { 59 typedef typename _GLIBCXX_STD_BASE _Base; 60 61 public: 62 typedef typename _Base::size_type size_type; 63 typedef typename _Base::hasher hasher; 64 typedef typename _Base::key_equal key_equal; 65 typedef typename _Base::allocator_type allocator_type; 66 typedef typename _Base::key_type key_type; 67 typedef typename _Base::value_type value_type; 68 typedef typename _Base::difference_type difference_type; 69 typedef typename _Base::reference reference; 70 typedef typename _Base::const_reference const_reference; 71 typedef typename _Base::mapped_type mapped_type; 72 73 typedef typename _Base::iterator iterator; 74 typedef typename _Base::const_iterator const_iterator; 75 76 explicit 77 unordered_map(size_type __n = 10, 78 const hasher& __hf = hasher(), 79 const key_equal& __eql = key_equal(), 80 const allocator_type& __a = allocator_type()) 81 : _Base(__n, __hf, __eql, __a) 82 { 83 __profcxx_hashtable_construct(this, _Base::bucket_count()); 84 __profcxx_hashtable_construct2(this); 85 } 86 87 template<typename _InputIterator> 88 unordered_map(_InputIterator __f, _InputIterator __l, 89 size_type __n = 10, 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 __profcxx_hashtable_construct(this, _Base::bucket_count()); 96 __profcxx_hashtable_construct2(this); 97 } 98 99 unordered_map(const _Base& __x) 100 : _Base(__x) 101 { 102 __profcxx_hashtable_construct(this, _Base::bucket_count()); 103 __profcxx_hashtable_construct2(this); 104 } 105 106 unordered_map(unordered_map&& __x) 107 : _Base(std::forward<_Base>(__x)) 108 { 109 __profcxx_hashtable_construct(this, _Base::bucket_count()); 110 __profcxx_hashtable_construct2(this); 111 } 112 113 unordered_map(initializer_list<value_type> __l, 114 size_type __n = 10, 115 const hasher& __hf = hasher(), 116 const key_equal& __eql = key_equal(), 117 const allocator_type& __a = allocator_type()) 118 : _Base(__l, __n, __hf, __eql, __a) { } 119 120 unordered_map& 121 operator=(const unordered_map& __x) 122 { 123 *static_cast<_Base*>(this) = __x; 124 return *this; 125 } 126 127 unordered_map& 128 operator=(unordered_map&& __x) 129 { 130 // NB: DR 1204. 131 // NB: DR 675. 132 this->clear(); 133 this->swap(__x); 134 return *this; 135 } 136 137 unordered_map& 138 operator=(initializer_list<value_type> __l) 139 { 140 this->clear(); 141 this->insert(__l); 142 return *this; 143 } 144 145 ~unordered_map() 146 { 147 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 148 _Base::size()); 149 _M_profile_destruct(); 150 } 151 152 _Base& 153 _M_base() { return *this; } 154 155 const _Base& 156 _M_base() const { return *this; } 157 158 159 void 160 clear() 161 { 162 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 163 _Base::size()); 164 _M_profile_destruct(); 165 _Base::clear(); 166 } 167 168 void 169 insert(std::initializer_list<value_type> __l) 170 { 171 size_type __old_size = _Base::bucket_count(); 172 _Base::insert(__l); 173 _M_profile_resize(__old_size, _Base::bucket_count()); 174 } 175 176 std::pair<iterator, bool> 177 insert(const value_type& __obj) 178 { 179 size_type __old_size = _Base::bucket_count(); 180 std::pair<iterator, bool> __res = _Base::insert(__obj); 181 _M_profile_resize(__old_size, _Base::bucket_count()); 182 return __res; 183 } 184 185 iterator 186 insert(const_iterator __iter, const value_type& __v) 187 { 188 size_type __old_size = _Base::bucket_count(); 189 iterator __res = _Base::insert(__iter, __v); 190 _M_profile_resize(__old_size, _Base::bucket_count()); 191 return __res; 192 } 193 194 template<typename _InputIter> 195 void 196 insert(_InputIter __first, _InputIter __last) 197 { 198 size_type __old_size = _Base::bucket_count(); 199 _Base::insert(__first, __last); 200 _M_profile_resize(__old_size, _Base::bucket_count()); 201 } 202 203 void 204 insert(const value_type* __first, const value_type* __last) 205 { 206 size_type __old_size = _Base::bucket_count(); 207 _Base::insert(__first, __last); 208 _M_profile_resize(__old_size, _Base::bucket_count()); 209 } 210 211 // operator [] 212 mapped_type& 213 operator[](const _Key& _k) 214 { 215 size_type __old_size = _Base::bucket_count(); 216 mapped_type& __res = _M_base()[_k]; 217 size_type __new_size = _Base::bucket_count(); 218 _M_profile_resize(__old_size, _Base::bucket_count()); 219 return __res; 220 } 221 222 void 223 swap(unordered_map& __x) 224 { _Base::swap(__x); } 225 226 void rehash(size_type __n) 227 { 228 size_type __old_size = _Base::bucket_count(); 229 _Base::rehash(__n); 230 _M_profile_resize(__old_size, _Base::bucket_count()); 231 } 232 233 private: 234 void 235 _M_profile_resize(size_type __old_size, size_type __new_size) 236 { 237 if (__old_size != __new_size) 238 __profcxx_hashtable_resize(this, __old_size, __new_size); 239 } 240 241 void 242 _M_profile_destruct() 243 { 244 size_type __hops = 0, __lc = 0, __chain = 0; 245 for (iterator __it = _M_base().begin(); __it != _M_base().end(); 246 ++__it) 247 { 248 while (__it._M_cur_node->_M_next) 249 { 250 ++__chain; 251 ++__it; 252 } 253 if (__chain) 254 { 255 ++__chain; 256 __lc = __lc > __chain ? __lc : __chain; 257 __hops += __chain * (__chain - 1) / 2; 258 __chain = 0; 259 } 260 } 261 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 262 } 263 }; 264 265 template<typename _Key, typename _Tp, typename _Hash, 266 typename _Pred, typename _Alloc> 267 inline void 268 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 269 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 270 { __x.swap(__y); } 271 272 template<typename _Key, typename _Tp, typename _Hash, 273 typename _Pred, typename _Alloc> 274 inline bool 275 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 276 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 277 { return __x._M_equal(__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 !(__x == __y); } 285 286#undef _GLIBCXX_BASE 287#undef _GLIBCXX_STD_BASE 288#define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 289#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE 290 291 /// Class std::unordered_multimap wrapper with performance instrumentation. 292 template<typename _Key, typename _Tp, 293 typename _Hash = std::hash<_Key>, 294 typename _Pred = std::equal_to<_Key>, 295 typename _Alloc = std::allocator<_Key> > 296 class unordered_multimap 297 : public _GLIBCXX_STD_BASE 298 { 299 typedef typename _GLIBCXX_STD_BASE _Base; 300 301 public: 302 typedef typename _Base::size_type size_type; 303 typedef typename _Base::hasher hasher; 304 typedef typename _Base::key_equal key_equal; 305 typedef typename _Base::allocator_type allocator_type; 306 typedef typename _Base::key_type key_type; 307 typedef typename _Base::value_type value_type; 308 typedef typename _Base::difference_type difference_type; 309 typedef typename _Base::reference reference; 310 typedef typename _Base::const_reference const_reference; 311 312 typedef typename _Base::iterator iterator; 313 typedef typename _Base::const_iterator const_iterator; 314 315 explicit 316 unordered_multimap(size_type __n = 10, 317 const hasher& __hf = hasher(), 318 const key_equal& __eql = key_equal(), 319 const allocator_type& __a = allocator_type()) 320 : _Base(__n, __hf, __eql, __a) 321 { 322 __profcxx_hashtable_construct(this, _Base::bucket_count()); 323 } 324 template<typename _InputIterator> 325 unordered_multimap(_InputIterator __f, _InputIterator __l, 326 size_type __n = 10, 327 const hasher& __hf = hasher(), 328 const key_equal& __eql = key_equal(), 329 const allocator_type& __a = allocator_type()) 330 : _Base(__f, __l, __n, __hf, __eql, __a) 331 { 332 __profcxx_hashtable_construct(this, _Base::bucket_count()); 333 } 334 335 unordered_multimap(const _Base& __x) 336 : _Base(__x) 337 { 338 __profcxx_hashtable_construct(this, _Base::bucket_count()); 339 } 340 341 unordered_multimap(unordered_multimap&& __x) 342 : _Base(std::forward<_Base>(__x)) 343 { 344 __profcxx_hashtable_construct(this, _Base::bucket_count()); 345 } 346 347 unordered_multimap(initializer_list<value_type> __l, 348 size_type __n = 10, 349 const hasher& __hf = hasher(), 350 const key_equal& __eql = key_equal(), 351 const allocator_type& __a = allocator_type()) 352 : _Base(__l, __n, __hf, __eql, __a) { } 353 354 unordered_multimap& 355 operator=(const unordered_multimap& __x) 356 { 357 *static_cast<_Base*>(this) = __x; 358 return *this; 359 } 360 361 unordered_multimap& 362 operator=(unordered_multimap&& __x) 363 { 364 // NB: DR 1204. 365 // NB: DR 675. 366 this->clear(); 367 this->swap(__x); 368 return *this; 369 } 370 371 unordered_multimap& 372 operator=(initializer_list<value_type> __l) 373 { 374 this->clear(); 375 this->insert(__l); 376 return *this; 377 } 378 379 ~unordered_multimap() 380 { 381 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 382 _Base::size()); 383 _M_profile_destruct(); 384 } 385 386 _Base& 387 _M_base() { return *this; } 388 389 const _Base& 390 _M_base() const { return *this; } 391 392 393 void 394 clear() 395 { 396 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 397 _Base::size()); 398 _M_profile_destruct(); 399 _Base::clear(); 400 } 401 402 void 403 insert(std::initializer_list<value_type> __l) 404 { 405 size_type __old_size = _Base::bucket_count(); 406 _Base::insert(__l); 407 _M_profile_resize(__old_size, _Base::bucket_count()); 408 } 409 410 iterator 411 insert(const value_type& __obj) 412 { 413 size_type __old_size = _Base::bucket_count(); 414 iterator __res = _Base::insert(__obj); 415 _M_profile_resize(__old_size, _Base::bucket_count()); 416 return __res; 417 } 418 419 iterator 420 insert(const_iterator __iter, const value_type& __v) 421 { 422 size_type __old_size = _Base::bucket_count(); 423 iterator __res =_Base::insert(__iter, __v); 424 _M_profile_resize(__old_size, _Base::bucket_count()); 425 return __res; 426 } 427 428 template<typename _InputIter> 429 void 430 insert(_InputIter __first, _InputIter __last) 431 { 432 size_type __old_size = _Base::bucket_count(); 433 _Base::insert(__first, __last); 434 _M_profile_resize(__old_size, _Base::bucket_count()); 435 } 436 437 void 438 insert(const value_type* __first, const value_type* __last) 439 { 440 size_type __old_size = _Base::bucket_count(); 441 _Base::insert(__first, __last); 442 _M_profile_resize(__old_size, _Base::bucket_count()); 443 } 444 445 void 446 swap(unordered_multimap& __x) 447 { _Base::swap(__x); } 448 449 void rehash(size_type __n) 450 { 451 size_type __old_size = _Base::bucket_count(); 452 _Base::rehash(__n); 453 _M_profile_resize(__old_size, _Base::bucket_count()); 454 } 455 456 private: 457 void 458 _M_profile_resize(size_type __old_size, size_type __new_size) 459 { 460 if (__old_size != __new_size) 461 __profcxx_hashtable_resize(this, __old_size, __new_size); 462 } 463 464 void 465 _M_profile_destruct() 466 { 467 size_type __hops = 0, __lc = 0, __chain = 0; 468 for (iterator __it = _M_base().begin(); __it != _M_base().end(); 469 ++__it) 470 { 471 while (__it._M_cur_node->_M_next) 472 { 473 ++__chain; 474 ++__it; 475 } 476 if (__chain) 477 { 478 ++__chain; 479 __lc = __lc > __chain ? __lc : __chain; 480 __hops += __chain * (__chain - 1) / 2; 481 __chain = 0; 482 } 483 } 484 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 485 } 486 487 }; 488 489 template<typename _Key, typename _Tp, typename _Hash, 490 typename _Pred, typename _Alloc> 491 inline void 492 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 493 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 494 { __x.swap(__y); } 495 496 template<typename _Key, typename _Tp, typename _Hash, 497 typename _Pred, typename _Alloc> 498 inline bool 499 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 500 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 501 { return __x._M_equal(__y); } 502 503 template<typename _Key, typename _Tp, typename _Hash, 504 typename _Pred, typename _Alloc> 505 inline bool 506 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 507 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 508 { return !(__x == __y); } 509 510} // namespace __profile 511} // namespace std 512 513#undef _GLIBCXX_BASE 514#undef _GLIBCXX_STD_BASE 515 516#endif // __GXX_EXPERIMENTAL_CXX0X__ 517 518#endif 519