Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

A new approach to memory management that solves the issues with shared_ptrs

, 23 Feb 2009 CPOL
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;
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Achilleas Margaritis
Software Developer (Senior)
Greece Greece
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141223.1 | Last Updated 23 Feb 2009
Article Copyright 2009 by Achilleas Margaritis
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid