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