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_PR::_GLIBCXX_BASE 46 47namespace std 48{ 49namespace __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 = 10, 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::forward<_Base>(__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 = 10, 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 template<typename _InputIter> 193 void 194 insert(_InputIter __first, _InputIter __last) 195 { 196 size_type __old_size = _Base::bucket_count(); 197 _Base::insert(__first, __last); 198 _M_profile_resize(__old_size, _Base::bucket_count()); 199 } 200 201 void 202 insert(const value_type* __first, const value_type* __last) 203 { 204 size_type __old_size = _Base::bucket_count(); 205 _Base::insert(__first, __last); 206 _M_profile_resize(__old_size, _Base::bucket_count()); 207 } 208 209 void rehash(size_type __n) 210 { 211 size_type __old_size = _Base::bucket_count(); 212 _Base::rehash(__n); 213 _M_profile_resize(__old_size, _Base::bucket_count()); 214 } 215 216 private: 217 _Base& 218 _M_base() { return *this; } 219 220 const _Base& 221 _M_base() const { return *this; } 222 223 void 224 _M_profile_resize(size_type __old_size, size_type __new_size) 225 { 226 if (__old_size != __new_size) 227 __profcxx_hashtable_resize(this, __old_size, __new_size); 228 } 229 230 void 231 _M_profile_destruct() 232 { 233 size_type __hops = 0, __lc = 0, __chain = 0; 234 for (iterator __it = _M_base().begin(); __it != _M_base().end(); 235 ++__it) 236 { 237 while (__it._M_cur_node->_M_next) 238 { 239 ++__chain; 240 ++__it; 241 } 242 243 if (__chain) 244 { 245 ++__chain; 246 __lc = __lc > __chain ? __lc : __chain; 247 __hops += __chain * (__chain - 1) / 2; 248 __chain = 0; 249 } 250 } 251 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 252 } 253 254 }; 255 256 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 257 inline void 258 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 259 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 260 { __x.swap(__y); } 261 262 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 263 inline bool 264 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 265 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 266 { return __x._M_equal(__y); } 267 268 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 269 inline bool 270 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 271 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 272 { return !(__x == __y); } 273 274#undef _GLIBCXX_BASE 275#undef _GLIBCXX_STD_BASE 276#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE 277#define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc> 278 279 /** @brief Unordered_multiset wrapper with performance instrumentation. */ 280 template<typename _Value, 281 typename _Hash = std::hash<_Value>, 282 typename _Pred = std::equal_to<_Value>, 283 typename _Alloc = std::allocator<_Value> > 284 class unordered_multiset 285 : public _GLIBCXX_STD_BASE 286 { 287 typedef typename _GLIBCXX_STD_BASE _Base; 288 289 public: 290 typedef typename _Base::size_type size_type; 291 typedef typename _Base::hasher hasher; 292 typedef typename _Base::key_equal key_equal; 293 typedef typename _Base::allocator_type allocator_type; 294 typedef typename _Base::key_type key_type; 295 typedef typename _Base::value_type value_type; 296 typedef typename _Base::difference_type difference_type; 297 typedef typename _Base::reference reference; 298 typedef typename _Base::const_reference const_reference; 299 300 typedef typename _Base::iterator iterator; 301 typedef typename _Base::const_iterator const_iterator; 302 303 explicit 304 unordered_multiset(size_type __n = 10, 305 const hasher& __hf = hasher(), 306 const key_equal& __eql = key_equal(), 307 const allocator_type& __a = allocator_type()) 308 : _Base(__n, __hf, __eql, __a) 309 { 310 __profcxx_hashtable_construct(this, _Base::bucket_count()); 311 } 312 313 template<typename _InputIterator> 314 unordered_multiset(_InputIterator __f, _InputIterator __l, 315 size_type __n = 10, 316 const hasher& __hf = hasher(), 317 const key_equal& __eql = key_equal(), 318 const allocator_type& __a = allocator_type()) 319 : _Base(__f, __l, __n, __hf, __eql, __a) 320 { 321 __profcxx_hashtable_construct(this, _Base::bucket_count()); 322 } 323 324 unordered_multiset(const _Base& __x) 325 : _Base(__x) 326 { 327 __profcxx_hashtable_construct(this, _Base::bucket_count()); 328 } 329 330 unordered_multiset(unordered_multiset&& __x) 331 : _Base(std::forward<_Base>(__x)) 332 { 333 __profcxx_hashtable_construct(this, _Base::bucket_count()); 334 } 335 336 unordered_multiset(initializer_list<value_type> __l, 337 size_type __n = 10, 338 const hasher& __hf = hasher(), 339 const key_equal& __eql = key_equal(), 340 const allocator_type& __a = allocator_type()) 341 : _Base(__l, __n, __hf, __eql, __a) { } 342 343 unordered_multiset& 344 operator=(const unordered_multiset& __x) 345 { 346 *static_cast<_Base*>(this) = __x; 347 return *this; 348 } 349 350 unordered_multiset& 351 operator=(unordered_multiset&& __x) 352 { 353 // NB: DR 1204. 354 // NB: DR 675. 355 this->clear(); 356 this->swap(__x); 357 return *this; 358 } 359 360 unordered_multiset& 361 operator=(initializer_list<value_type> __l) 362 { 363 this->clear(); 364 this->insert(__l); 365 return *this; 366 } 367 368 ~unordered_multiset() 369 { 370 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 371 _Base::size()); 372 _M_profile_destruct(); 373 } 374 375 void 376 swap(unordered_multiset& __x) 377 { 378 _Base::swap(__x); 379 } 380 381 void 382 clear() 383 { 384 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 385 _Base::size()); 386 _M_profile_destruct(); 387 _Base::clear(); 388 } 389 390 void 391 insert(std::initializer_list<value_type> __l) 392 { 393 size_type __old_size = _Base::bucket_count(); 394 _Base::insert(__l); 395 _M_profile_resize(__old_size, _Base::bucket_count()); 396 } 397 398 iterator 399 insert(const value_type& __obj) 400 { 401 size_type __old_size = _Base::bucket_count(); 402 iterator __res = _Base::insert(__obj); 403 _M_profile_resize(__old_size, _Base::bucket_count()); 404 return __res; 405 } 406 407 iterator 408 insert(const_iterator __iter, const value_type& __v) 409 { 410 size_type __old_size = _Base::bucket_count(); 411 iterator __res = _Base::insert(__iter, __v); 412 _M_profile_resize(__old_size, _Base::bucket_count()); 413 return __res; 414 } 415 416 template<typename _InputIter> 417 void 418 insert(_InputIter __first, _InputIter __last) 419 { 420 size_type __old_size = _Base::bucket_count(); 421 _Base::insert(__first, __last); 422 _M_profile_resize(__old_size, _Base::bucket_count()); 423 } 424 425 void 426 insert(const value_type* __first, const value_type* __last) 427 { 428 size_type __old_size = _Base::bucket_count(); 429 _Base::insert(__first, __last); 430 _M_profile_resize(__old_size, _Base::bucket_count()); 431 } 432 433 void rehash(size_type __n) 434 { 435 size_type __old_size = _Base::bucket_count(); 436 _Base::rehash(__n); 437 _M_profile_resize(__old_size, _Base::bucket_count()); 438 } 439 440 private: 441 _Base& 442 _M_base() { return *this; } 443 444 const _Base& 445 _M_base() const { return *this; } 446 447 void 448 _M_profile_resize(size_type __old_size, size_type __new_size) 449 { 450 if (__old_size != __new_size) 451 __profcxx_hashtable_resize(this, __old_size, __new_size); 452 } 453 454 void 455 _M_profile_destruct() 456 { 457 size_type __hops = 0, __lc = 0, __chain = 0; 458 for (iterator __it = _M_base().begin(); __it != _M_base().end(); 459 ++__it) 460 { 461 while (__it._M_cur_node->_M_next) 462 { 463 ++__chain; 464 ++__it; 465 } 466 467 if (__chain) 468 { 469 ++__chain; 470 __lc = __lc > __chain ? __lc : __chain; 471 __hops += __chain * (__chain - 1) / 2; 472 __chain = 0; 473 } 474 } 475 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 476 } 477 478 }; 479 480 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 481 inline void 482 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 483 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 484 { __x.swap(__y); } 485 486 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 487 inline bool 488 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 489 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 490 { return __x._M_equal(__y); } 491 492 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 493 inline bool 494 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 495 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 496 { return !(__x == __y); } 497 498} // namespace __profile 499} // namespace std 500 501#undef _GLIBCXX_BASE 502#undef _GLIBCXX_STD_BASE 503 504#endif // __GXX_EXPERIMENTAL_CXX0X__ 505 506#endif 507