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