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