1 // Debugging unordered_map/unordered_multimap 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_map 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP 31 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1 32 33 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 34 # include <unordered_map> 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 _Key, typename _Tp, 48 typename _Hash = std::hash<_Key>, 49 typename _Pred = std::equal_to<_Key>, 50 typename _Alloc = std::allocator<_Key> > 51 class unordered_map 52 : public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 53 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash, 54 _Pred, _Alloc> > 55 { 56 typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, 57 _Pred, _Alloc> _Base; 58 typedef __gnu_debug::_Safe_sequence<unordered_map> _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_map> iterator; 71 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 72 unordered_map> const_iterator; 73 74 explicit 75 unordered_map(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_map(_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_map(const unordered_map& __x) 91 : _Base(__x), _Safe_base() { } 92 93 unordered_map(const _Base& __x) 94 : _Base(__x), _Safe_base() { } 95 96 unordered_map(unordered_map&& __x) 97 : _Base(std::forward<unordered_map>(__x)), _Safe_base() { } 98 99 unordered_map(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_map& 107 operator=(const unordered_map& __x) 108 { 109 *static_cast<_Base*>(this) = __x; 110 this->_M_invalidate_all(); 111 return *this; 112 } 113 114 unordered_map& 115 operator=(unordered_map&& __x) 116 { 117 // NB: DR 675. 118 clear(); 119 swap(__x); 120 return *this; 121 } 122 123 unordered_map& 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_map&& __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 _Key, typename _Tp, typename _Hash, 311 typename _Pred, typename _Alloc> 312 inline void 313 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 314 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 315 { __x.swap(__y); } 316 317 template<typename _Key, typename _Tp, typename _Hash, 318 typename _Pred, typename _Alloc> 319 inline void 320 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x, 321 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 322 { __x.swap(__y); } 323 324 template<typename _Key, typename _Tp, typename _Hash, 325 typename _Pred, typename _Alloc> 326 inline void 327 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 328 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y) 329 { __x.swap(__y); } 330 331 332 template<typename _Key, typename _Tp, 333 typename _Hash = std::hash<_Key>, 334 typename _Pred = std::equal_to<_Key>, 335 typename _Alloc = std::allocator<_Key> > 336 class unordered_multimap 337 : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash, 338 _Pred, _Alloc>, 339 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash, 340 _Pred, _Alloc> > 341 { 342 typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash, 343 _Pred, _Alloc> _Base; 344 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base; 345 346 public: 347 typedef typename _Base::size_type size_type; 348 typedef typename _Base::hasher hasher; 349 typedef typename _Base::key_equal key_equal; 350 typedef typename _Base::allocator_type allocator_type; 351 352 typedef typename _Base::key_type key_type; 353 typedef typename _Base::value_type value_type; 354 355 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 356 unordered_multimap> iterator; 357 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 358 unordered_multimap> const_iterator; 359 360 explicit 361 unordered_multimap(size_type __n = 10, 362 const hasher& __hf = hasher(), 363 const key_equal& __eql = key_equal(), 364 const allocator_type& __a = allocator_type()) 365 : _Base(__n, __hf, __eql, __a) { } 366 367 template<typename _InputIterator> 368 unordered_multimap(_InputIterator __f, _InputIterator __l, 369 size_type __n = 10, 370 const hasher& __hf = hasher(), 371 const key_equal& __eql = key_equal(), 372 const allocator_type& __a = allocator_type()) 373 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 374 __hf, __eql, __a), _Safe_base() { } 375 376 unordered_multimap(const unordered_multimap& __x) 377 : _Base(__x), _Safe_base() { } 378 379 unordered_multimap(const _Base& __x) 380 : _Base(__x), _Safe_base() { } 381 382 unordered_multimap(unordered_multimap&& __x) 383 : _Base(std::forward<unordered_multimap>(__x)), _Safe_base() { } 384 385 unordered_multimap(initializer_list<value_type> __l, 386 size_type __n = 10, 387 const hasher& __hf = hasher(), 388 const key_equal& __eql = key_equal(), 389 const allocator_type& __a = allocator_type()) 390 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 391 392 unordered_multimap& 393 operator=(const unordered_multimap& __x) 394 { 395 *static_cast<_Base*>(this) = __x; 396 this->_M_invalidate_all(); 397 return *this; 398 } 399 400 unordered_multimap& 401 operator=(unordered_multimap&& __x) 402 { 403 // NB: DR 675. 404 clear(); 405 swap(__x); 406 return *this; 407 } 408 409 unordered_multimap& 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_multimap&& __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(iterator, const value_type& __obj) 467 { return iterator(_Base::insert(__obj), this); } 468 469 const_iterator 470 insert(const_iterator, const value_type& __obj) 471 { return const_iterator(_Base::insert(__obj), this); } 472 473 void 474 insert(std::initializer_list<value_type> __l) 475 { _Base::insert(__l); } 476 477 template<typename _InputIterator> 478 void 479 insert(_InputIterator __first, _InputIterator __last) 480 { 481 __glibcxx_check_valid_range(__first, __last); 482 _Base::insert(__first, __last); 483 } 484 485 iterator 486 find(const key_type& __key) 487 { return iterator(_Base::find(__key), this); } 488 489 const_iterator 490 find(const key_type& __key) const 491 { return const_iterator(_Base::find(__key), this); } 492 493 std::pair<iterator, iterator> 494 equal_range(const key_type& __key) 495 { 496 typedef typename _Base::iterator _Base_iterator; 497 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 498 __pair_type __res = _Base::equal_range(__key); 499 return std::make_pair(iterator(__res.first, this), 500 iterator(__res.second, this)); 501 } 502 503 std::pair<const_iterator, const_iterator> 504 equal_range(const key_type& __key) const 505 { 506 typedef typename _Base::const_iterator _Base_iterator; 507 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 508 __pair_type __res = _Base::equal_range(__key); 509 return std::make_pair(const_iterator(__res.first, this), 510 const_iterator(__res.second, this)); 511 } 512 513 size_type 514 erase(const key_type& __key) 515 { 516 size_type __ret(0); 517 iterator __victim(_Base::find(__key), this); 518 if (__victim != end()) 519 { 520 this->erase(__victim); 521 __ret = 1; 522 } 523 return __ret; 524 } 525 526 iterator 527 erase(iterator __it) 528 { 529 __glibcxx_check_erase(__it); 530 __it._M_invalidate(); 531 return iterator(_Base::erase(__it.base()), this); 532 } 533 534 const_iterator 535 erase(const_iterator __it) 536 { 537 __glibcxx_check_erase(__it); 538 __it._M_invalidate(); 539 return const_iterator(_Base::erase(__it.base()), this); 540 } 541 542 iterator 543 erase(iterator __first, iterator __last) 544 { 545 __glibcxx_check_erase_range(__first, __last); 546 for (iterator __tmp = __first; __tmp != __last;) 547 { 548 iterator __victim = __tmp++; 549 __victim._M_invalidate(); 550 } 551 return iterator(_Base::erase(__first.base(), 552 __last.base()), this); 553 } 554 555 const_iterator 556 erase(const_iterator __first, const_iterator __last) 557 { 558 __glibcxx_check_erase_range(__first, __last); 559 for (const_iterator __tmp = __first; __tmp != __last;) 560 { 561 const_iterator __victim = __tmp++; 562 __victim._M_invalidate(); 563 } 564 return const_iterator(_Base::erase(__first.base(), 565 __last.base()), this); 566 } 567 568 _Base& 569 _M_base() { return *this; } 570 571 const _Base& 572 _M_base() const { return *this; } 573 574 private: 575 void 576 _M_invalidate_all() 577 { 578 typedef typename _Base::const_iterator _Base_const_iterator; 579 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 580 this->_M_invalidate_if(_Not_equal(_M_base().end())); 581 } 582 }; 583 584 template<typename _Key, typename _Tp, typename _Hash, 585 typename _Pred, typename _Alloc> 586 inline void 587 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 588 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 589 { __x.swap(__y); } 590 591 template<typename _Key, typename _Tp, typename _Hash, 592 typename _Pred, typename _Alloc> 593 inline void 594 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x, 595 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 596 { __x.swap(__y); } 597 598 template<typename _Key, typename _Tp, typename _Hash, 599 typename _Pred, typename _Alloc> 600 inline void 601 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 602 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y) 603 { __x.swap(__y); } 604 605 } // namespace __debug 606 } // namespace std 607 608 #endif 609
