williamr@2: /* Copyright 2003-2006 Joaquín M López Muñoz. williamr@2: * Distributed under the Boost Software License, Version 1.0. williamr@2: * (See accompanying file LICENSE_1_0.txt or copy at williamr@2: * http://www.boost.org/LICENSE_1_0.txt) williamr@2: * williamr@2: * See http://www.boost.org/libs/multi_index for library home page. williamr@2: */ williamr@2: williamr@2: #ifndef BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP williamr@2: #define BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP williamr@2: williamr@2: #if defined(_MSC_VER)&&(_MSC_VER>=1200) williamr@2: #pragma once williamr@2: #endif williamr@2: williamr@2: /* Safe mode machinery, in the spirit of Cay Hortmann's "Safe STL" williamr@2: * (http://www.horstmann.com/safestl.html). williamr@2: * In this mode, containers of type Container are derived from williamr@2: * safe_container, and their corresponding iterators williamr@2: * are wrapped with safe_iterator. These classes provide williamr@2: * an internal record of which iterators are at a given moment associated williamr@2: * to a given container, and properly mark the iterators as invalid williamr@2: * when the container gets destroyed. williamr@2: * Iterators are chained in a single attached list, whose header is williamr@2: * kept by the container. More elaborate data structures would yield better williamr@2: * performance, but I decided to keep complexity to a minimum since williamr@2: * speed is not an issue here. williamr@2: * Safe mode iterators automatically check that only proper operations williamr@2: * are performed on them: for instance, an invalid iterator cannot be williamr@2: * dereferenced. Additionally, a set of utilty macros and functions are williamr@2: * provided that serve to implement preconditions and cooperate with williamr@2: * the framework within the container. williamr@2: * Iterators can also be unchecked, i.e. they do not have info about williamr@2: * which container they belong in. This situation arises when the iterator williamr@2: * is restored from a serialization archive: only information on the node williamr@2: * is available, and it is not possible to determine to which container williamr@2: * the iterator is associated to. The only sensible policy is to assume williamr@2: * unchecked iterators are valid, though this can certainly generate false williamr@2: * positive safe mode checks. williamr@2: * This is not a full-fledged safe mode framework, and is only intended williamr@2: * for use within the limits of Boost.MultiIndex. williamr@2: */ williamr@2: williamr@2: /* Assertion macros. These resolve to no-ops if williamr@2: * !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE). williamr@2: */ williamr@2: williamr@2: #if !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) williamr@2: #undef BOOST_MULTI_INDEX_SAFE_MODE_ASSERT williamr@2: #define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) ((void)0) williamr@2: #else williamr@2: #if !defined(BOOST_MULTI_INDEX_SAFE_MODE_ASSERT) williamr@2: #include williamr@2: #define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) BOOST_ASSERT(expr) williamr@2: #endif williamr@2: #endif williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_valid_iterator(it), \ williamr@2: safe_mode::invalid_iterator); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(it) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_dereferenceable_iterator(it), \ williamr@2: safe_mode::not_dereferenceable_iterator); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(it) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_incrementable_iterator(it), \ williamr@2: safe_mode::not_incrementable_iterator); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(it) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_decrementable_iterator(it), \ williamr@2: safe_mode::not_decrementable_iterator); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,cont) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_is_owner(it,cont), \ williamr@2: safe_mode::not_owner); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_SAME_OWNER(it0,it1) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_same_owner(it0,it1), \ williamr@2: safe_mode::not_same_owner); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_VALID_RANGE(it0,it1) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_valid_range(it0,it1), \ williamr@2: safe_mode::invalid_range); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(it,it0,it1) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_outside_range(it,it0,it1), \ williamr@2: safe_mode::inside_range); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(it,n) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_in_bounds(it,n), \ williamr@2: safe_mode::out_of_bounds); williamr@2: williamr@2: #define BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(cont0,cont1) \ williamr@2: BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ williamr@2: safe_mode::check_different_container(cont0,cont1), \ williamr@2: safe_mode::same_container); williamr@2: williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) williamr@2: #include /* keep it first to prevent nasty warns in MSVC */ williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) williamr@2: #include williamr@2: #endif williamr@2: williamr@2: #if defined(BOOST_HAS_THREADS) williamr@2: #include williamr@2: #endif williamr@2: williamr@2: namespace boost{ williamr@2: williamr@2: namespace multi_index{ williamr@2: williamr@2: namespace safe_mode{ williamr@2: williamr@2: /* Checking routines. Assume the best for unchecked iterators williamr@2: * (i.e. they pass the checking when there is not enough info williamr@2: * to know.) williamr@2: */ williamr@2: williamr@2: template williamr@2: inline bool check_valid_iterator(const Iterator& it) williamr@2: { williamr@2: return it.valid()||it.unchecked(); williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_dereferenceable_iterator(const Iterator& it) williamr@2: { williamr@2: return it.valid()&&it!=it.owner()->end()||it.unchecked(); williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_incrementable_iterator(const Iterator& it) williamr@2: { williamr@2: return it.valid()&&it!=it.owner()->end()||it.unchecked(); williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_decrementable_iterator(const Iterator& it) williamr@2: { williamr@2: return it.valid()&&it!=it.owner()->begin()||it.unchecked(); williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_is_owner( williamr@2: const Iterator& it,const typename Iterator::container_type& cont) williamr@2: { williamr@2: return it.valid()&&it.owner()==&cont||it.unchecked(); williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_same_owner(const Iterator& it0,const Iterator& it1) williamr@2: { williamr@2: return it0.valid()&&it1.valid()&&it0.owner()==it1.owner()|| williamr@2: it0.unchecked()||it1.unchecked(); williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_valid_range(const Iterator& it0,const Iterator& it1) williamr@2: { williamr@2: if(!check_same_owner(it0,it1))return false; williamr@2: williamr@2: if(it0.valid()){ williamr@2: Iterator last=it0.owner()->end(); williamr@2: if(it1==last)return true; williamr@2: williamr@2: for(Iterator first=it0;first!=last;++first){ williamr@2: if(first==it1)return true; williamr@2: } williamr@2: return false; williamr@2: } williamr@2: return true; williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_outside_range( williamr@2: const Iterator& it,const Iterator& it0,const Iterator& it1) williamr@2: { williamr@2: if(!check_same_owner(it0,it1))return false; williamr@2: williamr@2: if(it0.valid()){ williamr@2: Iterator last=it0.owner()->end(); williamr@2: bool found=false; williamr@2: williamr@2: Iterator first=it0; williamr@2: for(;first!=last;++first){ williamr@2: if(first==it1)break; williamr@2: williamr@2: /* crucial that this check goes after previous break */ williamr@2: williamr@2: if(first==it)found=true; williamr@2: } williamr@2: if(first!=it1)return false; williamr@2: return !found; williamr@2: } williamr@2: return true; williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_in_bounds(const Iterator& it,Difference n) williamr@2: { williamr@2: if(it.unchecked())return true; williamr@2: if(!it.valid()) return false; williamr@2: if(n>0) return it.owner()->end()-it>=n; williamr@2: else return it.owner()->begin()-it<=n; williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool check_different_container( williamr@2: const Container& cont0,const Container& cont1) williamr@2: { williamr@2: return &cont0!=&cont1; williamr@2: } williamr@2: williamr@2: /* Invalidates all iterators equivalent to that given. Safe containers williamr@2: * must call this when deleting elements: the safe mode framework cannot williamr@2: * perform this operation automatically without outside help. williamr@2: */ williamr@2: williamr@2: template williamr@2: inline void detach_equivalent_iterators(Iterator& it) williamr@2: { williamr@2: if(it.valid()){ williamr@2: Iterator *prev_,*next_; williamr@2: for( williamr@2: prev_=static_cast(&it.cont->header); williamr@2: (next_=static_cast(prev_->next))!=0;){ williamr@2: if(next_!=&it&&*next_==it){ williamr@2: prev_->next=next_->next; williamr@2: next_->cont=0; williamr@2: } williamr@2: else prev_=next_; williamr@2: } williamr@2: it.detach(); williamr@2: } williamr@2: } williamr@2: williamr@2: template class safe_container; /* fwd decl. */ williamr@2: williamr@2: } /* namespace multi_index::safe_mode */ williamr@2: williamr@2: namespace detail{ williamr@2: williamr@2: class safe_container_base; /* fwd decl. */ williamr@2: williamr@2: class safe_iterator_base williamr@2: { williamr@2: public: williamr@2: bool valid()const{return cont!=0;} williamr@2: bool unchecked()const{return unchecked_;} williamr@2: williamr@2: inline void detach(); williamr@2: williamr@2: void uncheck() williamr@2: { williamr@2: detach(); williamr@2: unchecked_=true; williamr@2: } williamr@2: williamr@2: protected: williamr@2: safe_iterator_base():cont(0),next(0),unchecked_(false){} williamr@2: williamr@2: explicit safe_iterator_base(safe_container_base* cont_): williamr@2: unchecked_(false) williamr@2: { williamr@2: attach(cont_); williamr@2: } williamr@2: williamr@2: safe_iterator_base(const safe_iterator_base& it): williamr@2: unchecked_(it.unchecked_) williamr@2: { williamr@2: attach(it.cont); williamr@2: } williamr@2: williamr@2: safe_iterator_base& operator=(const safe_iterator_base& it) williamr@2: { williamr@2: unchecked_=it.unchecked_; williamr@2: safe_container_base* new_cont=it.cont; williamr@2: if(cont!=new_cont){ williamr@2: detach(); williamr@2: attach(new_cont); williamr@2: } williamr@2: return *this; williamr@2: } williamr@2: williamr@2: ~safe_iterator_base() williamr@2: { williamr@2: detach(); williamr@2: } williamr@2: williamr@2: const safe_container_base* owner()const{return cont;} williamr@2: williamr@2: BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS: williamr@2: friend class safe_container_base; williamr@2: williamr@2: #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) williamr@2: template friend class safe_mode::safe_container; williamr@2: template friend williamr@2: void safe_mode::detach_equivalent_iterators(Iterator&); williamr@2: #endif williamr@2: williamr@2: inline void attach(safe_container_base* cont_); williamr@2: williamr@2: safe_container_base* cont; williamr@2: safe_iterator_base* next; williamr@2: bool unchecked_; williamr@2: }; williamr@2: williamr@2: class safe_container_base:private noncopyable williamr@2: { williamr@2: public: williamr@2: safe_container_base(){} williamr@2: williamr@2: BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: williamr@2: friend class safe_iterator_base; williamr@2: williamr@2: #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) williamr@2: template friend williamr@2: void safe_mode::detach_equivalent_iterators(Iterator&); williamr@2: #endif williamr@2: williamr@2: ~safe_container_base() williamr@2: { williamr@2: /* Detaches all remaining iterators, which by now will williamr@2: * be those pointing to the end of the container. williamr@2: */ williamr@2: williamr@2: for(safe_iterator_base* it=header.next;it;it=it->next)it->cont=0; williamr@2: header.next=0; williamr@2: } williamr@2: williamr@2: void swap(safe_container_base& x) williamr@2: { williamr@2: for(safe_iterator_base* it0=header.next;it0;it0=it0->next)it0->cont=&x; williamr@2: for(safe_iterator_base* it1=x.header.next;it1;it1=it1->next)it1->cont=this; williamr@2: std::swap(header.cont,x.header.cont); williamr@2: std::swap(header.next,x.header.next); williamr@2: } williamr@2: williamr@2: safe_iterator_base header; williamr@2: williamr@2: #if defined(BOOST_HAS_THREADS) williamr@2: boost::detail::lightweight_mutex mutex; williamr@2: #endif williamr@2: }; williamr@2: williamr@2: void safe_iterator_base::attach(safe_container_base* cont_) williamr@2: { williamr@2: cont=cont_; williamr@2: if(cont){ williamr@2: #if defined(BOOST_HAS_THREADS) williamr@2: boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex); williamr@2: #endif williamr@2: williamr@2: next=cont->header.next; williamr@2: cont->header.next=this; williamr@2: } williamr@2: } williamr@2: williamr@2: void safe_iterator_base::detach() williamr@2: { williamr@2: if(cont){ williamr@2: #if defined(BOOST_HAS_THREADS) williamr@2: boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex); williamr@2: #endif williamr@2: williamr@2: safe_iterator_base *prev_,*next_; williamr@2: for(prev_=&cont->header;(next_=prev_->next)!=this;prev_=next_){} williamr@2: prev_->next=next; williamr@2: cont=0; williamr@2: } williamr@2: } williamr@2: williamr@2: } /* namespace multi_index::detail */ williamr@2: williamr@2: namespace safe_mode{ williamr@2: williamr@2: /* In order to enable safe mode on a container: williamr@2: * - The container must derive from safe_container, williamr@2: * - iterators must be generated via safe_iterator, which adapts a williamr@2: * preexistent unsafe iterator class. williamr@2: */ williamr@2: williamr@2: template williamr@2: class safe_container; williamr@2: williamr@2: template williamr@2: class safe_iterator: williamr@2: public detail::iter_adaptor,Iterator>, williamr@2: public detail::safe_iterator_base williamr@2: { williamr@2: typedef detail::iter_adaptor super; williamr@2: typedef detail::safe_iterator_base safe_super; williamr@2: williamr@2: public: williamr@2: typedef Container container_type; williamr@2: typedef typename Iterator::reference reference; williamr@2: typedef typename Iterator::difference_type difference_type; williamr@2: williamr@2: safe_iterator(){} williamr@2: explicit safe_iterator(safe_container* cont_): williamr@2: safe_super(cont_){} williamr@2: template williamr@2: safe_iterator(const T0& t0,safe_container* cont_): williamr@2: super(Iterator(t0)),safe_super(cont_){} williamr@2: template williamr@2: safe_iterator( williamr@2: const T0& t0,const T1& t1,safe_container* cont_): williamr@2: super(Iterator(t0,t1)),safe_super(cont_){} williamr@2: williamr@2: safe_iterator& operator=(const safe_iterator& x) williamr@2: { williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); williamr@2: this->base_reference()=x.base_reference(); williamr@2: safe_super::operator=(x); williamr@2: return *this; williamr@2: } williamr@2: williamr@2: const container_type* owner()const williamr@2: { williamr@2: return williamr@2: static_cast( williamr@2: static_cast*>( williamr@2: this->safe_super::owner())); williamr@2: } williamr@2: williamr@2: /* get_node is not to be used by the user */ williamr@2: williamr@2: typedef typename Iterator::node_type node_type; williamr@2: williamr@2: node_type* get_node()const{return this->base_reference().get_node();} williamr@2: williamr@2: private: williamr@2: friend class boost::multi_index::detail::iter_adaptor_access; williamr@2: williamr@2: reference dereference()const williamr@2: { williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); williamr@2: BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(*this); williamr@2: return *(this->base_reference()); williamr@2: } williamr@2: williamr@2: bool equal(const safe_iterator& x)const williamr@2: { williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); williamr@2: BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x); williamr@2: return this->base_reference()==x.base_reference(); williamr@2: } williamr@2: williamr@2: void increment() williamr@2: { williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); williamr@2: BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(*this); williamr@2: ++(this->base_reference()); williamr@2: } williamr@2: williamr@2: void decrement() williamr@2: { williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); williamr@2: BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(*this); williamr@2: --(this->base_reference()); williamr@2: } williamr@2: williamr@2: void advance(difference_type n) williamr@2: { williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); williamr@2: BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(*this,n); williamr@2: this->base_reference()+=n; williamr@2: } williamr@2: williamr@2: difference_type distance_to(const safe_iterator& x)const williamr@2: { williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); williamr@2: BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x); williamr@2: return x.base_reference()-this->base_reference(); williamr@2: } williamr@2: williamr@2: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) williamr@2: /* Serialization. Note that Iterator::save and Iterator:load williamr@2: * are assumed to be defined and public: at first sight it seems williamr@2: * like we could have resorted to the public serialization interface williamr@2: * for doing the forwarding to the adapted iterator class: williamr@2: * ar<>base_reference(); williamr@2: * but this would cause incompatibilities if a saving williamr@2: * program is in safe mode and the loading program is not, or williamr@2: * viceversa --in safe mode, the archived iterator data is one layer williamr@2: * deeper, this is especially relevant with XML archives. williamr@2: * It'd be nice if Boost.Serialization provided some forwarding williamr@2: * facility for use by adaptor classes. williamr@2: */ williamr@2: williamr@2: friend class boost::serialization::access; williamr@2: williamr@2: BOOST_SERIALIZATION_SPLIT_MEMBER() williamr@2: williamr@2: template williamr@2: void save(Archive& ar,const unsigned int version)const williamr@2: { williamr@2: BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); williamr@2: this->base_reference().save(ar,version); williamr@2: } williamr@2: williamr@2: template williamr@2: void load(Archive& ar,const unsigned int version) williamr@2: { williamr@2: this->base_reference().load(ar,version); williamr@2: safe_super::uncheck(); williamr@2: } williamr@2: #endif williamr@2: }; williamr@2: williamr@2: template williamr@2: class safe_container:public detail::safe_container_base williamr@2: { williamr@2: typedef detail::safe_container_base super; williamr@2: williamr@2: public: williamr@2: void detach_dereferenceable_iterators() williamr@2: { williamr@2: typedef typename Container::iterator iterator; williamr@2: williamr@2: iterator end_=static_cast(this)->end(); williamr@2: iterator *prev_,*next_; williamr@2: for( williamr@2: prev_=static_cast(&this->header); williamr@2: (next_=static_cast(prev_->next))!=0;){ williamr@2: if(*next_!=end_){ williamr@2: prev_->next=next_->next; williamr@2: next_->cont=0; williamr@2: } williamr@2: else prev_=next_; williamr@2: } williamr@2: } williamr@2: williamr@2: void swap(safe_container& x) williamr@2: { williamr@2: super::swap(x); williamr@2: } williamr@2: }; williamr@2: williamr@2: } /* namespace multi_index::safe_mode */ williamr@2: williamr@2: } /* namespace multi_index */ williamr@2: williamr@2: } /* namespace boost */ williamr@2: williamr@2: #endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */ williamr@2: williamr@2: #endif