A New Approach to Memory Management that Solves the Issues with shared_ptrs

#pragma warning (disable: 4355)
#include <boost/intrusive/list.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/utility.hpp>


class object;


//ptr base class
class ptr_base : public boost::intrusive::list_base_hook<> {
public:

protected:
    //default ctor; the new object is acquired
    ptr_base(object *owner, object *ptr) :
        m_owner(owner), m_object(ptr)
    {
        _acquire();
    }

    //destructor; the existing object is released
    ~ptr_base() {
        _release();
    }

    //assignment from ptr
    ptr_base &operator = (const ptr_base &p) {
        set(p.m_object);
        return *this;
    }

    //get ptr value
    object *get() const {
        return m_object;
    }

    //set ptr; the old object is released, the new one is acquired
    void set(object *o) {
        if (o == m_object) return;
        _release();
        m_object = o;
        _acquire();
    }

    //sets the ptr to null
    void reset() {
        _release();
        m_object = 0;
    }

private:
    //owner object
    object *m_owner;

    //object that it points to
    object *m_object;

    //adds itself to the list of ptrs of the object it points to
    void _acquire();

    //removes itself from the list of ptrs of the object it points to and disposes the object
    void _release();

    //copy ctor not public due to owner member
    ptr_base(const ptr_base &);

    friend class object;
};


//a typed ptr
template <class T> class ptr : public ptr_base {
public:
    //root ptr ctor
    ptr(T *object = 0) :
        ptr_base(0, object)
    {
    }

    //root ptr copy ctor
    ptr(const ptr<T> &p) :
        ptr_base(0, p.get())
    {
    }

    //member ptr ctor
    ptr(object &owner, T *object = 0) :
        ptr_base(&owner, object)
    {
    }

    //member ptr copy ctor
    ptr(object &owner, const ptr<T> &p) :
        ptr_base(&owner, p.get())
    {
    }

    //dtor
    ~ptr() {
    }

    //assign op
    ptr<T> &operator = (const ptr<T> &p) {
        ptr_base::operator = (p);
        return *this;
    }

    //get ptr value
    T *get() const {
        return static_cast<T *>(ptr_base::get());
    }

    //auto conversion
    operator T *() const {
        return get();
    }

    //member access
    T *operator ->() const {
        BOOST_ASSERT(get());
        return get();
    }

    //set ptr
    ptr<T> &operator = (T *object) {
        set(object);
        return *this;
    }

    //sets the ptr to null
    void reset() {
        set(0);
    }
};


//ptr list
typedef boost::intrusive::list<ptr_base, boost::intrusive::constant_time_size<false> > ptr_list;


//base class for objects with ptrs
class object {
public:
    //default ctor
    object() : m_locked(0) {
    }

    //copy ctor
    object(const object &o) : m_locked(0) {
    }

    //dtor
    virtual ~object() {
        //when the object is deleted, there should not be any ptrs to it
        BOOST_ASSERT(m_ptrs.empty());
    }

    //the assignment operator
    object &operator = (const object &o) {
        return *this;
    }

    /* checks if the object is collectable from roots.
        It works for cyclic references as well.
     */
    bool collectable() const {
        //do not allow infinite recursion
        if (m_locked) return true;
        ++m_locked;

        bool result = true;

        //iterate all pointers and check if there are root references
        for(ptr_list::const_iterator it = m_ptrs.begin(); it != m_ptrs.end(); ++it) {
            const ptr_base &ptr = *it;

            //if the ptr is root (i.e. it does not have an owner),
            //or the ptr's owner is collectable, then this object is not collectable
            if (!ptr.m_owner || !ptr.m_owner->collectable()) {
                result = false;
                break;
            }
        }

        --m_locked;

        return result;
    }

    //deletes this object if it is not collectable
    virtual bool dispose() {
        //if not collectable, do nothing
        if (!collectable()) return false;

        //if there is a cycle, empty the ptrs before deleting the object
        while (!m_ptrs.empty()) {
            ptr_base &ptr = m_ptrs.back();
            ptr.m_object = 0;
            m_ptrs.pop_back();
        }

        //delete the object
        delete this;
        
        return true;
    }

private:
    //list of ptrs that point to this object
    ptr_list m_ptrs;

    //used for handling cycles
    mutable unsigned m_locked;

    friend class ptr_base;
};


//adds itself to the list of ptrs of the object it points to
void ptr_base::_acquire() {
    if (m_object) m_object->m_ptrs.push_front(*this);
}


//removes itself from the list of ptrs of the object it points to and disposes the object
void ptr_base::_release() {
    if (m_object) {
        m_object->m_ptrs.erase(m_object->m_ptrs.iterator_to(*this));
        m_object->dispose();
    }
}


class collector;


//a class that defers the disposal for a later date with the help of a collector.
class collector_object : public object, public boost::intrusive::list_base_hook<> {
public:
    //ctor from default collector
    collector_object();
    
    //ctor from collector
    collector_object(collector &c);
    
    //copy ctor; copies the collector from given object
    collector_object(const collector_object &o);
    
    //removes this object from the collector
    virtual ~collector_object();
    
    //it does nothing. Only the collector can dispose the object.
    virtual bool dispose() {
        return false;
    }
    
private:
    //the object set to put the object for lazy check
    collector &m_collector;
    
};


//collector
class collector : public boost::intrusive::list<collector_object> {
public:
    //collect garbage
    void collect() {
        //collect garbage from the head of the set
        while (!empty()) {
            collector_object &o = *begin();
            if (!o.object::dispose()) break;
        }

        //collect garbage from the tail of the set
        for(iterator it = boost::next(begin()), prev = begin(); it != end(); ) {
            object &o = *it;
            
            //if the object is collectable, delete it
            if (o.dispose()) {
                it = boost::next(prev);
            }
            
            //otherwise, go to the next element
            else {
                prev = it;
                ++it;
            }        
        }        
    }
    
    //gets the default collector
    static collector &get_default() {
        static collector c;
        return c;
    }
};


//ctor from default collector
collector_object::collector_object() : m_collector(collector::get_default()) {
    m_collector.push_back(*this);
}


//ctor from collector
collector_object::collector_object(collector &c) : m_collector(c) {
    m_collector.push_back(*this);
}


//copy ctor; copies the collector from given object
collector_object::collector_object(const collector_object &o) : m_collector(o.m_collector) {
    m_collector.push_back(*this);
}


//removes this object from the collector
collector_object::~collector_object() {
    m_collector.erase(m_collector.iterator_to(*this));
}


/******************************************************************************
    DEMO
 ******************************************************************************/


#include <list>
#include <iostream>
using namespace std;


int node_count = 0;


template <class NODE_BASE> class print_msg {
public:
    static void exec() {
        cout << "TEST WITH EAGER DISPOSE\n";
        cout << "-----------------------\n";
    }
};


template <> class print_msg<collector_object> {
public:
    static void exec() {
        cout << "TEST WITH LAZY DISPOSE\n";
        cout << "----------------------\n";
    }
};


template <class NODE_BASE> class collect_all {
public:
    static void exec() {
    }
};


template <> class collect_all<collector_object> {
public:
    static void exec() {
        collector::get_default().collect();
    }
};


template <class NODE_BASE> class test {
public:
    class node;

    typedef ptr<node> node_ptr_t;

    class node : public NODE_BASE {
    public:
        node_ptr_t m_link;

        node() :
            m_parent(*this),
            m_prev_sibling(*this),
            m_next_sibling(*this),
            m_first_child(*this),
            m_last_child(*this),
            m_link(*this)
        {
            ++node_count;
        }

        node(const node_ptr_t &parent) :
            m_parent(*this),
            m_prev_sibling(*this),
            m_next_sibling(*this),
            m_first_child(*this),
            m_last_child(*this),
            m_link(*this)
        {
            ++node_count;
            parent->add_child(this);
        }

        ~node() {
            --node_count;
        }

        void add_child(const node_ptr_t &child) {
            BOOST_ASSERT(child->m_parent == 0);
            child->m_parent = this;
            child->m_prev_sibling = m_last_child;
            if (m_last_child) m_last_child->m_next_sibling = child;
            else m_first_child = child;
            m_last_child = child;
        }
        
        void remove_child(const node_ptr_t &child) {
            BOOST_ASSERT(child->m_parent == this);
            if (child->m_prev_sibling) child->m_prev_sibling->m_next_sibling = child->m_next_sibling;
            else m_first_child = child->m_next_sibling;
            if (child->m_next_sibling) child->m_next_sibling->m_prev_sibling = child->m_prev_sibling;
            else m_last_child = child->m_prev_sibling;
            child->m_parent = 0;
            child->m_prev_sibling = 0;
            child->m_next_sibling = 0;
        }

    private:
        node_ptr_t m_parent;
        node_ptr_t m_prev_sibling;
        node_ptr_t m_next_sibling;
        node_ptr_t m_first_child;
        node_ptr_t m_last_child;
    };

    static void simple_test() {
        node_ptr_t node1 = new node;
        node1->m_link = new node;
        node1->m_link->m_link = new node;
        node1->m_link->m_link->m_link = node1;
        cout << "simple test node count = " << node_count << endl;
    }
    
    typedef list<node_ptr_t> node_list;
    
    class list_object : public object {
    public:
        boost::shared_ptr<node_list> m_list;
        
        list_object() : m_list(new node_list) {
        }
    };

    static void stack_test() {
        node_ptr_t root = new node;

        node_ptr_t node1 = new node(root);
        node_ptr_t node11 = new node(node1);
        node_ptr_t node12 = new node(node1);
        node_ptr_t node13 = new node(node1);

        node_ptr_t node2 = new node(root);
        node_ptr_t node21 = new node(node2);
        node_ptr_t node22 = new node(node2);
        node_ptr_t node23 = new node(node2);
        
        node_ptr_t node3 = new node(root);    
        node_ptr_t node31 = new node(node3);
        node_ptr_t node32 = new node(node3);
        node_ptr_t node33 = new node(node3);
        
        node33->m_link = root;
        
        root->remove_child(node2);
        
        cout << "stack test node count = " << node_count << endl;
    }

    static void container_test() {
        ptr<list_object> lo = new list_object;
        {
            node_ptr_t root = new node;

            node_ptr_t node1 = new node(root);
            node_ptr_t node11 = new node(node1);
            node_ptr_t node12 = new node(node1);
            node_ptr_t node13 = new node(node1);

            node_ptr_t node2 = new node(root);
            node_ptr_t node21 = new node(node2);
            node_ptr_t node22 = new node(node2);
            node_ptr_t node23 = new node(node2);

            node_ptr_t node3 = new node(root);
            node_ptr_t node31 = new node(node3);
            node_ptr_t node32 = new node(node3);
            node_ptr_t node33 = new node(node3);
            
            lo->m_list->push_back(root);
        }
        cout << "container test node count before collection = " << node_count << endl;
        collect_all<NODE_BASE>::exec();
        cout << "container test node count after collection = " << node_count << endl;
    }
    
    //collects all, depending on type of NODE_BASE
    static void exec() {
        print_msg<NODE_BASE>::exec();
        simple_test();
        collect_all<NODE_BASE>::exec();
        stack_test();
        collect_all<NODE_BASE>::exec();
        container_test();
        collect_all<NODE_BASE>::exec();
        cout << "final node count = " << node_count << endl << endl;    
    }
};


int main() {
    test<object>::exec();
    test<collector_object>::exec();
    getchar();
    return 0;
}