1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 18 * Permission to use or copy this software for any purpose is hereby granted 19 * without fee, provided the above notices are retained on all copies. 20 * Permission to modify the code and to distribute modified code is granted, 21 * provided the above notices are retained, and a notice that the code was 22 * modified is included with the above copyright notice. 23 * 24 */ 25 26 /* NOTE: This is an internal header file, included by other STL headers. 27 * You should not attempt to use it directly. 28 */ 29 30 #ifndef _STLP_INTERNAL_DBG_DEQUE_H 31 #define _STLP_INTERNAL_DBG_DEQUE_H 32 33 #ifndef _STLP_DBG_ITERATOR_H 34 # include <stl/debug/_iterator.h> 35 #endif 36 37 #define _STLP_NON_DBG_DEQUE _STLP_PRIV _STLP_NON_DBG_NAME(deque) <_Tp,_Alloc> 38 39 _STLP_BEGIN_NAMESPACE 40 41 #if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS) 42 template <class _Tp, class _Alloc> 43 inline _Tp* value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_DEQUE >&) 44 { return (_Tp*)0; } 45 template <class _Tp, class _Alloc> 46 inline random_access_iterator_tag iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_DEQUE >&) 47 { return random_access_iterator_tag(); } 48 #endif 49 50 template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) > 51 class deque : 52 #if !defined (__DMC__) 53 private 54 #endif 55 _STLP_PRIV __construct_checker<_STLP_NON_DBG_DEQUE > 56 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 57 , public __stlport_class<deque<_Tp, _Alloc> > 58 #endif 59 { 60 typedef deque<_Tp,_Alloc> _Self; 61 typedef _STLP_NON_DBG_DEQUE _Base; 62 typedef _STLP_PRIV __construct_checker<_STLP_NON_DBG_DEQUE > _ConstructCheck; 63 64 public: 65 // Basic types 66 __IMPORT_CONTAINER_TYPEDEFS(_Base) 67 68 // Iterators 69 typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_Nonconst_traits<value_type> > > iterator; 70 typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_Const_traits<value_type> > > const_iterator; 71 72 _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS; 73 74 protected: 75 _Base _M_non_dbg_impl; 76 _STLP_PRIV __owned_list _M_iter_list; 77 78 void _Invalidate_all() 79 { _M_iter_list._Invalidate_all(); } 80 void _Invalidate_iterator(const iterator& __it) 81 { _STLP_PRIV __invalidate_iterator(&_M_iter_list,__it); } 82 void _Invalidate_iterators(const iterator& __first, const iterator& __last) 83 { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); } 84 85 public: 86 // Basic accessors 87 allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); } 88 89 iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 90 iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 91 const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 92 const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 93 94 reverse_iterator rbegin() { return reverse_iterator(end()); } 95 reverse_iterator rend() { return reverse_iterator(begin()); } 96 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 97 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 98 99 reference operator[](size_type __n) { 100 _STLP_VERBOSE_ASSERT(__n < size(), _StlMsg_OUT_OF_BOUNDS) 101 return _M_non_dbg_impl[__n]; 102 } 103 const_reference operator[](size_type __n) const { 104 _STLP_VERBOSE_ASSERT(__n < size(), _StlMsg_OUT_OF_BOUNDS) 105 return _M_non_dbg_impl[__n]; 106 } 107 108 reference at(size_type __n) { return _M_non_dbg_impl.at(__n); } 109 const_reference at(size_type __n) const { return _M_non_dbg_impl.at(__n); } 110 111 reference front() { 112 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 113 return *begin(); 114 } 115 const_reference front() const { 116 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 117 return *begin(); 118 } 119 reference back() { 120 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 121 return *(--end()); 122 } 123 const_reference back() const { 124 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 125 return *(--end()); 126 } 127 128 // Constructor, destructor. 129 explicit deque(const allocator_type& __a = allocator_type()) : 130 _M_non_dbg_impl(__a), _M_iter_list(&_M_non_dbg_impl) {} 131 deque(const _Self& __x) : 132 _ConstructCheck(__x), _M_non_dbg_impl(__x._M_non_dbg_impl), 133 _M_iter_list(&_M_non_dbg_impl) {} 134 135 #if !defined(_STLP_DONT_SUP_DFLT_PARAM) 136 explicit deque(size_type __n, const value_type& __x = _Tp(), 137 #else 138 deque(size_type __n, const value_type& __x, 139 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 140 const allocator_type& __a = allocator_type()) : 141 _M_non_dbg_impl(__n, __x, __a), _M_iter_list(&_M_non_dbg_impl) {} 142 #if defined (_STLP_DONT_SUP_DFLT_PARAM) 143 explicit deque(size_type __n) : 144 _M_non_dbg_impl(__n), _M_iter_list(&_M_non_dbg_impl) {} 145 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 146 147 #if !defined (_STLP_NO_MOVE_SEMANTIC) 148 deque(__move_source<_Self> src) 149 : _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)), 150 _M_iter_list(&_M_non_dbg_impl) { 151 # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 152 src.get()._M_iter_list._Invalidate_all(); 153 # else 154 src.get()._M_iter_list._Set_owner(_M_iter_list); 155 # endif 156 } 157 #endif 158 159 #if defined (_STLP_MEMBER_TEMPLATES) 160 template <class _InputIterator> 161 deque(_InputIterator __first, _InputIterator __last, 162 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 163 : _ConstructCheck(__first, __last), 164 _M_non_dbg_impl(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last), __a), 165 _M_iter_list(&_M_non_dbg_impl) { 166 } 167 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 168 template <class _InputIterator> 169 deque(_InputIterator __first, _InputIterator __last) 170 : _ConstructCheck(__first, __last), 171 _M_non_dbg_impl(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)), 172 _M_iter_list(&_M_non_dbg_impl) { 173 } 174 # endif 175 #else 176 deque(const value_type* __first, const value_type* __last, 177 const allocator_type& __a = allocator_type()) 178 : _ConstructCheck(__first, __last), 179 _M_non_dbg_impl(__first, __last, __a), 180 _M_iter_list(&_M_non_dbg_impl) { 181 } 182 183 deque(const_iterator __first, const_iterator __last, 184 const allocator_type& __a = allocator_type()) 185 : _ConstructCheck(__first, __last), 186 _M_non_dbg_impl(__first._M_iterator, __last._M_iterator, __a), 187 _M_iter_list(&_M_non_dbg_impl) { 188 } 189 #endif 190 191 _Self& operator=(const _Self& __x) { 192 if (this != &__x) { 193 _Invalidate_all(); 194 _M_non_dbg_impl = __x._M_non_dbg_impl; 195 } 196 return *this; 197 } 198 199 bool empty() const { return _M_non_dbg_impl.empty(); } 200 size_type size() const { return _M_non_dbg_impl.size(); } 201 size_type max_size() const { return _M_non_dbg_impl.max_size(); } 202 203 void swap(_Self& __x) { 204 _M_iter_list._Swap_owners(__x._M_iter_list); 205 _M_non_dbg_impl.swap(__x._M_non_dbg_impl); 206 } 207 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 208 void _M_swap_workaround(_Self& __x) { swap(__x); } 209 #endif 210 211 public: 212 void assign(size_type __n, const _Tp& __val) { 213 _Invalidate_all(); 214 _M_non_dbg_impl.assign(__n, __val); 215 } 216 217 #if defined (_STLP_MEMBER_TEMPLATES) 218 template <class _InputIterator> 219 void assign(_InputIterator __first, _InputIterator __last) { 220 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 221 _Invalidate_all(); 222 _M_non_dbg_impl.assign(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 223 } 224 #else 225 void assign(const_iterator __first, const_iterator __last) { 226 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 227 _Invalidate_all(); 228 _M_non_dbg_impl.assign(__first._M_iterator, __last._M_iterator); 229 } 230 void assign(const value_type *__first, const value_type *__last) { 231 _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last)) 232 _Invalidate_all(); 233 _M_non_dbg_impl.assign(__first, __last); 234 } 235 #endif 236 237 public: // push_* and pop_* 238 239 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 240 void push_back(const value_type& __t = _Tp()) { 241 #else 242 void push_back(const value_type& __t) { 243 #endif 244 _Invalidate_all(); 245 _M_non_dbg_impl.push_back(__t); 246 } 247 248 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 249 void push_back() { 250 _Invalidate_all(); 251 _M_non_dbg_impl.push_back(); 252 } 253 #endif 254 255 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 256 void push_front(const value_type& __t = _Tp()) { 257 #else 258 void push_front(const value_type& __t) { 259 #endif 260 _Invalidate_all(); 261 _M_non_dbg_impl.push_front(__t); 262 } 263 264 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 265 void push_front() { 266 _Invalidate_all(); 267 _M_non_dbg_impl.push_front(); 268 } 269 #endif 270 271 void pop_back() { 272 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 273 _Invalidate_iterator(end()); 274 _M_non_dbg_impl.pop_back(); 275 } 276 277 void pop_front() { 278 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 279 _Invalidate_iterator(begin()); 280 _M_non_dbg_impl.pop_front(); 281 } 282 283 public: // Insert 284 285 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 286 iterator insert(iterator __pos, const value_type& __x = _Tp()) { 287 #else 288 iterator insert(iterator __pos, const value_type& __x) { 289 #endif 290 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 291 _Invalidate_all(); 292 return iterator(&_M_iter_list, _M_non_dbg_impl.insert(__pos._M_iterator, __x)); 293 } 294 295 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 296 iterator insert(iterator __pos) { 297 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 298 _Invalidate_all(); 299 return iterator(&_M_iter_list, _M_non_dbg_impl.insert(__pos._M_iterator)); 300 } 301 #endif 302 303 void insert(iterator __pos, size_type __n, const value_type& __x) { 304 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 305 if (__n != 0) _Invalidate_all(); 306 _M_non_dbg_impl.insert(__pos._M_iterator, __n, __x); 307 } 308 309 #if defined (_STLP_MEMBER_TEMPLATES) 310 template <class _InputIterator> 311 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { 312 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 313 // We perform invalidate first to detect self referencing in __check_range as __first and __last 314 // will have been invalidated. 315 if (__first != __last) _Invalidate_all(); 316 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 317 _M_non_dbg_impl.insert(__pos._M_iterator, 318 _STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 319 } 320 #endif 321 322 #if !defined (_STLP_MEMBER_TEMPLATES) 323 void insert(iterator __pos, 324 const value_type* __first, const value_type* __last) { 325 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 326 _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last)) 327 if (__first != __last) _Invalidate_all(); 328 _M_non_dbg_impl.insert(__pos._M_iterator, __first, __last); 329 } 330 #endif 331 332 #if !defined (_STLP_MEMBER_TEMPLATES) || !defined (_STLP_NO_METHOD_SPECIALIZATION) 333 void insert(iterator __pos, 334 const_iterator __first, const_iterator __last) { 335 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 336 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 337 //Sequence requirements 23.1.1 Table 67: 338 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_not_owner(&_M_iter_list, __first)); 339 if (__first != __last) _Invalidate_all(); 340 _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator); 341 } 342 343 void insert(iterator __pos, 344 iterator __first, iterator __last) { 345 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 346 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 347 //Sequence requirements 23.1.1 Table 67: 348 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_not_owner(&_M_iter_list, __first)); 349 if (__first != __last) _Invalidate_all(); 350 _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator); 351 } 352 #endif 353 354 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 355 void resize(size_type __new_size, const value_type& __x = _Tp()) { 356 #else 357 void resize(size_type __new_size, const value_type& __x) { 358 #endif 359 if (__new_size != size()) { 360 if ((__new_size > size()) || (__new_size < size() - 1)) 361 _Invalidate_all(); 362 else 363 _Invalidate_iterator(end()); 364 } 365 _M_non_dbg_impl.resize(__new_size, __x); 366 } 367 368 #if defined (_STLP_DONT_SUP_DFLT_PARAM) 369 void resize(size_type new_size) { resize(new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); } 370 #endif 371 372 // Erase 373 iterator erase(iterator __pos) { 374 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 375 _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__pos)) 376 if (__pos._M_iterator == _M_non_dbg_impl.begin()) { 377 _Invalidate_iterator(__pos); 378 } else { 379 typename _Base::iterator tmp = --(_M_non_dbg_impl.end()); 380 if (__pos._M_iterator == tmp) 381 _Invalidate_iterator(__pos); 382 else 383 _Invalidate_all(); 384 } 385 return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__pos._M_iterator)); 386 } 387 388 iterator erase(iterator __first, iterator __last) { 389 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last, begin(), end())) 390 if (!empty()) { 391 if (__first._M_iterator == _M_non_dbg_impl.begin() || 392 __last._M_iterator == _M_non_dbg_impl.end()) 393 _Invalidate_iterators(__first, __last); 394 else 395 _Invalidate_all(); 396 } 397 return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator)); 398 } 399 400 void clear() { 401 _Invalidate_all(); 402 _M_non_dbg_impl.clear(); 403 } 404 }; 405 406 _STLP_END_NAMESPACE 407 408 #undef _STLP_NON_DBG_DEQUE 409 410 #endif /* _STLP_INTERNAL_DEQUE_H */ 411 412 // Local Variables: 413 // mode:C++ 414 // End: 415
