source: NonGTP/Boost/boost/multi_index/detail/safe_mode.hpp @ 857

Revision 857, 11.4 KB checked in by igarcia, 19 years ago (diff)
Line 
1/* Copyright 2003-2005 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#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
17#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
18#include <algorithm>
19#include <boost/multi_index/detail/access_specifier.hpp>
20#include <boost/multi_index/safe_mode_errors.hpp>
21#include <boost/noncopyable.hpp>
22
23#if defined(BOOST_HAS_THREADS)
24#include <boost/detail/lightweight_mutex.hpp>
25#endif
26
27namespace boost{
28
29namespace multi_index{
30
31/* Safe mode machinery, in the spirit of Cay Hortmann's "Safe STL"
32 * (http://www.horstmann.com/safestl.html).
33 * In this mode, containers of type Container are derived from
34 * safe_container<Container>, and their corresponding iterators
35 * are derived from safe_iterator<Container>. These classes provide
36 * an internal record of which iterators are at a given moment associated
37 * to a given container, and properly mark the iterators as invalid
38 * when the container gets destroyed.
39 * Iterators are chained in a single attached list, whose header is
40 * kept by the container. More elaborate data structures would yield better
41 * performance, but I decided to keep complexity to a minimum since
42 * speed is not an issue here.
43 * Iterators can also be unchecked, i.e. they do not have info about
44 * which container they belong in. This situation arises when the iterator
45 * is restored from a serialization archive: only information on the node
46 * is available, and it is not possible to determine to which container
47 * the iterator is associated to. The only sensible policy is to assume
48 * unchecked iterators are valid, though this can certainly generate false
49 * positive safe mode checks.
50 * This is not a full-fledged safe mode framework, and is only intended
51 * for use within the limits of Boost.MultiIndex.
52 */
53
54namespace safe_mode{
55
56/* Invalidates all iterators equivalent to that given. Defined before
57 * safe_iterator_base and safe_container_base as these contain friendship
58 * declarations to this function.
59 */
60
61template<typename Iterator>
62inline void detach_equivalent_iterators(Iterator& it)
63{
64  if(it.valid()){
65    Iterator *prev_,*next_;
66    for(
67      prev_=static_cast<Iterator*>(&it.cont->header);
68      (next_=static_cast<Iterator*>(prev_->next))!=0;){
69      if(next_!=&it&&*next_==it){
70        prev_->next=next_->next;
71        next_->cont=0;
72      }
73      else prev_=next_;
74    }
75    it.detach();
76  }
77}
78
79} /* namespace multi_index::safe_mode */
80
81namespace detail{
82
83class safe_container_base;
84
85class safe_iterator_base
86{
87public:
88  bool valid()const{return cont!=0;}
89  bool unchecked()const{return unchecked_;}
90
91  inline void detach();
92
93  void uncheck()
94  {
95    detach();
96    unchecked_=true;
97  }
98
99protected:
100  safe_iterator_base():cont(0),next(0),unchecked_(false){}
101
102  explicit safe_iterator_base(safe_container_base* cont_):
103    unchecked_(false)
104  {
105    attach(cont_);
106  }
107
108  safe_iterator_base(const safe_iterator_base& it):
109    unchecked_(it.unchecked_)
110  {
111    attach(it.cont);
112  }
113
114  safe_iterator_base& operator=(const safe_iterator_base& it)
115  {
116    unchecked_=it.unchecked_;
117    safe_container_base* new_cont=it.cont;
118    if(cont!=new_cont){
119      detach();
120      attach(new_cont);
121    }
122    return *this;
123  }
124
125  ~safe_iterator_base()
126  {
127    detach();
128  }
129
130  const safe_container_base* owner()const{return cont;}
131
132BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS:
133  friend class safe_container_base;
134
135#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
136  template<typename Iterator> friend
137    void safe_mode::detach_equivalent_iterators(Iterator&);
138#endif
139
140  inline void attach(safe_container_base* cont_);
141
142  safe_container_base* cont;
143  safe_iterator_base*  next;
144  bool                 unchecked_;
145};
146
147class safe_container_base:private noncopyable
148{
149public:
150  safe_container_base(){}
151
152  ~safe_container_base()
153  {
154    detach_all_iterators();
155  }
156
157  void detach_all_iterators()
158  {
159    for(safe_iterator_base* it=header.next;it;it=it->next)it->cont=0;
160  }
161
162  void swap(safe_container_base& x)
163  {
164    for(safe_iterator_base* it0=header.next;it0;it0=it0->next)it0->cont=&x;
165    for(safe_iterator_base* it1=x.header.next;it1;it1=it1->next)it1->cont=this;
166    std::swap(header.cont,x.header.cont);
167    std::swap(header.next,x.header.next);
168  }
169
170BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS:
171  friend class safe_iterator_base;
172
173#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
174  template<typename Iterator> friend
175    void safe_mode::detach_equivalent_iterators(Iterator&);
176#endif
177
178  safe_iterator_base header;
179
180#if defined(BOOST_HAS_THREADS)
181  boost::detail::lightweight_mutex mutex;
182#endif
183};
184
185void safe_iterator_base::attach(safe_container_base* cont_)
186{
187  cont=cont_;
188  if(cont){
189#if defined(BOOST_HAS_THREADS)
190    boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex);
191#endif
192
193    next=cont->header.next;
194    cont->header.next=this;
195  }
196}
197
198void safe_iterator_base::detach()
199{
200  if(cont){
201#if defined(BOOST_HAS_THREADS)
202    boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex);
203#endif
204
205    safe_iterator_base *prev_,*next_;
206    for(prev_=&cont->header;(next_=prev_->next)!=this;prev_=next_){}
207    prev_->next=next;
208    cont=0;
209  }
210}
211
212template<typename Container>
213class safe_container;
214
215template<typename Container>
216class safe_iterator:public safe_iterator_base
217{
218public:
219  typedef Container container_type;
220
221  safe_iterator():safe_iterator_base(){}
222  explicit safe_iterator(safe_container<container_type>* cont_):
223    safe_iterator_base(cont_){}
224
225  const container_type* owner()const
226  {
227    return
228      static_cast<const container_type*>(
229        static_cast<const safe_container<container_type>*>(
230          safe_iterator_base::owner()));
231  }
232};
233
234template<typename Container>
235class safe_container:public safe_container_base
236{
237public:
238  void swap(safe_container<Container>& x){safe_container_base::swap(x);}
239};
240
241} /* namespace multi_index::detail */
242
243namespace safe_mode{
244
245/* Checking routines. Assume the best for unchecked iterators
246 * (i.e. they pass the checking when there is not enough info
247 * to know.)
248 */
249
250template<typename Iterator>
251inline bool check_valid_iterator(const Iterator& it)
252{
253  return it.valid()||it.unchecked();
254}
255
256template<typename Iterator>
257inline bool check_dereferenceable_iterator(const Iterator& it)
258{
259  return it.valid()&&it!=it.owner()->end()||it.unchecked();
260}
261
262template<typename Iterator>
263inline bool check_incrementable_iterator(const Iterator& it)
264{
265  return it.valid()&&it!=it.owner()->end()||it.unchecked();
266}
267
268template<typename Iterator>
269inline bool check_decrementable_iterator(const Iterator& it)
270{
271  return it.valid()&&it!=it.owner()->begin()||it.unchecked();
272}
273
274template<typename Iterator>
275inline bool check_is_owner(
276  const Iterator& it,const typename Iterator::container_type& cont)
277{
278  return it.valid()&&it.owner()==&cont||it.unchecked();
279}
280
281template<typename Iterator>
282inline bool check_same_owner(const Iterator& it0,const Iterator& it1)
283{
284  return it0.valid()&&it1.valid()&&it0.owner()==it1.owner()||
285         it0.unchecked()||it1.unchecked();
286}
287
288template<typename Iterator>
289inline bool check_valid_range(const Iterator& it0,const Iterator& it1)
290{
291  if(!check_same_owner(it0,it1))return false;
292
293  if(it0.valid()){
294    Iterator last=it0.owner()->end();
295    if(it1==last)return true;
296
297    for(Iterator first=it0;first!=last;++first){
298      if(first==it1)return true;
299    }
300    return false;
301  }
302  return true;
303}
304
305template<typename Iterator>
306inline bool check_outside_range(
307  const Iterator& it,const Iterator& it0,const Iterator& it1)
308{
309  if(!check_same_owner(it0,it1))return false;
310
311  if(it0.valid()){
312    Iterator last=it0.owner()->end();
313    bool found=false;
314
315    Iterator first=it0;
316    for(;first!=last;++first){
317      if(first==it1)break;
318   
319      /* crucial that this check goes after previous break */
320   
321      if(first==it)found=true;
322    }
323    if(first!=it1)return false;
324    return !found;
325  }
326  return true;
327}
328
329template<typename Container>
330inline bool check_different_container(
331  const Container& cont0,const Container& cont1)
332{
333  return &cont0!=&cont1;
334}
335
336} /* namespace multi_index::safe_mode */
337
338} /* namespace multi_index */
339
340} /* namespace boost */
341
342#endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */
343
344/* assertion macros */
345
346#if !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
347#undef BOOST_MULTI_INDEX_SAFE_MODE_ASSERT
348#define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) ((void)0)
349#else
350#if !defined(BOOST_MULTI_INDEX_SAFE_MODE_ASSERT)
351#include <boost/assert.hpp>
352#define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) BOOST_ASSERT(expr)
353#endif
354#endif
355
356#define BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it)                           \
357  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
358    safe_mode::check_valid_iterator(it),                                     \
359    safe_mode::invalid_iterator);
360
361#define BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(it)                 \
362  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
363    safe_mode::check_dereferenceable_iterator(it),                           \
364    safe_mode::not_dereferenceable_iterator);
365
366#define BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(it)                   \
367  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
368    safe_mode::check_incrementable_iterator(it),                             \
369    safe_mode::not_incrementable_iterator);
370
371#define BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(it)                   \
372  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(\
373    safe_mode::check_decrementable_iterator(it),                             \
374    safe_mode::not_decrementable_iterator);
375
376#define BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,cont)                            \
377  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
378    safe_mode::check_is_owner(it,cont),                                      \
379    safe_mode::not_owner);
380
381#define BOOST_MULTI_INDEX_CHECK_SAME_OWNER(it0,it1)                          \
382  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(\
383    safe_mode::check_same_owner(it0,it1),                                    \
384    safe_mode::not_same_owner);
385
386#define BOOST_MULTI_INDEX_CHECK_VALID_RANGE(it0,it1)                         \
387  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
388    safe_mode::check_valid_range(it0,it1),                                   \
389    safe_mode::invalid_range);
390
391#define BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(it,it0,it1)                    \
392  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(\
393    safe_mode::check_outside_range(it,it0,it1),                              \
394    safe_mode::inside_range);
395
396#define BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(cont0,cont1)             \
397  BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(                                        \
398    safe_mode::check_different_container(cont0,cont1),                       \
399    safe_mode::same_container);
400
401#endif
Note: See TracBrowser for help on using the repository browser.