libstdc++
|
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /** @file debug/unordered_map 00027 * This file is a GNU debug extension to the Standard C++ Library. 00028 */ 00029 00030 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP 00031 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1 00032 00033 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00034 # include <bits/c++0x_warning.h> 00035 #else 00036 # include <unordered_map> 00037 00038 #include <debug/safe_sequence.h> 00039 #include <debug/safe_iterator.h> 00040 00041 namespace std _GLIBCXX_VISIBILITY(default) 00042 { 00043 namespace __debug 00044 { 00045 /// Class std::unordered_map with safety/checking/debug instrumentation. 00046 template<typename _Key, typename _Tp, 00047 typename _Hash = std::hash<_Key>, 00048 typename _Pred = std::equal_to<_Key>, 00049 typename _Alloc = std::allocator<_Key> > 00050 class unordered_map 00051 : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 00052 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash, 00053 _Pred, _Alloc> > 00054 { 00055 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, 00056 _Pred, _Alloc> _Base; 00057 typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base; 00058 typedef typename _Base::const_iterator _Base_const_iterator; 00059 typedef typename _Base::iterator _Base_iterator; 00060 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00061 00062 public: 00063 typedef typename _Base::size_type size_type; 00064 typedef typename _Base::hasher hasher; 00065 typedef typename _Base::key_equal key_equal; 00066 typedef typename _Base::allocator_type allocator_type; 00067 00068 typedef typename _Base::key_type key_type; 00069 typedef typename _Base::value_type value_type; 00070 00071 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 00072 unordered_map> iterator; 00073 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00074 unordered_map> const_iterator; 00075 00076 explicit 00077 unordered_map(size_type __n = 10, 00078 const hasher& __hf = hasher(), 00079 const key_equal& __eql = key_equal(), 00080 const allocator_type& __a = allocator_type()) 00081 : _Base(__n, __hf, __eql, __a) { } 00082 00083 template<typename _InputIterator> 00084 unordered_map(_InputIterator __first, _InputIterator __last, 00085 size_type __n = 0, 00086 const hasher& __hf = hasher(), 00087 const key_equal& __eql = key_equal(), 00088 const allocator_type& __a = allocator_type()) 00089 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00090 __last)), 00091 __gnu_debug::__base(__last), __n, 00092 __hf, __eql, __a), _Safe_base() { } 00093 00094 unordered_map(const unordered_map& __x) 00095 : _Base(__x), _Safe_base() { } 00096 00097 unordered_map(const _Base& __x) 00098 : _Base(__x), _Safe_base() { } 00099 00100 unordered_map(unordered_map&& __x) 00101 : _Base(std::move(__x)), _Safe_base() { } 00102 00103 unordered_map(initializer_list<value_type> __l, 00104 size_type __n = 0, 00105 const hasher& __hf = hasher(), 00106 const key_equal& __eql = key_equal(), 00107 const allocator_type& __a = allocator_type()) 00108 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 00109 00110 unordered_map& 00111 operator=(const unordered_map& __x) 00112 { 00113 *static_cast<_Base*>(this) = __x; 00114 this->_M_invalidate_all(); 00115 return *this; 00116 } 00117 00118 unordered_map& 00119 operator=(unordered_map&& __x) 00120 { 00121 // NB: DR 1204. 00122 // NB: DR 675. 00123 clear(); 00124 swap(__x); 00125 return *this; 00126 } 00127 00128 unordered_map& 00129 operator=(initializer_list<value_type> __l) 00130 { 00131 this->clear(); 00132 this->insert(__l); 00133 return *this; 00134 } 00135 00136 void 00137 swap(unordered_map& __x) 00138 { 00139 _Base::swap(__x); 00140 _Safe_base::_M_swap(__x); 00141 } 00142 00143 void 00144 clear() 00145 { 00146 _Base::clear(); 00147 this->_M_invalidate_all(); 00148 } 00149 00150 iterator 00151 begin() 00152 { return iterator(_Base::begin(), this); } 00153 00154 const_iterator 00155 begin() const 00156 { return const_iterator(_Base::begin(), this); } 00157 00158 iterator 00159 end() 00160 { return iterator(_Base::end(), this); } 00161 00162 const_iterator 00163 end() const 00164 { return const_iterator(_Base::end(), this); } 00165 00166 const_iterator 00167 cbegin() const 00168 { return const_iterator(_Base::begin(), this); } 00169 00170 const_iterator 00171 cend() const 00172 { return const_iterator(_Base::end(), this); } 00173 00174 // local versions 00175 using _Base::begin; 00176 using _Base::end; 00177 using _Base::cbegin; 00178 using _Base::cend; 00179 00180 std::pair<iterator, bool> 00181 insert(const value_type& __obj) 00182 { 00183 std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); 00184 return std::make_pair(iterator(__res.first, this), __res.second); 00185 } 00186 00187 iterator 00188 insert(const_iterator __hint, const value_type& __obj) 00189 { 00190 __glibcxx_check_insert(__hint); 00191 return iterator(_Base::insert(__hint.base(), __obj), this); 00192 } 00193 00194 template<typename _Pair, typename = typename 00195 std::enable_if<std::is_convertible<_Pair, 00196 value_type>::value>::type> 00197 std::pair<iterator, bool> 00198 insert(_Pair&& __obj) 00199 { 00200 std::pair<_Base_iterator, bool> __res = 00201 _Base::insert(std::forward<_Pair>(__obj)); 00202 return std::make_pair(iterator(__res.first, this), __res.second); 00203 } 00204 00205 template<typename _Pair, typename = typename 00206 std::enable_if<std::is_convertible<_Pair, 00207 value_type>::value>::type> 00208 iterator 00209 insert(const_iterator __hint, _Pair&& __obj) 00210 { 00211 __glibcxx_check_insert(__hint); 00212 return iterator(_Base::insert(__hint.base(), 00213 std::forward<_Pair>(__obj)), 00214 this); 00215 } 00216 00217 void 00218 insert(std::initializer_list<value_type> __l) 00219 { _Base::insert(__l); } 00220 00221 template<typename _InputIterator> 00222 void 00223 insert(_InputIterator __first, _InputIterator __last) 00224 { 00225 __glibcxx_check_valid_range(__first, __last); 00226 _Base::insert(__gnu_debug::__base(__first), 00227 __gnu_debug::__base(__last)); 00228 } 00229 00230 iterator 00231 find(const key_type& __key) 00232 { return iterator(_Base::find(__key), this); } 00233 00234 const_iterator 00235 find(const key_type& __key) const 00236 { return const_iterator(_Base::find(__key), this); } 00237 00238 std::pair<iterator, iterator> 00239 equal_range(const key_type& __key) 00240 { 00241 std::pair<_Base_iterator, _Base_iterator> __res = 00242 _Base::equal_range(__key); 00243 return std::make_pair(iterator(__res.first, this), 00244 iterator(__res.second, this)); 00245 } 00246 00247 std::pair<const_iterator, const_iterator> 00248 equal_range(const key_type& __key) const 00249 { 00250 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00251 _Base::equal_range(__key); 00252 return std::make_pair(const_iterator(__res.first, this), 00253 const_iterator(__res.second, this)); 00254 } 00255 00256 size_type 00257 erase(const key_type& __key) 00258 { 00259 size_type __ret(0); 00260 _Base_iterator __victim(_Base::find(__key)); 00261 if (__victim != _Base::end()) 00262 { 00263 this->_M_invalidate_if(_Equal(__victim)); 00264 _Base::erase(__victim); 00265 __ret = 1; 00266 } 00267 return __ret; 00268 } 00269 00270 iterator 00271 erase(const_iterator __it) 00272 { 00273 __glibcxx_check_erase(__it); 00274 this->_M_invalidate_if(_Equal(__it.base())); 00275 return iterator(_Base::erase(__it.base()), this); 00276 } 00277 00278 iterator 00279 erase(iterator __it) 00280 { return erase(const_iterator(__it)); } 00281 00282 iterator 00283 erase(const_iterator __first, const_iterator __last) 00284 { 00285 __glibcxx_check_erase_range(__first, __last); 00286 for (_Base_const_iterator __tmp = __first.base(); 00287 __tmp != __last.base(); ++__tmp) 00288 { 00289 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00290 _M_message(__gnu_debug::__msg_valid_range) 00291 ._M_iterator(__first, "first") 00292 ._M_iterator(__last, "last")); 00293 this->_M_invalidate_if(_Equal(__tmp)); 00294 } 00295 return iterator(_Base::erase(__first.base(), 00296 __last.base()), this); 00297 } 00298 00299 _Base& 00300 _M_base() { return *this; } 00301 00302 const _Base& 00303 _M_base() const { return *this; } 00304 00305 private: 00306 void 00307 _M_invalidate_all() 00308 { 00309 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00310 this->_M_invalidate_if(_Not_equal(_Base::end())); 00311 } 00312 }; 00313 00314 template<typename _Key, typename _Tp, typename _Hash, 00315 typename _Pred, typename _Alloc> 00316 inline void 00317 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00318 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00319 { __x.swap(__y); } 00320 00321 template<typename _Key, typename _Tp, typename _Hash, 00322 typename _Pred, typename _Alloc> 00323 inline bool 00324 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00325 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00326 { return __x._M_equal(__y); } 00327 00328 template<typename _Key, typename _Tp, typename _Hash, 00329 typename _Pred, typename _Alloc> 00330 inline bool 00331 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00332 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00333 { return !(__x == __y); } 00334 00335 00336 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 00337 template<typename _Key, typename _Tp, 00338 typename _Hash = std::hash<_Key>, 00339 typename _Pred = std::equal_to<_Key>, 00340 typename _Alloc = std::allocator<_Key> > 00341 class unordered_multimap 00342 : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00343 _Pred, _Alloc>, 00344 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash, 00345 _Pred, _Alloc> > 00346 { 00347 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00348 _Pred, _Alloc> _Base; 00349 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base; 00350 typedef typename _Base::const_iterator _Base_const_iterator; 00351 typedef typename _Base::iterator _Base_iterator; 00352 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00353 00354 public: 00355 typedef typename _Base::size_type size_type; 00356 typedef typename _Base::hasher hasher; 00357 typedef typename _Base::key_equal key_equal; 00358 typedef typename _Base::allocator_type allocator_type; 00359 00360 typedef typename _Base::key_type key_type; 00361 typedef typename _Base::value_type value_type; 00362 00363 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 00364 unordered_multimap> iterator; 00365 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00366 unordered_multimap> const_iterator; 00367 00368 explicit 00369 unordered_multimap(size_type __n = 10, 00370 const hasher& __hf = hasher(), 00371 const key_equal& __eql = key_equal(), 00372 const allocator_type& __a = allocator_type()) 00373 : _Base(__n, __hf, __eql, __a) { } 00374 00375 template<typename _InputIterator> 00376 unordered_multimap(_InputIterator __first, _InputIterator __last, 00377 size_type __n = 0, 00378 const hasher& __hf = hasher(), 00379 const key_equal& __eql = key_equal(), 00380 const allocator_type& __a = allocator_type()) 00381 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00382 __last)), 00383 __gnu_debug::__base(__last), __n, 00384 __hf, __eql, __a), _Safe_base() { } 00385 00386 unordered_multimap(const unordered_multimap& __x) 00387 : _Base(__x), _Safe_base() { } 00388 00389 unordered_multimap(const _Base& __x) 00390 : _Base(__x), _Safe_base() { } 00391 00392 unordered_multimap(unordered_multimap&& __x) 00393 : _Base(std::move(__x)), _Safe_base() { } 00394 00395 unordered_multimap(initializer_list<value_type> __l, 00396 size_type __n = 0, 00397 const hasher& __hf = hasher(), 00398 const key_equal& __eql = key_equal(), 00399 const allocator_type& __a = allocator_type()) 00400 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 00401 00402 unordered_multimap& 00403 operator=(const unordered_multimap& __x) 00404 { 00405 *static_cast<_Base*>(this) = __x; 00406 this->_M_invalidate_all(); 00407 return *this; 00408 } 00409 00410 unordered_multimap& 00411 operator=(unordered_multimap&& __x) 00412 { 00413 // NB: DR 1204. 00414 // NB: DR 675. 00415 clear(); 00416 swap(__x); 00417 return *this; 00418 } 00419 00420 unordered_multimap& 00421 operator=(initializer_list<value_type> __l) 00422 { 00423 this->clear(); 00424 this->insert(__l); 00425 return *this; 00426 } 00427 00428 void 00429 swap(unordered_multimap& __x) 00430 { 00431 _Base::swap(__x); 00432 _Safe_base::_M_swap(__x); 00433 } 00434 00435 void 00436 clear() 00437 { 00438 _Base::clear(); 00439 this->_M_invalidate_all(); 00440 } 00441 00442 iterator 00443 begin() 00444 { return iterator(_Base::begin(), this); } 00445 00446 const_iterator 00447 begin() const 00448 { return const_iterator(_Base::begin(), this); } 00449 00450 iterator 00451 end() 00452 { return iterator(_Base::end(), this); } 00453 00454 const_iterator 00455 end() const 00456 { return const_iterator(_Base::end(), this); } 00457 00458 const_iterator 00459 cbegin() const 00460 { return const_iterator(_Base::begin(), this); } 00461 00462 const_iterator 00463 cend() const 00464 { return const_iterator(_Base::end(), this); } 00465 00466 // local versions 00467 using _Base::begin; 00468 using _Base::end; 00469 using _Base::cbegin; 00470 using _Base::cend; 00471 00472 iterator 00473 insert(const value_type& __obj) 00474 { return iterator(_Base::insert(__obj), this); } 00475 00476 iterator 00477 insert(const_iterator __hint, const value_type& __obj) 00478 { 00479 __glibcxx_check_insert(__hint); 00480 return iterator(_Base::insert(__hint.base(), __obj), this); 00481 } 00482 00483 template<typename _Pair, typename = typename 00484 std::enable_if<std::is_convertible<_Pair, 00485 value_type>::value>::type> 00486 iterator 00487 insert(_Pair&& __obj) 00488 { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); } 00489 00490 template<typename _Pair, typename = typename 00491 std::enable_if<std::is_convertible<_Pair, 00492 value_type>::value>::type> 00493 iterator 00494 insert(const_iterator __hint, _Pair&& __obj) 00495 { 00496 __glibcxx_check_insert(__hint); 00497 return iterator(_Base::insert(__hint.base(), 00498 std::forward<_Pair>(__obj)), 00499 this); 00500 } 00501 00502 void 00503 insert(std::initializer_list<value_type> __l) 00504 { _Base::insert(__l); } 00505 00506 template<typename _InputIterator> 00507 void 00508 insert(_InputIterator __first, _InputIterator __last) 00509 { 00510 __glibcxx_check_valid_range(__first, __last); 00511 _Base::insert(__gnu_debug::__base(__first), 00512 __gnu_debug::__base(__last)); 00513 } 00514 00515 iterator 00516 find(const key_type& __key) 00517 { return iterator(_Base::find(__key), this); } 00518 00519 const_iterator 00520 find(const key_type& __key) const 00521 { return const_iterator(_Base::find(__key), this); } 00522 00523 std::pair<iterator, iterator> 00524 equal_range(const key_type& __key) 00525 { 00526 std::pair<_Base_iterator, _Base_iterator> __res = 00527 _Base::equal_range(__key); 00528 return std::make_pair(iterator(__res.first, this), 00529 iterator(__res.second, this)); 00530 } 00531 00532 std::pair<const_iterator, const_iterator> 00533 equal_range(const key_type& __key) const 00534 { 00535 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00536 _Base::equal_range(__key); 00537 return std::make_pair(const_iterator(__res.first, this), 00538 const_iterator(__res.second, this)); 00539 } 00540 00541 size_type 00542 erase(const key_type& __key) 00543 { 00544 size_type __ret(0); 00545 std::pair<_Base_iterator, _Base_iterator> __pair = 00546 _Base::equal_range(__key); 00547 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 00548 { 00549 this->_M_invalidate_if(_Equal(__victim)); 00550 _Base::erase(__victim++); 00551 ++__ret; 00552 } 00553 return __ret; 00554 } 00555 00556 iterator 00557 erase(const_iterator __it) 00558 { 00559 __glibcxx_check_erase(__it); 00560 this->_M_invalidate_if(_Equal(__it.base())); 00561 return iterator(_Base::erase(__it.base()), this); 00562 } 00563 00564 iterator 00565 erase(iterator __it) 00566 { return erase(const_iterator(__it)); } 00567 00568 iterator 00569 erase(const_iterator __first, const_iterator __last) 00570 { 00571 __glibcxx_check_erase_range(__first, __last); 00572 for (_Base_const_iterator __tmp = __first.base(); 00573 __tmp != __last.base(); ++__tmp) 00574 { 00575 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00576 _M_message(__gnu_debug::__msg_valid_range) 00577 ._M_iterator(__first, "first") 00578 ._M_iterator(__last, "last")); 00579 this->_M_invalidate_if(_Equal(__tmp)); 00580 } 00581 return iterator(_Base::erase(__first.base(), 00582 __last.base()), this); 00583 } 00584 00585 _Base& 00586 _M_base() { return *this; } 00587 00588 const _Base& 00589 _M_base() const { return *this; } 00590 00591 private: 00592 void 00593 _M_invalidate_all() 00594 { 00595 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00596 this->_M_invalidate_if(_Not_equal(_Base::end())); 00597 } 00598 }; 00599 00600 template<typename _Key, typename _Tp, typename _Hash, 00601 typename _Pred, typename _Alloc> 00602 inline void 00603 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00604 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00605 { __x.swap(__y); } 00606 00607 template<typename _Key, typename _Tp, typename _Hash, 00608 typename _Pred, typename _Alloc> 00609 inline bool 00610 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00611 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00612 { return __x._M_equal(__y); } 00613 00614 template<typename _Key, typename _Tp, typename _Hash, 00615 typename _Pred, typename _Alloc> 00616 inline bool 00617 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00618 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00619 { return !(__x == __y); } 00620 00621 } // namespace __debug 00622 } // namespace std 00623 00624 #endif // __GXX_EXPERIMENTAL_CXX0X__ 00625 00626 #endif