1 // Debugging map implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011 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/map.h 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30 #ifndef _GLIBCXX_DEBUG_MAP_H 31 #define _GLIBCXX_DEBUG_MAP_H 1 32 33 #include <debug/safe_sequence.h> 34 #include <debug/safe_iterator.h> 35 #include <utility> 36 37 namespace std _GLIBCXX_VISIBILITY(default) 38 { 39 namespace __debug 40 { 41 /// Class std::map with safety/checking/debug instrumentation. 42 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 43 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 44 class map 45 : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>, 46 public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> > 47 { 48 typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base; 49 typedef __gnu_debug::_Safe_sequence<map> _Safe_base; 50 51 typedef typename _Base::const_iterator _Base_const_iterator; 52 typedef typename _Base::iterator _Base_iterator; 53 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 54 public: 55 // types: 56 typedef _Key key_type; 57 typedef _Tp mapped_type; 58 typedef std::pair<const _Key, _Tp> value_type; 59 typedef _Compare key_compare; 60 typedef _Allocator allocator_type; 61 typedef typename _Base::reference reference; 62 typedef typename _Base::const_reference const_reference; 63 64 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map> 65 iterator; 66 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map> 67 const_iterator; 68 69 typedef typename _Base::size_type size_type; 70 typedef typename _Base::difference_type difference_type; 71 typedef typename _Base::pointer pointer; 72 typedef typename _Base::const_pointer const_pointer; 73 typedef std::reverse_iterator<iterator> reverse_iterator; 74 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 75 76 // 23.3.1.1 construct/copy/destroy: 77 explicit map(const _Compare& __comp = _Compare(), 78 const _Allocator& __a = _Allocator()) 79 : _Base(__comp, __a) { } 80 81 template<typename _InputIterator> 82 map(_InputIterator __first, _InputIterator __last, 83 const _Compare& __comp = _Compare(), 84 const _Allocator& __a = _Allocator()) 85 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 86 __last)), 87 __gnu_debug::__base(__last), 88 __comp, __a), _Safe_base() { } 89 90 map(const map& __x) 91 : _Base(__x), _Safe_base() { } 92 93 map(const _Base& __x) 94 : _Base(__x), _Safe_base() { } 95 96 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 97 map(map&& __x) 98 : _Base(std::move(__x)), _Safe_base() 99 { this->_M_swap(__x); } 100 101 map(initializer_list<value_type> __l, 102 const _Compare& __c = _Compare(), 103 const allocator_type& __a = allocator_type()) 104 : _Base(__l, __c, __a), _Safe_base() { } 105 #endif 106 107 ~map() { } 108 109 map& 110 operator=(const map& __x) 111 { 112 *static_cast<_Base*>(this) = __x; 113 this->_M_invalidate_all(); 114 return *this; 115 } 116 117 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 118 map& 119 operator=(map&& __x) 120 { 121 // NB: DR 1204. 122 // NB: DR 675. 123 clear(); 124 swap(__x); 125 return *this; 126 } 127 128 map& 129 operator=(initializer_list<value_type> __l) 130 { 131 this->clear(); 132 this->insert(__l); 133 return *this; 134 } 135 #endif 136 137 // _GLIBCXX_RESOLVE_LIB_DEFECTS 138 // 133. map missing get_allocator() 139 using _Base::get_allocator; 140 141 // iterators: 142 iterator 143 begin() 144 { return iterator(_Base::begin(), this); } 145 146 const_iterator 147 begin() const 148 { return const_iterator(_Base::begin(), this); } 149 150 iterator 151 end() 152 { return iterator(_Base::end(), this); } 153 154 const_iterator 155 end() const 156 { return const_iterator(_Base::end(), this); } 157 158 reverse_iterator 159 rbegin() 160 { return reverse_iterator(end()); } 161 162 const_reverse_iterator 163 rbegin() const 164 { return const_reverse_iterator(end()); } 165 166 reverse_iterator 167 rend() 168 { return reverse_iterator(begin()); } 169 170 const_reverse_iterator 171 rend() const 172 { return const_reverse_iterator(begin()); } 173 174 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 175 const_iterator 176 cbegin() const 177 { return const_iterator(_Base::begin(), this); } 178 179 const_iterator 180 cend() const 181 { return const_iterator(_Base::end(), this); } 182 183 const_reverse_iterator 184 crbegin() const 185 { return const_reverse_iterator(end()); } 186 187 const_reverse_iterator 188 crend() const 189 { return const_reverse_iterator(begin()); } 190 #endif 191 192 // capacity: 193 using _Base::empty; 194 using _Base::size; 195 using _Base::max_size; 196 197 // 23.3.1.2 element access: 198 using _Base::operator[]; 199 200 // _GLIBCXX_RESOLVE_LIB_DEFECTS 201 // DR 464. Suggestion for new member functions in standard containers. 202 using _Base::at; 203 204 // modifiers: 205 std::pair<iterator, bool> 206 insert(const value_type& __x) 207 { 208 typedef typename _Base::iterator _Base_iterator; 209 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 210 return std::pair<iterator, bool>(iterator(__res.first, this), 211 __res.second); 212 } 213 214 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 215 template<typename _Pair, typename = typename 216 std::enable_if<std::is_convertible<_Pair, 217 value_type>::value>::type> 218 std::pair<iterator, bool> 219 insert(_Pair&& __x) 220 { 221 typedef typename _Base::iterator _Base_iterator; 222 std::pair<_Base_iterator, bool> __res 223 = _Base::insert(std::forward<_Pair>(__x)); 224 return std::pair<iterator, bool>(iterator(__res.first, this), 225 __res.second); 226 } 227 #endif 228 229 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 230 void 231 insert(std::initializer_list<value_type> __list) 232 { _Base::insert(__list); } 233 #endif 234 235 iterator 236 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 237 insert(const_iterator __position, const value_type& __x) 238 #else 239 insert(iterator __position, const value_type& __x) 240 #endif 241 { 242 __glibcxx_check_insert(__position); 243 return iterator(_Base::insert(__position.base(), __x), this); 244 } 245 246 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 247 template<typename _Pair, typename = typename 248 std::enable_if<std::is_convertible<_Pair, 249 value_type>::value>::type> 250 iterator 251 insert(const_iterator __position, _Pair&& __x) 252 { 253 __glibcxx_check_insert(__position); 254 return iterator(_Base::insert(__position.base(), 255 std::forward<_Pair>(__x)), this); 256 } 257 #endif 258 259 template<typename _InputIterator> 260 void 261 insert(_InputIterator __first, _InputIterator __last) 262 { 263 __glibcxx_check_valid_range(__first, __last); 264 _Base::insert(__gnu_debug::__base(__first), 265 __gnu_debug::__base(__last)); 266 } 267 268 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 269 iterator 270 erase(const_iterator __position) 271 { 272 __glibcxx_check_erase(__position); 273 this->_M_invalidate_if(_Equal(__position.base())); 274 return iterator(_Base::erase(__position.base()), this); 275 } 276 277 iterator 278 erase(iterator __position) 279 { return erase(const_iterator(__position)); } 280 #else 281 void 282 erase(iterator __position) 283 { 284 __glibcxx_check_erase(__position); 285 this->_M_invalidate_if(_Equal(__position.base())); 286 _Base::erase(__position.base()); 287 } 288 #endif 289 290 size_type 291 erase(const key_type& __x) 292 { 293 _Base_iterator __victim = _Base::find(__x); 294 if (__victim == _Base::end()) 295 return 0; 296 else 297 { 298 this->_M_invalidate_if(_Equal(__victim)); 299 _Base::erase(__victim); 300 return 1; 301 } 302 } 303 304 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 305 iterator 306 erase(const_iterator __first, const_iterator __last) 307 { 308 // _GLIBCXX_RESOLVE_LIB_DEFECTS 309 // 151. can't currently clear() empty container 310 __glibcxx_check_erase_range(__first, __last); 311 for (_Base_const_iterator __victim = __first.base(); 312 __victim != __last.base(); ++__victim) 313 { 314 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 315 _M_message(__gnu_debug::__msg_valid_range) 316 ._M_iterator(__first, "first") 317 ._M_iterator(__last, "last")); 318 this->_M_invalidate_if(_Equal(__victim)); 319 } 320 return iterator(_Base::erase(__first.base(), __last.base()), this); 321 } 322 #else 323 void 324 erase(iterator __first, iterator __last) 325 { 326 // _GLIBCXX_RESOLVE_LIB_DEFECTS 327 // 151. can't currently clear() empty container 328 __glibcxx_check_erase_range(__first, __last); 329 for (_Base_iterator __victim = __first.base(); 330 __victim != __last.base(); ++__victim) 331 { 332 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 333 _M_message(__gnu_debug::__msg_valid_range) 334 ._M_iterator(__first, "first") 335 ._M_iterator(__last, "last")); 336 this->_M_invalidate_if(_Equal(__victim)); 337 } 338 _Base::erase(__first.base(), __last.base()); 339 } 340 #endif 341 342 void 343 swap(map& __x) 344 { 345 _Base::swap(__x); 346 this->_M_swap(__x); 347 } 348 349 void 350 clear() 351 { 352 this->_M_invalidate_all(); 353 _Base::clear(); 354 } 355 356 // observers: 357 using _Base::key_comp; 358 using _Base::value_comp; 359 360 // 23.3.1.3 map operations: 361 iterator 362 find(const key_type& __x) 363 { return iterator(_Base::find(__x), this); } 364 365 const_iterator 366 find(const key_type& __x) const 367 { return const_iterator(_Base::find(__x), this); } 368 369 using _Base::count; 370 371 iterator 372 lower_bound(const key_type& __x) 373 { return iterator(_Base::lower_bound(__x), this); } 374 375 const_iterator 376 lower_bound(const key_type& __x) const 377 { return const_iterator(_Base::lower_bound(__x), this); } 378 379 iterator 380 upper_bound(const key_type& __x) 381 { return iterator(_Base::upper_bound(__x), this); } 382 383 const_iterator 384 upper_bound(const key_type& __x) const 385 { return const_iterator(_Base::upper_bound(__x), this); } 386 387 std::pair<iterator,iterator> 388 equal_range(const key_type& __x) 389 { 390 typedef typename _Base::iterator _Base_iterator; 391 std::pair<_Base_iterator, _Base_iterator> __res = 392 _Base::equal_range(__x); 393 return std::make_pair(iterator(__res.first, this), 394 iterator(__res.second, this)); 395 } 396 397 std::pair<const_iterator,const_iterator> 398 equal_range(const key_type& __x) const 399 { 400 typedef typename _Base::const_iterator _Base_const_iterator; 401 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 402 _Base::equal_range(__x); 403 return std::make_pair(const_iterator(__res.first, this), 404 const_iterator(__res.second, this)); 405 } 406 407 _Base& 408 _M_base() { return *this; } 409 410 const _Base& 411 _M_base() const { return *this; } 412 413 private: 414 void 415 _M_invalidate_all() 416 { 417 typedef typename _Base::const_iterator _Base_const_iterator; 418 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 419 this->_M_invalidate_if(_Not_equal(_M_base().end())); 420 } 421 }; 422 423 template<typename _Key, typename _Tp, 424 typename _Compare, typename _Allocator> 425 inline bool 426 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 427 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 428 { return __lhs._M_base() == __rhs._M_base(); } 429 430 template<typename _Key, typename _Tp, 431 typename _Compare, typename _Allocator> 432 inline bool 433 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 434 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 435 { return __lhs._M_base() != __rhs._M_base(); } 436 437 template<typename _Key, typename _Tp, 438 typename _Compare, typename _Allocator> 439 inline bool 440 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 441 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 442 { return __lhs._M_base() < __rhs._M_base(); } 443 444 template<typename _Key, typename _Tp, 445 typename _Compare, typename _Allocator> 446 inline bool 447 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 448 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 449 { return __lhs._M_base() <= __rhs._M_base(); } 450 451 template<typename _Key, typename _Tp, 452 typename _Compare, typename _Allocator> 453 inline bool 454 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 455 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 456 { return __lhs._M_base() >= __rhs._M_base(); } 457 458 template<typename _Key, typename _Tp, 459 typename _Compare, typename _Allocator> 460 inline bool 461 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 462 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 463 { return __lhs._M_base() > __rhs._M_base(); } 464 465 template<typename _Key, typename _Tp, 466 typename _Compare, typename _Allocator> 467 inline void 468 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 469 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 470 { __lhs.swap(__rhs); } 471 472 } // namespace __debug 473 } // namespace std 474 475 #endif 476
