OSDN Git Service

2011-10-01 Fran├žois Dumont <fdumont@gcc.gnu.org>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / debug / deque
1 // Debugging deque implementation -*- C++ -*-
2
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 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/deque
27  *  This file is a GNU debug extension to the Standard C++ Library.
28  */
29
30 #ifndef _GLIBCXX_DEBUG_DEQUE
31 #define _GLIBCXX_DEBUG_DEQUE 1
32
33 #include <deque>
34 #include <debug/safe_sequence.h>
35 #include <debug/safe_iterator.h>
36
37 namespace std _GLIBCXX_VISIBILITY(default)
38 {
39 namespace __debug
40 {
41   /// Class std::deque with safety/checking/debug instrumentation.
42   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
43     class deque
44     : public _GLIBCXX_STD_C::deque<_Tp, _Allocator>,
45       public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
46     {
47       typedef  _GLIBCXX_STD_C::deque<_Tp, _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       typedef typename _Base::reference             reference;
54       typedef typename _Base::const_reference       const_reference;
55
56       typedef __gnu_debug::_Safe_iterator<_Base_iterator,deque>
57                                                     iterator;
58       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,deque>
59                                                     const_iterator;
60
61       typedef typename _Base::size_type             size_type;
62       typedef typename _Base::difference_type       difference_type;
63
64       typedef _Tp                                   value_type;
65       typedef _Allocator                            allocator_type;
66       typedef typename _Base::pointer               pointer;
67       typedef typename _Base::const_pointer         const_pointer;
68       typedef std::reverse_iterator<iterator>       reverse_iterator;
69       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
70
71       // 23.2.1.1 construct/copy/destroy:
72       explicit
73       deque(const _Allocator& __a = _Allocator())
74       : _Base(__a) { }
75
76 #ifdef __GXX_EXPERIMENTAL_CXX0X__
77       explicit
78       deque(size_type __n)
79       : _Base(__n) { }
80
81       deque(size_type __n, const _Tp& __value,
82             const _Allocator& __a = _Allocator())
83       : _Base(__n, __value, __a) { }
84 #else
85       explicit
86       deque(size_type __n, const _Tp& __value = _Tp(),
87             const _Allocator& __a = _Allocator())
88       : _Base(__n, __value, __a) { }
89 #endif
90
91       template<class _InputIterator>
92         deque(_InputIterator __first, _InputIterator __last,
93               const _Allocator& __a = _Allocator())
94         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
95                                                                      __last)),
96                 __gnu_debug::__base(__last), __a)
97         { }
98
99       deque(const deque& __x)
100       : _Base(__x) { }
101
102       deque(const _Base& __x)
103       : _Base(__x) { }
104
105 #ifdef __GXX_EXPERIMENTAL_CXX0X__
106       deque(deque&& __x)
107       : _Base(std::move(__x))
108       { this->_M_swap(__x); }
109
110       deque(initializer_list<value_type> __l,
111             const allocator_type& __a = allocator_type())
112       : _Base(__l, __a) { }
113 #endif
114
115       ~deque() _GLIBCXX_NOEXCEPT { }
116
117       deque&
118       operator=(const deque& __x)
119       {
120         *static_cast<_Base*>(this) = __x;
121         this->_M_invalidate_all();
122         return *this;
123       }
124
125 #ifdef __GXX_EXPERIMENTAL_CXX0X__
126       deque&
127       operator=(deque&& __x)
128       {
129         // NB: DR 1204.
130         // NB: DR 675.
131         clear();
132         swap(__x);
133         return *this;
134       }
135
136       deque&
137       operator=(initializer_list<value_type> __l)
138       {
139         *static_cast<_Base*>(this) = __l;
140         this->_M_invalidate_all();
141         return *this;
142       }
143 #endif
144
145       template<class _InputIterator>
146         void
147         assign(_InputIterator __first, _InputIterator __last)
148         {
149           __glibcxx_check_valid_range(__first, __last);
150           _Base::assign(__gnu_debug::__base(__first),
151                         __gnu_debug::__base(__last));
152           this->_M_invalidate_all();
153         }
154
155       void
156       assign(size_type __n, const _Tp& __t)
157       {
158         _Base::assign(__n, __t);
159         this->_M_invalidate_all();
160       }
161
162 #ifdef __GXX_EXPERIMENTAL_CXX0X__
163       void
164       assign(initializer_list<value_type> __l)
165       {
166         _Base::assign(__l);
167         this->_M_invalidate_all();
168       }
169 #endif
170
171       using _Base::get_allocator;
172
173       // iterators:
174       iterator
175       begin() _GLIBCXX_NOEXCEPT
176       { return iterator(_Base::begin(), this); }
177
178       const_iterator
179       begin() const _GLIBCXX_NOEXCEPT
180       { return const_iterator(_Base::begin(), this); }
181
182       iterator
183       end() _GLIBCXX_NOEXCEPT
184       { return iterator(_Base::end(), this); }
185
186       const_iterator
187       end() const _GLIBCXX_NOEXCEPT
188       { return const_iterator(_Base::end(), this); }
189
190       reverse_iterator
191       rbegin() _GLIBCXX_NOEXCEPT
192       { return reverse_iterator(end()); }
193
194       const_reverse_iterator
195       rbegin() const _GLIBCXX_NOEXCEPT
196       { return const_reverse_iterator(end()); }
197
198       reverse_iterator
199       rend() _GLIBCXX_NOEXCEPT
200       { return reverse_iterator(begin()); }
201
202       const_reverse_iterator
203       rend() const _GLIBCXX_NOEXCEPT
204       { return const_reverse_iterator(begin()); }
205
206 #ifdef __GXX_EXPERIMENTAL_CXX0X__
207       const_iterator
208       cbegin() const noexcept
209       { return const_iterator(_Base::begin(), this); }
210
211       const_iterator
212       cend() const noexcept
213       { return const_iterator(_Base::end(), this); }
214
215       const_reverse_iterator
216       crbegin() const noexcept
217       { return const_reverse_iterator(end()); }
218
219       const_reverse_iterator
220       crend() const noexcept
221       { return const_reverse_iterator(begin()); }
222 #endif
223
224     private:
225       void
226       _M_invalidate_after_nth(difference_type __n)
227       {
228         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
229         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
230       }
231       
232     public:
233       // 23.2.1.2 capacity:
234       using _Base::size;
235       using _Base::max_size;
236
237 #ifdef __GXX_EXPERIMENTAL_CXX0X__
238       void
239       resize(size_type __sz)
240       {
241         bool __invalidate_all = __sz > this->size();
242         if (__sz < this->size())
243           this->_M_invalidate_after_nth(__sz);
244
245         _Base::resize(__sz);
246
247         if (__invalidate_all)
248           this->_M_invalidate_all();
249       }
250
251       void
252       resize(size_type __sz, const _Tp& __c)
253       {
254         bool __invalidate_all = __sz > this->size();
255         if (__sz < this->size())
256           this->_M_invalidate_after_nth(__sz);
257
258         _Base::resize(__sz, __c);
259
260         if (__invalidate_all)
261           this->_M_invalidate_all();
262       }
263 #else
264       void
265       resize(size_type __sz, _Tp __c = _Tp())
266       {
267         bool __invalidate_all = __sz > this->size();
268         if (__sz < this->size())
269           this->_M_invalidate_after_nth(__sz);
270
271         _Base::resize(__sz, __c);
272
273         if (__invalidate_all)
274           this->_M_invalidate_all();
275       }
276 #endif
277
278 #ifdef __GXX_EXPERIMENTAL_CXX0X__
279       void
280       shrink_to_fit()
281       {
282         if (_Base::_M_shrink_to_fit())
283           this->_M_invalidate_all();
284       }
285 #endif
286
287       using _Base::empty;
288
289       // element access:
290       reference
291       operator[](size_type __n)
292       {
293         __glibcxx_check_subscript(__n);
294         return _M_base()[__n];
295       }
296
297       const_reference
298       operator[](size_type __n) const
299       {
300         __glibcxx_check_subscript(__n);
301         return _M_base()[__n];
302       }
303
304       using _Base::at;
305
306       reference
307       front()
308       {
309         __glibcxx_check_nonempty();
310         return _Base::front();
311       }
312
313       const_reference
314       front() const
315       {
316         __glibcxx_check_nonempty();
317         return _Base::front();
318       }
319
320       reference
321       back()
322       {
323         __glibcxx_check_nonempty();
324         return _Base::back();
325       }
326
327       const_reference
328       back() const
329       {
330         __glibcxx_check_nonempty();
331         return _Base::back();
332       }
333
334       // 23.2.1.3 modifiers:
335       void
336       push_front(const _Tp& __x)
337       {
338         _Base::push_front(__x);
339         this->_M_invalidate_all();
340       }
341
342       void
343       push_back(const _Tp& __x)
344       {
345         _Base::push_back(__x);
346         this->_M_invalidate_all();
347       }
348
349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
350       void
351       push_front(_Tp&& __x)
352       { emplace_front(std::move(__x)); }
353
354       void
355       push_back(_Tp&& __x)
356       { emplace_back(std::move(__x)); }
357
358       template<typename... _Args>
359         void
360         emplace_front(_Args&&... __args)
361         {
362           _Base::emplace_front(std::forward<_Args>(__args)...);
363           this->_M_invalidate_all();
364         }
365
366       template<typename... _Args>
367         void
368         emplace_back(_Args&&... __args)
369         {
370           _Base::emplace_back(std::forward<_Args>(__args)...);
371           this->_M_invalidate_all();
372         }
373
374       template<typename... _Args>
375         iterator
376         emplace(iterator __position, _Args&&... __args)
377         {
378           __glibcxx_check_insert(__position);
379           _Base_iterator __res = _Base::emplace(__position.base(),
380                                                 std::forward<_Args>(__args)...);
381           this->_M_invalidate_all();
382           return iterator(__res, this);
383         }
384 #endif
385
386       iterator
387       insert(iterator __position, const _Tp& __x)
388       {
389         __glibcxx_check_insert(__position);
390         _Base_iterator __res = _Base::insert(__position.base(), __x);
391         this->_M_invalidate_all();
392         return iterator(__res, this);
393       }
394
395 #ifdef __GXX_EXPERIMENTAL_CXX0X__
396       iterator
397       insert(iterator __position, _Tp&& __x)
398       { return emplace(__position, std::move(__x)); }
399
400       void
401       insert(iterator __p, initializer_list<value_type> __l)
402       {
403         _Base::insert(__p, __l);
404         this->_M_invalidate_all();
405       }
406 #endif
407
408       void
409       insert(iterator __position, size_type __n, const _Tp& __x)
410       {
411         __glibcxx_check_insert(__position);
412         _Base::insert(__position.base(), __n, __x);
413         this->_M_invalidate_all();
414       }
415
416       template<class _InputIterator>
417         void
418         insert(iterator __position,
419                _InputIterator __first, _InputIterator __last)
420         {
421           __glibcxx_check_insert_range(__position, __first, __last);
422           _Base::insert(__position.base(), __gnu_debug::__base(__first),
423                                            __gnu_debug::__base(__last));
424           this->_M_invalidate_all();
425         }
426
427       void
428       pop_front()
429       {
430         __glibcxx_check_nonempty();
431         this->_M_invalidate_if(_Equal(_Base::begin()));
432         _Base::pop_front();
433       }
434
435       void
436       pop_back()
437       {
438         __glibcxx_check_nonempty();
439         this->_M_invalidate_if(_Equal(--_Base::end()));
440         _Base::pop_back();
441       }
442
443       iterator
444       erase(iterator __position)
445       {
446         __glibcxx_check_erase(__position);
447         _Base_iterator __victim = __position.base();
448         if (__victim == _Base::begin() || __victim == _Base::end()-1)
449           {
450             this->_M_invalidate_if(_Equal(__victim));
451             return iterator(_Base::erase(__victim), this);
452           }
453         else
454           {
455             _Base_iterator __res = _Base::erase(__victim);
456             this->_M_invalidate_all();
457             return iterator(__res, this);
458           }
459       }
460
461       iterator
462       erase(iterator __first, iterator __last)
463       {
464         // _GLIBCXX_RESOLVE_LIB_DEFECTS
465         // 151. can't currently clear() empty container
466         __glibcxx_check_erase_range(__first, __last);
467
468         if (__first.base() == __last.base())
469           return __first;
470         else if (__first.base() == _Base::begin()
471                  || __last.base() == _Base::end())
472           {
473             this->_M_detach_singular();
474             for (_Base_iterator __position = __first.base();
475                  __position != __last.base(); ++__position)
476               {
477                 this->_M_invalidate_if(_Equal(__position));
478               }
479             __try
480               {
481                 return iterator(_Base::erase(__first.base(), __last.base()),
482                                 this);
483               }
484             __catch(...)
485               {
486                 this->_M_revalidate_singular();
487                 __throw_exception_again;
488               }
489           }
490         else
491           {
492             _Base_iterator __res = _Base::erase(__first.base(),
493                                                 __last.base());
494             this->_M_invalidate_all();
495             return iterator(__res, this);
496           }
497       }
498
499       void
500       swap(deque& __x)
501       {
502         _Base::swap(__x);
503         this->_M_swap(__x);
504       }
505
506       void
507       clear() _GLIBCXX_NOEXCEPT
508       {
509         _Base::clear();
510         this->_M_invalidate_all();
511       }
512
513       _Base&
514       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
515
516       const _Base&
517       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
518     };
519
520   template<typename _Tp, typename _Alloc>
521     inline bool
522     operator==(const deque<_Tp, _Alloc>& __lhs,
523                const deque<_Tp, _Alloc>& __rhs)
524     { return __lhs._M_base() == __rhs._M_base(); }
525
526   template<typename _Tp, typename _Alloc>
527     inline bool
528     operator!=(const deque<_Tp, _Alloc>& __lhs,
529                const deque<_Tp, _Alloc>& __rhs)
530     { return __lhs._M_base() != __rhs._M_base(); }
531
532   template<typename _Tp, typename _Alloc>
533     inline bool
534     operator<(const deque<_Tp, _Alloc>& __lhs,
535               const deque<_Tp, _Alloc>& __rhs)
536     { return __lhs._M_base() < __rhs._M_base(); }
537
538   template<typename _Tp, typename _Alloc>
539     inline bool
540     operator<=(const deque<_Tp, _Alloc>& __lhs,
541                const deque<_Tp, _Alloc>& __rhs)
542     { return __lhs._M_base() <= __rhs._M_base(); }
543
544   template<typename _Tp, typename _Alloc>
545     inline bool
546     operator>=(const deque<_Tp, _Alloc>& __lhs,
547                const deque<_Tp, _Alloc>& __rhs)
548     { return __lhs._M_base() >= __rhs._M_base(); }
549
550   template<typename _Tp, typename _Alloc>
551     inline bool
552     operator>(const deque<_Tp, _Alloc>& __lhs,
553               const deque<_Tp, _Alloc>& __rhs)
554     { return __lhs._M_base() > __rhs._M_base(); }
555
556   template<typename _Tp, typename _Alloc>
557     inline void
558     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
559     { __lhs.swap(__rhs); }
560
561 } // namespace __debug
562 } // namespace std
563
564 #endif