epoc32/include/stdapis/boost/multi_index/detail/safe_mode.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
     1 /* Copyright 2003-2006 Joaquín M López Muñoz.
     2  * Distributed under the Boost Software License, Version 1.0.
     3  * (See accompanying file LICENSE_1_0.txt or copy at
     4  * http://www.boost.org/LICENSE_1_0.txt)
     5  *
     6  * See http://www.boost.org/libs/multi_index for library home page.
     7  */
     8 
     9 #ifndef BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP
    10 #define BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP
    11 
    12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
    13 #pragma once
    14 #endif
    15 
    16 /* Safe mode machinery, in the spirit of Cay Hortmann's "Safe STL"
    17  * (http://www.horstmann.com/safestl.html).
    18  * In this mode, containers of type Container are derived from
    19  * safe_container<Container>, and their corresponding iterators
    20  * are wrapped with safe_iterator. These classes provide
    21  * an internal record of which iterators are at a given moment associated
    22  * to a given container, and properly mark the iterators as invalid
    23  * when the container gets destroyed.
    24  * Iterators are chained in a single attached list, whose header is
    25  * kept by the container. More elaborate data structures would yield better
    26  * performance, but I decided to keep complexity to a minimum since
    27  * speed is not an issue here.
    28  * Safe mode iterators automatically check that only proper operations
    29  * are performed on them: for instance, an invalid iterator cannot be
    30  * dereferenced. Additionally, a set of utilty macros and functions are
    31  * provided that serve to implement preconditions and cooperate with
    32  * the framework within the container.
    33  * Iterators can also be unchecked, i.e. they do not have info about
    34  * which container they belong in. This situation arises when the iterator
    35  * is restored from a serialization archive: only information on the node
    36  * is available, and it is not possible to determine to which container
    37  * the iterator is associated to. The only sensible policy is to assume
    38  * unchecked iterators are valid, though this can certainly generate false
    39  * positive safe mode checks.
    40  * This is not a full-fledged safe mode framework, and is only intended
    41  * for use within the limits of Boost.MultiIndex.
    42  */
    43 
    44 /* Assertion macros. These resolve to no-ops if
    45  * !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE).
    46  */
    47 
    48 #if !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    49 #undef BOOST_MULTI_INDEX_SAFE_MODE_ASSERT
    50 #define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) ((void)0)
    51 #else
    52 #if !defined(BOOST_MULTI_INDEX_SAFE_MODE_ASSERT)
    53 #include <boost/assert.hpp>
    54 #define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) BOOST_ASSERT(expr)
    55 #endif
    56 #endif
    57 
    58 #define BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it)                           \
    59   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
    60     safe_mode::check_valid_iterator(it),                                     \
    61     safe_mode::invalid_iterator);
    62 
    63 #define BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(it)                 \
    64   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
    65     safe_mode::check_dereferenceable_iterator(it),                           \
    66     safe_mode::not_dereferenceable_iterator);
    67 
    68 #define BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(it)                   \
    69   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
    70     safe_mode::check_incrementable_iterator(it),                             \
    71     safe_mode::not_incrementable_iterator);
    72 
    73 #define BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(it)                   \
    74   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
    75     safe_mode::check_decrementable_iterator(it),                             \
    76     safe_mode::not_decrementable_iterator);
    77 
    78 #define BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,cont)                            \
    79   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
    80     safe_mode::check_is_owner(it,cont),                                      \
    81     safe_mode::not_owner);
    82 
    83 #define BOOST_MULTI_INDEX_CHECK_SAME_OWNER(it0,it1)                          \
    84   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
    85     safe_mode::check_same_owner(it0,it1),                                    \
    86     safe_mode::not_same_owner);
    87 
    88 #define BOOST_MULTI_INDEX_CHECK_VALID_RANGE(it0,it1)                         \
    89   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
    90     safe_mode::check_valid_range(it0,it1),                                   \
    91     safe_mode::invalid_range);
    92 
    93 #define BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(it,it0,it1)                    \
    94   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
    95     safe_mode::check_outside_range(it,it0,it1),                              \
    96     safe_mode::inside_range);
    97 
    98 #define BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(it,n)                              \
    99   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
   100     safe_mode::check_in_bounds(it,n),                                        \
   101     safe_mode::out_of_bounds);
   102 
   103 #define BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(cont0,cont1)             \
   104   BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
   105     safe_mode::check_different_container(cont0,cont1),                       \
   106     safe_mode::same_container);
   107 
   108 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   109 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
   110 #include <algorithm>
   111 #include <boost/detail/iterator.hpp>
   112 #include <boost/multi_index/detail/access_specifier.hpp>
   113 #include <boost/multi_index/detail/iter_adaptor.hpp>
   114 #include <boost/multi_index/safe_mode_errors.hpp>
   115 #include <boost/noncopyable.hpp>
   116 
   117 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
   118 #include <boost/serialization/split_member.hpp>
   119 #endif
   120 
   121 #if defined(BOOST_HAS_THREADS)
   122 #include <boost/detail/lightweight_mutex.hpp>
   123 #endif
   124 
   125 namespace boost{
   126 
   127 namespace multi_index{
   128 
   129 namespace safe_mode{
   130 
   131 /* Checking routines. Assume the best for unchecked iterators
   132  * (i.e. they pass the checking when there is not enough info
   133  * to know.)
   134  */
   135 
   136 template<typename Iterator>
   137 inline bool check_valid_iterator(const Iterator& it)
   138 {
   139   return it.valid()||it.unchecked();
   140 }
   141 
   142 template<typename Iterator>
   143 inline bool check_dereferenceable_iterator(const Iterator& it)
   144 {
   145   return it.valid()&&it!=it.owner()->end()||it.unchecked();
   146 }
   147 
   148 template<typename Iterator>
   149 inline bool check_incrementable_iterator(const Iterator& it)
   150 {
   151   return it.valid()&&it!=it.owner()->end()||it.unchecked();
   152 }
   153 
   154 template<typename Iterator>
   155 inline bool check_decrementable_iterator(const Iterator& it)
   156 {
   157   return it.valid()&&it!=it.owner()->begin()||it.unchecked();
   158 }
   159 
   160 template<typename Iterator>
   161 inline bool check_is_owner(
   162   const Iterator& it,const typename Iterator::container_type& cont)
   163 {
   164   return it.valid()&&it.owner()==&cont||it.unchecked();
   165 }
   166 
   167 template<typename Iterator>
   168 inline bool check_same_owner(const Iterator& it0,const Iterator& it1)
   169 {
   170   return it0.valid()&&it1.valid()&&it0.owner()==it1.owner()||
   171          it0.unchecked()||it1.unchecked();
   172 }
   173 
   174 template<typename Iterator>
   175 inline bool check_valid_range(const Iterator& it0,const Iterator& it1)
   176 {
   177   if(!check_same_owner(it0,it1))return false;
   178 
   179   if(it0.valid()){
   180     Iterator last=it0.owner()->end();
   181     if(it1==last)return true;
   182 
   183     for(Iterator first=it0;first!=last;++first){
   184       if(first==it1)return true;
   185     }
   186     return false;
   187   }
   188   return true;
   189 }
   190 
   191 template<typename Iterator>
   192 inline bool check_outside_range(
   193   const Iterator& it,const Iterator& it0,const Iterator& it1)
   194 {
   195   if(!check_same_owner(it0,it1))return false;
   196 
   197   if(it0.valid()){
   198     Iterator last=it0.owner()->end();
   199     bool found=false;
   200 
   201     Iterator first=it0;
   202     for(;first!=last;++first){
   203       if(first==it1)break;
   204     
   205       /* crucial that this check goes after previous break */
   206     
   207       if(first==it)found=true;
   208     }
   209     if(first!=it1)return false;
   210     return !found;
   211   }
   212   return true;
   213 }
   214 
   215 template<typename Iterator,typename Difference>
   216 inline bool check_in_bounds(const Iterator& it,Difference n)
   217 {
   218   if(it.unchecked())return true;
   219   if(!it.valid())   return false;
   220   if(n>0)           return it.owner()->end()-it>=n;
   221   else              return it.owner()->begin()-it<=n;
   222 }
   223 
   224 template<typename Container>
   225 inline bool check_different_container(
   226   const Container& cont0,const Container& cont1)
   227 {
   228   return &cont0!=&cont1;
   229 }
   230 
   231 /* Invalidates all iterators equivalent to that given. Safe containers
   232  * must call this when deleting elements: the safe mode framework cannot
   233  * perform this operation automatically without outside help.
   234  */
   235 
   236 template<typename Iterator>
   237 inline void detach_equivalent_iterators(Iterator& it)
   238 {
   239   if(it.valid()){
   240     Iterator *prev_,*next_;
   241     for(
   242       prev_=static_cast<Iterator*>(&it.cont->header);
   243       (next_=static_cast<Iterator*>(prev_->next))!=0;){
   244       if(next_!=&it&&*next_==it){
   245         prev_->next=next_->next;
   246         next_->cont=0;
   247       }
   248       else prev_=next_;
   249     }
   250     it.detach();
   251   }
   252 }
   253 
   254 template<typename Container> class safe_container; /* fwd decl. */
   255 
   256 } /* namespace multi_index::safe_mode */
   257 
   258 namespace detail{
   259 
   260 class safe_container_base;                 /* fwd decl. */
   261 
   262 class safe_iterator_base
   263 {
   264 public:
   265   bool valid()const{return cont!=0;}
   266   bool unchecked()const{return unchecked_;}
   267 
   268   inline void detach();
   269 
   270   void uncheck()
   271   {
   272     detach();
   273     unchecked_=true;
   274   }
   275 
   276 protected:
   277   safe_iterator_base():cont(0),next(0),unchecked_(false){}
   278 
   279   explicit safe_iterator_base(safe_container_base* cont_):
   280     unchecked_(false)
   281   {
   282     attach(cont_);
   283   }
   284 
   285   safe_iterator_base(const safe_iterator_base& it):
   286     unchecked_(it.unchecked_)
   287   {
   288     attach(it.cont);
   289   }
   290 
   291   safe_iterator_base& operator=(const safe_iterator_base& it)
   292   {
   293     unchecked_=it.unchecked_;
   294     safe_container_base* new_cont=it.cont;
   295     if(cont!=new_cont){
   296       detach();
   297       attach(new_cont);
   298     }
   299     return *this;
   300   }
   301 
   302   ~safe_iterator_base()
   303   {
   304     detach();
   305   }
   306 
   307   const safe_container_base* owner()const{return cont;}
   308 
   309 BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS:
   310   friend class safe_container_base;
   311 
   312 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
   313   template<typename>          friend class safe_mode::safe_container;
   314   template<typename Iterator> friend
   315     void safe_mode::detach_equivalent_iterators(Iterator&);
   316 #endif
   317 
   318   inline void attach(safe_container_base* cont_);
   319 
   320   safe_container_base* cont;
   321   safe_iterator_base*  next;
   322   bool                 unchecked_;
   323 };
   324 
   325 class safe_container_base:private noncopyable
   326 {
   327 public:
   328   safe_container_base(){}
   329 
   330 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
   331   friend class safe_iterator_base;
   332 
   333 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
   334   template<typename Iterator> friend
   335     void safe_mode::detach_equivalent_iterators(Iterator&);
   336 #endif
   337 
   338   ~safe_container_base()
   339   {
   340     /* Detaches all remaining iterators, which by now will
   341      * be those pointing to the end of the container.
   342      */
   343 
   344     for(safe_iterator_base* it=header.next;it;it=it->next)it->cont=0;
   345     header.next=0;
   346   }
   347 
   348   void swap(safe_container_base& x)
   349   {
   350     for(safe_iterator_base* it0=header.next;it0;it0=it0->next)it0->cont=&x;
   351     for(safe_iterator_base* it1=x.header.next;it1;it1=it1->next)it1->cont=this;
   352     std::swap(header.cont,x.header.cont);
   353     std::swap(header.next,x.header.next);
   354   }
   355 
   356   safe_iterator_base header;
   357 
   358 #if defined(BOOST_HAS_THREADS)
   359   boost::detail::lightweight_mutex mutex;
   360 #endif
   361 };
   362 
   363 void safe_iterator_base::attach(safe_container_base* cont_)
   364 {
   365   cont=cont_;
   366   if(cont){
   367 #if defined(BOOST_HAS_THREADS)
   368     boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex);
   369 #endif
   370 
   371     next=cont->header.next;
   372     cont->header.next=this;
   373   }
   374 }
   375 
   376 void safe_iterator_base::detach()
   377 {
   378   if(cont){
   379 #if defined(BOOST_HAS_THREADS)
   380     boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex);
   381 #endif
   382 
   383     safe_iterator_base *prev_,*next_;
   384     for(prev_=&cont->header;(next_=prev_->next)!=this;prev_=next_){}
   385     prev_->next=next;
   386     cont=0;
   387   }
   388 }
   389 
   390 } /* namespace multi_index::detail */
   391 
   392 namespace safe_mode{
   393 
   394 /* In order to enable safe mode on a container:
   395  *   - The container must derive from safe_container<container_type>,
   396  *   - iterators must be generated via safe_iterator, which adapts a
   397  *     preexistent unsafe iterator class.
   398  */
   399  
   400 template<typename Container>
   401 class safe_container;
   402 
   403 template<typename Iterator,typename Container>
   404 class safe_iterator:
   405   public detail::iter_adaptor<safe_iterator<Iterator,Container>,Iterator>,
   406   public detail::safe_iterator_base
   407 {
   408   typedef detail::iter_adaptor<safe_iterator,Iterator> super;
   409   typedef detail::safe_iterator_base                   safe_super;
   410 
   411 public:
   412   typedef Container                                    container_type;
   413   typedef typename Iterator::reference                 reference;
   414   typedef typename Iterator::difference_type           difference_type;
   415 
   416   safe_iterator(){}
   417   explicit safe_iterator(safe_container<container_type>* cont_):
   418     safe_super(cont_){}
   419   template<typename T0>
   420   safe_iterator(const T0& t0,safe_container<container_type>* cont_):
   421     super(Iterator(t0)),safe_super(cont_){}
   422   template<typename T0,typename T1>
   423   safe_iterator(
   424     const T0& t0,const T1& t1,safe_container<container_type>* cont_):
   425     super(Iterator(t0,t1)),safe_super(cont_){}
   426 
   427   safe_iterator& operator=(const safe_iterator& x)
   428   {
   429     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x);
   430     this->base_reference()=x.base_reference();
   431     safe_super::operator=(x);
   432     return *this;
   433   }
   434 
   435   const container_type* owner()const
   436   {
   437     return
   438       static_cast<const container_type*>(
   439         static_cast<const safe_container<container_type>*>(
   440           this->safe_super::owner()));
   441   }
   442 
   443   /* get_node is not to be used by the user */
   444 
   445   typedef typename Iterator::node_type node_type;
   446 
   447   node_type* get_node()const{return this->base_reference().get_node();}
   448 
   449 private:
   450   friend class boost::multi_index::detail::iter_adaptor_access;
   451 
   452   reference dereference()const
   453   {
   454     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
   455     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(*this);
   456     return *(this->base_reference());
   457   }
   458 
   459   bool equal(const safe_iterator& x)const
   460   {
   461     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
   462     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x);
   463     BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x);
   464     return this->base_reference()==x.base_reference();
   465   }
   466 
   467   void increment()
   468   {
   469     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
   470     BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(*this);
   471     ++(this->base_reference());
   472   }
   473 
   474   void decrement()
   475   {
   476     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
   477     BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(*this);
   478     --(this->base_reference());
   479   }
   480 
   481   void advance(difference_type n)
   482   {
   483     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
   484     BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(*this,n);
   485     this->base_reference()+=n;
   486   }
   487 
   488   difference_type distance_to(const safe_iterator& x)const
   489   {
   490     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
   491     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x);
   492     BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x);
   493     return x.base_reference()-this->base_reference();
   494   }
   495 
   496 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
   497   /* Serialization. Note that Iterator::save and Iterator:load
   498    * are assumed to be defined and public: at first sight it seems
   499    * like we could have resorted to the public serialization interface
   500    * for doing the forwarding to the adapted iterator class:
   501    *   ar<<base_reference();
   502    *   ar>>base_reference();
   503    * but this would cause incompatibilities if a saving
   504    * program is in safe mode and the loading program is not, or
   505    * viceversa --in safe mode, the archived iterator data is one layer
   506    * deeper, this is especially relevant with XML archives.
   507    * It'd be nice if Boost.Serialization provided some forwarding
   508    * facility for use by adaptor classes.
   509    */ 
   510 
   511   friend class boost::serialization::access;
   512 
   513   BOOST_SERIALIZATION_SPLIT_MEMBER()
   514 
   515   template<class Archive>
   516   void save(Archive& ar,const unsigned int version)const
   517   {
   518     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
   519     this->base_reference().save(ar,version);
   520   }
   521 
   522   template<class Archive>
   523   void load(Archive& ar,const unsigned int version)
   524   {
   525     this->base_reference().load(ar,version);
   526     safe_super::uncheck();
   527   }
   528 #endif
   529 };
   530 
   531 template<typename Container>
   532 class safe_container:public detail::safe_container_base
   533 {
   534   typedef detail::safe_container_base super;
   535 
   536 public:
   537   void detach_dereferenceable_iterators()
   538   {
   539     typedef typename Container::iterator iterator;
   540 
   541     iterator end_=static_cast<Container*>(this)->end();
   542     iterator *prev_,*next_;
   543     for(
   544       prev_=static_cast<iterator*>(&this->header);
   545       (next_=static_cast<iterator*>(prev_->next))!=0;){
   546       if(*next_!=end_){
   547         prev_->next=next_->next;
   548         next_->cont=0;
   549       }
   550       else prev_=next_;
   551     }
   552   }
   553 
   554   void swap(safe_container<Container>& x)
   555   {
   556     super::swap(x);
   557   }
   558 };
   559 
   560 } /* namespace multi_index::safe_mode */
   561 
   562 } /* namespace multi_index */
   563 
   564 } /* namespace boost */
   565 
   566 #endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */
   567 
   568 #endif