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 41namespace std 42{ 43namespace __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_D::unordered_set<_Value, _Hash, _Pred, _Alloc>, 52 public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash, 53 _Pred, _Alloc> > 54 { 55 typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash, 56 _Pred, _Alloc> _Base; 57 typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base; 58 59 public: 60 typedef typename _Base::size_type size_type; 61 typedef typename _Base::hasher hasher; 62 typedef typename _Base::key_equal key_equal; 63 typedef typename _Base::allocator_type allocator_type; 64 65 typedef typename _Base::key_type key_type; 66 typedef typename _Base::value_type value_type; 67 68 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 69 unordered_set> iterator; 70 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 71 unordered_set> const_iterator; 72 73 explicit 74 unordered_set(size_type __n = 10, 75 const hasher& __hf = hasher(), 76 const key_equal& __eql = key_equal(), 77 const allocator_type& __a = allocator_type()) 78 : _Base(__n, __hf, __eql, __a) { } 79 80 template<typename _InputIterator> 81 unordered_set(_InputIterator __f, _InputIterator __l, 82 size_type __n = 10, 83 const hasher& __hf = hasher(), 84 const key_equal& __eql = key_equal(), 85 const allocator_type& __a = allocator_type()) 86 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 87 __hf, __eql, __a), _Safe_base() { } 88 89 unordered_set(const unordered_set& __x) 90 : _Base(__x), _Safe_base() { } 91 92 unordered_set(const _Base& __x) 93 : _Base(__x), _Safe_base() { } 94 95 unordered_set(unordered_set&& __x) 96 : _Base(std::forward<unordered_set>(__x)), _Safe_base() { } 97 98 unordered_set(initializer_list<value_type> __l, 99 size_type __n = 10, 100 const hasher& __hf = hasher(), 101 const key_equal& __eql = key_equal(), 102 const allocator_type& __a = allocator_type()) 103 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 104 105 unordered_set& 106 operator=(const unordered_set& __x) 107 { 108 *static_cast<_Base*>(this) = __x; 109 this->_M_invalidate_all(); 110 return *this; 111 } 112 113 unordered_set& 114 operator=(unordered_set&& __x) 115 { 116 // NB: DR 1204. 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(const_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 void 192 insert(std::initializer_list<value_type> __l) 193 { _Base::insert(__l); } 194 195 template<typename _InputIterator> 196 void 197 insert(_InputIterator __first, _InputIterator __last) 198 { 199 __glibcxx_check_valid_range(__first, __last); 200 _Base::insert(__first, __last); 201 } 202 203 iterator 204 find(const key_type& __key) 205 { return iterator(_Base::find(__key), this); } 206 207 const_iterator 208 find(const key_type& __key) const 209 { return const_iterator(_Base::find(__key), this); } 210 211 std::pair<iterator, iterator> 212 equal_range(const key_type& __key) 213 { 214 typedef typename _Base::iterator _Base_iterator; 215 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 216 __pair_type __res = _Base::equal_range(__key); 217 return std::make_pair(iterator(__res.first, this), 218 iterator(__res.second, this)); 219 } 220 221 std::pair<const_iterator, const_iterator> 222 equal_range(const key_type& __key) const 223 { 224 typedef typename _Base::const_iterator _Base_iterator; 225 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 226 __pair_type __res = _Base::equal_range(__key); 227 return std::make_pair(const_iterator(__res.first, this), 228 const_iterator(__res.second, this)); 229 } 230 231 size_type 232 erase(const key_type& __key) 233 { 234 size_type __ret(0); 235 iterator __victim(_Base::find(__key), this); 236 if (__victim != end()) 237 { 238 this->erase(__victim); 239 __ret = 1; 240 } 241 return __ret; 242 } 243 244 iterator 245 erase(const_iterator __it) 246 { 247 __glibcxx_check_erase(__it); 248 __it._M_invalidate(); 249 return iterator(_Base::erase(__it.base()), this); 250 } 251 252 iterator 253 erase(const_iterator __first, const_iterator __last) 254 { 255 __glibcxx_check_erase_range(__first, __last); 256 for (const_iterator __tmp = __first; __tmp != __last;) 257 { 258 const_iterator __victim = __tmp++; 259 __victim._M_invalidate(); 260 } 261 return iterator(_Base::erase(__first.base(), 262 __last.base()), this); 263 } 264 265 _Base& 266 _M_base() { return *this; } 267 268 const _Base& 269 _M_base() const { return *this; } 270 271 private: 272 void 273 _M_invalidate_all() 274 { 275 typedef typename _Base::const_iterator _Base_const_iterator; 276 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 277 this->_M_invalidate_if(_Not_equal(_M_base().end())); 278 } 279 }; 280 281 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 282 inline void 283 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 284 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 285 { __x.swap(__y); } 286 287 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 288 inline bool 289 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 290 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 291 { return __x._M_equal(__y); } 292 293 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 294 inline bool 295 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 296 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 297 { return !(__x == __y); } 298 299 300 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 301 template<typename _Value, 302 typename _Hash = std::hash<_Value>, 303 typename _Pred = std::equal_to<_Value>, 304 typename _Alloc = std::allocator<_Value> > 305 class unordered_multiset 306 : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>, 307 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash, 308 _Pred, _Alloc> > 309 { 310 typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, 311 _Pred, _Alloc> _Base; 312 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base; 313 314 public: 315 typedef typename _Base::size_type size_type; 316 typedef typename _Base::hasher hasher; 317 typedef typename _Base::key_equal key_equal; 318 typedef typename _Base::allocator_type allocator_type; 319 320 typedef typename _Base::key_type key_type; 321 typedef typename _Base::value_type value_type; 322 323 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 324 unordered_multiset> iterator; 325 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 326 unordered_multiset> const_iterator; 327 328 explicit 329 unordered_multiset(size_type __n = 10, 330 const hasher& __hf = hasher(), 331 const key_equal& __eql = key_equal(), 332 const allocator_type& __a = allocator_type()) 333 : _Base(__n, __hf, __eql, __a) { } 334 335 template<typename _InputIterator> 336 unordered_multiset(_InputIterator __f, _InputIterator __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(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 342 __hf, __eql, __a), _Safe_base() { } 343 344 unordered_multiset(const unordered_multiset& __x) 345 : _Base(__x), _Safe_base() { } 346 347 unordered_multiset(const _Base& __x) 348 : _Base(__x), _Safe_base() { } 349 350 unordered_multiset(unordered_multiset&& __x) 351 : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { } 352 353 unordered_multiset(initializer_list<value_type> __l, 354 size_type __n = 10, 355 const hasher& __hf = hasher(), 356 const key_equal& __eql = key_equal(), 357 const allocator_type& __a = allocator_type()) 358 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 359 360 unordered_multiset& 361 operator=(const unordered_multiset& __x) 362 { 363 *static_cast<_Base*>(this) = __x; 364 this->_M_invalidate_all(); 365 return *this; 366 } 367 368 unordered_multiset& 369 operator=(unordered_multiset&& __x) 370 { 371 // NB: DR 1204. 372 // NB: DR 675. 373 clear(); 374 swap(__x); 375 return *this; 376 } 377 378 unordered_multiset& 379 operator=(initializer_list<value_type> __l) 380 { 381 this->clear(); 382 this->insert(__l); 383 return *this; 384 } 385 386 void 387 swap(unordered_multiset& __x) 388 { 389 _Base::swap(__x); 390 _Safe_base::_M_swap(__x); 391 } 392 393 void 394 clear() 395 { 396 _Base::clear(); 397 this->_M_invalidate_all(); 398 } 399 400 iterator 401 begin() 402 { return iterator(_Base::begin(), this); } 403 404 const_iterator 405 begin() const 406 { return const_iterator(_Base::begin(), this); } 407 408 iterator 409 end() 410 { return iterator(_Base::end(), this); } 411 412 const_iterator 413 end() const 414 { return const_iterator(_Base::end(), this); } 415 416 const_iterator 417 cbegin() const 418 { return const_iterator(_Base::begin(), this); } 419 420 const_iterator 421 cend() const 422 { return const_iterator(_Base::end(), this); } 423 424 // local versions 425 using _Base::begin; 426 using _Base::end; 427 using _Base::cbegin; 428 using _Base::cend; 429 430 iterator 431 insert(const value_type& __obj) 432 { return iterator(_Base::insert(__obj), this); } 433 434 iterator 435 insert(const_iterator, const value_type& __obj) 436 { return iterator(_Base::insert(__obj), this); } 437 438 void 439 insert(std::initializer_list<value_type> __l) 440 { _Base::insert(__l); } 441 442 template<typename _InputIterator> 443 void 444 insert(_InputIterator __first, _InputIterator __last) 445 { 446 __glibcxx_check_valid_range(__first, __last); 447 _Base::insert(__first, __last); 448 } 449 450 iterator 451 find(const key_type& __key) 452 { return iterator(_Base::find(__key), this); } 453 454 const_iterator 455 find(const key_type& __key) const 456 { return const_iterator(_Base::find(__key), this); } 457 458 std::pair<iterator, iterator> 459 equal_range(const key_type& __key) 460 { 461 typedef typename _Base::iterator _Base_iterator; 462 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 463 __pair_type __res = _Base::equal_range(__key); 464 return std::make_pair(iterator(__res.first, this), 465 iterator(__res.second, this)); 466 } 467 468 std::pair<const_iterator, const_iterator> 469 equal_range(const key_type& __key) const 470 { 471 typedef typename _Base::const_iterator _Base_iterator; 472 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 473 __pair_type __res = _Base::equal_range(__key); 474 return std::make_pair(const_iterator(__res.first, this), 475 const_iterator(__res.second, this)); 476 } 477 478 size_type 479 erase(const key_type& __key) 480 { 481 size_type __ret(0); 482 iterator __victim(_Base::find(__key), this); 483 if (__victim != end()) 484 { 485 this->erase(__victim); 486 __ret = 1; 487 } 488 return __ret; 489 } 490 491 iterator 492 erase(const_iterator __it) 493 { 494 __glibcxx_check_erase(__it); 495 __it._M_invalidate(); 496 return iterator(_Base::erase(__it.base()), this); 497 } 498 499 iterator 500 erase(const_iterator __first, const_iterator __last) 501 { 502 __glibcxx_check_erase_range(__first, __last); 503 for (const_iterator __tmp = __first; __tmp != __last;) 504 { 505 const_iterator __victim = __tmp++; 506 __victim._M_invalidate(); 507 } 508 return iterator(_Base::erase(__first.base(), 509 __last.base()), this); 510 } 511 512 _Base& 513 _M_base() { return *this; } 514 515 const _Base& 516 _M_base() const { return *this; } 517 518 private: 519 void 520 _M_invalidate_all() 521 { 522 typedef typename _Base::const_iterator _Base_const_iterator; 523 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 524 this->_M_invalidate_if(_Not_equal(_M_base().end())); 525 } 526 }; 527 528 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 529 inline void 530 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 531 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 532 { __x.swap(__y); } 533 534 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 535 inline bool 536 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 537 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 538 { return __x._M_equal(__y); } 539 540 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 541 inline bool 542 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 543 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 544 { return !(__x == __y); } 545 546} // namespace __debug 547} // namespace std 548 549#endif // __GXX_EXPERIMENTAL_CXX0X__ 550 551#endif 552