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(const_iterator __first, const_iterator __last) 00280 { 00281 __glibcxx_check_erase_range(__first, __last); 00282 for (_Base_const_iterator __tmp = __first.base(); 00283 __tmp != __last.base(); ++__tmp) 00284 { 00285 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00286 _M_message(__gnu_debug::__msg_valid_range) 00287 ._M_iterator(__first, "first") 00288 ._M_iterator(__last, "last")); 00289 this->_M_invalidate_if(_Equal(__tmp)); 00290 } 00291 return iterator(_Base::erase(__first.base(), 00292 __last.base()), this); 00293 } 00294 00295 _Base& 00296 _M_base() { return *this; } 00297 00298 const _Base& 00299 _M_base() const { return *this; } 00300 00301 private: 00302 void 00303 _M_invalidate_all() 00304 { 00305 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00306 this->_M_invalidate_if(_Not_equal(_Base::end())); 00307 } 00308 }; 00309 00310 template<typename _Key, typename _Tp, typename _Hash, 00311 typename _Pred, typename _Alloc> 00312 inline void 00313 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00314 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00315 { __x.swap(__y); } 00316 00317 template<typename _Key, typename _Tp, typename _Hash, 00318 typename _Pred, typename _Alloc> 00319 inline bool 00320 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00321 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00322 { return __x._M_equal(__y); } 00323 00324 template<typename _Key, typename _Tp, typename _Hash, 00325 typename _Pred, typename _Alloc> 00326 inline bool 00327 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00328 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00329 { return !(__x == __y); } 00330 00331 00332 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 00333 template<typename _Key, typename _Tp, 00334 typename _Hash = std::hash<_Key>, 00335 typename _Pred = std::equal_to<_Key>, 00336 typename _Alloc = std::allocator<_Key> > 00337 class unordered_multimap 00338 : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00339 _Pred, _Alloc>, 00340 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash, 00341 _Pred, _Alloc> > 00342 { 00343 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00344 _Pred, _Alloc> _Base; 00345 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base; 00346 typedef typename _Base::const_iterator _Base_const_iterator; 00347 typedef typename _Base::iterator _Base_iterator; 00348 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00349 00350 public: 00351 typedef typename _Base::size_type size_type; 00352 typedef typename _Base::hasher hasher; 00353 typedef typename _Base::key_equal key_equal; 00354 typedef typename _Base::allocator_type allocator_type; 00355 00356 typedef typename _Base::key_type key_type; 00357 typedef typename _Base::value_type value_type; 00358 00359 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 00360 unordered_multimap> iterator; 00361 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00362 unordered_multimap> const_iterator; 00363 00364 explicit 00365 unordered_multimap(size_type __n = 10, 00366 const hasher& __hf = hasher(), 00367 const key_equal& __eql = key_equal(), 00368 const allocator_type& __a = allocator_type()) 00369 : _Base(__n, __hf, __eql, __a) { } 00370 00371 template<typename _InputIterator> 00372 unordered_multimap(_InputIterator __first, _InputIterator __last, 00373 size_type __n = 0, 00374 const hasher& __hf = hasher(), 00375 const key_equal& __eql = key_equal(), 00376 const allocator_type& __a = allocator_type()) 00377 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00378 __last)), 00379 __gnu_debug::__base(__last), __n, 00380 __hf, __eql, __a), _Safe_base() { } 00381 00382 unordered_multimap(const unordered_multimap& __x) 00383 : _Base(__x), _Safe_base() { } 00384 00385 unordered_multimap(const _Base& __x) 00386 : _Base(__x), _Safe_base() { } 00387 00388 unordered_multimap(unordered_multimap&& __x) 00389 : _Base(std::move(__x)), _Safe_base() { } 00390 00391 unordered_multimap(initializer_list<value_type> __l, 00392 size_type __n = 0, 00393 const hasher& __hf = hasher(), 00394 const key_equal& __eql = key_equal(), 00395 const allocator_type& __a = allocator_type()) 00396 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 00397 00398 unordered_multimap& 00399 operator=(const unordered_multimap& __x) 00400 { 00401 *static_cast<_Base*>(this) = __x; 00402 this->_M_invalidate_all(); 00403 return *this; 00404 } 00405 00406 unordered_multimap& 00407 operator=(unordered_multimap&& __x) 00408 { 00409 // NB: DR 1204. 00410 // NB: DR 675. 00411 clear(); 00412 swap(__x); 00413 return *this; 00414 } 00415 00416 unordered_multimap& 00417 operator=(initializer_list<value_type> __l) 00418 { 00419 this->clear(); 00420 this->insert(__l); 00421 return *this; 00422 } 00423 00424 void 00425 swap(unordered_multimap& __x) 00426 { 00427 _Base::swap(__x); 00428 _Safe_base::_M_swap(__x); 00429 } 00430 00431 void 00432 clear() 00433 { 00434 _Base::clear(); 00435 this->_M_invalidate_all(); 00436 } 00437 00438 iterator 00439 begin() 00440 { return iterator(_Base::begin(), this); } 00441 00442 const_iterator 00443 begin() const 00444 { return const_iterator(_Base::begin(), this); } 00445 00446 iterator 00447 end() 00448 { return iterator(_Base::end(), this); } 00449 00450 const_iterator 00451 end() const 00452 { return const_iterator(_Base::end(), this); } 00453 00454 const_iterator 00455 cbegin() const 00456 { return const_iterator(_Base::begin(), this); } 00457 00458 const_iterator 00459 cend() const 00460 { return const_iterator(_Base::end(), this); } 00461 00462 // local versions 00463 using _Base::begin; 00464 using _Base::end; 00465 using _Base::cbegin; 00466 using _Base::cend; 00467 00468 iterator 00469 insert(const value_type& __obj) 00470 { return iterator(_Base::insert(__obj), this); } 00471 00472 iterator 00473 insert(const_iterator __hint, const value_type& __obj) 00474 { 00475 __glibcxx_check_insert(__hint); 00476 return iterator(_Base::insert(__hint.base(), __obj), this); 00477 } 00478 00479 template<typename _Pair, typename = typename 00480 std::enable_if<std::is_convertible<_Pair, 00481 value_type>::value>::type> 00482 iterator 00483 insert(_Pair&& __obj) 00484 { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); } 00485 00486 template<typename _Pair, typename = typename 00487 std::enable_if<std::is_convertible<_Pair, 00488 value_type>::value>::type> 00489 iterator 00490 insert(const_iterator __hint, _Pair&& __obj) 00491 { 00492 __glibcxx_check_insert(__hint); 00493 return iterator(_Base::insert(__hint.base(), 00494 std::forward<_Pair>(__obj)), 00495 this); 00496 } 00497 00498 void 00499 insert(std::initializer_list<value_type> __l) 00500 { _Base::insert(__l); } 00501 00502 template<typename _InputIterator> 00503 void 00504 insert(_InputIterator __first, _InputIterator __last) 00505 { 00506 __glibcxx_check_valid_range(__first, __last); 00507 _Base::insert(__gnu_debug::__base(__first), 00508 __gnu_debug::__base(__last)); 00509 } 00510 00511 iterator 00512 find(const key_type& __key) 00513 { return iterator(_Base::find(__key), this); } 00514 00515 const_iterator 00516 find(const key_type& __key) const 00517 { return const_iterator(_Base::find(__key), this); } 00518 00519 std::pair<iterator, iterator> 00520 equal_range(const key_type& __key) 00521 { 00522 std::pair<_Base_iterator, _Base_iterator> __res = 00523 _Base::equal_range(__key); 00524 return std::make_pair(iterator(__res.first, this), 00525 iterator(__res.second, this)); 00526 } 00527 00528 std::pair<const_iterator, const_iterator> 00529 equal_range(const key_type& __key) const 00530 { 00531 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00532 _Base::equal_range(__key); 00533 return std::make_pair(const_iterator(__res.first, this), 00534 const_iterator(__res.second, this)); 00535 } 00536 00537 size_type 00538 erase(const key_type& __key) 00539 { 00540 size_type __ret(0); 00541 std::pair<_Base_iterator, _Base_iterator> __pair = 00542 _Base::equal_range(__key); 00543 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 00544 { 00545 this->_M_invalidate_if(_Equal(__victim)); 00546 _Base::erase(__victim++); 00547 ++__ret; 00548 } 00549 return __ret; 00550 } 00551 00552 iterator 00553 erase(const_iterator __it) 00554 { 00555 __glibcxx_check_erase(__it); 00556 this->_M_invalidate_if(_Equal(__it.base())); 00557 return iterator(_Base::erase(__it.base()), this); 00558 } 00559 00560 iterator 00561 erase(const_iterator __first, const_iterator __last) 00562 { 00563 __glibcxx_check_erase_range(__first, __last); 00564 for (_Base_const_iterator __tmp = __first.base(); 00565 __tmp != __last.base(); ++__tmp) 00566 { 00567 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00568 _M_message(__gnu_debug::__msg_valid_range) 00569 ._M_iterator(__first, "first") 00570 ._M_iterator(__last, "last")); 00571 this->_M_invalidate_if(_Equal(__tmp)); 00572 } 00573 return iterator(_Base::erase(__first.base(), 00574 __last.base()), this); 00575 } 00576 00577 _Base& 00578 _M_base() { return *this; } 00579 00580 const _Base& 00581 _M_base() const { return *this; } 00582 00583 private: 00584 void 00585 _M_invalidate_all() 00586 { 00587 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00588 this->_M_invalidate_if(_Not_equal(_Base::end())); 00589 } 00590 }; 00591 00592 template<typename _Key, typename _Tp, typename _Hash, 00593 typename _Pred, typename _Alloc> 00594 inline void 00595 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00596 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00597 { __x.swap(__y); } 00598 00599 template<typename _Key, typename _Tp, typename _Hash, 00600 typename _Pred, typename _Alloc> 00601 inline bool 00602 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00603 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00604 { return __x._M_equal(__y); } 00605 00606 template<typename _Key, typename _Tp, typename _Hash, 00607 typename _Pred, typename _Alloc> 00608 inline bool 00609 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00610 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00611 { return !(__x == __y); } 00612 00613 } // namespace __debug 00614 } // namespace std 00615 00616 #endif // __GXX_EXPERIMENTAL_CXX0X__ 00617 00618 #endif