1// Debugging unordered_map/unordered_multimap 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_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#ifndef __GXX_EXPERIMENTAL_CXX0X__ 34# include <bits/c++0x_warning.h> 35#else 36# include <unordered_map> 37 38#include <debug/safe_sequence.h> 39#include <debug/safe_iterator.h> 40 41namespace std 42{ 43namespace __debug 44{ 45 /// Class std::unordered_map with safety/checking/debug instrumentation. 46 template<typename _Key, typename _Tp, 47 typename _Hash = std::hash<_Key>, 48 typename _Pred = std::equal_to<_Key>, 49 typename _Alloc = std::allocator<_Key> > 50 class unordered_map 51 : public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 52 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash, 53 _Pred, _Alloc> > 54 { 55 typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, 56 _Pred, _Alloc> _Base; 57 typedef __gnu_debug::_Safe_sequence<unordered_map> _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_map> iterator; 70 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 71 unordered_map> const_iterator; 72 73 explicit 74 unordered_map(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_map(_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_map(const unordered_map& __x) 90 : _Base(__x), _Safe_base() { } 91 92 unordered_map(const _Base& __x) 93 : _Base(__x), _Safe_base() { } 94 95 unordered_map(unordered_map&& __x) 96 : _Base(std::forward<unordered_map>(__x)), _Safe_base() { } 97 98 unordered_map(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_map& 106 operator=(const unordered_map& __x) 107 { 108 *static_cast<_Base*>(this) = __x; 109 this->_M_invalidate_all(); 110 return *this; 111 } 112 113 unordered_map& 114 operator=(unordered_map&& __x) 115 { 116 // NB: DR 1204. 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(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 _Key, typename _Tp, typename _Hash, 282 typename _Pred, typename _Alloc> 283 inline void 284 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 285 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 286 { __x.swap(__y); } 287 288 template<typename _Key, typename _Tp, typename _Hash, 289 typename _Pred, typename _Alloc> 290 inline bool 291 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 292 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 293 { return __x._M_equal(__y); } 294 295 template<typename _Key, typename _Tp, typename _Hash, 296 typename _Pred, typename _Alloc> 297 inline bool 298 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 299 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 300 { return !(__x == __y); } 301 302 303 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 304 template<typename _Key, typename _Tp, 305 typename _Hash = std::hash<_Key>, 306 typename _Pred = std::equal_to<_Key>, 307 typename _Alloc = std::allocator<_Key> > 308 class unordered_multimap 309 : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash, 310 _Pred, _Alloc>, 311 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash, 312 _Pred, _Alloc> > 313 { 314 typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash, 315 _Pred, _Alloc> _Base; 316 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base; 317 318 public: 319 typedef typename _Base::size_type size_type; 320 typedef typename _Base::hasher hasher; 321 typedef typename _Base::key_equal key_equal; 322 typedef typename _Base::allocator_type allocator_type; 323 324 typedef typename _Base::key_type key_type; 325 typedef typename _Base::value_type value_type; 326 327 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 328 unordered_multimap> iterator; 329 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 330 unordered_multimap> const_iterator; 331 332 explicit 333 unordered_multimap(size_type __n = 10, 334 const hasher& __hf = hasher(), 335 const key_equal& __eql = key_equal(), 336 const allocator_type& __a = allocator_type()) 337 : _Base(__n, __hf, __eql, __a) { } 338 339 template<typename _InputIterator> 340 unordered_multimap(_InputIterator __f, _InputIterator __l, 341 size_type __n = 10, 342 const hasher& __hf = hasher(), 343 const key_equal& __eql = key_equal(), 344 const allocator_type& __a = allocator_type()) 345 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 346 __hf, __eql, __a), _Safe_base() { } 347 348 unordered_multimap(const unordered_multimap& __x) 349 : _Base(__x), _Safe_base() { } 350 351 unordered_multimap(const _Base& __x) 352 : _Base(__x), _Safe_base() { } 353 354 unordered_multimap(unordered_multimap&& __x) 355 : _Base(std::forward<unordered_multimap>(__x)), _Safe_base() { } 356 357 unordered_multimap(initializer_list<value_type> __l, 358 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(__l, __n, __hf, __eql, __a), _Safe_base() { } 363 364 unordered_multimap& 365 operator=(const unordered_multimap& __x) 366 { 367 *static_cast<_Base*>(this) = __x; 368 this->_M_invalidate_all(); 369 return *this; 370 } 371 372 unordered_multimap& 373 operator=(unordered_multimap&& __x) 374 { 375 // NB: DR 1204. 376 // NB: DR 675. 377 clear(); 378 swap(__x); 379 return *this; 380 } 381 382 unordered_multimap& 383 operator=(initializer_list<value_type> __l) 384 { 385 this->clear(); 386 this->insert(__l); 387 return *this; 388 } 389 390 void 391 swap(unordered_multimap& __x) 392 { 393 _Base::swap(__x); 394 _Safe_base::_M_swap(__x); 395 } 396 397 void 398 clear() 399 { 400 _Base::clear(); 401 this->_M_invalidate_all(); 402 } 403 404 iterator 405 begin() 406 { return iterator(_Base::begin(), this); } 407 408 const_iterator 409 begin() const 410 { return const_iterator(_Base::begin(), this); } 411 412 iterator 413 end() 414 { return iterator(_Base::end(), this); } 415 416 const_iterator 417 end() const 418 { return const_iterator(_Base::end(), this); } 419 420 const_iterator 421 cbegin() const 422 { return const_iterator(_Base::begin(), this); } 423 424 const_iterator 425 cend() const 426 { return const_iterator(_Base::end(), this); } 427 428 // local versions 429 using _Base::begin; 430 using _Base::end; 431 using _Base::cbegin; 432 using _Base::cend; 433 434 iterator 435 insert(const value_type& __obj) 436 { return iterator(_Base::insert(__obj), this); } 437 438 iterator 439 insert(const_iterator, const value_type& __obj) 440 { return iterator(_Base::insert(__obj), this); } 441 442 void 443 insert(std::initializer_list<value_type> __l) 444 { _Base::insert(__l); } 445 446 template<typename _InputIterator> 447 void 448 insert(_InputIterator __first, _InputIterator __last) 449 { 450 __glibcxx_check_valid_range(__first, __last); 451 _Base::insert(__first, __last); 452 } 453 454 iterator 455 find(const key_type& __key) 456 { return iterator(_Base::find(__key), this); } 457 458 const_iterator 459 find(const key_type& __key) const 460 { return const_iterator(_Base::find(__key), this); } 461 462 std::pair<iterator, iterator> 463 equal_range(const key_type& __key) 464 { 465 typedef typename _Base::iterator _Base_iterator; 466 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 467 __pair_type __res = _Base::equal_range(__key); 468 return std::make_pair(iterator(__res.first, this), 469 iterator(__res.second, this)); 470 } 471 472 std::pair<const_iterator, const_iterator> 473 equal_range(const key_type& __key) const 474 { 475 typedef typename _Base::const_iterator _Base_iterator; 476 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 477 __pair_type __res = _Base::equal_range(__key); 478 return std::make_pair(const_iterator(__res.first, this), 479 const_iterator(__res.second, this)); 480 } 481 482 size_type 483 erase(const key_type& __key) 484 { 485 size_type __ret(0); 486 iterator __victim(_Base::find(__key), this); 487 if (__victim != end()) 488 { 489 this->erase(__victim); 490 __ret = 1; 491 } 492 return __ret; 493 } 494 495 iterator 496 erase(const_iterator __it) 497 { 498 __glibcxx_check_erase(__it); 499 __it._M_invalidate(); 500 return iterator(_Base::erase(__it.base()), this); 501 } 502 503 iterator 504 erase(const_iterator __first, const_iterator __last) 505 { 506 __glibcxx_check_erase_range(__first, __last); 507 for (const_iterator __tmp = __first; __tmp != __last;) 508 { 509 const_iterator __victim = __tmp++; 510 __victim._M_invalidate(); 511 } 512 return iterator(_Base::erase(__first.base(), 513 __last.base()), this); 514 } 515 516 _Base& 517 _M_base() { return *this; } 518 519 const _Base& 520 _M_base() const { return *this; } 521 522 private: 523 void 524 _M_invalidate_all() 525 { 526 typedef typename _Base::const_iterator _Base_const_iterator; 527 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 528 this->_M_invalidate_if(_Not_equal(_M_base().end())); 529 } 530 }; 531 532 template<typename _Key, typename _Tp, typename _Hash, 533 typename _Pred, typename _Alloc> 534 inline void 535 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 536 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 537 { __x.swap(__y); } 538 539 template<typename _Key, typename _Tp, typename _Hash, 540 typename _Pred, typename _Alloc> 541 inline bool 542 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 543 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 544 { return __x._M_equal(__y); } 545 546 template<typename _Key, typename _Tp, typename _Hash, 547 typename _Pred, typename _Alloc> 548 inline bool 549 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 550 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 551 { return !(__x == __y); } 552 553} // namespace __debug 554} // namespace std 555 556#endif // __GXX_EXPERIMENTAL_CXX0X__ 557 558#endif 559