How is the std::tr1::shared_ptr implemented?

I've been thinking about using shared pointers, and I know how to implement one myself--Don't want to do it, so I'm trying std::tr1::shared_ptr,and I have couple of questions...

How is the reference counting implemented? Does it use a doubly linked list? (Btw, I've already googled, but I can't find anything reliable.)

Are there any pitfalls for using the std::tr1::shared_ptr?

Solution

shared_ptr must manage a reference counter and the carrying of a deleter functor that is deduced by the type of the object given at initialization.

The shared_ptr class typically hosts two members: a T* (that is returned by operator-> and dereferenced in operator*) and a aux* where aux is a inner abstract class that contains:

a counter (incremented / decremented upon copy-assign / destroy)
whatever is needed to make increment / decrement atomic (not needed if specific platform atomic INC/DEC is available)
an abstract virtual destroy()=0;
a virtual destructor.

Such aux class (the actual name depends on the implementation) is derived by a family of templatized classes (parametrized on the type given by the explicit constructor, say U derived from T), that add:

a pointer to the object (same as T*, but with the actual type: this is needed to properly manage all the cases of T being a base for whatever U having multiple T in the derivation hierarchy)
a copy of the deletor object given as deletion policy to the explicit constructor (or the default deletor just doing delete p, where p is the U* above)
the override of the destroy method, calling the deleter functor.

A simplified sketch can be this one:

template<class T>
class shared_ptr
{
    struct aux
    {
        unsigned count;

        aux() :count(1) {}
        virtual void destroy()=0;
        virtual ~aux() {} //must be polymorphic
    };

    template<class U, class Deleter>
    struct auximpl: public aux
    {
        U* p;
        Deleter d;

        auximpl(U* pu, Deleter x) :p(pu), d(x) {}
        virtual void destroy() { d(p); } 
    };

    template<class U>
    struct default_deleter
    {
        void operator()(U* p) const { delete p; }
    };

    aux* pa;
    T* pt;

    void inc() { if(pa) interlocked_inc(pa->count); }

    void dec() 
    { 
        if(pa && !interlocked_dec(pa->count)) 
        {  pa->destroy(); delete pa; }
    }

public:

    shared_ptr() :pa(), pt() {}

    template<class U, class Deleter>
    shared_ptr(U* pu, Deleter d) :pa(new auximpl<U,Deleter>(pu,d)), pt(pu) {}

    template<class U>
    explicit shared_ptr(U* pu) :pa(new auximpl<U,default_deleter<U> >(pu,default_deleter<U>())), pt(pu) {}

    shared_ptr(const shared_ptr& s) :pa(s.pa), pt(s.pt) { inc(); }

    template<class U>
    shared_ptr(const shared_ptr<U>& s) :pa(s.pa), pt(s.pt) { inc(); }

    ~shared_ptr() { dec(); }

    shared_ptr& operator=(const shared_ptr& s)
    {
        if(this!=&s)
        {
            dec();
            pa = s.pa; pt=s.pt;
            inc();
        }        
        return *this;
    }

    T* operator->() const { return pt; }
    T& operator*() const { return *pt; }
};

Where weak_ptr interoperability is required a second counter (weak_count) is required in aux (will be incremented / decremented by weak_ptr), and delete pa must happen only when both the counters reach zero.