]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /////////////////////////////////////////////////////////////////////////////// |
2 | // tracking_ptr.hpp | |
3 | // | |
4 | // Copyright 2008 Eric Niebler. Distributed under the Boost | |
5 | // Software License, Version 1.0. (See accompanying file | |
6 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | #ifndef BOOST_XPRESSIVE_DETAIL_UTILITY_TRACKING_PTR_HPP_EAN_10_04_2005 | |
9 | #define BOOST_XPRESSIVE_DETAIL_UTILITY_TRACKING_PTR_HPP_EAN_10_04_2005 | |
10 | ||
11 | // MS compatible compilers support #pragma once | |
12 | #if defined(_MSC_VER) | |
13 | # pragma once | |
14 | #endif | |
15 | ||
16 | #ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
17 | # include <iostream> | |
18 | #endif | |
19 | #include <set> | |
20 | #include <functional> | |
21 | #include <boost/config.hpp> | |
22 | #include <boost/assert.hpp> | |
23 | #include <boost/weak_ptr.hpp> | |
24 | #include <boost/shared_ptr.hpp> | |
25 | #include <boost/mpl/assert.hpp> | |
26 | #include <boost/intrusive_ptr.hpp> | |
27 | #include <boost/detail/workaround.hpp> | |
28 | #include <boost/detail/atomic_count.hpp> | |
29 | #include <boost/iterator/iterator_facade.hpp> | |
30 | #include <boost/iterator/filter_iterator.hpp> | |
31 | #include <boost/type_traits/is_base_and_derived.hpp> | |
32 | ||
33 | namespace boost { namespace xpressive { namespace detail | |
34 | { | |
35 | ||
36 | template<typename Type> | |
37 | struct tracking_ptr; | |
38 | ||
39 | template<typename Derived> | |
40 | struct enable_reference_tracking; | |
41 | ||
42 | /////////////////////////////////////////////////////////////////////////////// | |
43 | // weak_iterator | |
44 | // steps through a set of weak_ptr, converts to shared_ptrs on the fly and | |
45 | // removes from the set the weak_ptrs that have expired. | |
46 | template<typename Derived> | |
47 | struct weak_iterator | |
48 | : iterator_facade | |
49 | < | |
50 | weak_iterator<Derived> | |
51 | , shared_ptr<Derived> const | |
52 | , std::forward_iterator_tag | |
53 | > | |
54 | { | |
55 | typedef std::set<weak_ptr<Derived> > set_type; | |
56 | typedef typename set_type::iterator base_iterator; | |
57 | ||
58 | weak_iterator() | |
59 | : cur_() | |
60 | , iter_() | |
61 | , set_(0) | |
62 | { | |
63 | } | |
64 | ||
65 | weak_iterator(base_iterator iter, set_type *set) | |
66 | : cur_() | |
67 | , iter_(iter) | |
68 | , set_(set) | |
69 | { | |
70 | this->satisfy_(); | |
71 | } | |
72 | ||
73 | private: | |
74 | friend class boost::iterator_core_access; | |
75 | ||
76 | shared_ptr<Derived> const &dereference() const | |
77 | { | |
78 | return this->cur_; | |
79 | } | |
80 | ||
81 | void increment() | |
82 | { | |
83 | ++this->iter_; | |
84 | this->satisfy_(); | |
85 | } | |
86 | ||
87 | bool equal(weak_iterator<Derived> const &that) const | |
88 | { | |
89 | return this->iter_ == that.iter_; | |
90 | } | |
91 | ||
92 | void satisfy_() | |
93 | { | |
94 | while(this->iter_ != this->set_->end()) | |
95 | { | |
96 | this->cur_ = this->iter_->lock(); | |
97 | if(this->cur_) | |
98 | return; | |
99 | base_iterator tmp = this->iter_++; | |
100 | this->set_->erase(tmp); | |
101 | } | |
102 | this->cur_.reset(); | |
103 | } | |
104 | ||
105 | shared_ptr<Derived> cur_; | |
106 | base_iterator iter_; | |
107 | set_type *set_; | |
108 | }; | |
109 | ||
110 | /////////////////////////////////////////////////////////////////////////////// | |
111 | // filter_self | |
112 | // for use with a filter_iterator to filter a node out of a list of dependencies | |
113 | template<typename Derived> | |
114 | struct filter_self | |
115 | : std::unary_function<shared_ptr<Derived>, bool> | |
116 | { | |
117 | filter_self(enable_reference_tracking<Derived> *self) | |
118 | : self_(self) | |
119 | { | |
120 | } | |
121 | ||
122 | bool operator ()(shared_ptr<Derived> const &that) const | |
123 | { | |
124 | return this->self_ != that.get(); | |
125 | } | |
126 | ||
127 | private: | |
128 | enable_reference_tracking<Derived> *self_; | |
129 | }; | |
130 | ||
131 | /////////////////////////////////////////////////////////////////////////////// | |
132 | // swap without bringing in std::swap -- must be found by ADL. | |
133 | template<typename T> | |
134 | void adl_swap(T &t1, T &t2) | |
135 | { | |
136 | swap(t1, t2); | |
137 | } | |
138 | ||
139 | /////////////////////////////////////////////////////////////////////////////// | |
140 | // enable_reference_tracking | |
141 | // inherit from this type to enable reference tracking for a type. You can | |
142 | // then use tracking_ptr (below) as a holder for derived objects. | |
143 | // | |
144 | template<typename Derived> | |
145 | struct enable_reference_tracking | |
146 | { | |
147 | typedef std::set<shared_ptr<Derived> > references_type; | |
148 | typedef std::set<weak_ptr<Derived> > dependents_type; | |
149 | ||
150 | void tracking_copy(Derived const &that) | |
151 | { | |
152 | if(&this->derived_() != &that) | |
153 | { | |
154 | this->raw_copy_(that); | |
155 | this->tracking_update(); | |
156 | } | |
157 | } | |
158 | ||
159 | void tracking_clear() | |
160 | { | |
161 | this->raw_copy_(Derived()); | |
162 | } | |
163 | ||
164 | // called automatically as a result of a tracking_copy(). Must be called explicitly | |
165 | // if you change the references without calling tracking_copy(). | |
166 | void tracking_update() | |
167 | { | |
168 | // add "this" as a dependency to all the references | |
169 | this->update_references_(); | |
170 | // notify our dependencies that we have new references | |
171 | this->update_dependents_(); | |
172 | } | |
173 | ||
174 | void track_reference(enable_reference_tracking<Derived> &that) | |
175 | { | |
176 | // avoid some unbounded memory growth in certain circumstances by | |
177 | // opportunistically removing stale dependencies from "that" | |
178 | that.purge_stale_deps_(); | |
179 | // add "that" as a reference | |
180 | this->refs_.insert(that.self_); | |
181 | // also inherit that's references | |
182 | this->refs_.insert(that.refs_.begin(), that.refs_.end()); | |
183 | } | |
184 | ||
185 | long use_count() const | |
186 | { | |
187 | return this->cnt_; | |
188 | } | |
189 | ||
190 | void add_ref() | |
191 | { | |
192 | ++this->cnt_; | |
193 | } | |
194 | ||
195 | void release() | |
196 | { | |
197 | BOOST_ASSERT(0 < this->cnt_); | |
198 | if(0 == --this->cnt_) | |
199 | { | |
200 | this->refs_.clear(); | |
201 | this->self_.reset(); | |
202 | } | |
203 | } | |
204 | ||
205 | //{{AFX_DEBUG | |
206 | #ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
207 | friend std::ostream &operator <<(std::ostream &sout, enable_reference_tracking<Derived> const &that) | |
208 | { | |
209 | that.dump_(sout); | |
210 | return sout; | |
211 | } | |
212 | #endif | |
213 | //}}AFX_DEBUG | |
214 | ||
215 | protected: | |
216 | ||
217 | enable_reference_tracking() | |
218 | : refs_() | |
219 | , deps_() | |
220 | , self_() | |
221 | , cnt_(0) | |
222 | { | |
223 | } | |
224 | ||
225 | enable_reference_tracking(enable_reference_tracking<Derived> const &that) | |
226 | : refs_() | |
227 | , deps_() | |
228 | , self_() | |
229 | , cnt_(0) | |
230 | { | |
231 | this->operator =(that); | |
232 | } | |
233 | ||
234 | enable_reference_tracking<Derived> &operator =(enable_reference_tracking<Derived> const &that) | |
235 | { | |
236 | references_type(that.refs_).swap(this->refs_); | |
237 | return *this; | |
238 | } | |
239 | ||
240 | void swap(enable_reference_tracking<Derived> &that) | |
241 | { | |
242 | this->refs_.swap(that.refs_); | |
243 | } | |
244 | ||
245 | private: | |
246 | friend struct tracking_ptr<Derived>; | |
247 | ||
248 | Derived &derived_() | |
249 | { | |
250 | return *static_cast<Derived *>(this); | |
251 | } | |
252 | ||
253 | void raw_copy_(Derived that) | |
254 | { | |
255 | detail::adl_swap(this->derived_(), that); | |
256 | } | |
257 | ||
258 | bool has_deps_() const | |
259 | { | |
260 | return !this->deps_.empty(); | |
261 | } | |
262 | ||
263 | void update_references_() | |
264 | { | |
265 | typename references_type::iterator cur = this->refs_.begin(); | |
266 | typename references_type::iterator end = this->refs_.end(); | |
267 | for(; cur != end; ++cur) | |
268 | { | |
269 | // for each reference, add this as a dependency | |
270 | (*cur)->track_dependency_(*this); | |
271 | } | |
272 | } | |
273 | ||
274 | void update_dependents_() | |
275 | { | |
276 | // called whenever this regex object changes (i.e., is assigned to). it walks | |
277 | // the list of dependent regexes and updates *their* lists of references, | |
278 | // thereby spreading out the reference counting responsibility evenly. | |
279 | weak_iterator<Derived> cur(this->deps_.begin(), &this->deps_); | |
280 | weak_iterator<Derived> end(this->deps_.end(), &this->deps_); | |
281 | ||
282 | for(; cur != end; ++cur) | |
283 | { | |
284 | (*cur)->track_reference(*this); | |
285 | } | |
286 | } | |
287 | ||
288 | void track_dependency_(enable_reference_tracking<Derived> &dep) | |
289 | { | |
290 | if(this == &dep) // never add ourself as a dependency | |
291 | return; | |
292 | ||
293 | // add dep as a dependency | |
294 | this->deps_.insert(dep.self_); | |
295 | ||
296 | filter_self<Derived> not_self(this); | |
297 | weak_iterator<Derived> begin(dep.deps_.begin(), &dep.deps_); | |
298 | weak_iterator<Derived> end(dep.deps_.end(), &dep.deps_); | |
299 | ||
300 | // also inherit dep's dependencies | |
301 | this->deps_.insert( | |
302 | make_filter_iterator(not_self, begin, end) | |
303 | , make_filter_iterator(not_self, end, end) | |
304 | ); | |
305 | } | |
306 | ||
307 | void purge_stale_deps_() | |
308 | { | |
309 | weak_iterator<Derived> cur(this->deps_.begin(), &this->deps_); | |
310 | weak_iterator<Derived> end(this->deps_.end(), &this->deps_); | |
311 | ||
312 | for(; cur != end; ++cur) | |
313 | ; | |
314 | } | |
315 | ||
316 | //{{AFX_DEBUG | |
317 | #ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
318 | void dump_(std::ostream &sout) const; | |
319 | #endif | |
320 | //}}AFX_DEBUG | |
321 | ||
322 | references_type refs_; | |
323 | dependents_type deps_; | |
324 | shared_ptr<Derived> self_; | |
325 | boost::detail::atomic_count cnt_; | |
326 | }; | |
327 | ||
328 | template<typename Derived> | |
329 | inline void intrusive_ptr_add_ref(enable_reference_tracking<Derived> *p) | |
330 | { | |
331 | p->add_ref(); | |
332 | } | |
333 | ||
334 | template<typename Derived> | |
335 | inline void intrusive_ptr_release(enable_reference_tracking<Derived> *p) | |
336 | { | |
337 | p->release(); | |
338 | } | |
339 | ||
340 | //{{AFX_DEBUG | |
341 | #ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
342 | /////////////////////////////////////////////////////////////////////////////// | |
343 | // dump_ | |
344 | // | |
345 | template<typename Derived> | |
346 | inline void enable_reference_tracking<Derived>::dump_(std::ostream &sout) const | |
347 | { | |
348 | shared_ptr<Derived> this_ = this->self_; | |
349 | sout << "0x" << (void*)this << " cnt=" << this_.use_count()-1 << " refs={"; | |
350 | typename references_type::const_iterator cur1 = this->refs_.begin(); | |
351 | typename references_type::const_iterator end1 = this->refs_.end(); | |
352 | for(; cur1 != end1; ++cur1) | |
353 | { | |
354 | sout << "0x" << (void*)&**cur1 << ','; | |
355 | } | |
356 | sout << "} deps={"; | |
357 | typename dependents_type::const_iterator cur2 = this->deps_.begin(); | |
358 | typename dependents_type::const_iterator end2 = this->deps_.end(); | |
359 | for(; cur2 != end2; ++cur2) | |
360 | { | |
361 | // ericne, 27/nov/05: CW9_4 doesn't like if(shared_ptr x = y) | |
362 | shared_ptr<Derived> dep = cur2->lock(); | |
363 | if(dep.get()) | |
364 | { | |
365 | sout << "0x" << (void*)&*dep << ','; | |
366 | } | |
367 | } | |
368 | sout << '}'; | |
369 | } | |
370 | #endif | |
371 | //}}AFX_DEBUG | |
372 | ||
373 | /////////////////////////////////////////////////////////////////////////////// | |
374 | // tracking_ptr | |
375 | // holder for a reference-tracked type. Does cycle-breaking, lazy initialization | |
376 | // and copy-on-write. TODO: implement move semantics. | |
377 | // | |
378 | template<typename Type> | |
379 | struct tracking_ptr | |
380 | { | |
381 | BOOST_MPL_ASSERT((is_base_and_derived<enable_reference_tracking<Type>, Type>)); | |
382 | typedef Type element_type; | |
383 | ||
384 | tracking_ptr() | |
385 | : impl_() | |
386 | { | |
387 | } | |
388 | ||
389 | tracking_ptr(tracking_ptr<element_type> const &that) | |
390 | : impl_() | |
391 | { | |
392 | this->operator =(that); | |
393 | } | |
394 | ||
395 | tracking_ptr<element_type> &operator =(tracking_ptr<element_type> const &that) | |
396 | { | |
397 | // Note: the copy-and-swap idiom doesn't work here if has_deps_()==true | |
398 | // because it invalidates references to the element_type object. | |
399 | if(this != &that) | |
400 | { | |
401 | if(that) | |
402 | { | |
403 | if(that.has_deps_() || this->has_deps_()) | |
404 | { | |
405 | this->fork_(); // deep copy, forks data if necessary | |
406 | this->impl_->tracking_copy(*that); | |
407 | } | |
408 | else | |
409 | { | |
410 | this->impl_ = that.impl_; // shallow, copy-on-write | |
411 | } | |
412 | } | |
413 | else if(*this) | |
414 | { | |
415 | this->impl_->tracking_clear(); | |
416 | } | |
417 | } | |
418 | return *this; | |
419 | } | |
420 | ||
421 | // NOTE: this does *not* do tracking. Can't provide a non-throwing swap that tracks references | |
422 | void swap(tracking_ptr<element_type> &that) // throw() | |
423 | { | |
424 | this->impl_.swap(that.impl_); | |
425 | } | |
426 | ||
427 | // calling this forces this->impl_ to fork. | |
428 | shared_ptr<element_type> const &get() const | |
429 | { | |
430 | if(intrusive_ptr<element_type> impl = this->fork_()) | |
431 | { | |
432 | this->impl_->tracking_copy(*impl); | |
433 | } | |
434 | return this->impl_->self_; | |
435 | } | |
436 | ||
437 | // smart-pointer operators | |
438 | #if defined(__SUNPRO_CC) && BOOST_WORKAROUND(__SUNPRO_CC, <= 0x530) | |
439 | ||
440 | operator bool() const | |
441 | { | |
442 | return this->impl_; | |
443 | } | |
444 | ||
445 | #else | |
446 | ||
447 | typedef intrusive_ptr<element_type> tracking_ptr::* unspecified_bool_type; | |
448 | ||
449 | operator unspecified_bool_type() const | |
450 | { | |
451 | return this->impl_ ? &tracking_ptr::impl_ : 0; | |
452 | } | |
453 | ||
454 | #endif | |
455 | ||
456 | bool operator !() const | |
457 | { | |
458 | return !this->impl_; | |
459 | } | |
460 | ||
461 | // Since this does not un-share the data, it returns a ptr-to-const | |
462 | element_type const *operator ->() const | |
463 | { | |
464 | return get_pointer(this->impl_); | |
465 | } | |
466 | ||
467 | // Since this does not un-share the data, it returns a ref-to-const | |
468 | element_type const &operator *() const | |
469 | { | |
470 | return *this->impl_; | |
471 | } | |
472 | ||
473 | private: | |
474 | ||
475 | // calling this forces impl_ to fork. | |
476 | intrusive_ptr<element_type> fork_() const | |
477 | { | |
478 | intrusive_ptr<element_type> impl; | |
479 | if(!this->impl_ || 1 != this->impl_->use_count()) | |
480 | { | |
481 | impl = this->impl_; | |
482 | BOOST_ASSERT(!this->has_deps_()); | |
483 | shared_ptr<element_type> simpl(new element_type); | |
484 | this->impl_ = get_pointer(simpl->self_ = simpl); | |
485 | } | |
486 | return impl; | |
487 | } | |
488 | ||
489 | // does anybody have a dependency on us? | |
490 | bool has_deps_() const | |
491 | { | |
492 | return this->impl_ && this->impl_->has_deps_(); | |
493 | } | |
494 | ||
495 | // mutable to allow lazy initialization | |
496 | mutable intrusive_ptr<element_type> impl_; | |
497 | }; | |
498 | ||
499 | }}} // namespace boost::xpressive::detail | |
500 | ||
501 | #endif |