# safe_base.h

Go to the documentation of this file.

    00001 // Safe sequence/iterator base implementation  -*- C++ -*-
    00002
    00003 // Copyright (C) 2003, 2004, 2005, 2006
    00004 // Free Software Foundation, Inc.
    00005 //
    00006 // This file is part of the GNU ISO C++ Library.  This library is free
    00007 // software; you can redistribute it and/or modify it under the
    00008 // terms of the GNU General Public License as published by the
    00009 // Free Software Foundation; either version 2, or (at your option)
    00010 // any later version.
    00011
    00012 // This library is distributed in the hope that it will be useful,
    00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00015 // GNU General Public License for more details.
    00016
    00017 // You should have received a copy of the GNU General Public License along
    00018 // with this library; see the file COPYING.  If not, write to the Free
    00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00020 // USA.
    00021
    00022 // As a special exception, you may use this file as part of a free software
    00023 // library without restriction.  Specifically, if other files instantiate
    00024 // templates or use macros or inline functions from this file, or you compile
    00025 // this file and link it with other files to produce an executable, this
    00026 // file does not by itself cause the resulting executable to be covered by
    00027 // the GNU General Public License.  This exception does not however
    00028 // invalidate any other reasons why the executable file might be covered by
    00029 // the GNU General Public License.
    00030
    00031 /** @file debug/safe_base.h
    00032  *  This file is a GNU debug extension to the Standard C++ Library.
    00033  */
    00034
    00035 #ifndef _GLIBCXX_DEBUG_SAFE_BASE_H
    00036 #define _GLIBCXX_DEBUG_SAFE_BASE_H 1
    00037
    00038 #include <ext/concurrence.h>
    00039
    00040 namespace __gnu_debug
    00041 {
    00042   class _Safe_sequence_base;
    00043
    00044   /** \brief Basic functionality for a "safe" iterator.
    00045    *
    00046    *  The %_Safe_iterator_base base class implements the functionality
    00047    *  of a safe iterator that is not specific to a particular iterator
    00048    *  type. It contains a pointer back to the sequence it references
    00049    *  along with iterator version information and pointers to form a
    00050    *  doubly-linked list of iterators referenced by the container.
    00051    *
    00052    *  This class must not perform any operations that can throw an
    00053    *  exception, or the exception guarantees of derived iterators will
    00054    *  be broken.
    00055    */
    00056   class _Safe_iterator_base
    00057   {
    00058   public:
    00059     /** The sequence this iterator references; may be NULL to indicate
    00060     a singular iterator. */
    00061     _Safe_sequence_base* _M_sequence;
    00062
    00063     /** The version number of this iterator. The sentinel value 0 is
    00064      *  used to indicate an invalidated iterator (i.e., one that is
    00065      *  singular because of an operation on the container). This
    00066      *  version number must equal the version number in the sequence
    00067      *  referenced by _M_sequence for the iterator to be
    00068      *  non-singular.
    00069      */
    00070     unsigned int         _M_version;
    00071
    00072     /** Pointer to the previous iterator in the sequence's list of
    00073     iterators. Only valid when _M_sequence != NULL. */
    00074     _Safe_iterator_base* _M_prior;
    00075
    00076     /** Pointer to the next iterator in the sequence's list of
    00077     iterators. Only valid when _M_sequence != NULL. */
    00078     _Safe_iterator_base* _M_next;
    00079
    00080   protected:
    00081     /** Initializes the iterator and makes it singular. */
    00082     _Safe_iterator_base()
    00083     : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
    00084     { }
    00085
    00086     /** Initialize the iterator to reference the sequence pointed to
    00087      *  by @p__seq. @p __constant is true when we are initializing a
    00088      *  constant iterator, and false if it is a mutable iterator. Note
    00089      *  that @p __seq may be NULL, in which case the iterator will be
    00090      *  singular. Otherwise, the iterator will reference @p __seq and
    00091      *  be nonsingular.
    00092      */
    00093     _Safe_iterator_base(const _Safe_sequence_base* __seq, bool __constant)
    00094     : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
    00095     { this->_M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); }
    00096
    00097     /** Initializes the iterator to reference the same sequence that
    00098     @p __x does. @p __constant is true if this is a constant
    00099     iterator, and false if it is mutable. */
    00100     _Safe_iterator_base(const _Safe_iterator_base& __x, bool __constant)
    00101     : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
    00102     { this->_M_attach(__x._M_sequence, __constant); }
    00103
    00104     _Safe_iterator_base&
    00105     operator=(const _Safe_iterator_base&);
    00106
    00107     explicit
    00108     _Safe_iterator_base(const _Safe_iterator_base&);
    00109
    00110     ~_Safe_iterator_base() { this->_M_detach(); }
    00111
    00112     /** For use in _Safe_iterator. */
    00113     __gnu_cxx::__mutex& _M_get_mutex();
    00114
    00115   public:
    00116     /** Attaches this iterator to the given sequence, detaching it
    00117      *  from whatever sequence it was attached to originally. If the
    00118      *  new sequence is the NULL pointer, the iterator is left
    00119      *  unattached.
    00120      */
    00121     void _M_attach(_Safe_sequence_base* __seq, bool __constant);
    00122
    00123     /** Likewise, but not thread-safe. */
    00124     void _M_attach_single(_Safe_sequence_base* __seq, bool __constant);
    00125
    00126     /** Detach the iterator for whatever sequence it is attached to,
    00127      *  if any.
    00128     */
    00129     void _M_detach();
    00130
    00131     /** Likewise, but not thread-safe. */
    00132     void _M_detach_single();
    00133
    00134     /** Determines if we are attached to the given sequence. */
    00135     bool _M_attached_to(const _Safe_sequence_base* __seq) const
    00136     { return _M_sequence == __seq; }
    00137
    00138     /** Is this iterator singular? */
    00139     bool _M_singular() const;
    00140
    00141     /** Can we compare this iterator to the given iterator @p __x?
    00142     Returns true if both iterators are nonsingular and reference
    00143     the same sequence. */
    00144     bool _M_can_compare(const _Safe_iterator_base& __x) const;
    00145   };
    00146
    00147   /**
    00148    * @brief Base class that supports tracking of iterators that
    00149    * reference a sequence.
    00150    *
    00151    * The %_Safe_sequence_base class provides basic support for
    00152    * tracking iterators into a sequence. Sequences that track
    00153    * iterators must derived from %_Safe_sequence_base publicly, so
    00154    * that safe iterators (which inherit _Safe_iterator_base) can
    00155    * attach to them. This class contains two linked lists of
    00156    * iterators, one for constant iterators and one for mutable
    00157    * iterators, and a version number that allows very fast
    00158    * invalidation of all iterators that reference the container.
    00159    *
    00160    * This class must ensure that no operation on it may throw an
    00161    * exception, otherwise "safe" sequences may fail to provide the
    00162    * exception-safety guarantees required by the C++ standard.
    00163    */
    00164   class _Safe_sequence_base
    00165   {
    00166   public:
    00167     /// The list of mutable iterators that reference this container
    00168     _Safe_iterator_base* _M_iterators;
    00169
    00170     /// The list of constant iterators that reference this container
    00171     _Safe_iterator_base* _M_const_iterators;
    00172
    00173     /// The container version number. This number may never be 0.
    00174     mutable unsigned int _M_version;
    00175
    00176   protected:
    00177     // Initialize with a version number of 1 and no iterators
    00178     _Safe_sequence_base()
    00179     : _M_iterators(0), _M_const_iterators(0), _M_version(1)
    00180     { }
    00181
    00182     /** Notify all iterators that reference this sequence that the
    00183     sequence is being destroyed. */
    00184     ~_Safe_sequence_base()
    00185     { this->_M_detach_all(); }
    00186
    00187     /** Detach all iterators, leaving them singular. */
    00188     void
    00189     _M_detach_all();
    00190
    00191     /** Detach all singular iterators.
    00192      *  @post for all iterators i attached to this sequence,
    00193      *   i->_M_version == _M_version.
    00194      */
    00195     void
    00196     _M_detach_singular();
    00197
    00198     /** Revalidates all attached singular iterators.  This method may
    00199      *  be used to validate iterators that were invalidated before
    00200      *  (but for some reasion, such as an exception, need to become
    00201      *  valid again).
    00202      */
    00203     void
    00204     _M_revalidate_singular();
    00205
    00206     /** Swap this sequence with the given sequence. This operation
    00207      *  also swaps ownership of the iterators, so that when the
    00208      *  operation is complete all iterators that originally referenced
    00209      *  one container now reference the other container.
    00210      */
    00211     void
    00212     _M_swap(_Safe_sequence_base& __x);
    00213
    00214     /** For use in _Safe_sequence. */
    00215     __gnu_cxx::__mutex& _M_get_mutex();
    00216
    00217   public:
    00218     /** Invalidates all iterators. */
    00219     void
    00220     _M_invalidate_all() const
    00221     { if (++_M_version == 0) _M_version = 1; }
    00222   };
    00223 } // namespace __gnu_debug
    00224
    00225 #endif