1132720Skan// Safe sequence/iterator base implementation -*- C++ -*- 2132720Skan 3169691Skan// Copyright (C) 2003, 2004, 2005, 2006 4132720Skan// Free Software Foundation, Inc. 5132720Skan// 6132720Skan// This file is part of the GNU ISO C++ Library. This library is free 7132720Skan// software; you can redistribute it and/or modify it under the 8132720Skan// terms of the GNU General Public License as published by the 9132720Skan// Free Software Foundation; either version 2, or (at your option) 10132720Skan// any later version. 11132720Skan 12132720Skan// This library is distributed in the hope that it will be useful, 13132720Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 14132720Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15132720Skan// GNU General Public License for more details. 16132720Skan 17132720Skan// You should have received a copy of the GNU General Public License along 18132720Skan// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20132720Skan// USA. 21132720Skan 22132720Skan// As a special exception, you may use this file as part of a free software 23132720Skan// library without restriction. Specifically, if other files instantiate 24132720Skan// templates or use macros or inline functions from this file, or you compile 25132720Skan// this file and link it with other files to produce an executable, this 26132720Skan// file does not by itself cause the resulting executable to be covered by 27132720Skan// the GNU General Public License. This exception does not however 28132720Skan// invalidate any other reasons why the executable file might be covered by 29132720Skan// the GNU General Public License. 30132720Skan 31169691Skan/** @file debug/safe_base.h 32169691Skan * This file is a GNU debug extension to the Standard C++ Library. 33169691Skan */ 34169691Skan 35132720Skan#ifndef _GLIBCXX_DEBUG_SAFE_BASE_H 36132720Skan#define _GLIBCXX_DEBUG_SAFE_BASE_H 1 37132720Skan 38169691Skan#include <ext/concurrence.h> 39169691Skan 40132720Skannamespace __gnu_debug 41132720Skan{ 42132720Skan class _Safe_sequence_base; 43132720Skan 44132720Skan /** \brief Basic functionality for a "safe" iterator. 45132720Skan * 46132720Skan * The %_Safe_iterator_base base class implements the functionality 47132720Skan * of a safe iterator that is not specific to a particular iterator 48132720Skan * type. It contains a pointer back to the sequence it references 49132720Skan * along with iterator version information and pointers to form a 50132720Skan * doubly-linked list of iterators referenced by the container. 51132720Skan * 52132720Skan * This class must not perform any operations that can throw an 53132720Skan * exception, or the exception guarantees of derived iterators will 54132720Skan * be broken. 55132720Skan */ 56132720Skan class _Safe_iterator_base 57132720Skan { 58132720Skan public: 59132720Skan /** The sequence this iterator references; may be NULL to indicate 60132720Skan a singular iterator. */ 61132720Skan _Safe_sequence_base* _M_sequence; 62132720Skan 63132720Skan /** The version number of this iterator. The sentinel value 0 is 64132720Skan * used to indicate an invalidated iterator (i.e., one that is 65132720Skan * singular because of an operation on the container). This 66132720Skan * version number must equal the version number in the sequence 67132720Skan * referenced by _M_sequence for the iterator to be 68132720Skan * non-singular. 69132720Skan */ 70132720Skan unsigned int _M_version; 71132720Skan 72132720Skan /** Pointer to the previous iterator in the sequence's list of 73132720Skan iterators. Only valid when _M_sequence != NULL. */ 74132720Skan _Safe_iterator_base* _M_prior; 75132720Skan 76132720Skan /** Pointer to the next iterator in the sequence's list of 77132720Skan iterators. Only valid when _M_sequence != NULL. */ 78132720Skan _Safe_iterator_base* _M_next; 79132720Skan 80132720Skan protected: 81132720Skan /** Initializes the iterator and makes it singular. */ 82132720Skan _Safe_iterator_base() 83132720Skan : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0) 84132720Skan { } 85132720Skan 86132720Skan /** Initialize the iterator to reference the sequence pointed to 87132720Skan * by @p__seq. @p __constant is true when we are initializing a 88132720Skan * constant iterator, and false if it is a mutable iterator. Note 89132720Skan * that @p __seq may be NULL, in which case the iterator will be 90132720Skan * singular. Otherwise, the iterator will reference @p __seq and 91132720Skan * be nonsingular. 92132720Skan */ 93132720Skan _Safe_iterator_base(const _Safe_sequence_base* __seq, bool __constant) 94132720Skan : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0) 95132720Skan { this->_M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); } 96132720Skan 97132720Skan /** Initializes the iterator to reference the same sequence that 98132720Skan @p __x does. @p __constant is true if this is a constant 99132720Skan iterator, and false if it is mutable. */ 100132720Skan _Safe_iterator_base(const _Safe_iterator_base& __x, bool __constant) 101132720Skan : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0) 102132720Skan { this->_M_attach(__x._M_sequence, __constant); } 103132720Skan 104132720Skan _Safe_iterator_base& 105132720Skan operator=(const _Safe_iterator_base&); 106132720Skan 107132720Skan explicit 108132720Skan _Safe_iterator_base(const _Safe_iterator_base&); 109132720Skan 110132720Skan ~_Safe_iterator_base() { this->_M_detach(); } 111132720Skan 112169691Skan /** For use in _Safe_iterator. */ 113169691Skan __gnu_cxx::__mutex& _M_get_mutex(); 114169691Skan 115132720Skan public: 116132720Skan /** Attaches this iterator to the given sequence, detaching it 117132720Skan * from whatever sequence it was attached to originally. If the 118132720Skan * new sequence is the NULL pointer, the iterator is left 119132720Skan * unattached. 120132720Skan */ 121132720Skan void _M_attach(_Safe_sequence_base* __seq, bool __constant); 122132720Skan 123169691Skan /** Likewise, but not thread-safe. */ 124169691Skan void _M_attach_single(_Safe_sequence_base* __seq, bool __constant); 125169691Skan 126132720Skan /** Detach the iterator for whatever sequence it is attached to, 127132720Skan * if any. 128132720Skan */ 129132720Skan void _M_detach(); 130132720Skan 131169691Skan /** Likewise, but not thread-safe. */ 132169691Skan void _M_detach_single(); 133169691Skan 134132720Skan /** Determines if we are attached to the given sequence. */ 135132720Skan bool _M_attached_to(const _Safe_sequence_base* __seq) const 136132720Skan { return _M_sequence == __seq; } 137132720Skan 138132720Skan /** Is this iterator singular? */ 139132720Skan bool _M_singular() const; 140132720Skan 141132720Skan /** Can we compare this iterator to the given iterator @p __x? 142132720Skan Returns true if both iterators are nonsingular and reference 143132720Skan the same sequence. */ 144132720Skan bool _M_can_compare(const _Safe_iterator_base& __x) const; 145132720Skan }; 146132720Skan 147132720Skan /** 148132720Skan * @brief Base class that supports tracking of iterators that 149132720Skan * reference a sequence. 150132720Skan * 151132720Skan * The %_Safe_sequence_base class provides basic support for 152132720Skan * tracking iterators into a sequence. Sequences that track 153132720Skan * iterators must derived from %_Safe_sequence_base publicly, so 154132720Skan * that safe iterators (which inherit _Safe_iterator_base) can 155132720Skan * attach to them. This class contains two linked lists of 156132720Skan * iterators, one for constant iterators and one for mutable 157132720Skan * iterators, and a version number that allows very fast 158132720Skan * invalidation of all iterators that reference the container. 159132720Skan * 160132720Skan * This class must ensure that no operation on it may throw an 161132720Skan * exception, otherwise "safe" sequences may fail to provide the 162132720Skan * exception-safety guarantees required by the C++ standard. 163132720Skan */ 164132720Skan class _Safe_sequence_base 165132720Skan { 166132720Skan public: 167132720Skan /// The list of mutable iterators that reference this container 168132720Skan _Safe_iterator_base* _M_iterators; 169132720Skan 170132720Skan /// The list of constant iterators that reference this container 171132720Skan _Safe_iterator_base* _M_const_iterators; 172132720Skan 173132720Skan /// The container version number. This number may never be 0. 174132720Skan mutable unsigned int _M_version; 175132720Skan 176132720Skan protected: 177132720Skan // Initialize with a version number of 1 and no iterators 178132720Skan _Safe_sequence_base() 179132720Skan : _M_iterators(0), _M_const_iterators(0), _M_version(1) 180132720Skan { } 181132720Skan 182132720Skan /** Notify all iterators that reference this sequence that the 183132720Skan sequence is being destroyed. */ 184132720Skan ~_Safe_sequence_base() 185132720Skan { this->_M_detach_all(); } 186132720Skan 187132720Skan /** Detach all iterators, leaving them singular. */ 188132720Skan void 189132720Skan _M_detach_all(); 190132720Skan 191132720Skan /** Detach all singular iterators. 192132720Skan * @post for all iterators i attached to this sequence, 193132720Skan * i->_M_version == _M_version. 194132720Skan */ 195132720Skan void 196132720Skan _M_detach_singular(); 197132720Skan 198132720Skan /** Revalidates all attached singular iterators. This method may 199132720Skan * be used to validate iterators that were invalidated before 200132720Skan * (but for some reasion, such as an exception, need to become 201132720Skan * valid again). 202132720Skan */ 203132720Skan void 204132720Skan _M_revalidate_singular(); 205132720Skan 206132720Skan /** Swap this sequence with the given sequence. This operation 207132720Skan * also swaps ownership of the iterators, so that when the 208132720Skan * operation is complete all iterators that originally referenced 209132720Skan * one container now reference the other container. 210132720Skan */ 211132720Skan void 212132720Skan _M_swap(_Safe_sequence_base& __x); 213132720Skan 214169691Skan /** For use in _Safe_sequence. */ 215169691Skan __gnu_cxx::__mutex& _M_get_mutex(); 216169691Skan 217132720Skan public: 218132720Skan /** Invalidates all iterators. */ 219132720Skan void 220132720Skan _M_invalidate_all() const 221132720Skan { if (++_M_version == 0) _M_version = 1; } 222132720Skan }; 223132720Skan} // namespace __gnu_debug 224132720Skan 225132720Skan#endif 226