contrib/libstdc++/include/debug/safe_sequence.h

   1 // Safe sequence implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006
   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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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 /** @file debug/safe_sequence.h
  32  *  This file is a GNU debug extension to the Standard C++ Library.
  33  */
  34
  35 #ifndef _GLIBCXX_DEBUG_SAFE_SEQUENCE_H
  36 #define _GLIBCXX_DEBUG_SAFE_SEQUENCE_H 1
  37
  38 #include <debug/debug.h>
  39 #include <debug/macros.h>
  40 #include <debug/functions.h>
  41 #include <debug/safe_base.h>
  42
  43 namespace __gnu_debug
  44 {
  45   template<typename _Iterator, typename _Sequence>
  46     class _Safe_iterator;
  47
  48   /** A simple function object that returns true if the passed-in
  49    *  value is not equal to the stored value. It saves typing over
  50    *  using both bind1st and not_equal.
  51    */
  52   template<typename _Type>
  53     class _Not_equal_to
  54     {
  55       _Type __value;
  56
  57     public:
  58       explicit _Not_equal_to(const _Type& __v) : __value(__v) { }
  59
  60       bool
  61       operator()(const _Type& __x) const
  62       { return __value != __x; }
  63     };
  64
  65   /** A function object that returns true when the given random access
  66       iterator is at least @c n steps away from the given iterator. */
  67   template<typename _Iterator>
  68     class _After_nth_from
  69     {
  70       typedef typename std::iterator_traits<_Iterator>::difference_type
  71       difference_type;
  72
  73       _Iterator _M_base;
  74       difference_type _M_n;
  75
  76     public:
  77       _After_nth_from(const difference_type& __n, const _Iterator& __base)
  78       : _M_base(__base), _M_n(__n) { }
  79
  80       bool
  81       operator()(const _Iterator& __x) const
  82       { return __x - _M_base >= _M_n; }
  83     };
  84
  85   /**
  86    * @brief Base class for constructing a "safe" sequence type that
  87    * tracks iterators that reference it.
  88    *
  89    * The class template %_Safe_sequence simplifies the construction of
  90    * "safe" sequences that track the iterators that reference the
  91    * sequence, so that the iterators are notified of changes in the
  92    * sequence that may affect their operation, e.g., if the container
  93    * invalidates its iterators or is destructed. This class template
  94    * may only be used by deriving from it and passing the name of the
  95    * derived class as its template parameter via the curiously
  96    * recurring template pattern. The derived class must have @c
  97    * iterator and @const_iterator types that are instantiations of
  98    * class template _Safe_iterator for this sequence. Iterators will
  99    * then be tracked automatically.
 100    */
 101   template<typename _Sequence>
 102     class _Safe_sequence : public _Safe_sequence_base
 103     {
 104     public:
 105       /** Invalidates all iterators @c x that reference this sequence,
 106           are not singular, and for which @c pred(x) returns @c
 107           true. The user of this routine should be careful not to make
 108           copies of the iterators passed to @p pred, as the copies may
 109           interfere with the invalidation. */
 110       template<typename _Predicate>
 111         void
 112         _M_invalidate_if(_Predicate __pred);
 113
 114       /** Transfers all iterators that reference this memory location
 115           to this sequence from whatever sequence they are attached
 116           to. */
 117       template<typename _Iterator>
 118         void
 119         _M_transfer_iter(const _Safe_iterator<_Iterator, _Sequence>& __x);
 120     };
 121
 122   template<typename _Sequence>
 123     template<typename _Predicate>
 124       void
 125       _Safe_sequence<_Sequence>::
 126       _M_invalidate_if(_Predicate __pred)
 127       {
 128         typedef typename _Sequence::iterator iterator;
 129         typedef typename _Sequence::const_iterator const_iterator;
 130
 131         __gnu_cxx::__scoped_lock sentry(this->_M_get_mutex());
 132         for (_Safe_iterator_base* __iter = _M_iterators; __iter;)
 133           {
 134             iterator* __victim = static_cast<iterator*>(__iter);
 135             __iter = __iter->_M_next;
 136             if (!__victim->_M_singular())
 137               {
 138                 if (__pred(__victim->base()))
 139                   __victim->_M_invalidate_single();
 140               }
 141           }
 142
 143         for (_Safe_iterator_base* __iter2 = _M_const_iterators; __iter2;)
 144           {
 145             const_iterator* __victim = static_cast<const_iterator*>(__iter2);
 146             __iter2 = __iter2->_M_next;
 147             if (!__victim->_M_singular())
 148               {
 149                 if (__pred(__victim->base()))
 150                   __victim->_M_invalidate_single();
 151               }
 152           }
 153       }
 154
 155   template<typename _Sequence>
 156     template<typename _Iterator>
 157       void
 158       _Safe_sequence<_Sequence>::
 159       _M_transfer_iter(const _Safe_iterator<_Iterator, _Sequence>& __x)
 160       {
 161         _Safe_sequence_base* __from = __x._M_sequence;
 162         if (!__from)
 163           return;
 164
 165         typedef typename _Sequence::iterator iterator;
 166         typedef typename _Sequence::const_iterator const_iterator;
 167
 168         __gnu_cxx::__scoped_lock sentry(this->_M_get_mutex());
 169         for (_Safe_iterator_base* __iter = __from->_M_iterators; __iter;)
 170           {
 171             iterator* __victim = static_cast<iterator*>(__iter);
 172             __iter = __iter->_M_next;
 173             if (!__victim->_M_singular() && __victim->base() == __x.base())
 174               __victim->_M_attach_single(static_cast<_Sequence*>(this));
 175           }
 176
 177         for (_Safe_iterator_base* __iter2 = __from->_M_const_iterators;
 178              __iter2;)
 179           {
 180             const_iterator* __victim = static_cast<const_iterator*>(__iter2);
 181             __iter2 = __iter2->_M_next;
 182             if (!__victim->_M_singular() && __victim->base() == __x.base())
 183               __victim->_M_attach_single(static_cast<_Sequence*>(this));
 184           }
 185       }
 186 } // namespace __gnu_debug
 187
 188 #endif