/////////////////////////////////////////////////////////////////////////////// | |
// tracking_ptr.hpp | |
// | |
// Copyright 2008 Eric Niebler. Distributed under the Boost | |
// Software License, Version 1.0. (See accompanying file | |
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
#ifndef BOOST_XPRESSIVE_DETAIL_UTILITY_TRACKING_PTR_HPP_EAN_10_04_2005 | |
#define BOOST_XPRESSIVE_DETAIL_UTILITY_TRACKING_PTR_HPP_EAN_10_04_2005 | |
// MS compatible compilers support #pragma once | |
#if defined(_MSC_VER) && (_MSC_VER >= 1020) | |
# pragma once | |
#endif | |
#ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
# include <iostream> | |
#endif | |
#include <set> | |
#include <functional> | |
#include <boost/config.hpp> | |
#include <boost/assert.hpp> | |
#include <boost/weak_ptr.hpp> | |
#include <boost/shared_ptr.hpp> | |
#include <boost/mpl/assert.hpp> | |
#include <boost/intrusive_ptr.hpp> | |
#include <boost/detail/workaround.hpp> | |
#include <boost/detail/atomic_count.hpp> | |
#include <boost/iterator/iterator_facade.hpp> | |
#include <boost/iterator/filter_iterator.hpp> | |
#include <boost/type_traits/is_base_and_derived.hpp> | |
namespace boost { namespace xpressive { namespace detail | |
{ | |
template<typename Type> | |
struct tracking_ptr; | |
template<typename Derived> | |
struct enable_reference_tracking; | |
/////////////////////////////////////////////////////////////////////////////// | |
// weak_iterator | |
// steps through a set of weak_ptr, converts to shared_ptrs on the fly and | |
// removes from the set the weak_ptrs that have expired. | |
template<typename Derived> | |
struct weak_iterator | |
: iterator_facade | |
< | |
weak_iterator<Derived> | |
, shared_ptr<Derived> const | |
, std::forward_iterator_tag | |
> | |
{ | |
typedef std::set<weak_ptr<Derived> > set_type; | |
typedef typename set_type::iterator base_iterator; | |
weak_iterator() | |
: cur_() | |
, iter_() | |
, set_(0) | |
{ | |
} | |
weak_iterator(base_iterator iter, set_type *set) | |
: cur_() | |
, iter_(iter) | |
, set_(set) | |
{ | |
this->satisfy_(); | |
} | |
private: | |
friend class boost::iterator_core_access; | |
shared_ptr<Derived> const &dereference() const | |
{ | |
return this->cur_; | |
} | |
void increment() | |
{ | |
++this->iter_; | |
this->satisfy_(); | |
} | |
bool equal(weak_iterator<Derived> const &that) const | |
{ | |
return this->iter_ == that.iter_; | |
} | |
void satisfy_() | |
{ | |
while(this->iter_ != this->set_->end()) | |
{ | |
this->cur_ = this->iter_->lock(); | |
if(this->cur_) | |
return; | |
base_iterator tmp = this->iter_++; | |
this->set_->erase(tmp); | |
} | |
this->cur_.reset(); | |
} | |
shared_ptr<Derived> cur_; | |
base_iterator iter_; | |
set_type *set_; | |
}; | |
/////////////////////////////////////////////////////////////////////////////// | |
// filter_self | |
// for use with a filter_iterator to filter a node out of a list of dependencies | |
template<typename Derived> | |
struct filter_self | |
: std::unary_function<shared_ptr<Derived>, bool> | |
{ | |
filter_self(enable_reference_tracking<Derived> *self) | |
: self_(self) | |
{ | |
} | |
bool operator ()(shared_ptr<Derived> const &that) const | |
{ | |
return this->self_ != that.get(); | |
} | |
private: | |
enable_reference_tracking<Derived> *self_; | |
}; | |
/////////////////////////////////////////////////////////////////////////////// | |
// swap without bringing in std::swap -- must be found by ADL. | |
template<typename T> | |
void adl_swap(T &t1, T &t2) | |
{ | |
swap(t1, t2); | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
// enable_reference_tracking | |
// inherit from this type to enable reference tracking for a type. You can | |
// then use tracking_ptr (below) as a holder for derived objects. | |
// | |
template<typename Derived> | |
struct enable_reference_tracking | |
{ | |
typedef std::set<shared_ptr<Derived> > references_type; | |
typedef std::set<weak_ptr<Derived> > dependents_type; | |
void tracking_copy(Derived const &that) | |
{ | |
if(&this->derived_() != &that) | |
{ | |
this->raw_copy_(that); | |
this->tracking_update(); | |
} | |
} | |
void tracking_clear() | |
{ | |
this->raw_copy_(Derived()); | |
} | |
// called automatically as a result of a tracking_copy(). Must be called explicitly | |
// if you change the references without calling tracking_copy(). | |
void tracking_update() | |
{ | |
// add "this" as a dependency to all the references | |
this->update_references_(); | |
// notify our dependencies that we have new references | |
this->update_dependents_(); | |
} | |
void track_reference(enable_reference_tracking<Derived> &that) | |
{ | |
// avoid some unbounded memory growth in certain circumstances by | |
// opportunistically removing stale dependencies from "that" | |
that.purge_stale_deps_(); | |
// add "that" as a reference | |
this->refs_.insert(that.self_); | |
// also inherit that's references | |
this->refs_.insert(that.refs_.begin(), that.refs_.end()); | |
} | |
long use_count() const | |
{ | |
return this->cnt_; | |
} | |
void add_ref() | |
{ | |
++this->cnt_; | |
} | |
void release() | |
{ | |
BOOST_ASSERT(0 < this->cnt_); | |
if(0 == --this->cnt_) | |
{ | |
this->refs_.clear(); | |
this->self_.reset(); | |
} | |
} | |
//{{AFX_DEBUG | |
#ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
friend std::ostream &operator <<(std::ostream &sout, enable_reference_tracking<Derived> const &that) | |
{ | |
that.dump_(sout); | |
return sout; | |
} | |
#endif | |
//}}AFX_DEBUG | |
protected: | |
enable_reference_tracking() | |
: refs_() | |
, deps_() | |
, self_() | |
, cnt_(0) | |
{ | |
} | |
enable_reference_tracking(enable_reference_tracking<Derived> const &that) | |
: refs_() | |
, deps_() | |
, self_() | |
, cnt_(0) | |
{ | |
this->operator =(that); | |
} | |
enable_reference_tracking<Derived> &operator =(enable_reference_tracking<Derived> const &that) | |
{ | |
references_type(that.refs_).swap(this->refs_); | |
return *this; | |
} | |
void swap(enable_reference_tracking<Derived> &that) | |
{ | |
this->refs_.swap(that.refs_); | |
} | |
private: | |
friend struct tracking_ptr<Derived>; | |
Derived &derived_() | |
{ | |
return *static_cast<Derived *>(this); | |
} | |
void raw_copy_(Derived that) | |
{ | |
detail::adl_swap(this->derived_(), that); | |
} | |
bool has_deps_() const | |
{ | |
return !this->deps_.empty(); | |
} | |
void update_references_() | |
{ | |
typename references_type::iterator cur = this->refs_.begin(); | |
typename references_type::iterator end = this->refs_.end(); | |
for(; cur != end; ++cur) | |
{ | |
// for each reference, add this as a dependency | |
(*cur)->track_dependency_(*this); | |
} | |
} | |
void update_dependents_() | |
{ | |
// called whenever this regex object changes (i.e., is assigned to). it walks | |
// the list of dependent regexes and updates *their* lists of references, | |
// thereby spreading out the reference counting responsibility evenly. | |
weak_iterator<Derived> cur(this->deps_.begin(), &this->deps_); | |
weak_iterator<Derived> end(this->deps_.end(), &this->deps_); | |
for(; cur != end; ++cur) | |
{ | |
(*cur)->track_reference(*this); | |
} | |
} | |
void track_dependency_(enable_reference_tracking<Derived> &dep) | |
{ | |
if(this == &dep) // never add ourself as a dependency | |
return; | |
// add dep as a dependency | |
this->deps_.insert(dep.self_); | |
filter_self<Derived> not_self(this); | |
weak_iterator<Derived> begin(dep.deps_.begin(), &dep.deps_); | |
weak_iterator<Derived> end(dep.deps_.end(), &dep.deps_); | |
// also inherit dep's dependencies | |
this->deps_.insert( | |
make_filter_iterator(not_self, begin, end) | |
, make_filter_iterator(not_self, end, end) | |
); | |
} | |
void purge_stale_deps_() | |
{ | |
weak_iterator<Derived> cur(this->deps_.begin(), &this->deps_); | |
weak_iterator<Derived> end(this->deps_.end(), &this->deps_); | |
for(; cur != end; ++cur) | |
; | |
} | |
//{{AFX_DEBUG | |
#ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
void dump_(std::ostream &sout) const; | |
#endif | |
//}}AFX_DEBUG | |
references_type refs_; | |
dependents_type deps_; | |
shared_ptr<Derived> self_; | |
boost::detail::atomic_count cnt_; | |
}; | |
template<typename Derived> | |
inline void intrusive_ptr_add_ref(enable_reference_tracking<Derived> *p) | |
{ | |
p->add_ref(); | |
} | |
template<typename Derived> | |
inline void intrusive_ptr_release(enable_reference_tracking<Derived> *p) | |
{ | |
p->release(); | |
} | |
//{{AFX_DEBUG | |
#ifdef BOOST_XPRESSIVE_DEBUG_TRACKING_POINTER | |
/////////////////////////////////////////////////////////////////////////////// | |
// dump_ | |
// | |
template<typename Derived> | |
inline void enable_reference_tracking<Derived>::dump_(std::ostream &sout) const | |
{ | |
shared_ptr<Derived> this_ = this->self_; | |
sout << "0x" << (void*)this << " cnt=" << this_.use_count()-1 << " refs={"; | |
typename references_type::const_iterator cur1 = this->refs_.begin(); | |
typename references_type::const_iterator end1 = this->refs_.end(); | |
for(; cur1 != end1; ++cur1) | |
{ | |
sout << "0x" << (void*)&**cur1 << ','; | |
} | |
sout << "} deps={"; | |
typename dependents_type::const_iterator cur2 = this->deps_.begin(); | |
typename dependents_type::const_iterator end2 = this->deps_.end(); | |
for(; cur2 != end2; ++cur2) | |
{ | |
// ericne, 27/nov/05: CW9_4 doesn't like if(shared_ptr x = y) | |
shared_ptr<Derived> dep = cur2->lock(); | |
if(dep.get()) | |
{ | |
sout << "0x" << (void*)&*dep << ','; | |
} | |
} | |
sout << '}'; | |
} | |
#endif | |
//}}AFX_DEBUG | |
/////////////////////////////////////////////////////////////////////////////// | |
// tracking_ptr | |
// holder for a reference-tracked type. Does cycle-breaking, lazy initialization | |
// and copy-on-write. TODO: implement move semantics. | |
// | |
template<typename Type> | |
struct tracking_ptr | |
{ | |
BOOST_MPL_ASSERT((is_base_and_derived<enable_reference_tracking<Type>, Type>)); | |
typedef Type element_type; | |
tracking_ptr() | |
: impl_() | |
{ | |
} | |
tracking_ptr(tracking_ptr<element_type> const &that) | |
: impl_() | |
{ | |
this->operator =(that); | |
} | |
tracking_ptr<element_type> &operator =(tracking_ptr<element_type> const &that) | |
{ | |
// Note: the copy-and-swap idiom doesn't work here if has_deps_()==true | |
// because it invalidates references to the element_type object. | |
if(this != &that) | |
{ | |
if(that) | |
{ | |
if(that.has_deps_() || this->has_deps_()) | |
{ | |
this->fork_(); // deep copy, forks data if necessary | |
this->impl_->tracking_copy(*that); | |
} | |
else | |
{ | |
this->impl_ = that.impl_; // shallow, copy-on-write | |
} | |
} | |
else if(*this) | |
{ | |
this->impl_->tracking_clear(); | |
} | |
} | |
return *this; | |
} | |
// NOTE: this does *not* do tracking. Can't provide a non-throwing swap that tracks references | |
void swap(tracking_ptr<element_type> &that) // throw() | |
{ | |
this->impl_.swap(that.impl_); | |
} | |
// calling this forces this->impl_ to fork. | |
shared_ptr<element_type> const &get() const | |
{ | |
if(intrusive_ptr<element_type> impl = this->fork_()) | |
{ | |
this->impl_->tracking_copy(*impl); | |
} | |
return this->impl_->self_; | |
} | |
#if defined(__SUNPRO_CC) && BOOST_WORKAROUND(__SUNPRO_CC, <= 0x530) | |
typedef bool unspecified_bool_type; | |
#else | |
typedef typename intrusive_ptr<element_type>::unspecified_bool_type unspecified_bool_type; | |
#endif | |
// smart-pointer operators | |
operator unspecified_bool_type() const | |
{ | |
return this->impl_; | |
} | |
bool operator !() const | |
{ | |
return !this->impl_; | |
} | |
// Since this does not un-share the data, it returns a ptr-to-const | |
element_type const *operator ->() const | |
{ | |
return get_pointer(this->impl_); | |
} | |
// Since this does not un-share the data, it returns a ref-to-const | |
element_type const &operator *() const | |
{ | |
return *this->impl_; | |
} | |
private: | |
// calling this forces impl_ to fork. | |
intrusive_ptr<element_type> fork_() const | |
{ | |
intrusive_ptr<element_type> impl; | |
if(!this->impl_ || 1 != this->impl_->use_count()) | |
{ | |
impl = this->impl_; | |
BOOST_ASSERT(!this->has_deps_()); | |
shared_ptr<element_type> simpl(new element_type); | |
this->impl_ = get_pointer(simpl->self_ = simpl); | |
} | |
return impl; | |
} | |
// does anybody have a dependency on us? | |
bool has_deps_() const | |
{ | |
return this->impl_ && this->impl_->has_deps_(); | |
} | |
// mutable to allow lazy initialization | |
mutable intrusive_ptr<element_type> impl_; | |
}; | |
}}} // namespace boost::xpressive::detail | |
#endif |