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