1 // Profiling unordered_set/unordered_multiset 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_set 31 * This file is a GNU profile extension to the Standard C++ Library. 32 */ 33 34 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET 35 #define _GLIBCXX_PROFILE_UNORDERED_SET 1 36 37 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 38 # include <bits/c++0x_warning.h> 39 #else 40 # include <unordered_set> 41 42 #include <profile/base.h> 43 44 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc> 45 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 46 47 namespace std _GLIBCXX_VISIBILITY(default) 48 { 49 namespace __profile 50 { 51 /** @brief Unordered_set wrapper with performance instrumentation. */ 52 template<typename _Key, 53 typename _Hash = std::hash<_Key>, 54 typename _Pred = std::equal_to<_Key>, 55 typename _Alloc = std::allocator<_Key> > 56 class unordered_set 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 72 typedef typename _Base::iterator iterator; 73 typedef typename _Base::const_iterator const_iterator; 74 75 explicit 76 unordered_set(size_type __n = 10, 77 const hasher& __hf = hasher(), 78 const key_equal& __eql = key_equal(), 79 const allocator_type& __a = allocator_type()) 80 : _Base(__n, __hf, __eql, __a) 81 { 82 __profcxx_hashtable_construct(this, _Base::bucket_count()); 83 __profcxx_hashtable_construct2(this); 84 } 85 86 template<typename _InputIterator> 87 unordered_set(_InputIterator __f, _InputIterator __l, 88 size_type __n = 0, 89 const hasher& __hf = hasher(), 90 const key_equal& __eql = key_equal(), 91 const allocator_type& __a = allocator_type()) 92 : _Base(__f, __l, __n, __hf, __eql, __a) 93 { 94 __profcxx_hashtable_construct(this, _Base::bucket_count()); 95 __profcxx_hashtable_construct2(this); 96 } 97 98 unordered_set(const _Base& __x) 99 : _Base(__x) 100 { 101 __profcxx_hashtable_construct(this, _Base::bucket_count()); 102 __profcxx_hashtable_construct2(this); 103 } 104 105 unordered_set(unordered_set&& __x) 106 : _Base(std::move(__x)) 107 { 108 __profcxx_hashtable_construct(this, _Base::bucket_count()); 109 __profcxx_hashtable_construct2(this); 110 } 111 112 unordered_set(initializer_list<value_type> __l, 113 size_type __n = 0, 114 const hasher& __hf = hasher(), 115 const key_equal& __eql = key_equal(), 116 const allocator_type& __a = allocator_type()) 117 : _Base(__l, __n, __hf, __eql, __a) { } 118 119 unordered_set& 120 operator=(const unordered_set& __x) 121 { 122 *static_cast<_Base*>(this) = __x; 123 return *this; 124 } 125 126 unordered_set& 127 operator=(unordered_set&& __x) 128 { 129 // NB: DR 1204. 130 // NB: DR 675. 131 this->clear(); 132 this->swap(__x); 133 return *this; 134 } 135 136 unordered_set& 137 operator=(initializer_list<value_type> __l) 138 { 139 this->clear(); 140 this->insert(__l); 141 return *this; 142 } 143 144 ~unordered_set() 145 { 146 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 147 _Base::size()); 148 _M_profile_destruct(); 149 } 150 151 void 152 swap(unordered_set& __x) 153 { 154 _Base::swap(__x); 155 } 156 157 void 158 clear() 159 { 160 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 161 _Base::size()); 162 _M_profile_destruct(); 163 _Base::clear(); 164 } 165 166 void 167 insert(std::initializer_list<value_type> __l) 168 { 169 size_type __old_size = _Base::bucket_count(); 170 _Base::insert(__l); 171 _M_profile_resize(__old_size, _Base::bucket_count()); 172 } 173 174 std::pair<iterator, bool> 175 insert(const value_type& __obj) 176 { 177 size_type __old_size = _Base::bucket_count(); 178 std::pair<iterator, bool> __res = _Base::insert(__obj); 179 _M_profile_resize(__old_size, _Base::bucket_count()); 180 return __res; 181 } 182 183 iterator 184 insert(const_iterator __iter, const value_type& __v) 185 { 186 size_type __old_size = _Base::bucket_count(); 187 iterator __res = _Base::insert(__iter, __v); 188 _M_profile_resize(__old_size, _Base::bucket_count()); 189 return __res; 190 } 191 192 std::pair<iterator, bool> 193 insert(value_type&& __obj) 194 { 195 size_type __old_size = _Base::bucket_count(); 196 std::pair<iterator, bool> __res = _Base::insert(std::move(__obj)); 197 _M_profile_resize(__old_size, _Base::bucket_count()); 198 return __res; 199 } 200 201 iterator 202 insert(const_iterator __iter, value_type&& __v) 203 { 204 size_type __old_size = _Base::bucket_count(); 205 iterator __res = _Base::insert(__iter, std::move(__v)); 206 _M_profile_resize(__old_size, _Base::bucket_count()); 207 return __res; 208 } 209 210 template<typename _InputIter> 211 void 212 insert(_InputIter __first, _InputIter __last) 213 { 214 size_type __old_size = _Base::bucket_count(); 215 _Base::insert(__first, __last); 216 _M_profile_resize(__old_size, _Base::bucket_count()); 217 } 218 219 void 220 insert(const value_type* __first, const value_type* __last) 221 { 222 size_type __old_size = _Base::bucket_count(); 223 _Base::insert(__first, __last); 224 _M_profile_resize(__old_size, _Base::bucket_count()); 225 } 226 227 void rehash(size_type __n) 228 { 229 size_type __old_size = _Base::bucket_count(); 230 _Base::rehash(__n); 231 _M_profile_resize(__old_size, _Base::bucket_count()); 232 } 233 234 private: 235 _Base& 236 _M_base() { return *this; } 237 238 const _Base& 239 _M_base() const { return *this; } 240 241 void 242 _M_profile_resize(size_type __old_size, size_type __new_size) 243 { 244 if (__old_size != __new_size) 245 __profcxx_hashtable_resize(this, __old_size, __new_size); 246 } 247 248 void 249 _M_profile_destruct() 250 { 251 size_type __hops = 0, __lc = 0, __chain = 0; 252 for (iterator __it = _M_base().begin(); __it != _M_base().end(); 253 ++__it) 254 { 255 while (__it._M_cur_node->_M_next) 256 { 257 ++__chain; 258 ++__it; 259 } 260 261 if (__chain) 262 { 263 ++__chain; 264 __lc = __lc > __chain ? __lc : __chain; 265 __hops += __chain * (__chain - 1) / 2; 266 __chain = 0; 267 } 268 } 269 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 270 } 271 272 }; 273 274 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 275 inline void 276 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 277 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 278 { __x.swap(__y); } 279 280 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 281 inline bool 282 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 283 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 284 { return __x._M_equal(__y); } 285 286 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 287 inline bool 288 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 289 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 290 { return !(__x == __y); } 291 292 #undef _GLIBCXX_BASE 293 #undef _GLIBCXX_STD_BASE 294 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 295 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc> 296 297 /** @brief Unordered_multiset wrapper with performance instrumentation. */ 298 template<typename _Value, 299 typename _Hash = std::hash<_Value>, 300 typename _Pred = std::equal_to<_Value>, 301 typename _Alloc = std::allocator<_Value> > 302 class unordered_multiset 303 : public _GLIBCXX_STD_BASE 304 { 305 typedef typename _GLIBCXX_STD_BASE _Base; 306 307 public: 308 typedef typename _Base::size_type size_type; 309 typedef typename _Base::hasher hasher; 310 typedef typename _Base::key_equal key_equal; 311 typedef typename _Base::allocator_type allocator_type; 312 typedef typename _Base::key_type key_type; 313 typedef typename _Base::value_type value_type; 314 typedef typename _Base::difference_type difference_type; 315 typedef typename _Base::reference reference; 316 typedef typename _Base::const_reference const_reference; 317 318 typedef typename _Base::iterator iterator; 319 typedef typename _Base::const_iterator const_iterator; 320 321 explicit 322 unordered_multiset(size_type __n = 10, 323 const hasher& __hf = hasher(), 324 const key_equal& __eql = key_equal(), 325 const allocator_type& __a = allocator_type()) 326 : _Base(__n, __hf, __eql, __a) 327 { 328 __profcxx_hashtable_construct(this, _Base::bucket_count()); 329 } 330 331 template<typename _InputIterator> 332 unordered_multiset(_InputIterator __f, _InputIterator __l, 333 size_type __n = 0, 334 const hasher& __hf = hasher(), 335 const key_equal& __eql = key_equal(), 336 const allocator_type& __a = allocator_type()) 337 : _Base(__f, __l, __n, __hf, __eql, __a) 338 { 339 __profcxx_hashtable_construct(this, _Base::bucket_count()); 340 } 341 342 unordered_multiset(const _Base& __x) 343 : _Base(__x) 344 { 345 __profcxx_hashtable_construct(this, _Base::bucket_count()); 346 } 347 348 unordered_multiset(unordered_multiset&& __x) 349 : _Base(std::move(__x)) 350 { 351 __profcxx_hashtable_construct(this, _Base::bucket_count()); 352 } 353 354 unordered_multiset(initializer_list<value_type> __l, 355 size_type __n = 0, 356 const hasher& __hf = hasher(), 357 const key_equal& __eql = key_equal(), 358 const allocator_type& __a = allocator_type()) 359 : _Base(__l, __n, __hf, __eql, __a) { } 360 361 unordered_multiset& 362 operator=(const unordered_multiset& __x) 363 { 364 *static_cast<_Base*>(this) = __x; 365 return *this; 366 } 367 368 unordered_multiset& 369 operator=(unordered_multiset&& __x) 370 { 371 // NB: DR 1204. 372 // NB: DR 675. 373 this->clear(); 374 this->swap(__x); 375 return *this; 376 } 377 378 unordered_multiset& 379 operator=(initializer_list<value_type> __l) 380 { 381 this->clear(); 382 this->insert(__l); 383 return *this; 384 } 385 386 ~unordered_multiset() 387 { 388 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 389 _Base::size()); 390 _M_profile_destruct(); 391 } 392 393 void 394 swap(unordered_multiset& __x) 395 { 396 _Base::swap(__x); 397 } 398 399 void 400 clear() 401 { 402 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 403 _Base::size()); 404 _M_profile_destruct(); 405 _Base::clear(); 406 } 407 408 void 409 insert(std::initializer_list<value_type> __l) 410 { 411 size_type __old_size = _Base::bucket_count(); 412 _Base::insert(__l); 413 _M_profile_resize(__old_size, _Base::bucket_count()); 414 } 415 416 iterator 417 insert(const value_type& __obj) 418 { 419 size_type __old_size = _Base::bucket_count(); 420 iterator __res = _Base::insert(__obj); 421 _M_profile_resize(__old_size, _Base::bucket_count()); 422 return __res; 423 } 424 425 iterator 426 insert(const_iterator __iter, const value_type& __v) 427 { 428 size_type __old_size = _Base::bucket_count(); 429 iterator __res = _Base::insert(__iter, __v); 430 _M_profile_resize(__old_size, _Base::bucket_count()); 431 return __res; 432 } 433 434 iterator 435 insert(value_type&& __obj) 436 { 437 size_type __old_size = _Base::bucket_count(); 438 iterator __res = _Base::insert(std::move(__obj)); 439 _M_profile_resize(__old_size, _Base::bucket_count()); 440 return __res; 441 } 442 443 iterator 444 insert(const_iterator __iter, value_type&& __v) 445 { 446 size_type __old_size = _Base::bucket_count(); 447 iterator __res = _Base::insert(__iter, std::move(__v)); 448 _M_profile_resize(__old_size, _Base::bucket_count()); 449 return __res; 450 } 451 452 template<typename _InputIter> 453 void 454 insert(_InputIter __first, _InputIter __last) 455 { 456 size_type __old_size = _Base::bucket_count(); 457 _Base::insert(__first, __last); 458 _M_profile_resize(__old_size, _Base::bucket_count()); 459 } 460 461 void 462 insert(const value_type* __first, const value_type* __last) 463 { 464 size_type __old_size = _Base::bucket_count(); 465 _Base::insert(__first, __last); 466 _M_profile_resize(__old_size, _Base::bucket_count()); 467 } 468 469 void rehash(size_type __n) 470 { 471 size_type __old_size = _Base::bucket_count(); 472 _Base::rehash(__n); 473 _M_profile_resize(__old_size, _Base::bucket_count()); 474 } 475 476 private: 477 _Base& 478 _M_base() { return *this; } 479 480 const _Base& 481 _M_base() const { return *this; } 482 483 void 484 _M_profile_resize(size_type __old_size, size_type __new_size) 485 { 486 if (__old_size != __new_size) 487 __profcxx_hashtable_resize(this, __old_size, __new_size); 488 } 489 490 void 491 _M_profile_destruct() 492 { 493 size_type __hops = 0, __lc = 0, __chain = 0; 494 for (iterator __it = _M_base().begin(); __it != _M_base().end(); 495 ++__it) 496 { 497 while (__it._M_cur_node->_M_next) 498 { 499 ++__chain; 500 ++__it; 501 } 502 503 if (__chain) 504 { 505 ++__chain; 506 __lc = __lc > __chain ? __lc : __chain; 507 __hops += __chain * (__chain - 1) / 2; 508 __chain = 0; 509 } 510 } 511 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 512 } 513 514 }; 515 516 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 517 inline void 518 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 519 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 520 { __x.swap(__y); } 521 522 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 523 inline bool 524 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 525 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 526 { return __x._M_equal(__y); } 527 528 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 529 inline bool 530 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 531 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 532 { return !(__x == __y); } 533 534 } // namespace __profile 535 } // namespace std 536 537 #undef _GLIBCXX_BASE 538 #undef _GLIBCXX_STD_BASE 539 540 #endif // __GXX_EXPERIMENTAL_CXX0X__ 541 542 #endif 543
