1 // Debugging map implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2013 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file debug/map.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_MAP_H 30 #define _GLIBCXX_DEBUG_MAP_H 1 31 32 #include <debug/safe_sequence.h> 33 #include <debug/safe_iterator.h> 34 #include <utility> 35 36 namespace std _GLIBCXX_VISIBILITY(default) 37 { 38 namespace __debug 39 { 40 /// Class std::map with safety/checking/debug instrumentation. 41 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 42 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 43 class map 44 : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>, 45 public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> > 46 { 47 typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base; 48 49 typedef typename _Base::const_iterator _Base_const_iterator; 50 typedef typename _Base::iterator _Base_iterator; 51 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 52 public: 53 // types: 54 typedef _Key key_type; 55 typedef _Tp mapped_type; 56 typedef std::pair<const _Key, _Tp> value_type; 57 typedef _Compare key_compare; 58 typedef _Allocator allocator_type; 59 typedef typename _Base::reference reference; 60 typedef typename _Base::const_reference const_reference; 61 62 typedef __gnu_debug::_Safe_iterator<_Base_iterator, map> 63 iterator; 64 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map> 65 const_iterator; 66 67 typedef typename _Base::size_type size_type; 68 typedef typename _Base::difference_type difference_type; 69 typedef typename _Base::pointer pointer; 70 typedef typename _Base::const_pointer const_pointer; 71 typedef std::reverse_iterator<iterator> reverse_iterator; 72 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 73 74 // 23.3.1.1 construct/copy/destroy: 75 explicit map(const _Compare& __comp = _Compare(), 76 const _Allocator& __a = _Allocator()) 77 : _Base(__comp, __a) { } 78 79 template<typename _InputIterator> 80 map(_InputIterator __first, _InputIterator __last, 81 const _Compare& __comp = _Compare(), 82 const _Allocator& __a = _Allocator()) 83 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 84 __last)), 85 __gnu_debug::__base(__last), 86 __comp, __a) { } 87 88 map(const map& __x) 89 : _Base(__x) { } 90 91 map(const _Base& __x) 92 : _Base(__x) { } 93 94 #if __cplusplus >= 201103L 95 map(map&& __x) 96 noexcept(is_nothrow_copy_constructible<_Compare>::value) 97 : _Base(std::move(__x)) 98 { this->_M_swap(__x); } 99 100 map(initializer_list<value_type> __l, 101 const _Compare& __c = _Compare(), 102 const allocator_type& __a = allocator_type()) 103 : _Base(__l, __c, __a) { } 104 #endif 105 106 ~map() _GLIBCXX_NOEXCEPT { } 107 108 map& 109 operator=(const map& __x) 110 { 111 *static_cast<_Base*>(this) = __x; 112 this->_M_invalidate_all(); 113 return *this; 114 } 115 116 #if __cplusplus >= 201103L 117 map& 118 operator=(map&& __x) 119 { 120 // NB: DR 1204. 121 // NB: DR 675. 122 __glibcxx_check_self_move_assign(__x); 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() _GLIBCXX_NOEXCEPT 144 { return iterator(_Base::begin(), this); } 145 146 const_iterator 147 begin() const _GLIBCXX_NOEXCEPT 148 { return const_iterator(_Base::begin(), this); } 149 150 iterator 151 end() _GLIBCXX_NOEXCEPT 152 { return iterator(_Base::end(), this); } 153 154 const_iterator 155 end() const _GLIBCXX_NOEXCEPT 156 { return const_iterator(_Base::end(), this); } 157 158 reverse_iterator 159 rbegin() _GLIBCXX_NOEXCEPT 160 { return reverse_iterator(end()); } 161 162 const_reverse_iterator 163 rbegin() const _GLIBCXX_NOEXCEPT 164 { return const_reverse_iterator(end()); } 165 166 reverse_iterator 167 rend() _GLIBCXX_NOEXCEPT 168 { return reverse_iterator(begin()); } 169 170 const_reverse_iterator 171 rend() const _GLIBCXX_NOEXCEPT 172 { return const_reverse_iterator(begin()); } 173 174 #if __cplusplus >= 201103L 175 const_iterator 176 cbegin() const noexcept 177 { return const_iterator(_Base::begin(), this); } 178 179 const_iterator 180 cend() const noexcept 181 { return const_iterator(_Base::end(), this); } 182 183 const_reverse_iterator 184 crbegin() const noexcept 185 { return const_reverse_iterator(end()); } 186 187 const_reverse_iterator 188 crend() const noexcept 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 #if __cplusplus >= 201103L 206 template<typename... _Args> 207 std::pair<iterator, bool> 208 emplace(_Args&&... __args) 209 { 210 auto __res = _Base::emplace(std::forward<_Args>(__args)...); 211 return std::pair<iterator, bool>(iterator(__res.first, this), 212 __res.second); 213 } 214 215 template<typename... _Args> 216 iterator 217 emplace_hint(const_iterator __pos, _Args&&... __args) 218 { 219 __glibcxx_check_insert(__pos); 220 return iterator(_Base::emplace_hint(__pos.base(), 221 std::forward<_Args>(__args)...), 222 this); 223 } 224 #endif 225 226 std::pair<iterator, bool> 227 insert(const value_type& __x) 228 { 229 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 230 return std::pair<iterator, bool>(iterator(__res.first, this), 231 __res.second); 232 } 233 234 #if __cplusplus >= 201103L 235 template<typename _Pair, typename = typename 236 std::enable_if<std::is_constructible<value_type, 237 _Pair&&>::value>::type> 238 std::pair<iterator, bool> 239 insert(_Pair&& __x) 240 { 241 std::pair<_Base_iterator, bool> __res 242 = _Base::insert(std::forward<_Pair>(__x)); 243 return std::pair<iterator, bool>(iterator(__res.first, this), 244 __res.second); 245 } 246 #endif 247 248 #if __cplusplus >= 201103L 249 void 250 insert(std::initializer_list<value_type> __list) 251 { _Base::insert(__list); } 252 #endif 253 254 iterator 255 #if __cplusplus >= 201103L 256 insert(const_iterator __position, const value_type& __x) 257 #else 258 insert(iterator __position, const value_type& __x) 259 #endif 260 { 261 __glibcxx_check_insert(__position); 262 return iterator(_Base::insert(__position.base(), __x), this); 263 } 264 265 #if __cplusplus >= 201103L 266 template<typename _Pair, typename = typename 267 std::enable_if<std::is_constructible<value_type, 268 _Pair&&>::value>::type> 269 iterator 270 insert(const_iterator __position, _Pair&& __x) 271 { 272 __glibcxx_check_insert(__position); 273 return iterator(_Base::insert(__position.base(), 274 std::forward<_Pair>(__x)), this); 275 } 276 #endif 277 278 template<typename _InputIterator> 279 void 280 insert(_InputIterator __first, _InputIterator __last) 281 { 282 __glibcxx_check_valid_range(__first, __last); 283 _Base::insert(__gnu_debug::__base(__first), 284 __gnu_debug::__base(__last)); 285 } 286 287 #if __cplusplus >= 201103L 288 iterator 289 erase(const_iterator __position) 290 { 291 __glibcxx_check_erase(__position); 292 this->_M_invalidate_if(_Equal(__position.base())); 293 return iterator(_Base::erase(__position.base()), this); 294 } 295 296 iterator 297 erase(iterator __position) 298 { return erase(const_iterator(__position)); } 299 #else 300 void 301 erase(iterator __position) 302 { 303 __glibcxx_check_erase(__position); 304 this->_M_invalidate_if(_Equal(__position.base())); 305 _Base::erase(__position.base()); 306 } 307 #endif 308 309 size_type 310 erase(const key_type& __x) 311 { 312 _Base_iterator __victim = _Base::find(__x); 313 if (__victim == _Base::end()) 314 return 0; 315 else 316 { 317 this->_M_invalidate_if(_Equal(__victim)); 318 _Base::erase(__victim); 319 return 1; 320 } 321 } 322 323 #if __cplusplus >= 201103L 324 iterator 325 erase(const_iterator __first, const_iterator __last) 326 { 327 // _GLIBCXX_RESOLVE_LIB_DEFECTS 328 // 151. can't currently clear() empty container 329 __glibcxx_check_erase_range(__first, __last); 330 for (_Base_const_iterator __victim = __first.base(); 331 __victim != __last.base(); ++__victim) 332 { 333 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 334 _M_message(__gnu_debug::__msg_valid_range) 335 ._M_iterator(__first, "first") 336 ._M_iterator(__last, "last")); 337 this->_M_invalidate_if(_Equal(__victim)); 338 } 339 return iterator(_Base::erase(__first.base(), __last.base()), this); 340 } 341 #else 342 void 343 erase(iterator __first, iterator __last) 344 { 345 // _GLIBCXX_RESOLVE_LIB_DEFECTS 346 // 151. can't currently clear() empty container 347 __glibcxx_check_erase_range(__first, __last); 348 for (_Base_iterator __victim = __first.base(); 349 __victim != __last.base(); ++__victim) 350 { 351 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 352 _M_message(__gnu_debug::__msg_valid_range) 353 ._M_iterator(__first, "first") 354 ._M_iterator(__last, "last")); 355 this->_M_invalidate_if(_Equal(__victim)); 356 } 357 _Base::erase(__first.base(), __last.base()); 358 } 359 #endif 360 361 void 362 swap(map& __x) 363 { 364 _Base::swap(__x); 365 this->_M_swap(__x); 366 } 367 368 void 369 clear() _GLIBCXX_NOEXCEPT 370 { 371 this->_M_invalidate_all(); 372 _Base::clear(); 373 } 374 375 // observers: 376 using _Base::key_comp; 377 using _Base::value_comp; 378 379 // 23.3.1.3 map operations: 380 iterator 381 find(const key_type& __x) 382 { return iterator(_Base::find(__x), this); } 383 384 const_iterator 385 find(const key_type& __x) const 386 { return const_iterator(_Base::find(__x), this); } 387 388 using _Base::count; 389 390 iterator 391 lower_bound(const key_type& __x) 392 { return iterator(_Base::lower_bound(__x), this); } 393 394 const_iterator 395 lower_bound(const key_type& __x) const 396 { return const_iterator(_Base::lower_bound(__x), this); } 397 398 iterator 399 upper_bound(const key_type& __x) 400 { return iterator(_Base::upper_bound(__x), this); } 401 402 const_iterator 403 upper_bound(const key_type& __x) const 404 { return const_iterator(_Base::upper_bound(__x), this); } 405 406 std::pair<iterator,iterator> 407 equal_range(const key_type& __x) 408 { 409 std::pair<_Base_iterator, _Base_iterator> __res = 410 _Base::equal_range(__x); 411 return std::make_pair(iterator(__res.first, this), 412 iterator(__res.second, this)); 413 } 414 415 std::pair<const_iterator,const_iterator> 416 equal_range(const key_type& __x) const 417 { 418 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 419 _Base::equal_range(__x); 420 return std::make_pair(const_iterator(__res.first, this), 421 const_iterator(__res.second, this)); 422 } 423 424 _Base& 425 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 426 427 const _Base& 428 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 429 430 private: 431 void 432 _M_invalidate_all() 433 { 434 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 435 this->_M_invalidate_if(_Not_equal(_M_base().end())); 436 } 437 }; 438 439 template<typename _Key, typename _Tp, 440 typename _Compare, typename _Allocator> 441 inline bool 442 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 443 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 444 { return __lhs._M_base() == __rhs._M_base(); } 445 446 template<typename _Key, typename _Tp, 447 typename _Compare, typename _Allocator> 448 inline bool 449 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 450 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 451 { return __lhs._M_base() != __rhs._M_base(); } 452 453 template<typename _Key, typename _Tp, 454 typename _Compare, typename _Allocator> 455 inline bool 456 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 457 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 458 { return __lhs._M_base() < __rhs._M_base(); } 459 460 template<typename _Key, typename _Tp, 461 typename _Compare, typename _Allocator> 462 inline bool 463 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 464 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 465 { return __lhs._M_base() <= __rhs._M_base(); } 466 467 template<typename _Key, typename _Tp, 468 typename _Compare, typename _Allocator> 469 inline bool 470 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 471 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 472 { return __lhs._M_base() >= __rhs._M_base(); } 473 474 template<typename _Key, typename _Tp, 475 typename _Compare, typename _Allocator> 476 inline bool 477 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 478 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 479 { return __lhs._M_base() > __rhs._M_base(); } 480 481 template<typename _Key, typename _Tp, 482 typename _Compare, typename _Allocator> 483 inline void 484 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 485 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 486 { __lhs.swap(__rhs); } 487 488 } // namespace __debug 489 } // namespace std 490 491 #endif 492