libstdc++
|
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00034 # include <unordered_map> 00035 #else 00036 # include <c++0x_warning.h> 00037 #endif 00038 00039 #include <debug/safe_sequence.h> 00040 #include <debug/safe_iterator.h> 00041 #include <initializer_list> 00042 00043 namespace std 00044 { 00045 namespace __debug 00046 { 00047 template<typename _Key, typename _Tp, 00048 typename _Hash = std::hash<_Key>, 00049 typename _Pred = std::equal_to<_Key>, 00050 typename _Alloc = std::allocator<_Key> > 00051 class unordered_map 00052 : public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 00053 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash, 00054 _Pred, _Alloc> > 00055 { 00056 typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, 00057 _Pred, _Alloc> _Base; 00058 typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base; 00059 00060 public: 00061 typedef typename _Base::size_type size_type; 00062 typedef typename _Base::hasher hasher; 00063 typedef typename _Base::key_equal key_equal; 00064 typedef typename _Base::allocator_type allocator_type; 00065 00066 typedef typename _Base::key_type key_type; 00067 typedef typename _Base::value_type value_type; 00068 00069 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 00070 unordered_map> iterator; 00071 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 00072 unordered_map> const_iterator; 00073 00074 explicit 00075 unordered_map(size_type __n = 10, 00076 const hasher& __hf = hasher(), 00077 const key_equal& __eql = key_equal(), 00078 const allocator_type& __a = allocator_type()) 00079 : _Base(__n, __hf, __eql, __a) { } 00080 00081 template<typename _InputIterator> 00082 unordered_map(_InputIterator __f, _InputIterator __l, 00083 size_type __n = 10, 00084 const hasher& __hf = hasher(), 00085 const key_equal& __eql = key_equal(), 00086 const allocator_type& __a = allocator_type()) 00087 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 00088 __hf, __eql, __a), _Safe_base() { } 00089 00090 unordered_map(const unordered_map& __x) 00091 : _Base(__x), _Safe_base() { } 00092 00093 unordered_map(const _Base& __x) 00094 : _Base(__x), _Safe_base() { } 00095 00096 unordered_map(unordered_map&& __x) 00097 : _Base(std::forward<unordered_map>(__x)), _Safe_base() { } 00098 00099 unordered_map(initializer_list<value_type> __l, 00100 size_type __n = 10, 00101 const hasher& __hf = hasher(), 00102 const key_equal& __eql = key_equal(), 00103 const allocator_type& __a = allocator_type()) 00104 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 00105 00106 unordered_map& 00107 operator=(const unordered_map& __x) 00108 { 00109 *static_cast<_Base*>(this) = __x; 00110 this->_M_invalidate_all(); 00111 return *this; 00112 } 00113 00114 unordered_map& 00115 operator=(unordered_map&& __x) 00116 { 00117 // NB: DR 675. 00118 clear(); 00119 swap(__x); 00120 return *this; 00121 } 00122 00123 unordered_map& 00124 operator=(initializer_list<value_type> __l) 00125 { 00126 this->clear(); 00127 this->insert(__l); 00128 return *this; 00129 } 00130 00131 void 00132 swap(unordered_map&& __x) 00133 { 00134 _Base::swap(__x); 00135 _Safe_base::_M_swap(__x); 00136 } 00137 00138 void 00139 clear() 00140 { 00141 _Base::clear(); 00142 this->_M_invalidate_all(); 00143 } 00144 00145 iterator 00146 begin() 00147 { return iterator(_Base::begin(), this); } 00148 00149 const_iterator 00150 begin() const 00151 { return const_iterator(_Base::begin(), this); } 00152 00153 iterator 00154 end() 00155 { return iterator(_Base::end(), this); } 00156 00157 const_iterator 00158 end() const 00159 { return const_iterator(_Base::end(), this); } 00160 00161 const_iterator 00162 cbegin() const 00163 { return const_iterator(_Base::begin(), this); } 00164 00165 const_iterator 00166 cend() const 00167 { return const_iterator(_Base::end(), this); } 00168 00169 // local versions 00170 using _Base::begin; 00171 using _Base::end; 00172 using _Base::cbegin; 00173 using _Base::cend; 00174 00175 std::pair<iterator, bool> 00176 insert(const value_type& __obj) 00177 { 00178 typedef std::pair<typename _Base::iterator, bool> __pair_type; 00179 __pair_type __res = _Base::insert(__obj); 00180 return std::make_pair(iterator(__res.first, this), __res.second); 00181 } 00182 00183 iterator 00184 insert(iterator, const value_type& __obj) 00185 { 00186 typedef std::pair<typename _Base::iterator, bool> __pair_type; 00187 __pair_type __res = _Base::insert(__obj); 00188 return iterator(__res.first, this); 00189 } 00190 00191 const_iterator 00192 insert(const_iterator, const value_type& __obj) 00193 { 00194 typedef std::pair<typename _Base::iterator, bool> __pair_type; 00195 __pair_type __res = _Base::insert(__obj); 00196 return const_iterator(__res.first, this); 00197 } 00198 00199 void 00200 insert(std::initializer_list<value_type> __l) 00201 { _Base::insert(__l); } 00202 00203 template<typename _InputIterator> 00204 void 00205 insert(_InputIterator __first, _InputIterator __last) 00206 { 00207 __glibcxx_check_valid_range(__first, __last); 00208 _Base::insert(__first, __last); 00209 } 00210 00211 iterator 00212 find(const key_type& __key) 00213 { return iterator(_Base::find(__key), this); } 00214 00215 const_iterator 00216 find(const key_type& __key) const 00217 { return const_iterator(_Base::find(__key), this); } 00218 00219 std::pair<iterator, iterator> 00220 equal_range(const key_type& __key) 00221 { 00222 typedef typename _Base::iterator _Base_iterator; 00223 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00224 __pair_type __res = _Base::equal_range(__key); 00225 return std::make_pair(iterator(__res.first, this), 00226 iterator(__res.second, this)); 00227 } 00228 00229 std::pair<const_iterator, const_iterator> 00230 equal_range(const key_type& __key) const 00231 { 00232 typedef typename _Base::const_iterator _Base_iterator; 00233 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00234 __pair_type __res = _Base::equal_range(__key); 00235 return std::make_pair(const_iterator(__res.first, this), 00236 const_iterator(__res.second, this)); 00237 } 00238 00239 size_type 00240 erase(const key_type& __key) 00241 { 00242 size_type __ret(0); 00243 iterator __victim(_Base::find(__key), this); 00244 if (__victim != end()) 00245 { 00246 this->erase(__victim); 00247 __ret = 1; 00248 } 00249 return __ret; 00250 } 00251 00252 iterator 00253 erase(iterator __it) 00254 { 00255 __glibcxx_check_erase(__it); 00256 __it._M_invalidate(); 00257 return iterator(_Base::erase(__it.base()), this); 00258 } 00259 00260 const_iterator 00261 erase(const_iterator __it) 00262 { 00263 __glibcxx_check_erase(__it); 00264 __it._M_invalidate(); 00265 return const_iterator(_Base::erase(__it.base()), this); 00266 } 00267 00268 iterator 00269 erase(iterator __first, iterator __last) 00270 { 00271 __glibcxx_check_erase_range(__first, __last); 00272 for (iterator __tmp = __first; __tmp != __last;) 00273 { 00274 iterator __victim = __tmp++; 00275 __victim._M_invalidate(); 00276 } 00277 return iterator(_Base::erase(__first.base(), 00278 __last.base()), this); 00279 } 00280 00281 const_iterator 00282 erase(const_iterator __first, const_iterator __last) 00283 { 00284 __glibcxx_check_erase_range(__first, __last); 00285 for (const_iterator __tmp = __first; __tmp != __last;) 00286 { 00287 const_iterator __victim = __tmp++; 00288 __victim._M_invalidate(); 00289 } 00290 return const_iterator(_Base::erase(__first.base(), 00291 __last.base()), this); 00292 } 00293 00294 _Base& 00295 _M_base() { return *this; } 00296 00297 const _Base& 00298 _M_base() const { return *this; } 00299 00300 private: 00301 void 00302 _M_invalidate_all() 00303 { 00304 typedef typename _Base::const_iterator _Base_const_iterator; 00305 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00306 this->_M_invalidate_if(_Not_equal(_M_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 void 00320 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x, 00321 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00322 { __x.swap(__y); } 00323 00324 template<typename _Key, typename _Tp, typename _Hash, 00325 typename _Pred, typename _Alloc> 00326 inline void 00327 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00328 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y) 00329 { __x.swap(__y); } 00330 00331 00332 template<typename _Key, typename _Tp, 00333 typename _Hash = std::hash<_Key>, 00334 typename _Pred = std::equal_to<_Key>, 00335 typename _Alloc = std::allocator<_Key> > 00336 class unordered_multimap 00337 : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash, 00338 _Pred, _Alloc>, 00339 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash, 00340 _Pred, _Alloc> > 00341 { 00342 typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash, 00343 _Pred, _Alloc> _Base; 00344 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base; 00345 00346 public: 00347 typedef typename _Base::size_type size_type; 00348 typedef typename _Base::hasher hasher; 00349 typedef typename _Base::key_equal key_equal; 00350 typedef typename _Base::allocator_type allocator_type; 00351 00352 typedef typename _Base::key_type key_type; 00353 typedef typename _Base::value_type value_type; 00354 00355 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 00356 unordered_multimap> iterator; 00357 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 00358 unordered_multimap> const_iterator; 00359 00360 explicit 00361 unordered_multimap(size_type __n = 10, 00362 const hasher& __hf = hasher(), 00363 const key_equal& __eql = key_equal(), 00364 const allocator_type& __a = allocator_type()) 00365 : _Base(__n, __hf, __eql, __a) { } 00366 00367 template<typename _InputIterator> 00368 unordered_multimap(_InputIterator __f, _InputIterator __l, 00369 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(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 00374 __hf, __eql, __a), _Safe_base() { } 00375 00376 unordered_multimap(const unordered_multimap& __x) 00377 : _Base(__x), _Safe_base() { } 00378 00379 unordered_multimap(const _Base& __x) 00380 : _Base(__x), _Safe_base() { } 00381 00382 unordered_multimap(unordered_multimap&& __x) 00383 : _Base(std::forward<unordered_multimap>(__x)), _Safe_base() { } 00384 00385 unordered_multimap(initializer_list<value_type> __l, 00386 size_type __n = 10, 00387 const hasher& __hf = hasher(), 00388 const key_equal& __eql = key_equal(), 00389 const allocator_type& __a = allocator_type()) 00390 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 00391 00392 unordered_multimap& 00393 operator=(const unordered_multimap& __x) 00394 { 00395 *static_cast<_Base*>(this) = __x; 00396 this->_M_invalidate_all(); 00397 return *this; 00398 } 00399 00400 unordered_multimap& 00401 operator=(unordered_multimap&& __x) 00402 { 00403 // NB: DR 675. 00404 clear(); 00405 swap(__x); 00406 return *this; 00407 } 00408 00409 unordered_multimap& 00410 operator=(initializer_list<value_type> __l) 00411 { 00412 this->clear(); 00413 this->insert(__l); 00414 return *this; 00415 } 00416 00417 void 00418 swap(unordered_multimap&& __x) 00419 { 00420 _Base::swap(__x); 00421 _Safe_base::_M_swap(__x); 00422 } 00423 00424 void 00425 clear() 00426 { 00427 _Base::clear(); 00428 this->_M_invalidate_all(); 00429 } 00430 00431 iterator 00432 begin() 00433 { return iterator(_Base::begin(), this); } 00434 00435 const_iterator 00436 begin() const 00437 { return const_iterator(_Base::begin(), this); } 00438 00439 iterator 00440 end() 00441 { return iterator(_Base::end(), this); } 00442 00443 const_iterator 00444 end() const 00445 { return const_iterator(_Base::end(), this); } 00446 00447 const_iterator 00448 cbegin() const 00449 { return const_iterator(_Base::begin(), this); } 00450 00451 const_iterator 00452 cend() const 00453 { return const_iterator(_Base::end(), this); } 00454 00455 // local versions 00456 using _Base::begin; 00457 using _Base::end; 00458 using _Base::cbegin; 00459 using _Base::cend; 00460 00461 iterator 00462 insert(const value_type& __obj) 00463 { return iterator(_Base::insert(__obj), this); } 00464 00465 iterator 00466 insert(iterator, const value_type& __obj) 00467 { return iterator(_Base::insert(__obj), this); } 00468 00469 const_iterator 00470 insert(const_iterator, const value_type& __obj) 00471 { return const_iterator(_Base::insert(__obj), this); } 00472 00473 void 00474 insert(std::initializer_list<value_type> __l) 00475 { _Base::insert(__l); } 00476 00477 template<typename _InputIterator> 00478 void 00479 insert(_InputIterator __first, _InputIterator __last) 00480 { 00481 __glibcxx_check_valid_range(__first, __last); 00482 _Base::insert(__first, __last); 00483 } 00484 00485 iterator 00486 find(const key_type& __key) 00487 { return iterator(_Base::find(__key), this); } 00488 00489 const_iterator 00490 find(const key_type& __key) const 00491 { return const_iterator(_Base::find(__key), this); } 00492 00493 std::pair<iterator, iterator> 00494 equal_range(const key_type& __key) 00495 { 00496 typedef typename _Base::iterator _Base_iterator; 00497 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00498 __pair_type __res = _Base::equal_range(__key); 00499 return std::make_pair(iterator(__res.first, this), 00500 iterator(__res.second, this)); 00501 } 00502 00503 std::pair<const_iterator, const_iterator> 00504 equal_range(const key_type& __key) const 00505 { 00506 typedef typename _Base::const_iterator _Base_iterator; 00507 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00508 __pair_type __res = _Base::equal_range(__key); 00509 return std::make_pair(const_iterator(__res.first, this), 00510 const_iterator(__res.second, this)); 00511 } 00512 00513 size_type 00514 erase(const key_type& __key) 00515 { 00516 size_type __ret(0); 00517 iterator __victim(_Base::find(__key), this); 00518 if (__victim != end()) 00519 { 00520 this->erase(__victim); 00521 __ret = 1; 00522 } 00523 return __ret; 00524 } 00525 00526 iterator 00527 erase(iterator __it) 00528 { 00529 __glibcxx_check_erase(__it); 00530 __it._M_invalidate(); 00531 return iterator(_Base::erase(__it.base()), this); 00532 } 00533 00534 const_iterator 00535 erase(const_iterator __it) 00536 { 00537 __glibcxx_check_erase(__it); 00538 __it._M_invalidate(); 00539 return const_iterator(_Base::erase(__it.base()), this); 00540 } 00541 00542 iterator 00543 erase(iterator __first, iterator __last) 00544 { 00545 __glibcxx_check_erase_range(__first, __last); 00546 for (iterator __tmp = __first; __tmp != __last;) 00547 { 00548 iterator __victim = __tmp++; 00549 __victim._M_invalidate(); 00550 } 00551 return iterator(_Base::erase(__first.base(), 00552 __last.base()), this); 00553 } 00554 00555 const_iterator 00556 erase(const_iterator __first, const_iterator __last) 00557 { 00558 __glibcxx_check_erase_range(__first, __last); 00559 for (const_iterator __tmp = __first; __tmp != __last;) 00560 { 00561 const_iterator __victim = __tmp++; 00562 __victim._M_invalidate(); 00563 } 00564 return const_iterator(_Base::erase(__first.base(), 00565 __last.base()), this); 00566 } 00567 00568 _Base& 00569 _M_base() { return *this; } 00570 00571 const _Base& 00572 _M_base() const { return *this; } 00573 00574 private: 00575 void 00576 _M_invalidate_all() 00577 { 00578 typedef typename _Base::const_iterator _Base_const_iterator; 00579 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00580 this->_M_invalidate_if(_Not_equal(_M_base().end())); 00581 } 00582 }; 00583 00584 template<typename _Key, typename _Tp, typename _Hash, 00585 typename _Pred, typename _Alloc> 00586 inline void 00587 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00588 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00589 { __x.swap(__y); } 00590 00591 template<typename _Key, typename _Tp, typename _Hash, 00592 typename _Pred, typename _Alloc> 00593 inline void 00594 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x, 00595 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00596 { __x.swap(__y); } 00597 00598 template<typename _Key, typename _Tp, typename _Hash, 00599 typename _Pred, typename _Alloc> 00600 inline void 00601 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00602 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y) 00603 { __x.swap(__y); } 00604 00605 } // namespace __debug 00606 } // namespace std 00607 00608 #endif