ceph/src/boost/libs/xpressive/include/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   : 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