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