Minimalistic Garbage Collecting Smart Pointers

gc_ptr.cpp

#include "gc_ptr.h"

#include <new>
#include <list>
#include <stack>

// A NULL owner pointer signifies that a gc_poiner is owned by the stack
// (or a manually managed heap block)
const unsigned int SOLID_REFERENCE = 0;

// Used when parsing the gc_ptr reference tree
enum GC_FLAGS { FLAG_HAS_BEEN_VISITED = 0x1, FLAG_MARKED_FOR_DELETION = 0x2 };

// Wrap all allocated blocks in a HeapBlockWrapper 
struct gc_ptr_base;
typedef std::list<gc_ptr_base*> GcPointerList;
struct HeapBlockWrapper { GcPointerList list; unsigned int flags; };

// Stack to keep track of blocks allocated with gc_ptr::create
// The HeapBlockDescriptions are only alive while gc_ptr::create runs the 
// constructor for the underlying data type
struct HeapBlockDescription { char* ptr; size_t size; }; 
typedef std::stack<HeapBlockDescription*> HeapBlockDescriptionStack;
HeapBlockDescriptionStack memBlockStack;


////////// GC POINTER IMPLEMENTATION //////////////////////////////////////////

// This wraps the construction of objects that will be garbage collected
// We have to do this because we need to track the creation of any gc_ptr
// objects that are part of the allocated heap blocks so we can mark these
// as weak pointers
template <typename T> gc_ptr<T> gc_ptr<T>::create(unsigned int count = 1)
{
    size_t size = sizeof(T) * count;
    HeapBlockWrapper* p = (HeapBlockWrapper*)operator new(size + sizeof(HeapBlockWrapper));
    p = new(p) HeapBlockWrapper();
    p->flags = count << 2;

    HeapBlockDescription b = { (char*)p, size };
    memBlockStack.push(&b);
    for (unsigned int i = 0; i < count; ++i) new((T*)(p + 1) + i) T();
    memBlockStack.pop();
    gc_ptr g(p);
    return g;
}

////////// GC POINTER CONSTRUCTORS ////////////////////////////////////////////

template <typename T> gc_ptr<T>::gc_ptr() : ptr(0)                                 { FindOwner(); }
template <typename T> gc_ptr<T>::gc_ptr(const gc_ptr &rhs) : ptr(rhs.ptr)          { FindOwner(); ptr->list.push_front(this); }
template <typename T> gc_ptr<T>::gc_ptr(HeapBlockWrapper* ptr) : ptr(ptr)          { parentHeapBlock = 0; ptr->list.push_front(this); }
template <typename T> gc_ptr<T>::~gc_ptr() 
{ 
    if (ptr == 0 || (ptr->flags & FLAG_MARKED_FOR_DELETION)) return;

    ptr->flags += FLAG_MARKED_FOR_DELETION;
    ptr->list.remove(this);

    // If object has no more references to it or if all remaining references are cyclic
    if (!ptr->list.empty() && FindSolidReference(ptr))
    {
        ptr->flags -= FLAG_MARKED_FOR_DELETION;
        return;
    }

    unsigned int count = ptr->flags >> 2;
    for (unsigned int i = 0; i < count; ++i) (operator->() + count)->~T();
    ::operator delete(ptr); // Delete the HeapBlockWrapper object
}


////////// GC POINTER OPERATORS ///////////////////////////////////////////////

template <typename T> gc_ptr<T>& gc_ptr<T>::operator=(const gc_ptr &rhs) 
{ 
    if (ptr != 0) this->~gc_ptr(); // Call destructor to cleanup previous target (gc_ptr-pointer will not be deleted by this...)

    ptr = rhs.ptr;
    ptr->list.push_front(this);
    return *this;
}

template <typename T> T& gc_ptr<T>::operator*() { return *(T*)(ptr + 1); }
template <typename T> T* gc_ptr<T>::operator->() { return (T*)(ptr + 1); }


////////// GC POINTER REFERENCE TREE //////////////////////////////////////////

// Follow all links back until we find a root or a place we have already been
// A root is a block with an empty Hdr list
// If we find a root the object is still reachable
// If we have reached the end in all paths, and no roots have been found, delete the object
template <typename T> bool gc_ptr<T>::FindSolidReference(HeapBlockWrapper* pInfo)
{
    if (ptr->flags & FLAG_HAS_BEEN_VISITED) 
        return false; // Check if the block has been visited before
    pInfo->flags += FLAG_HAS_BEEN_VISITED;

    GcPointerList* reflist = &pInfo->list;

    // explore all gc_ptr pointers pointing to this header
    for (GcPointerList::iterator i = reflist->begin(); i != reflist->end(); ++i)
    {
        HeapBlockWrapper* pInfo2 = (*i)->parentHeapBlock;
        // If referencing gc_ptr is owned by the stack or the memory block
        if (pInfo2 == SOLID_REFERENCE || FindSolidReference(pInfo2))
        {
            pInfo->flags -= FLAG_HAS_BEEN_VISITED; // remove marker
            return true;
        }
    }
             
    pInfo->flags -= FLAG_HAS_BEEN_VISITED; // remove marker
    return false;
}

template <typename T> void gc_ptr<T>::FindOwner()
{
    if (memBlockStack.empty()) { parentHeapBlock = 0; return; }

    HeapBlockDescription* pBlock = memBlockStack.top();
    parentHeapBlock = ((char*)this > pBlock->ptr && (char*)this < pBlock->ptr + pBlock->size) ? (HeapBlockWrapper*)pBlock->ptr : 0;
}

gc_ptr.hpp

// 
// GARBAGE POINTER (gb_ptr)
// 
// Author: Daniel Peterson 2012
// Contact: daniel.peterson@inbox.com
// License: Public Domain
// 
// This is a version of the smart pointer concept that handles cyclic links.
// It does this by keeping track of all garbage pointers created in heap blocks
// and then traversing this tree whenever a garbage pointer goes out of scope
// or is re-assigned.
//  
// This is much slower than traditional smart pointers and weak pointers and
// also slower than traditional garbage collection with a separate thread
// doing mark and sweep.
// 
// It is however a very small code base and does the job for lazy Sunday
// afternoon coding sessions :)
// 
// Code is currently not thread safe. To make the code thread safe there
// must be a separate HeapBlockDescriptionStack for each tread. Also
// traversing adding to and deleting from GcPointerLists must be protected
// with a mutex. 
// 
// // Example 1:
// gc_ptr<T> p1 = gc_ptr<T>::create();
// gc_ptr<T> p2 = p1;
// 
// // Example 2:
// // Define a struct
// struct MyStruct { gc_ptr<int> gcPtr; };
//  
// // In main()
// gc_ptr<MyStruct> myStruct = gc_ptr<MyStruct>::create();
// myStruct->gcPtr = myStruct;
// 
// TODO:
// * Handle virtual inheritance
// * Thread Safety
// * ~gc_ptr() performance (iterative traversal and a stack for brancing)
// * Constructor arguments
//

#ifndef GC_PTR_H
#define GC_PTR_H

struct HeapBlockWrapper;
struct gc_ptr_base { HeapBlockWrapper* parentHeapBlock; };
template <typename T> struct gc_ptr : gc_ptr_base
{
    // Static function create wraps the construction of objects that will be 
    // garbage collected. This has to be done this because we need to track the
    // creation of any gc_ptr objects that are part of the allocated heap 
    // blocks so we can mark these as weak pointers
    static gc_ptr create(unsigned int count = 1);

    gc_ptr();
    gc_ptr(const gc_ptr &rhs);
    ~gc_ptr(); 

    gc_ptr& operator=(const gc_ptr &rhs);
    T& operator*();
    T* operator->();

    // Internal: For parsing the gc_ptr tree...
    bool FindSolidReference(HeapBlockWrapper* pInfo);

private: 
    void FindOwner();
    gc_ptr(HeapBlockWrapper* ptr);

    HeapBlockWrapper* ptr;
};

#endif