|
|
Boost : |
From: Greg Colvin (gcolvin_at_[hidden])
Date: 2000-01-30 14:53:21
> Greg,
>
> I really think it's time to trot out your new implementation which uses
> deque so we can test against that (I'm thinking the allocation cost will be
> much lower since the deque works like a pool allocator). If you need help
> finishing it, please call on me.
>
> -Dave
I've appended cyclic_ptr.hpp and cyclic_ptr.cpp, which compile with EDG's latest,
and are not conditionalized for anything else. Define NDEBUG for performance
tests, but note that I haven't yet tuned the allocation.
////////////////////////////////////////////////////////////////////////////////
// cyclic_ptr.cpp
namespace boost {
template<typename> struct weak_ptr;
/////////////////////////////////////////////////////////////////////////////
// Each handle refers to a deleter_base object, and cyclic_ptr constructor
// takes an optional deleter argument. Derive from deleter to customize
// destroy function, but don't mess with recycle.
struct deleter_base {
virtual void destroy(void*)=0;
virtual void recycle(void*)=0;
};
template<typename T> struct deleter : deleter_base {
void destroy(void* p) { delete(reinterpret_cast<T*>(p)); }
void recycle(void* p) { if (T* q = reinterpret_cast<T*>(p)) *q = *q; }
};
/////////////////////////////////////////////////////////////////////////////
// Recycler handle class for cyclic_ptr and weak_ptr.
// Collect cycles of cyclic_ptr by calling recycler::recycle().
struct recycler {
static void recycle() throw();
private:
template<typename> friend struct recyclable_base;
template<typename> friend struct cyclic_ptr;
template<typename> friend struct weak_ptr;
recycler() : p(0),n(0),n_weak(0),action(0) {}
void* p;
long n, n_weak;
deleter_base* action;
void do_it();
void decrement();
void decrement_weak();
static recycler* alloc(void*,deleter_base*);
static void free(recycler*);
};
/////////////////////////////////////////////////////////////////////////////
// Base class for cyclic_ptr and weak_ptr.
// Initializes handle with appropriate deleter.
template<typename T> class recyclable_base {
template<typename> friend struct cyclic_ptr;
template<typename> friend struct weak_ptr;
private:
recycler* ph;
T* p;
recycler* new_handle(T* q,deleter_base* d) { return recycler::alloc(q,d);}
static deleter<T>& default_deleter() { static deleter<T> r; return r; }
};
/////////////////////////////////////////////////////////////////////////////
// The object pointed to is deleted when the last cyclic_ptr pointing to it
// is destroyed, or when a recycler::recycle() call finds no cyclic_ptr to
// the object outside a cycle.
template<typename T> struct cyclic_ptr : recyclable_base<T> {
typedef T element_type;
long use_count() const throw() { return ph->n; }
bool unique() const throw() { return use_count() == 1; }
explicit
cyclic_ptr(T* q=0,deleter<T>& r=default_deleter()) {
p = q, ph = new_handle(q,&r), ph->n = 1;
}
cyclic_ptr(const cyclic_ptr& r) throw() {
p = r.p, ph = r.ph, ++ph->n;
}
~cyclic_ptr() { ph->decrement(); }
cyclic_ptr& operator=(const cyclic_ptr& r) throw() {
copy(r);
return *this;
}
template<typename U> cyclic_ptr(const cyclic_ptr<U>& r) throw() {
p = r.p, ph = r.ph, ++ph->n;
}
template<typename U> cyclic_ptr& operator=(const cyclic_ptr<U>& r) throw() {
copy(r);
return *this;
}
template<typename U> cyclic_ptr(std::auto_ptr<U>& r) {
p = r.release(), ph = new_handle(p,&default_deleter()), ph->n = 1;
}
template<typename U> cyclic_ptr& operator=(std::auto_ptr<U>& r) {
p = r.release(), ph = new_handle(p,&default_deleter()), ph->n = 1;
return *this;
}
template<typename U> cyclic_ptr(const weak_ptr<U>&) throw();
template<typename U> cyclic_ptr& operator=(const weak_ptr<U>&) throw();
void reset(T* p=0,deleter<T>& r=default_deleter()) {
if (--ph->n == 0)
free(ph);
ph = new_handle(p,&r), ph->n = 1;
}
T* get() const throw() { return p; }
T& operator*() const throw() { return *get(); }
T* operator->() const throw() { return get(); }
operator T*() const throw() { return get(); }
private:
template<typename U> void copy(const recyclable_base<U>&);
};
/////////////////////////////////////////////////////////////////////////////
// A weak_ptr does not prevent a shared object from being destroyed, but
// when it is destroyed weak_ptr::get() returns 0.
template<typename T> struct weak_ptr : recyclable_base<T> {
typedef T element_type;
weak_ptr() { p = 0, ph = new_handle(0,0), ph->n_weak = 1; }
weak_ptr(const weak_ptr& r) throw() { p = r.p, ph = r.ph, ++ph->n_weak; }
~weak_ptr() { if (ph) ph->decrement_weak(); }
weak_ptr& operator=(const weak_ptr& r) throw() {
copy(r);
return *this;
}
template<typename U> weak_ptr(const weak_ptr<U>& r) throw() {
p = r.p, ph = r.ph, ++ph->n_weak;
}
template<typename U> weak_ptr& operator=(const weak_ptr<U>& r) throw() {
copy(r);
return *this;
}
template<typename U> weak_ptr(const cyclic_ptr<U>& r) throw() {
p = r.p, ph = r.ph, ++ph->n_weak;
}
template<typename U> weak_ptr& operator=(const cyclic_ptr<U>& r) throw() {
copy(r);
return *this;
}
T* get() const throw() {
return ph->n ? p : 0; }
T& operator*() const throw() { return *get(); }
T* operator->() const throw() { return get(); }
operator T*() const throw() { return get(); }
private:
template<typename U> void copy(const recyclable_base<U>&);
};
template<typename T> template<typename U>
inline cyclic_ptr<T>::cyclic_ptr(const weak_ptr<U>& r) throw() {
p = r.p, ph = r.ph, ++ph->n;
}
template<typename T> template<typename U>
cyclic_ptr<T>& cyclic_ptr<T>::operator=(const weak_ptr<U>& r) throw() {
copy(r);
return *this;
}
}
////////////////////////////////////////////////////////////////////////////////
// cyclic_ptr.cpp
#include <cyclic_ptr.hpp>
#include <memory>
#include <deque>
#ifndef NDEBUG
#include <set>
#endif
#include <cassert>
namespace boost {
namespace {
enum { SWEEP, MARK, SCAN, DONE } phase = DONE;
std::deque<recycler> handles;
recycler* free_handle = 0;
#ifndef NDEBUG
std::set<void*> no_duplicates;
#endif
}
// maintain pool of available handles in a deque
recycler* recycler::alloc(void* p,deleter_base* action) {
assert(!p || no_duplicates.insert(p).second == true);
recycler* ph;
if (free_handle) {
ph = free_handle;
free_handle = reinterpret_cast<recycler*>(ph->p);
} else {
handles.push_back(recycler());
ph = &*(handles.end() - 1);
}
ph->p = p;
ph->action = action;
return ph;
}
void recycler::free(recycler* ph) {
if (ph->p) {
assert(no_duplicates.erase(ph->p) == 1);
assert(ph->n == 0);
ph->action->destroy(ph->p);
ph->p = 0;
}
if (ph->n_weak == 0) {
ph->p = free_handle;
free_handle = ph;
}
ph->action = 0;
}
// traverse all handles in deque three times to collect garbage
void recycler::recycle() throw() {
std::deque<recycler>::iterator i, end=handles.end();
// reduce counts to find root pointers
phase = SCAN;
for (i=handles.begin(); i != end; ++i)
if (i->action)
i->action->recycle(i->p);
// recursively mark all handles reachable from roots
phase = MARK;
for (i=handles.begin(); i != end; ++i)
if (i->action && i->n > 0)
i->action->recycle(i->p);
// free unreachable objects and restore counts for the rest
phase = SWEEP;
for (i=handles.begin(); i != end; ++i)
if (i->action)
if (i->n == 0)
free(&*i);
else
i->action->recycle(i->p);
phase = DONE;
}
void recycler::do_it() {
switch (phase) {
case SCAN:
--n; // reduce count
break;
case MARK:
n = -1; // mark as root or reachable from root
assert(action);
action->recycle(p); // recurse for cyclic_ptr members of this
break;
case SWEEP:
if (n < 0)
n = 1; // restore count for marked object
else if (n > 0)
++n; // restore count
break;
case DONE:
break;
}
}
void recycler::decrement() {
if (phase != SWEEP && --n == 0)
free(this);
}
void recycler::decrement_weak() {
if (phase != SWEEP && --n_weak == 0 && n == 0)
free(this);
}
template<typename T> template<typename U>
void cyclic_ptr<T>::copy(const recyclable_base<U>& r) {
if (ph != r.ph) {
this->~cyclic_ptr();
p = r.p;
ph = r.ph;
++ph->n;
} else
ph->do_it(); // has no effect except during recycler::recycle()
}
template<typename T> template<typename U>
void weak_ptr<T>::copy(const recyclable_base<U>& r) {
this->~weak_ptr();
p = r.p;
ph = r.ph;
++ph->n_weak;
}
}
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk