list revision 132720 
1// Debugging list implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004
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 2, 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// You should have received a copy of the GNU General Public License along
18// with this library; see the file COPYING.  If not, write to the Free
19// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
20// USA.
21
22// As a special exception, you may use this file as part of a free software
23// library without restriction.  Specifically, if other files instantiate
24// templates or use macros or inline functions from this file, or you compile
25// this file and link it with other files to produce an executable, this
26// file does not by itself cause the resulting executable to be covered by
27// the GNU General Public License.  This exception does not however
28// invalidate any other reasons why the executable file might be covered by
29// the GNU General Public License.
30
31#ifndef _GLIBCXX_DEBUG_LIST
32#define _GLIBCXX_DEBUG_LIST 1
33
34#include <list>
35#include <bits/stl_algo.h>
36#include <debug/safe_sequence.h>
37#include <debug/safe_iterator.h>
38
39namespace __gnu_debug_def
40{
41  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
42    class list
43    : public _GLIBCXX_STD::list<_Tp, _Allocator>,
44      public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
45    {
46      typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base;
47      typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
48
49    public:
50      typedef typename _Allocator::reference        reference;
51      typedef typename _Allocator::const_reference  const_reference;
52
53      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
54						    iterator;
55      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
56						    const_iterator;
57
58      typedef typename _Base::size_type             size_type;
59      typedef typename _Base::difference_type       difference_type;
60
61      typedef _Tp				    value_type;
62      typedef _Allocator			    allocator_type;
63      typedef typename _Allocator::pointer          pointer;
64      typedef typename _Allocator::const_pointer    const_pointer;
65      typedef std::reverse_iterator<iterator>       reverse_iterator;
66      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
67
68      // 23.2.2.1 construct/copy/destroy:
69      explicit list(const _Allocator& __a = _Allocator())
70      : _Base(__a) { }
71
72      explicit list(size_type __n, const _Tp& __value = _Tp(),
73		    const _Allocator& __a = _Allocator())
74      : _Base(__n, __value, __a) { }
75
76      template<class _InputIterator>
77      list(_InputIterator __first, _InputIterator __last,
78	   const _Allocator& __a = _Allocator())
79      : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
80      { }
81
82
83      list(const list& __x) : _Base(__x), _Safe_base() { }
84
85      list(const _Base& __x) : _Base(__x), _Safe_base() { }
86
87      ~list() { }
88
89      list&
90      operator=(const list& __x)
91      {
92	static_cast<_Base&>(*this) = __x;
93	this->_M_invalidate_all();
94	return *this;
95      }
96
97      template<class _InputIterator>
98        void
99        assign(_InputIterator __first, _InputIterator __last)
100        {
101	  __glibcxx_check_valid_range(__first, __last);
102	  _Base::assign(__first, __last);
103	  this->_M_invalidate_all();
104	}
105
106      void
107      assign(size_type __n, const _Tp& __t)
108      {
109	_Base::assign(__n, __t);
110	this->_M_invalidate_all();
111      }
112
113      using _Base::get_allocator;
114
115      // iterators:
116      iterator
117      begin()
118      { return iterator(_Base::begin(), this); }
119
120      const_iterator
121      begin() const
122      { return const_iterator(_Base::begin(), this); }
123
124      iterator
125      end()
126      { return iterator(_Base::end(), this); }
127
128      const_iterator
129      end() const
130      { return const_iterator(_Base::end(), this); }
131
132      reverse_iterator
133      rbegin()
134      { return reverse_iterator(end()); }
135
136      const_reverse_iterator
137      rbegin() const
138      { return const_reverse_iterator(end()); }
139
140      reverse_iterator
141      rend()
142      { return reverse_iterator(begin()); }
143
144      const_reverse_iterator
145      rend() const
146      { return const_reverse_iterator(begin()); }
147
148      // 23.2.2.2 capacity:
149      using _Base::empty;
150      using _Base::size;
151      using _Base::max_size;
152
153      void
154      resize(size_type __sz, _Tp __c = _Tp())
155      {
156	this->_M_detach_singular();
157
158	// if __sz < size(), invalidate all iterators in [begin+__sz, end())
159	iterator __victim = begin();
160	iterator __end = end();
161	for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
162	  ++__victim;
163
164	while (__victim != __end)
165	  {
166	    iterator __real_victim = __victim++;
167	    __real_victim._M_invalidate();
168	  }
169
170	try
171	  {
172	    _Base::resize(__sz, __c);
173	  }
174	catch(...)
175	  {
176	    this->_M_revalidate_singular();
177	    __throw_exception_again;
178	  }
179      }
180
181      // element access:
182      reference
183      front()
184      {
185	__glibcxx_check_nonempty();
186	return _Base::front();
187      }
188
189      const_reference
190      front() const
191      {
192	__glibcxx_check_nonempty();
193	return _Base::front();
194      }
195
196      reference
197      back()
198      {
199	__glibcxx_check_nonempty();
200	return _Base::back();
201      }
202
203      const_reference
204      back() const
205      {
206	__glibcxx_check_nonempty();
207	return _Base::back();
208      }
209
210      // 23.2.2.3 modifiers:
211      using _Base::push_front;
212
213      void
214      pop_front()
215      {
216	__glibcxx_check_nonempty();
217	iterator __victim = begin();
218	__victim._M_invalidate();
219	_Base::pop_front();
220      }
221
222      using _Base::push_back;
223
224      void
225      pop_back()
226      {
227	__glibcxx_check_nonempty();
228	iterator __victim = end();
229	--__victim;
230	__victim._M_invalidate();
231	_Base::pop_back();
232      }
233
234      iterator
235      insert(iterator __position, const _Tp& __x)
236      {
237	__glibcxx_check_insert(__position);
238	return iterator(_Base::insert(__position.base(), __x), this);
239      }
240
241      void
242      insert(iterator __position, size_type __n, const _Tp& __x)
243      {
244	__glibcxx_check_insert(__position);
245	_Base::insert(__position.base(), __n, __x);
246      }
247
248      template<class _InputIterator>
249        void
250        insert(iterator __position, _InputIterator __first,
251	       _InputIterator __last)
252        {
253	  __glibcxx_check_insert_range(__position, __first, __last);
254	  _Base::insert(__position.base(), __first, __last);
255	}
256
257      iterator
258      erase(iterator __position)
259      {
260	__glibcxx_check_erase(__position);
261	__position._M_invalidate();
262	return iterator(_Base::erase(__position.base()), this);
263      }
264
265      iterator
266      erase(iterator __position, iterator __last)
267      {
268	// _GLIBCXX_RESOLVE_LIB_DEFECTS
269	// 151. can't currently clear() empty container
270	__glibcxx_check_erase_range(__position, __last);
271	for (iterator __victim = __position; __victim != __last; )
272	  {
273	    iterator __old = __victim;
274	    ++__victim;
275	    __old._M_invalidate();
276	  }
277	return iterator(_Base::erase(__position.base(), __last.base()), this);
278      }
279
280      void
281      swap(list& __x)
282      {
283	_Base::swap(__x);
284	this->_M_swap(__x);
285      }
286
287      void
288      clear()
289      {
290	_Base::clear();
291	this->_M_invalidate_all();
292      }
293
294      // 23.2.2.4 list operations:
295      void
296      splice(iterator __position, list& __x)
297      {
298	_GLIBCXX_DEBUG_VERIFY(&__x != this,
299			      _M_message(::__gnu_debug::__msg_self_splice)
300			      ._M_sequence(*this, "this"));
301	this->splice(__position, __x, __x.begin(), __x.end());
302      }
303
304      void
305      splice(iterator __position, list& __x, iterator __i)
306      {
307	__glibcxx_check_insert(__position);
308	_GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(),
309			      _M_message(::__gnu_debug::__msg_splice_alloc)
310			    ._M_sequence(*this)._M_sequence(__x, "__x"));
311	_GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
312			      _M_message(::__gnu_debug::__msg_splice_bad)
313			      ._M_iterator(__i, "__i"));
314	_GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
315			      _M_message(::__gnu_debug::__msg_splice_other)
316			     ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
317
318	// _GLIBCXX_RESOLVE_LIB_DEFECTS
319	// 250. splicing invalidates iterators
320	this->_M_transfer_iter(__i);
321	_Base::splice(__position.base(), __x._M_base(), __i.base());
322      }
323
324      void
325      splice(iterator __position, list& __x, iterator __first, iterator __last)
326      {
327	__glibcxx_check_insert(__position);
328	__glibcxx_check_valid_range(__first, __last);
329	_GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
330			      _M_message(::__gnu_debug::__msg_splice_other)
331			      ._M_sequence(__x, "x")
332			      ._M_iterator(__first, "first"));
333	_GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(),
334			      _M_message(::__gnu_debug::__msg_splice_alloc)
335			      ._M_sequence(*this)._M_sequence(__x));
336
337	for (iterator __tmp = __first; __tmp != __last; )
338	  {
339	    _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
340				_M_message(::__gnu_debug::__msg_splice_overlap)
341				  ._M_iterator(__tmp, "position")
342				  ._M_iterator(__first, "first")
343				  ._M_iterator(__last, "last"));
344	    iterator __victim = __tmp++;
345	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
346	    // 250. splicing invalidates iterators
347	    this->_M_transfer_iter(__victim);
348	  }
349
350	_Base::splice(__position.base(), __x._M_base(), __first.base(),
351		      __last.base());
352      }
353
354      void
355      remove(const _Tp& __value)
356      {
357	for (iterator __x = begin(); __x.base() != _Base::end(); )
358	  {
359	    if (*__x == __value)
360	      __x = erase(__x);
361	    else
362	      ++__x;
363	  }
364      }
365
366      template<class _Predicate>
367        void
368        remove_if(_Predicate __pred)
369        {
370	  for (iterator __x = begin(); __x.base() != _Base::end(); )
371	    {
372	      if (__pred(*__x))
373		__x = erase(__x);
374	      else
375		++__x;
376	    }
377	}
378
379      void
380      unique()
381      {
382	iterator __first = begin();
383	iterator __last = end();
384	if (__first == __last)
385	  return;
386	iterator __next = __first;
387	while (++__next != __last)
388	  {
389	    if (*__first == *__next)
390	      erase(__next);
391	    else
392	      __first = __next;
393	    __next = __first;
394	  }
395      }
396
397      template<class _BinaryPredicate>
398        void
399        unique(_BinaryPredicate __binary_pred)
400        {
401	  iterator __first = begin();
402	  iterator __last = end();
403	  if (__first == __last)
404	    return;
405	  iterator __next = __first;
406	  while (++__next != __last)
407	    {
408	      if (__binary_pred(*__first, *__next))
409		erase(__next);
410	      else
411		__first = __next;
412	      __next = __first;
413	    }
414	}
415
416      void
417      merge(list& __x)
418      {
419	__glibcxx_check_sorted(_Base::begin(), _Base::end());
420	__glibcxx_check_sorted(__x.begin().base(), __x.end().base());
421	for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
422	  {
423	    iterator __victim = __tmp++;
424	    __victim._M_attach(&__x);
425	  }
426	_Base::merge(__x._M_base());
427      }
428
429      template<class _Compare>
430        void
431        merge(list& __x, _Compare __comp)
432        {
433	  __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
434	  __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
435				      __comp);
436	  for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
437	    {
438	      iterator __victim = __tmp++;
439	      __victim._M_attach(&__x);
440	    }
441	  _Base::merge(__x._M_base(), __comp);
442	}
443
444      void
445      sort() { _Base::sort(); }
446
447      template<typename _StrictWeakOrdering>
448        void
449        sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
450
451      using _Base::reverse;
452
453      _Base&
454      _M_base()       { return *this; }
455
456      const _Base&
457      _M_base() const { return *this; }
458
459    private:
460      void
461      _M_invalidate_all()
462      {
463	typedef typename _Base::const_iterator _Base_const_iterator;
464	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
465	this->_M_invalidate_if(_Not_equal(_M_base().end()));
466      }
467    };
468
469  template<typename _Tp, typename _Alloc>
470    inline bool
471    operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
472    { return __lhs._M_base() == __rhs._M_base(); }
473
474  template<typename _Tp, typename _Alloc>
475    inline bool
476    operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
477    { return __lhs._M_base() != __rhs._M_base(); }
478
479  template<typename _Tp, typename _Alloc>
480    inline bool
481    operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
482    { return __lhs._M_base() < __rhs._M_base(); }
483
484  template<typename _Tp, typename _Alloc>
485    inline bool
486    operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
487    { return __lhs._M_base() <= __rhs._M_base(); }
488
489  template<typename _Tp, typename _Alloc>
490    inline bool
491    operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
492    { return __lhs._M_base() >= __rhs._M_base(); }
493
494  template<typename _Tp, typename _Alloc>
495    inline bool
496    operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
497    { return __lhs._M_base() > __rhs._M_base(); }
498
499  template<typename _Tp, typename _Alloc>
500    inline void
501    swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
502    { __lhs.swap(__rhs); }
503} // namespace __gnu_debug_def
504
505#endif
506