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)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP
12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
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.
44 /* Assertion macros. These resolve to no-ops if
45 * !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE).
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)
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)
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);
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);
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);
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);
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);
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);
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);
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);
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);
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);
108 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
109 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
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>
117 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
118 #include <boost/serialization/split_member.hpp>
121 #if defined(BOOST_HAS_THREADS)
122 #include <boost/detail/lightweight_mutex.hpp>
127 namespace multi_index{
131 /* Checking routines. Assume the best for unchecked iterators
132 * (i.e. they pass the checking when there is not enough info
136 template<typename Iterator>
137 inline bool check_valid_iterator(const Iterator& it)
139 return it.valid()||it.unchecked();
142 template<typename Iterator>
143 inline bool check_dereferenceable_iterator(const Iterator& it)
145 return it.valid()&&it!=it.owner()->end()||it.unchecked();
148 template<typename Iterator>
149 inline bool check_incrementable_iterator(const Iterator& it)
151 return it.valid()&&it!=it.owner()->end()||it.unchecked();
154 template<typename Iterator>
155 inline bool check_decrementable_iterator(const Iterator& it)
157 return it.valid()&&it!=it.owner()->begin()||it.unchecked();
160 template<typename Iterator>
161 inline bool check_is_owner(
162 const Iterator& it,const typename Iterator::container_type& cont)
164 return it.valid()&&it.owner()==&cont||it.unchecked();
167 template<typename Iterator>
168 inline bool check_same_owner(const Iterator& it0,const Iterator& it1)
170 return it0.valid()&&it1.valid()&&it0.owner()==it1.owner()||
171 it0.unchecked()||it1.unchecked();
174 template<typename Iterator>
175 inline bool check_valid_range(const Iterator& it0,const Iterator& it1)
177 if(!check_same_owner(it0,it1))return false;
180 Iterator last=it0.owner()->end();
181 if(it1==last)return true;
183 for(Iterator first=it0;first!=last;++first){
184 if(first==it1)return true;
191 template<typename Iterator>
192 inline bool check_outside_range(
193 const Iterator& it,const Iterator& it0,const Iterator& it1)
195 if(!check_same_owner(it0,it1))return false;
198 Iterator last=it0.owner()->end();
202 for(;first!=last;++first){
205 /* crucial that this check goes after previous break */
207 if(first==it)found=true;
209 if(first!=it1)return false;
215 template<typename Iterator,typename Difference>
216 inline bool check_in_bounds(const Iterator& it,Difference n)
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;
224 template<typename Container>
225 inline bool check_different_container(
226 const Container& cont0,const Container& cont1)
228 return &cont0!=&cont1;
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.
236 template<typename Iterator>
237 inline void detach_equivalent_iterators(Iterator& it)
240 Iterator *prev_,*next_;
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;
254 template<typename Container> class safe_container; /* fwd decl. */
256 } /* namespace multi_index::safe_mode */
260 class safe_container_base; /* fwd decl. */
262 class safe_iterator_base
265 bool valid()const{return cont!=0;}
266 bool unchecked()const{return unchecked_;}
268 inline void detach();
277 safe_iterator_base():cont(0),next(0),unchecked_(false){}
279 explicit safe_iterator_base(safe_container_base* cont_):
285 safe_iterator_base(const safe_iterator_base& it):
286 unchecked_(it.unchecked_)
291 safe_iterator_base& operator=(const safe_iterator_base& it)
293 unchecked_=it.unchecked_;
294 safe_container_base* new_cont=it.cont;
302 ~safe_iterator_base()
307 const safe_container_base* owner()const{return cont;}
309 BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS:
310 friend class safe_container_base;
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&);
318 inline void attach(safe_container_base* cont_);
320 safe_container_base* cont;
321 safe_iterator_base* next;
325 class safe_container_base:private noncopyable
328 safe_container_base(){}
330 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
331 friend class safe_iterator_base;
333 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
334 template<typename Iterator> friend
335 void safe_mode::detach_equivalent_iterators(Iterator&);
338 ~safe_container_base()
340 /* Detaches all remaining iterators, which by now will
341 * be those pointing to the end of the container.
344 for(safe_iterator_base* it=header.next;it;it=it->next)it->cont=0;
348 void swap(safe_container_base& x)
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);
356 safe_iterator_base header;
358 #if defined(BOOST_HAS_THREADS)
359 boost::detail::lightweight_mutex mutex;
363 void safe_iterator_base::attach(safe_container_base* cont_)
367 #if defined(BOOST_HAS_THREADS)
368 boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex);
371 next=cont->header.next;
372 cont->header.next=this;
376 void safe_iterator_base::detach()
379 #if defined(BOOST_HAS_THREADS)
380 boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex);
383 safe_iterator_base *prev_,*next_;
384 for(prev_=&cont->header;(next_=prev_->next)!=this;prev_=next_){}
390 } /* namespace multi_index::detail */
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.
400 template<typename Container>
401 class safe_container;
403 template<typename Iterator,typename Container>
405 public detail::iter_adaptor<safe_iterator<Iterator,Container>,Iterator>,
406 public detail::safe_iterator_base
408 typedef detail::iter_adaptor<safe_iterator,Iterator> super;
409 typedef detail::safe_iterator_base safe_super;
412 typedef Container container_type;
413 typedef typename Iterator::reference reference;
414 typedef typename Iterator::difference_type difference_type;
417 explicit safe_iterator(safe_container<container_type>* 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>
424 const T0& t0,const T1& t1,safe_container<container_type>* cont_):
425 super(Iterator(t0,t1)),safe_super(cont_){}
427 safe_iterator& operator=(const safe_iterator& x)
429 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x);
430 this->base_reference()=x.base_reference();
431 safe_super::operator=(x);
435 const container_type* owner()const
438 static_cast<const container_type*>(
439 static_cast<const safe_container<container_type>*>(
440 this->safe_super::owner()));
443 /* get_node is not to be used by the user */
445 typedef typename Iterator::node_type node_type;
447 node_type* get_node()const{return this->base_reference().get_node();}
450 friend class boost::multi_index::detail::iter_adaptor_access;
452 reference dereference()const
454 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
455 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(*this);
456 return *(this->base_reference());
459 bool equal(const safe_iterator& x)const
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();
469 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
470 BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(*this);
471 ++(this->base_reference());
476 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
477 BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(*this);
478 --(this->base_reference());
481 void advance(difference_type n)
483 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
484 BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(*this,n);
485 this->base_reference()+=n;
488 difference_type distance_to(const safe_iterator& x)const
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();
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.
511 friend class boost::serialization::access;
513 BOOST_SERIALIZATION_SPLIT_MEMBER()
515 template<class Archive>
516 void save(Archive& ar,const unsigned int version)const
518 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
519 this->base_reference().save(ar,version);
522 template<class Archive>
523 void load(Archive& ar,const unsigned int version)
525 this->base_reference().load(ar,version);
526 safe_super::uncheck();
531 template<typename Container>
532 class safe_container:public detail::safe_container_base
534 typedef detail::safe_container_base super;
537 void detach_dereferenceable_iterators()
539 typedef typename Container::iterator iterator;
541 iterator end_=static_cast<Container*>(this)->end();
542 iterator *prev_,*next_;
544 prev_=static_cast<iterator*>(&this->header);
545 (next_=static_cast<iterator*>(prev_->next))!=0;){
547 prev_->next=next_->next;
554 void swap(safe_container<Container>& x)
560 } /* namespace multi_index::safe_mode */
562 } /* namespace multi_index */
564 } /* namespace boost */
566 #endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */