111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Safe container/iterator base implementation -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2011-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// terms of the GNU General Public License as published by the 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Free Software Foundation; either version 3, or (at your option) 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// any later version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// but WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// GNU General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** @file debug/safe_unordered_base.h 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This file is a GNU debug extension to the Standard C++ Library. 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _GLIBCXX_DEBUG_SAFE_UNORDERED_BASE_H 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _GLIBCXX_DEBUG_SAFE_UNORDERED_BASE_H 1 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <debug/safe_base.h> 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_debug 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Safe_unordered_container_base; 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** \brief Basic functionality for a @a safe iterator. 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The %_Safe_local_iterator_base base class implements the functionality 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * of a safe local iterator that is not specific to a particular iterator 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * type. It contains a pointer back to the container it references 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * along with iterator version information and pointers to form a 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * doubly-linked list of local iterators referenced by the container. 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This class must not perform any operations that can throw an 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * exception, or the exception guarantees of derived iterators will 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * be broken. 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Safe_local_iterator_base : public _Safe_iterator_base 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Initializes the iterator and makes it singular. */ 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_local_iterator_base() 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { } 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Initialize the iterator to reference the container pointed to 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * by @p __seq. @p __constant is true when we are initializing a 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * constant local iterator, and false if it is a mutable local iterator. 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Note that @p __seq may be NULL, in which case the iterator will be 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * singular. Otherwise, the iterator will reference @p __seq and 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * be nonsingular. 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_local_iterator_base(const _Safe_sequence_base* __seq, bool __constant) 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { this->_M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); } 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Initializes the iterator to reference the same container that 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert @p __x does. @p __constant is true if this is a constant 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator, and false if it is mutable. */ 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_local_iterator_base(const _Safe_local_iterator_base& __x, 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __constant) 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { this->_M_attach(__x._M_sequence, __constant); } 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_local_iterator_base& 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator=(const _Safe_local_iterator_base&); 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert explicit 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_local_iterator_base(const _Safe_local_iterator_base&); 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Safe_local_iterator_base() { this->_M_detach(); } 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_unordered_container_base* 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_container() const _GLIBCXX_NOEXCEPT; 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Attaches this iterator to the given container, detaching it 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * from whatever container it was attached to originally. If the 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * new container is the NULL pointer, the iterator is left 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * unattached. 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _M_attach(_Safe_sequence_base* __seq, bool __constant); 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Likewise, but not thread-safe. */ 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _M_attach_single(_Safe_sequence_base* __seq, bool __constant) throw (); 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Detach the iterator for whatever container it is attached to, 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * if any. 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _M_detach(); 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Likewise, but not thread-safe. */ 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _M_detach_single() throw (); 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Base class that supports tracking of local iterators that 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * reference an unordered container. 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The %_Safe_unordered_container_base class provides basic support for 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * tracking iterators into an unordered container. Containers that track 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * iterators must derived from %_Safe_unordered_container_base publicly, so 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * that safe iterators (which inherit _Safe_iterator_base) can 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * attach to them. This class contains four linked lists of 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * iterators, one for constant iterators, one for mutable 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * iterators, one for constant local iterators, one for mutable local 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * iterators and a version number that allows very fast 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * invalidation of all iterators that reference the container. 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This class must ensure that no operation on it may throw an 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * exception, otherwise @a safe containers may fail to provide the 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * exception-safety guarantees required by the C++ standard. 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Safe_unordered_container_base : public _Safe_sequence_base 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Safe_sequence_base _Base; 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// The list of mutable local iterators that reference this container 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_iterator_base* _M_local_iterators; 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// The list of constant local iterators that reference this container 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_iterator_base* _M_const_local_iterators; 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Initialize with a version number of 1 and no iterators 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_unordered_container_base() 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_local_iterators(nullptr), _M_const_local_iterators(nullptr) 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { } 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Initialize with a version number of 1 and no iterators 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_unordered_container_base(const _Safe_unordered_container_base&) 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert noexcept 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _Safe_unordered_container_base() { } 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Safe_unordered_container_base(_Safe_unordered_container_base&& __x) 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert noexcept 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _Safe_unordered_container_base() 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { this->_M_swap(__x); } 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Notify all iterators that reference this container that the 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert container is being destroyed. */ 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Safe_unordered_container_base() 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { this->_M_detach_all(); } 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Detach all iterators, leaving them singular. */ 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_detach_all(); 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Swap this container with the given container. This operation 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * also swaps ownership of the iterators, so that when the 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * operation is complete all iterators that originally referenced 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * one container now reference the other container. 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_swap(_Safe_unordered_container_base& __x); 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Attach an iterator to this container. */ 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_attach_local(_Safe_iterator_base* __it, bool __constant); 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Likewise but not thread safe. */ 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_attach_local_single(_Safe_iterator_base* __it, bool __constant) throw (); 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Detach an iterator from this container */ 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_detach_local(_Safe_iterator_base* __it); 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** Likewise but not thread safe. */ 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_detach_local_single(_Safe_iterator_base* __it) throw (); 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace __gnu_debug 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 186