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