]>
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 | |
7c673cae | 115 | { |
b32b8144 FG |
116 | typedef shared_ptr<Derived> argument_type; |
117 | typedef bool result_type; | |
118 | ||
7c673cae FG |
119 | filter_self(enable_reference_tracking<Derived> *self) |
120 | : self_(self) | |
121 | { | |
122 | } | |
123 | ||
124 | bool operator ()(shared_ptr<Derived> const &that) const | |
125 | { | |
126 | return this->self_ != that.get(); | |
127 | } | |
128 | ||
129 | private: | |
130 | enable_reference_tracking<Derived> *self_; | |
131 | }; | |
132 | ||
133 | /////////////////////////////////////////////////////////////////////////////// | |
134 | // swap without bringing in std::swap -- must be found by ADL. | |
135 | template<typename T> | |
136 | void adl_swap(T &t1, T &t2) | |
137 | { | |
138 | swap(t1, t2); | |
139 | } | |
140 | ||
141 | /////////////////////////////////////////////////////////////////////////////// | |
142 | // enable_reference_tracking | |
143 | // inherit from this type to enable reference tracking for a type. You can | |
144 | // then use tracking_ptr (below) as a holder for derived objects. | |
145 | // | |
146 | template<typename Derived> | |
147 | struct enable_reference_tracking | |
148 | { | |
149 | typedef std::set<shared_ptr<Derived> > references_type; | |
150 | typedef std::set<weak_ptr<Derived> > dependents_type; | |
151 | ||
152 | void tracking_copy(Derived const &that) | |
153 | { | |
154 | if(&this->derived_() != &that) | |
155 | { | |
156 | this->raw_copy_(that); | |
157 | this->tracking_update(); | |
158 | } | |
159 | } | |
160 | ||
161 | void tracking_clear() | |
162 | { | |
163 | this->raw_copy_(Derived()); | |
164 | } | |
165 | ||
166 | // called automatically as a result of a tracking_copy(). Must be called explicitly | |
167 | // if you change the references without calling tracking_copy(). | |
168 | void tracking_update() | |
169 | { | |
170 | // add "this" as a dependency to all the references | |
171 | this->update_references_(); | |
172 | // notify our dependencies that we have new references | |
173 | this->update_dependents_(); | |
174 | } | |
175 | ||
176 | void track_reference(enable_reference_tracking<Derived> &that) | |
177 | { | |
178 | // avoid some unbounded memory growth in certain circumstances by | |
179 | // opportunistically removing stale dependencies from "that" | |
180 | that.purge_stale_deps_(); | |
181 | // add "that" as a reference | |
182 | this->refs_.insert(that.self_); | |
183 | // also inherit that's references | |
184 | this->refs_.insert(that.refs_.begin(), that.refs_.end()); | |
185 | } | |
186 | ||
187 | long use_count() const | |
188 | { | |
189 | return this->cnt_; | |
190 | } | |
191 | ||
192 | void add_ref() | |
193 | { | |
194 | ++this->cnt_; | |
195 | } | |
196 | ||
197 | void release() | |
198 | { | |
199 | BOOST_ASSERT(0 < this->cnt_); | |
200 | if(0 == --this->cnt_) | |
201 | { | |
202 | this->refs_.clear(); | |
203 | this->self_.reset(); | |
204 | } | |
205 | } | |
206 | ||
207 | //{{AFX_DEBUG | |
208 | #ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
209 | friend std::ostream &operator <<(std::ostream &sout, enable_reference_tracking<Derived> const &that) | |
210 | { | |
211 | that.dump_(sout); | |
212 | return sout; | |
213 | } | |
214 | #endif | |
215 | //}}AFX_DEBUG | |
216 | ||
217 | protected: | |
218 | ||
219 | enable_reference_tracking() | |
220 | : refs_() | |
221 | , deps_() | |
222 | , self_() | |
223 | , cnt_(0) | |
224 | { | |
225 | } | |
226 | ||
227 | enable_reference_tracking(enable_reference_tracking<Derived> const &that) | |
228 | : refs_() | |
229 | , deps_() | |
230 | , self_() | |
231 | , cnt_(0) | |
232 | { | |
233 | this->operator =(that); | |
234 | } | |
235 | ||
236 | enable_reference_tracking<Derived> &operator =(enable_reference_tracking<Derived> const &that) | |
237 | { | |
238 | references_type(that.refs_).swap(this->refs_); | |
239 | return *this; | |
240 | } | |
241 | ||
242 | void swap(enable_reference_tracking<Derived> &that) | |
243 | { | |
244 | this->refs_.swap(that.refs_); | |
245 | } | |
246 | ||
247 | private: | |
248 | friend struct tracking_ptr<Derived>; | |
249 | ||
250 | Derived &derived_() | |
251 | { | |
252 | return *static_cast<Derived *>(this); | |
253 | } | |
254 | ||
255 | void raw_copy_(Derived that) | |
256 | { | |
257 | detail::adl_swap(this->derived_(), that); | |
258 | } | |
259 | ||
260 | bool has_deps_() const | |
261 | { | |
262 | return !this->deps_.empty(); | |
263 | } | |
264 | ||
265 | void update_references_() | |
266 | { | |
267 | typename references_type::iterator cur = this->refs_.begin(); | |
268 | typename references_type::iterator end = this->refs_.end(); | |
269 | for(; cur != end; ++cur) | |
270 | { | |
271 | // for each reference, add this as a dependency | |
272 | (*cur)->track_dependency_(*this); | |
273 | } | |
274 | } | |
275 | ||
276 | void update_dependents_() | |
277 | { | |
278 | // called whenever this regex object changes (i.e., is assigned to). it walks | |
279 | // the list of dependent regexes and updates *their* lists of references, | |
280 | // thereby spreading out the reference counting responsibility evenly. | |
281 | weak_iterator<Derived> cur(this->deps_.begin(), &this->deps_); | |
282 | weak_iterator<Derived> end(this->deps_.end(), &this->deps_); | |
283 | ||
284 | for(; cur != end; ++cur) | |
285 | { | |
286 | (*cur)->track_reference(*this); | |
287 | } | |
288 | } | |
289 | ||
290 | void track_dependency_(enable_reference_tracking<Derived> &dep) | |
291 | { | |
292 | if(this == &dep) // never add ourself as a dependency | |
293 | return; | |
294 | ||
295 | // add dep as a dependency | |
296 | this->deps_.insert(dep.self_); | |
297 | ||
298 | filter_self<Derived> not_self(this); | |
299 | weak_iterator<Derived> begin(dep.deps_.begin(), &dep.deps_); | |
300 | weak_iterator<Derived> end(dep.deps_.end(), &dep.deps_); | |
301 | ||
302 | // also inherit dep's dependencies | |
303 | this->deps_.insert( | |
304 | make_filter_iterator(not_self, begin, end) | |
305 | , make_filter_iterator(not_self, end, end) | |
306 | ); | |
307 | } | |
308 | ||
309 | void purge_stale_deps_() | |
310 | { | |
311 | weak_iterator<Derived> cur(this->deps_.begin(), &this->deps_); | |
312 | weak_iterator<Derived> end(this->deps_.end(), &this->deps_); | |
313 | ||
314 | for(; cur != end; ++cur) | |
315 | ; | |
316 | } | |
317 | ||
318 | //{{AFX_DEBUG | |
319 | #ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
320 | void dump_(std::ostream &sout) const; | |
321 | #endif | |
322 | //}}AFX_DEBUG | |
323 | ||
324 | references_type refs_; | |
325 | dependents_type deps_; | |
326 | shared_ptr<Derived> self_; | |
327 | boost::detail::atomic_count cnt_; | |
328 | }; | |
329 | ||
330 | template<typename Derived> | |
331 | inline void intrusive_ptr_add_ref(enable_reference_tracking<Derived> *p) | |
332 | { | |
333 | p->add_ref(); | |
334 | } | |
335 | ||
336 | template<typename Derived> | |
337 | inline void intrusive_ptr_release(enable_reference_tracking<Derived> *p) | |
338 | { | |
339 | p->release(); | |
340 | } | |
341 | ||
342 | //{{AFX_DEBUG | |
343 | #ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
344 | /////////////////////////////////////////////////////////////////////////////// | |
345 | // dump_ | |
346 | // | |
347 | template<typename Derived> | |
348 | inline void enable_reference_tracking<Derived>::dump_(std::ostream &sout) const | |
349 | { | |
350 | shared_ptr<Derived> this_ = this->self_; | |
351 | sout << "0x" << (void*)this << " cnt=" << this_.use_count()-1 << " refs={"; | |
352 | typename references_type::const_iterator cur1 = this->refs_.begin(); | |
353 | typename references_type::const_iterator end1 = this->refs_.end(); | |
354 | for(; cur1 != end1; ++cur1) | |
355 | { | |
356 | sout << "0x" << (void*)&**cur1 << ','; | |
357 | } | |
358 | sout << "} deps={"; | |
359 | typename dependents_type::const_iterator cur2 = this->deps_.begin(); | |
360 | typename dependents_type::const_iterator end2 = this->deps_.end(); | |
361 | for(; cur2 != end2; ++cur2) | |
362 | { | |
363 | // ericne, 27/nov/05: CW9_4 doesn't like if(shared_ptr x = y) | |
364 | shared_ptr<Derived> dep = cur2->lock(); | |
365 | if(dep.get()) | |
366 | { | |
367 | sout << "0x" << (void*)&*dep << ','; | |
368 | } | |
369 | } | |
370 | sout << '}'; | |
371 | } | |
372 | #endif | |
373 | //}}AFX_DEBUG | |
374 | ||
375 | /////////////////////////////////////////////////////////////////////////////// | |
376 | // tracking_ptr | |
377 | // holder for a reference-tracked type. Does cycle-breaking, lazy initialization | |
378 | // and copy-on-write. TODO: implement move semantics. | |
379 | // | |
380 | template<typename Type> | |
381 | struct tracking_ptr | |
382 | { | |
383 | BOOST_MPL_ASSERT((is_base_and_derived<enable_reference_tracking<Type>, Type>)); | |
384 | typedef Type element_type; | |
385 | ||
386 | tracking_ptr() | |
387 | : impl_() | |
388 | { | |
389 | } | |
390 | ||
391 | tracking_ptr(tracking_ptr<element_type> const &that) | |
392 | : impl_() | |
393 | { | |
394 | this->operator =(that); | |
395 | } | |
396 | ||
397 | tracking_ptr<element_type> &operator =(tracking_ptr<element_type> const &that) | |
398 | { | |
399 | // Note: the copy-and-swap idiom doesn't work here if has_deps_()==true | |
400 | // because it invalidates references to the element_type object. | |
401 | if(this != &that) | |
402 | { | |
403 | if(that) | |
404 | { | |
405 | if(that.has_deps_() || this->has_deps_()) | |
406 | { | |
407 | this->fork_(); // deep copy, forks data if necessary | |
408 | this->impl_->tracking_copy(*that); | |
409 | } | |
410 | else | |
411 | { | |
412 | this->impl_ = that.impl_; // shallow, copy-on-write | |
413 | } | |
414 | } | |
415 | else if(*this) | |
416 | { | |
417 | this->impl_->tracking_clear(); | |
418 | } | |
419 | } | |
420 | return *this; | |
421 | } | |
422 | ||
423 | // NOTE: this does *not* do tracking. Can't provide a non-throwing swap that tracks references | |
424 | void swap(tracking_ptr<element_type> &that) // throw() | |
425 | { | |
426 | this->impl_.swap(that.impl_); | |
427 | } | |
428 | ||
429 | // calling this forces this->impl_ to fork. | |
430 | shared_ptr<element_type> const &get() const | |
431 | { | |
432 | if(intrusive_ptr<element_type> impl = this->fork_()) | |
433 | { | |
434 | this->impl_->tracking_copy(*impl); | |
435 | } | |
436 | return this->impl_->self_; | |
437 | } | |
438 | ||
439 | // smart-pointer operators | |
440 | #if defined(__SUNPRO_CC) && BOOST_WORKAROUND(__SUNPRO_CC, <= 0x530) | |
441 | ||
442 | operator bool() const | |
443 | { | |
444 | return this->impl_; | |
445 | } | |
446 | ||
447 | #else | |
448 | ||
449 | typedef intrusive_ptr<element_type> tracking_ptr::* unspecified_bool_type; | |
450 | ||
451 | operator unspecified_bool_type() const | |
452 | { | |
453 | return this->impl_ ? &tracking_ptr::impl_ : 0; | |
454 | } | |
455 | ||
456 | #endif | |
457 | ||
458 | bool operator !() const | |
459 | { | |
460 | return !this->impl_; | |
461 | } | |
462 | ||
463 | // Since this does not un-share the data, it returns a ptr-to-const | |
464 | element_type const *operator ->() const | |
465 | { | |
466 | return get_pointer(this->impl_); | |
467 | } | |
468 | ||
469 | // Since this does not un-share the data, it returns a ref-to-const | |
470 | element_type const &operator *() const | |
471 | { | |
472 | return *this->impl_; | |
473 | } | |
474 | ||
475 | private: | |
476 | ||
477 | // calling this forces impl_ to fork. | |
478 | intrusive_ptr<element_type> fork_() const | |
479 | { | |
480 | intrusive_ptr<element_type> impl; | |
481 | if(!this->impl_ || 1 != this->impl_->use_count()) | |
482 | { | |
483 | impl = this->impl_; | |
484 | BOOST_ASSERT(!this->has_deps_()); | |
485 | shared_ptr<element_type> simpl(new element_type); | |
486 | this->impl_ = get_pointer(simpl->self_ = simpl); | |
487 | } | |
488 | return impl; | |
489 | } | |
490 | ||
491 | // does anybody have a dependency on us? | |
492 | bool has_deps_() const | |
493 | { | |
494 | return this->impl_ && this->impl_->has_deps_(); | |
495 | } | |
496 | ||
497 | // mutable to allow lazy initialization | |
498 | mutable intrusive_ptr<element_type> impl_; | |
499 | }; | |
500 | ||
501 | }}} // namespace boost::xpressive::detail | |
502 | ||
503 | #endif |