1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /** @file debug/unordered_set 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET 31 #define _GLIBCXX_DEBUG_UNORDERED_SET 1 32 33 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 34 # include <unordered_set> 35 #else 36 # include <c++0x_warning.h> 37 #endif 38 39 #include <debug/safe_sequence.h> 40 #include <debug/safe_iterator.h> 41 #include <initializer_list> 42 43 namespace std 44 { 45 namespace __debug 46 { 47 template<typename _Value, 48 typename _Hash = std::hash<_Value>, 49 typename _Pred = std::equal_to<_Value>, 50 typename _Alloc = std::allocator<_Value> > 51 class unordered_set 52 : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>, 53 public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash, 54 _Pred, _Alloc> > 55 { 56 typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash, 57 _Pred, _Alloc> _Base; 58 typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base; 59 60 public: 61 typedef typename _Base::size_type size_type; 62 typedef typename _Base::hasher hasher; 63 typedef typename _Base::key_equal key_equal; 64 typedef typename _Base::allocator_type allocator_type; 65 66 typedef typename _Base::key_type key_type; 67 typedef typename _Base::value_type value_type; 68 69 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 70 unordered_set> iterator; 71 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 72 unordered_set> const_iterator; 73 74 explicit 75 unordered_set(size_type __n = 10, 76 const hasher& __hf = hasher(), 77 const key_equal& __eql = key_equal(), 78 const allocator_type& __a = allocator_type()) 79 : _Base(__n, __hf, __eql, __a) { } 80 81 template<typename _InputIterator> 82 unordered_set(_InputIterator __f, _InputIterator __l, 83 size_type __n = 10, 84 const hasher& __hf = hasher(), 85 const key_equal& __eql = key_equal(), 86 const allocator_type& __a = allocator_type()) 87 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 88 __hf, __eql, __a), _Safe_base() { } 89 90 unordered_set(const unordered_set& __x) 91 : _Base(__x), _Safe_base() { } 92 93 unordered_set(const _Base& __x) 94 : _Base(__x), _Safe_base() { } 95 96 unordered_set(unordered_set&& __x) 97 : _Base(std::forward<unordered_set>(__x)), _Safe_base() { } 98 99 unordered_set(initializer_list<value_type> __l, 100 size_type __n = 10, 101 const hasher& __hf = hasher(), 102 const key_equal& __eql = key_equal(), 103 const allocator_type& __a = allocator_type()) 104 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 105 106 unordered_set& 107 operator=(const unordered_set& __x) 108 { 109 *static_cast<_Base*>(this) = __x; 110 this->_M_invalidate_all(); 111 return *this; 112 } 113 114 unordered_set& 115 operator=(unordered_set&& __x) 116 { 117 // NB: DR 675. 118 clear(); 119 swap(__x); 120 return *this; 121 } 122 123 unordered_set& 124 operator=(initializer_list<value_type> __l) 125 { 126 this->clear(); 127 this->insert(__l); 128 return *this; 129 } 130 131 void 132 swap(unordered_set&& __x) 133 { 134 _Base::swap(__x); 135 _Safe_base::_M_swap(__x); 136 } 137 138 void 139 clear() 140 { 141 _Base::clear(); 142 this->_M_invalidate_all(); 143 } 144 145 iterator 146 begin() 147 { return iterator(_Base::begin(), this); } 148 149 const_iterator 150 begin() const 151 { return const_iterator(_Base::begin(), this); } 152 153 iterator 154 end() 155 { return iterator(_Base::end(), this); } 156 157 const_iterator 158 end() const 159 { return const_iterator(_Base::end(), this); } 160 161 const_iterator 162 cbegin() const 163 { return const_iterator(_Base::begin(), this); } 164 165 const_iterator 166 cend() const 167 { return const_iterator(_Base::end(), this); } 168 169 // local versions 170 using _Base::begin; 171 using _Base::end; 172 using _Base::cbegin; 173 using _Base::cend; 174 175 std::pair<iterator, bool> 176 insert(const value_type& __obj) 177 { 178 typedef std::pair<typename _Base::iterator, bool> __pair_type; 179 __pair_type __res = _Base::insert(__obj); 180 return std::make_pair(iterator(__res.first, this), __res.second); 181 } 182 183 iterator 184 insert(iterator, const value_type& __obj) 185 { 186 typedef std::pair<typename _Base::iterator, bool> __pair_type; 187 __pair_type __res = _Base::insert(__obj); 188 return iterator(__res.first, this); 189 } 190 191 const_iterator 192 insert(const_iterator, const value_type& __obj) 193 { 194 typedef std::pair<typename _Base::iterator, bool> __pair_type; 195 __pair_type __res = _Base::insert(__obj); 196 return const_iterator(__res.first, this); 197 } 198 199 void 200 insert(std::initializer_list<value_type> __l) 201 { _Base::insert(__l); } 202 203 template<typename _InputIterator> 204 void 205 insert(_InputIterator __first, _InputIterator __last) 206 { 207 __glibcxx_check_valid_range(__first, __last); 208 _Base::insert(__first, __last); 209 } 210 211 iterator 212 find(const key_type& __key) 213 { return iterator(_Base::find(__key), this); } 214 215 const_iterator 216 find(const key_type& __key) const 217 { return const_iterator(_Base::find(__key), this); } 218 219 std::pair<iterator, iterator> 220 equal_range(const key_type& __key) 221 { 222 typedef typename _Base::iterator _Base_iterator; 223 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 224 __pair_type __res = _Base::equal_range(__key); 225 return std::make_pair(iterator(__res.first, this), 226 iterator(__res.second, this)); 227 } 228 229 std::pair<const_iterator, const_iterator> 230 equal_range(const key_type& __key) const 231 { 232 typedef typename _Base::const_iterator _Base_iterator; 233 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 234 __pair_type __res = _Base::equal_range(__key); 235 return std::make_pair(const_iterator(__res.first, this), 236 const_iterator(__res.second, this)); 237 } 238 239 size_type 240 erase(const key_type& __key) 241 { 242 size_type __ret(0); 243 iterator __victim(_Base::find(__key), this); 244 if (__victim != end()) 245 { 246 this->erase(__victim); 247 __ret = 1; 248 } 249 return __ret; 250 } 251 252 iterator 253 erase(iterator __it) 254 { 255 __glibcxx_check_erase(__it); 256 __it._M_invalidate(); 257 return iterator(_Base::erase(__it.base()), this); 258 } 259 260 const_iterator 261 erase(const_iterator __it) 262 { 263 __glibcxx_check_erase(__it); 264 __it._M_invalidate(); 265 return const_iterator(_Base::erase(__it.base()), this); 266 } 267 268 iterator 269 erase(iterator __first, iterator __last) 270 { 271 __glibcxx_check_erase_range(__first, __last); 272 for (iterator __tmp = __first; __tmp != __last;) 273 { 274 iterator __victim = __tmp++; 275 __victim._M_invalidate(); 276 } 277 return iterator(_Base::erase(__first.base(), 278 __last.base()), this); 279 } 280 281 const_iterator 282 erase(const_iterator __first, const_iterator __last) 283 { 284 __glibcxx_check_erase_range(__first, __last); 285 for (const_iterator __tmp = __first; __tmp != __last;) 286 { 287 const_iterator __victim = __tmp++; 288 __victim._M_invalidate(); 289 } 290 return const_iterator(_Base::erase(__first.base(), 291 __last.base()), this); 292 } 293 294 _Base& 295 _M_base() { return *this; } 296 297 const _Base& 298 _M_base() const { return *this; } 299 300 private: 301 void 302 _M_invalidate_all() 303 { 304 typedef typename _Base::const_iterator _Base_const_iterator; 305 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 306 this->_M_invalidate_if(_Not_equal(_M_base().end())); 307 } 308 }; 309 310 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 311 inline void 312 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 313 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 314 { __x.swap(__y); } 315 316 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 317 inline void 318 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>&& __x, 319 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 320 { __x.swap(__y); } 321 322 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 323 inline void 324 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 325 unordered_set<_Value, _Hash, _Pred, _Alloc>&& __y) 326 { __x.swap(__y); } 327 328 329 template<typename _Value, 330 typename _Hash = std::hash<_Value>, 331 typename _Pred = std::equal_to<_Value>, 332 typename _Alloc = std::allocator<_Value> > 333 class unordered_multiset 334 : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>, 335 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash, 336 _Pred, _Alloc> > 337 { 338 typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, 339 _Pred, _Alloc> _Base; 340 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base; 341 342 public: 343 typedef typename _Base::size_type size_type; 344 typedef typename _Base::hasher hasher; 345 typedef typename _Base::key_equal key_equal; 346 typedef typename _Base::allocator_type allocator_type; 347 348 typedef typename _Base::key_type key_type; 349 typedef typename _Base::value_type value_type; 350 351 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 352 unordered_multiset> iterator; 353 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 354 unordered_multiset> const_iterator; 355 356 explicit 357 unordered_multiset(size_type __n = 10, 358 const hasher& __hf = hasher(), 359 const key_equal& __eql = key_equal(), 360 const allocator_type& __a = allocator_type()) 361 : _Base(__n, __hf, __eql, __a) { } 362 363 template<typename _InputIterator> 364 unordered_multiset(_InputIterator __f, _InputIterator __l, 365 size_type __n = 10, 366 const hasher& __hf = hasher(), 367 const key_equal& __eql = key_equal(), 368 const allocator_type& __a = allocator_type()) 369 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 370 __hf, __eql, __a), _Safe_base() { } 371 372 unordered_multiset(const unordered_multiset& __x) 373 : _Base(__x), _Safe_base() { } 374 375 unordered_multiset(const _Base& __x) 376 : _Base(__x), _Safe_base() { } 377 378 unordered_multiset(unordered_multiset&& __x) 379 : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { } 380 381 unordered_multiset(initializer_list<value_type> __l, 382 size_type __n = 10, 383 const hasher& __hf = hasher(), 384 const key_equal& __eql = key_equal(), 385 const allocator_type& __a = allocator_type()) 386 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 387 388 unordered_multiset& 389 operator=(const unordered_multiset& __x) 390 { 391 *static_cast<_Base*>(this) = __x; 392 this->_M_invalidate_all(); 393 return *this; 394 } 395 396 unordered_multiset& 397 operator=(unordered_multiset&& __x) 398 { 399 // NB: DR 675. 400 clear(); 401 swap(__x); 402 return *this; 403 } 404 405 unordered_multiset& 406 operator=(initializer_list<value_type> __l) 407 { 408 this->clear(); 409 this->insert(__l); 410 return *this; 411 } 412 413 void 414 swap(unordered_multiset&& __x) 415 { 416 _Base::swap(__x); 417 _Safe_base::_M_swap(__x); 418 } 419 420 void 421 clear() 422 { 423 _Base::clear(); 424 this->_M_invalidate_all(); 425 } 426 427 iterator 428 begin() 429 { return iterator(_Base::begin(), this); } 430 431 const_iterator 432 begin() const 433 { return const_iterator(_Base::begin(), this); } 434 435 iterator 436 end() 437 { return iterator(_Base::end(), this); } 438 439 const_iterator 440 end() const 441 { return const_iterator(_Base::end(), this); } 442 443 const_iterator 444 cbegin() const 445 { return const_iterator(_Base::begin(), this); } 446 447 const_iterator 448 cend() const 449 { return const_iterator(_Base::end(), this); } 450 451 // local versions 452 using _Base::begin; 453 using _Base::end; 454 using _Base::cbegin; 455 using _Base::cend; 456 457 iterator 458 insert(const value_type& __obj) 459 { return iterator(_Base::insert(__obj), this); } 460 461 iterator 462 insert(iterator, const value_type& __obj) 463 { return iterator(_Base::insert(__obj), this); } 464 465 const_iterator 466 insert(const_iterator, const value_type& __obj) 467 { return const_iterator(_Base::insert(__obj), this); } 468 469 void 470 insert(std::initializer_list<value_type> __l) 471 { _Base::insert(__l); } 472 473 template<typename _InputIterator> 474 void 475 insert(_InputIterator __first, _InputIterator __last) 476 { 477 __glibcxx_check_valid_range(__first, __last); 478 _Base::insert(__first, __last); 479 } 480 481 iterator 482 find(const key_type& __key) 483 { return iterator(_Base::find(__key), this); } 484 485 const_iterator 486 find(const key_type& __key) const 487 { return const_iterator(_Base::find(__key), this); } 488 489 std::pair<iterator, iterator> 490 equal_range(const key_type& __key) 491 { 492 typedef typename _Base::iterator _Base_iterator; 493 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 494 __pair_type __res = _Base::equal_range(__key); 495 return std::make_pair(iterator(__res.first, this), 496 iterator(__res.second, this)); 497 } 498 499 std::pair<const_iterator, const_iterator> 500 equal_range(const key_type& __key) const 501 { 502 typedef typename _Base::const_iterator _Base_iterator; 503 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 504 __pair_type __res = _Base::equal_range(__key); 505 return std::make_pair(const_iterator(__res.first, this), 506 const_iterator(__res.second, this)); 507 } 508 509 size_type 510 erase(const key_type& __key) 511 { 512 size_type __ret(0); 513 iterator __victim(_Base::find(__key), this); 514 if (__victim != end()) 515 { 516 this->erase(__victim); 517 __ret = 1; 518 } 519 return __ret; 520 } 521 522 iterator 523 erase(iterator __it) 524 { 525 __glibcxx_check_erase(__it); 526 __it._M_invalidate(); 527 return iterator(_Base::erase(__it.base()), this); 528 } 529 530 const_iterator 531 erase(const_iterator __it) 532 { 533 __glibcxx_check_erase(__it); 534 __it._M_invalidate(); 535 return const_iterator(_Base::erase(__it.base()), this); 536 } 537 538 iterator 539 erase(iterator __first, iterator __last) 540 { 541 __glibcxx_check_erase_range(__first, __last); 542 for (iterator __tmp = __first; __tmp != __last;) 543 { 544 iterator __victim = __tmp++; 545 __victim._M_invalidate(); 546 } 547 return iterator(_Base::erase(__first.base(), 548 __last.base()), this); 549 } 550 551 const_iterator 552 erase(const_iterator __first, const_iterator __last) 553 { 554 __glibcxx_check_erase_range(__first, __last); 555 for (const_iterator __tmp = __first; __tmp != __last;) 556 { 557 const_iterator __victim = __tmp++; 558 __victim._M_invalidate(); 559 } 560 return const_iterator(_Base::erase(__first.base(), 561 __last.base()), this); 562 } 563 564 _Base& 565 _M_base() { return *this; } 566 567 const _Base& 568 _M_base() const { return *this; } 569 570 private: 571 void 572 _M_invalidate_all() 573 { 574 typedef typename _Base::const_iterator _Base_const_iterator; 575 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 576 this->_M_invalidate_if(_Not_equal(_M_base().end())); 577 } 578 }; 579 580 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 581 inline void 582 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 583 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 584 { __x.swap(__y); } 585 586 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 587 inline void 588 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __x, 589 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 590 { __x.swap(__y); } 591 592 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 593 inline void 594 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 595 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __y) 596 { __x.swap(__y); } 597 598 } // namespace __debug 599 } // namespace std 600 601 #endif 602
