ceph/src/boost/boost/xpressive/detail/utility/tracking_ptr.hpp

   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 {
 116     typedef shared_ptr<Derived> argument_type;
 117     typedef bool result_type;
 118
 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