libstdc++
safe_iterator.tcc
Go to the documentation of this file.
1// Debugging iterator implementation (out of line) -*- C++ -*-
2
3// Copyright (C) 2003-2020 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/safe_iterator.tcc
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC
30#define _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC 1
31
32#include <bits/stl_algobase.h>
33
34namespace __gnu_debug
35{
36 template<typename _Iterator, typename _Sequence, typename _Category>
37 typename _Distance_traits<_Iterator>::__type
38 _Safe_iterator<_Iterator, _Sequence, _Category>::
39 _M_get_distance_from_begin() const
40 {
41 typedef _Sequence_traits<_Sequence> _SeqTraits;
42
43 // No need to consider before_begin as this function is only used in
44 // _M_can_advance which won't be used for forward_list iterators.
45 if (_M_is_begin())
46 return std::make_pair(0, __dp_exact);
47
48 if (_M_is_end())
49 return _SeqTraits::_S_size(*_M_get_sequence());
50
51 typename _Distance_traits<_Iterator>::__type __res
52 = __get_distance(_M_get_sequence()->_M_base().begin(), base());
53
54 if (__res.second == __dp_equality)
55 return std::make_pair(1, __dp_sign);
56
57 return __res;
58 }
59
60 template<typename _Iterator, typename _Sequence, typename _Category>
61 typename _Distance_traits<_Iterator>::__type
62 _Safe_iterator<_Iterator, _Sequence, _Category>::
63 _M_get_distance_to_end() const
64 {
65 typedef _Sequence_traits<_Sequence> _SeqTraits;
66
67 // No need to consider before_begin as this function is only used in
68 // _M_can_advance which won't be used for forward_list iterators.
69 if (_M_is_begin())
70 return _SeqTraits::_S_size(*_M_get_sequence());
71
72 if (_M_is_end())
73 return std::make_pair(0, __dp_exact);
74
75 typename _Distance_traits<_Iterator>::__type __res
76 = __get_distance(base(), _M_get_sequence()->_M_base().end());
77
78 if (__res.second == __dp_equality)
79 return std::make_pair(1, __dp_sign);
80
81 return __res;
82 }
83
84 template<typename _Iterator, typename _Sequence, typename _Category>
85 bool
86 _Safe_iterator<_Iterator, _Sequence, _Category>::
87 _M_can_advance(difference_type __n, bool __strict) const
88 {
89 if (this->_M_singular())
90 return false;
91
92 if (__n == 0)
93 return true;
94
96 ? _M_get_distance_from_begin()
97 : _M_get_distance_to_end();
98
99 if (__n < 0)
100 __n = -__n;
101
102 return __dist.second > __dp_sign
103 ? __dist.first >= __n
104 : !__strict && __dist.first > 0;
105 }
106
107 template<typename _Iterator, typename _Sequence, typename _Category>
108 template<typename _Diff>
109 bool
110 _Safe_iterator<_Iterator, _Sequence, _Category>::
111 _M_can_advance(const std::pair<_Diff, _Distance_precision>& __dist,
112 int __way) const
113 {
114 return __dist.second == __dp_exact
115 ? _M_can_advance(__way * __dist.first)
116 : _M_can_advance(__way * (__dist.first == 0
117 ? 0
118 : __dist.first < 0 ? -1 : 1));
119 }
120
121 template<typename _Iterator, typename _Sequence, typename _Category>
122 typename _Distance_traits<_Iterator>::__type
123 _Safe_iterator<_Iterator, _Sequence, _Category>::
124 _M_get_distance_to(const _Safe_iterator& __rhs) const
125 {
126 typedef typename _Distance_traits<_Iterator>::__type _Dist;
127 typedef _Sequence_traits<_Sequence> _SeqTraits;
128
129 _Dist __base_dist = __get_distance(this->base(), __rhs.base());
130 if (__base_dist.second == __dp_exact)
131 return __base_dist;
132
133 _Dist __seq_dist = _SeqTraits::_S_size(*this->_M_get_sequence());
134 if (this->_M_is_before_begin())
135 {
136 if (__rhs._M_is_begin())
137 return std::make_pair(1, __dp_exact);
138
139 return __seq_dist.second == __dp_exact
140 ? std::make_pair(__seq_dist.first + 1, __dp_exact)
141 : __seq_dist;
142 }
143
144 if (this->_M_is_begin())
145 {
146 if (__rhs._M_is_before_begin())
147 return std::make_pair(-1, __dp_exact);
148
149 if (__rhs._M_is_end())
150 return __seq_dist;
151
152 return std::make_pair(__seq_dist.first,
153 __seq_dist.second == __dp_exact
154 ? __dp_sign_max_size : __seq_dist.second);
155 }
156
157 if (this->_M_is_end())
158 {
159 if (__rhs._M_is_before_begin())
160 return __seq_dist.second == __dp_exact
161 ? std::make_pair(-__seq_dist.first - 1, __dp_exact)
162 : std::make_pair(-__seq_dist.first, __dp_sign);
163
164 if (__rhs._M_is_begin())
165 return std::make_pair(-__seq_dist.first, __seq_dist.second);
166
167 return std::make_pair(-__seq_dist.first,
168 __seq_dist.second == __dp_exact
169 ? __dp_sign_max_size : __seq_dist.second);
170 }
171
172 if (__rhs._M_is_before_begin())
173 return __seq_dist.second == __dp_exact
174 ? std::make_pair(__seq_dist.first - 1, __dp_exact)
175 : std::make_pair(-__seq_dist.first, __dp_sign);
176
177 if (__rhs._M_is_begin())
178 return std::make_pair(-__seq_dist.first,
179 __seq_dist.second == __dp_exact
180 ? __dp_sign_max_size : __seq_dist.second);
181
182 if (__rhs._M_is_end())
183 return std::make_pair(__seq_dist.first,
184 __seq_dist.second == __dp_exact
185 ? __dp_sign_max_size : __seq_dist.second);
186
187 return std::make_pair(1, __dp_equality);
188 }
189
190 template<typename _Iterator, typename _Sequence, typename _Category>
191 bool
192 _Safe_iterator<_Iterator, _Sequence, _Category>::
193 _M_valid_range(const _Safe_iterator& __rhs,
195 bool __check_dereferenceable) const
196 {
197 if (!_M_can_compare(__rhs))
198 return false;
199
200 /* Determine iterators order */
201 __dist = _M_get_distance_to(__rhs);
202 if (__dist.second != __dp_equality)
203 {
204 // If range is not empty first iterator must be dereferenceable.
205 return __dist.first == 0
206 || (__dist.first > 0
207 && (!__check_dereferenceable || _M_dereferenceable()));
208 }
209
210 // Assume that this is a valid range; we can't check anything else.
211 return true;
212 }
213
214 template<typename _Iterator, typename _Sequence>
215 bool
216 _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>::
217 _M_valid_range(const _Safe_iterator& __rhs,
218 std::pair<difference_type,
219 _Distance_precision>& __dist) const
220 {
221 if (!this->_M_can_compare(__rhs))
222 return false;
223
224 /* Determine iterators order */
225 __dist = std::make_pair(__rhs.base() - this->base(), __dp_exact);
226
227 // If range is not empty first iterator must be dereferenceable.
228 return __dist.first == 0
229 || (__dist.first > 0 && this->_M_dereferenceable());
230 }
231} // namespace __gnu_debug
232
233namespace std _GLIBCXX_VISIBILITY(default)
234{
235_GLIBCXX_BEGIN_NAMESPACE_VERSION
236
237 template<bool _IsMove,
238 typename _Ite, typename _Seq, typename _Cat, typename _OI>
239 _OI
240 __copy_move_a(
241 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
242 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
243 _OI __result)
244 {
245 typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
246 __glibcxx_check_valid_range2(__first, __last, __dist);
247 __glibcxx_check_can_increment_dist(__result, __dist, 1);
248
249 if (__dist.second > ::__gnu_debug::__dp_equality)
250 return std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
251 __result);
252
253 return std::__copy_move_a1<_IsMove>(__first, __last, __result);
254 }
255
256 template<bool _IsMove,
257 typename _II, typename _Ite, typename _Seq, typename _Cat>
259 __copy_move_a(_II __first, _II __last,
260 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result)
261 {
262 typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
263 __glibcxx_check_valid_range2(__first, __last, __dist);
264 __glibcxx_check_can_increment_dist(__result, __dist, 1);
265
266 if (__dist.second > ::__gnu_debug::__dp_sign
267 && __result._M_can_advance(__dist.first, true))
268 return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
269 std::__copy_move_a<_IsMove>(__first, __last, __result.base()),
270 __result._M_sequence);
271
272 return std::__copy_move_a1<_IsMove>(__first, __last, __result);
273 }
274
275 template<bool _IsMove,
276 typename _IIte, typename _ISeq, typename _ICat,
277 typename _OIte, typename _OSeq, typename _OCat>
279 __copy_move_a(
280 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first,
281 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last,
282 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result)
283 {
284 typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist;
285 __glibcxx_check_valid_range2(__first, __last, __dist);
286 __glibcxx_check_can_increment_dist(__result, __dist, 1);
287
288 if (__dist.second > ::__gnu_debug::__dp_equality)
289 {
290 if (__dist.second > ::__gnu_debug::__dp_sign
291 && __result._M_can_advance(__dist.first, true))
292 return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>(
293 std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
294 __result.base()),
295 __result._M_sequence);
296
297 return std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
298 __result);
299 }
300
301 return std::__copy_move_a1<_IsMove>(__first, __last, __result);
302 }
303
304 template<bool _IsMove,
305 typename _Ite, typename _Seq, typename _Cat, typename _OI>
306 _OI
307 __copy_move_backward_a(
308 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
309 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
310 _OI __result)
311 {
312 typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
313 __glibcxx_check_valid_range2(__first, __last, __dist);
314 __glibcxx_check_can_increment_dist(__result, __dist, -1);
315
316 if (__dist.second > ::__gnu_debug::__dp_equality)
317 return std::__copy_move_backward_a<_IsMove>(
318 __first.base(), __last.base(), __result);
319
320 return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
321 }
322
323 template<bool _IsMove,
324 typename _II, typename _Ite, typename _Seq, typename _Cat>
326 __copy_move_backward_a(_II __first, _II __last,
327 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result)
328 {
329 typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
330 __glibcxx_check_valid_range2(__first, __last, __dist);
331 __glibcxx_check_can_increment_dist(__result, __dist, -1);
332
333 if (__dist.second > ::__gnu_debug::__dp_sign
334 && __result._M_can_advance(-__dist.first, true))
335 return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
336 std::__copy_move_backward_a<_IsMove>(__first, __last,
337 __result.base()),
338 __result._M_sequence);
339
340 return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
341 }
342
343 template<bool _IsMove,
344 typename _IIte, typename _ISeq, typename _ICat,
345 typename _OIte, typename _OSeq, typename _OCat>
347 __copy_move_backward_a(
348 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first,
349 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last,
350 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result)
351 {
352 typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist;
353 __glibcxx_check_valid_range2(__first, __last, __dist);
354 __glibcxx_check_can_increment_dist(__result, __dist, -1);
355
356 if (__dist.second > ::__gnu_debug::__dp_equality)
357 {
358 if (__dist.second > ::__gnu_debug::__dp_sign
359 && __result._M_can_advance(-__dist.first, true))
360 return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>(
361 std::__copy_move_backward_a<_IsMove>(__first.base(), __last.base(),
362 __result.base()),
363 __result._M_sequence);
364
365 return std::__copy_move_backward_a<_IsMove>(
366 __first.base(), __last.base(), __result);
367 }
368
369 return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
370 }
371
372 template<typename _Ite, typename _Seq, typename _Cat, typename _Tp>
373 void
374 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
375 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
376 const _Tp& __value)
377 {
378 typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
379 __glibcxx_check_valid_range2(__first, __last, __dist);
380
381 if (__dist.second > ::__gnu_debug::__dp_equality)
382 std::__fill_a(__first.base(), __last.base(), __value);
383
384 std::__fill_a1(__first, __last, __value);
385 }
386
387 template<typename _Ite, typename _Seq, typename _Cat, typename _Size,
388 typename _Tp>
390 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
391 _Size __n, const _Tp& __value,
393 {
394#if __cplusplus >= 201103L
395 static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
396#endif
397
398 if (__n <= 0)
399 return __first;
400
401 __glibcxx_check_can_increment(__first, __n);
402 if (__first._M_can_advance(__n, true))
403 return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
404 std::__fill_n_a(__first.base(), __n, __value, _Cat()),
405 __first._M_sequence);
406
407 return std::__fill_n_a1(__first, __n, __value);
408 }
409
410 template<typename _II1, typename _Seq1, typename _Cat1, typename _II2>
411 bool
412 __equal_aux(
413 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1,
414 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1,
415 _II2 __first2)
416 {
417 typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
418 __glibcxx_check_valid_range2(__first1, __last1, __dist);
419 __glibcxx_check_can_increment_dist(__first2, __dist, 1);
420
421 if (__dist.second > ::__gnu_debug::__dp_equality)
422 return std::__equal_aux(__first1.base(), __last1.base(), __first2);
423
424 return std::__equal_aux1(__first1, __last1, __first2);
425 }
426
427 template<typename _II1, typename _II2, typename _Seq2, typename _Cat2>
428 bool
429 __equal_aux(_II1 __first1, _II1 __last1,
430 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2)
431 {
432 typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
433 __glibcxx_check_valid_range2(__first1, __last1, __dist);
434 __glibcxx_check_can_increment_dist(__first2, __dist, 1);
435
436 if (__dist.second > ::__gnu_debug::__dp_sign
437 && __first2._M_can_advance(__dist.first, true))
438 return std::__equal_aux(__first1, __last1, __first2.base());
439
440 return std::__equal_aux1(__first1, __last1, __first2);
441 }
442
443 template<typename _II1, typename _Seq1, typename _Cat1,
444 typename _II2, typename _Seq2, typename _Cat2>
445 bool
446 __equal_aux(
447 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1,
448 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1,
449 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2)
450 {
451 typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
452 __glibcxx_check_valid_range2(__first1, __last1, __dist);
453 __glibcxx_check_can_increment_dist(__first2, __dist, 1);
454
455 if (__dist.second > ::__gnu_debug::__dp_equality)
456 {
457 if (__dist.second > ::__gnu_debug::__dp_sign &&
458 __first2._M_can_advance(__dist.first, true))
459 return std::__equal_aux(__first1.base(), __last1.base(),
460 __first2.base());
461 return std::__equal_aux(__first1.base(), __last1.base(), __first2);
462 }
463
464 return __equal_aux1(__first1, __last1, __first2);
465 }
466
467_GLIBCXX_END_NAMESPACE_VERSION
468} // namespace std
469
470#endif
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
ISO C++ entities toplevel namespace is std.
GNU debug classes for public use.
constexpr _Distance_traits< _Iterator >::__type __get_distance(_Iterator __lhs, _Iterator __rhs, std::random_access_iterator_tag)
Marking input iterators.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
_T1 first
The first member.
Definition: stl_pair.h:217
_T2 second
The second member.
Definition: stl_pair.h:218
Safe iterator wrapper.