1/* Copyright 2003-2013 Joaquin M Lopez Munoz.
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)
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#include <boost/serialization/version.hpp>
120#endif
121
122#if defined(BOOST_HAS_THREADS)
123#include <boost/detail/lightweight_mutex.hpp>
124#endif
125
126namespace boost{
127
128namespace multi_index{
129
130namespace safe_mode{
131
132/* Checking routines. Assume the best for unchecked iterators
133 * (i.e. they pass the checking when there is not enough info
134 * to know.)
135 */
136
137template<typename Iterator>
138inline bool check_valid_iterator(const Iterator& it)
139{
140 return it.valid()||it.unchecked();
141}
142
143template<typename Iterator>
144inline bool check_dereferenceable_iterator(const Iterator& it)
145{
146 return (it.valid()&&it!=it.owner()->end())||it.unchecked();
147}
148
149template<typename Iterator>
150inline bool check_incrementable_iterator(const Iterator& it)
151{
152 return (it.valid()&&it!=it.owner()->end())||it.unchecked();
153}
154
155template<typename Iterator>
156inline bool check_decrementable_iterator(const Iterator& it)
157{
158 return (it.valid()&&it!=it.owner()->begin())||it.unchecked();
159}
160
161template<typename Iterator>
162inline bool check_is_owner(
163 const Iterator& it,const typename Iterator::container_type& cont)
164{
165 return (it.valid()&&it.owner()==&cont)||it.unchecked();
166}
167
168template<typename Iterator>
169inline bool check_same_owner(const Iterator& it0,const Iterator& it1)
170{
171 return (it0.valid()&&it1.valid()&&it0.owner()==it1.owner())||
172 it0.unchecked()||it1.unchecked();
173}
174
175template<typename Iterator>
176inline bool check_valid_range(const Iterator& it0,const Iterator& it1)
177{
178 if(!check_same_owner(it0,it1))return false;
179
180 if(it0.valid()){
181 Iterator last=it0.owner()->end();
182 if(it1==last)return true;
183
184 for(Iterator first=it0;first!=last;++first){
185 if(first==it1)return true;
186 }
187 return false;
188 }
189 return true;
190}
191
192template<typename Iterator>
193inline bool check_outside_range(
194 const Iterator& it,const Iterator& it0,const Iterator& it1)
195{
196 if(!check_same_owner(it0,it1))return false;
197
198 if(it0.valid()){
199 Iterator last=it0.owner()->end();
200 bool found=false;
201
202 Iterator first=it0;
203 for(;first!=last;++first){
204 if(first==it1)break;
205
206 /* crucial that this check goes after previous break */
207
208 if(first==it)found=true;
209 }
210 if(first!=it1)return false;
211 return !found;
212 }
213 return true;
214}
215
216template<typename Iterator,typename Difference>
217inline bool check_in_bounds(const Iterator& it,Difference n)
218{
219 if(it.unchecked())return true;
220 if(!it.valid()) return false;
221 if(n>0) return it.owner()->end()-it>=n;
222 else return it.owner()->begin()-it<=n;
223}
224
225template<typename Container>
226inline bool check_different_container(
227 const Container& cont0,const Container& cont1)
228{
229 return &cont0!=&cont1;
230}
231
232/* Invalidates all iterators equivalent to that given. Safe containers
233 * must call this when deleting elements: the safe mode framework cannot
234 * perform this operation automatically without outside help.
235 */
236
237template<typename Iterator>
238inline void detach_equivalent_iterators(Iterator& it)
239{
240 if(it.valid()){
241 {
242#if defined(BOOST_HAS_THREADS)
243 boost::detail::lightweight_mutex::scoped_lock lock(it.cont->mutex);
244#endif
245
246 Iterator *prev_,*next_;
247 for(
248 prev_=static_cast<Iterator*>(&it.cont->header);
249 (next_=static_cast<Iterator*>(prev_->next))!=0;){
250 if(next_!=&it&&*next_==it){
251 prev_->next=next_->next;
252 next_->cont=0;
253 }
254 else prev_=next_;
255 }
256 }
257 it.detach();
258 }
259}
260
261template<typename Container> class safe_container; /* fwd decl. */
262
263} /* namespace multi_index::safe_mode */
264
265namespace detail{
266
267class safe_container_base; /* fwd decl. */
268
269class safe_iterator_base
270{
271public:
272 bool valid()const{return cont!=0;}
273 bool unchecked()const{return unchecked_;}
274
275 inline void detach();
276
277 void uncheck()
278 {
279 detach();
280 unchecked_=true;
281 }
282
283protected:
284 safe_iterator_base():cont(0),next(0),unchecked_(false){}
285
286 explicit safe_iterator_base(safe_container_base* cont_):
287 unchecked_(false)
288 {
289 attach(cont_);
290 }
291
292 safe_iterator_base(const safe_iterator_base& it):
293 unchecked_(it.unchecked_)
294 {
295 attach(it.cont);
296 }
297
298 safe_iterator_base& operator=(const safe_iterator_base& it)
299 {
300 unchecked_=it.unchecked_;
301 safe_container_base* new_cont=it.cont;
302 if(cont!=new_cont){
303 detach();
304 attach(new_cont);
305 }
306 return *this;
307 }
308
309 ~safe_iterator_base()
310 {
311 detach();
312 }
313
314 const safe_container_base* owner()const{return cont;}
315
316BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS:
317 friend class safe_container_base;
318
319#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
320 template<typename> friend class safe_mode::safe_container;
321 template<typename Iterator> friend
322 void safe_mode::detach_equivalent_iterators(Iterator&);
323#endif
324
325 inline void attach(safe_container_base* cont_);
326
327 safe_container_base* cont;
328 safe_iterator_base* next;
329 bool unchecked_;
330};
331
332class safe_container_base:private noncopyable
333{
334public:
335 safe_container_base(){}
336
337BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
338 friend class safe_iterator_base;
339
340#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
341 template<typename Iterator> friend
342 void safe_mode::detach_equivalent_iterators(Iterator&);
343#endif
344
345 ~safe_container_base()
346 {
347 /* Detaches all remaining iterators, which by now will
348 * be those pointing to the end of the container.
349 */
350
351 for(safe_iterator_base* it=header.next;it;it=it->next)it->cont=0;
352 header.next=0;
353 }
354
355 void swap(safe_container_base& x)
356 {
357 for(safe_iterator_base* it0=header.next;it0;it0=it0->next)it0->cont=&x;
358 for(safe_iterator_base* it1=x.header.next;it1;it1=it1->next)it1->cont=this;
359 std::swap(header.cont,x.header.cont);
360 std::swap(header.next,x.header.next);
361 }
362
363 safe_iterator_base header;
364
365#if defined(BOOST_HAS_THREADS)
366 boost::detail::lightweight_mutex mutex;
367#endif
368};
369
370void safe_iterator_base::attach(safe_container_base* cont_)
371{
372 cont=cont_;
373 if(cont){
374#if defined(BOOST_HAS_THREADS)
375 boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex);
376#endif
377
378 next=cont->header.next;
379 cont->header.next=this;
380 }
381}
382
383void safe_iterator_base::detach()
384{
385 if(cont){
386#if defined(BOOST_HAS_THREADS)
387 boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex);
388#endif
389
390 safe_iterator_base *prev_,*next_;
391 for(prev_=&cont->header;(next_=prev_->next)!=this;prev_=next_){}
392 prev_->next=next;
393 cont=0;
394 }
395}
396
397} /* namespace multi_index::detail */
398
399namespace safe_mode{
400
401/* In order to enable safe mode on a container:
402 * - The container must derive from safe_container<container_type>,
403 * - iterators must be generated via safe_iterator, which adapts a
404 * preexistent unsafe iterator class.
405 */
406
407template<typename Container>
408class safe_container;
409
410template<typename Iterator,typename Container>
411class safe_iterator:
412 public detail::iter_adaptor<safe_iterator<Iterator,Container>,Iterator>,
413 public detail::safe_iterator_base
414{
415 typedef detail::iter_adaptor<safe_iterator,Iterator> super;
416 typedef detail::safe_iterator_base safe_super;
417
418public:
419 typedef Container container_type;
420 typedef typename Iterator::reference reference;
421 typedef typename Iterator::difference_type difference_type;
422
423 safe_iterator(){}
424 explicit safe_iterator(safe_container<container_type>* cont_):
425 safe_super(cont_){}
426 template<typename T0>
427 safe_iterator(const T0& t0,safe_container<container_type>* cont_):
428 super(Iterator(t0)),safe_super(cont_){}
429 template<typename T0,typename T1>
430 safe_iterator(
431 const T0& t0,const T1& t1,safe_container<container_type>* cont_):
432 super(Iterator(t0,t1)),safe_super(cont_){}
433
434 safe_iterator& operator=(const safe_iterator& x)
435 {
436 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x);
437 this->base_reference()=x.base_reference();
438 safe_super::operator=(x);
439 return *this;
440 }
441
442 const container_type* owner()const
443 {
444 return
445 static_cast<const container_type*>(
446 static_cast<const safe_container<container_type>*>(
447 this->safe_super::owner()));
448 }
449
450 /* get_node is not to be used by the user */
451
452 typedef typename Iterator::node_type node_type;
453
454 node_type* get_node()const{return this->base_reference().get_node();}
455
456private:
457 friend class boost::multi_index::detail::iter_adaptor_access;
458
459 reference dereference()const
460 {
461 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
462 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(*this);
463 return *(this->base_reference());
464 }
465
466 bool equal(const safe_iterator& x)const
467 {
468 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
469 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x);
470 BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x);
471 return this->base_reference()==x.base_reference();
472 }
473
474 void increment()
475 {
476 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
477 BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(*this);
478 ++(this->base_reference());
479 }
480
481 void decrement()
482 {
483 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
484 BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(*this);
485 --(this->base_reference());
486 }
487
488 void advance(difference_type n)
489 {
490 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
491 BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(*this,n);
492 this->base_reference()+=n;
493 }
494
495 difference_type distance_to(const safe_iterator& x)const
496 {
497 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
498 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x);
499 BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x);
500 return x.base_reference()-this->base_reference();
501 }
502
503#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
504 /* Serialization. Note that Iterator::save and Iterator:load
505 * are assumed to be defined and public: at first sight it seems
506 * like we could have resorted to the public serialization interface
507 * for doing the forwarding to the adapted iterator class:
508 * ar<<base_reference();
509 * ar>>base_reference();
510 * but this would cause incompatibilities if a saving
511 * program is in safe mode and the loading program is not, or
512 * viceversa --in safe mode, the archived iterator data is one layer
513 * deeper, this is especially relevant with XML archives.
514 * It'd be nice if Boost.Serialization provided some forwarding
515 * facility for use by adaptor classes.
516 */
517
518 friend class boost::serialization::access;
519
520 BOOST_SERIALIZATION_SPLIT_MEMBER()
521
522 template<class Archive>
523 void save(Archive& ar,const unsigned int version)const
524 {
525 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this);
526 this->base_reference().save(ar,version);
527 }
528
529 template<class Archive>
530 void load(Archive& ar,const unsigned int version)
531 {
532 this->base_reference().load(ar,version);
533 safe_super::uncheck();
534 }
535#endif
536};
537
538template<typename Container>
539class safe_container:public detail::safe_container_base
540{
541 typedef detail::safe_container_base super;
542
543public:
544 void detach_dereferenceable_iterators()
545 {
546 typedef typename Container::iterator iterator;
547
548 iterator end_=static_cast<Container*>(this)->end();
549 iterator *prev_,*next_;
550 for(
551 prev_=static_cast<iterator*>(&this->header);
552 (next_=static_cast<iterator*>(prev_->next))!=0;){
553 if(*next_!=end_){
554 prev_->next=next_->next;
555 next_->cont=0;
556 }
557 else prev_=next_;
558 }
559 }
560
561 void swap(safe_container<Container>& x)
562 {
563 super::swap(x);
564 }
565};
566
567} /* namespace multi_index::safe_mode */
568
569} /* namespace multi_index */
570
571#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
572namespace serialization{
573template<typename Iterator,typename Container>
574struct version<
575 boost::multi_index::safe_mode::safe_iterator<Iterator,Container>
576>
577{
578 BOOST_STATIC_CONSTANT(
579 int,value=boost::serialization::version<Iterator>::value);
580};
581} /* namespace serialization */
582#endif
583
584} /* namespace boost */
585
586#endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */
587
588#endif
589