A simple concurrent mark-sweep garbage collector. Requires manual management of the referential graph. I'm confident it works for a single mutator thread, but not sure about multiple mutator threads. Requires boost::lockfree.

Collector.cpp

//
//  Collector.cpp
//  Dev
//
//  Created by Taylor Holliday on 6/14/13.
//  This file is in the public domain.
//

#include "gc2/Collector.hpp"

Collector Collector::collector;

Collector& Collector::GetInstance() {
  return collector;
}

Collector::Collector() : _eventQueue(new boost::lockfree::queue<Event>(128)) { }

void Collector::AddRoot(Collectable* node) {
    
  Event e;
  e.type = Event::AddRoot;
  e.a = node;
  
  _eventQueue->push(e);
  
}

void Collector::RemoveRoot(Collectable* node) {
    
  Event e;
  e.type = Event::RemoveRoot;
  e.a = node;
  
  _eventQueue->push(e);
  
}

void Collector::AddEdge(Collectable* a, Collectable* b) {
  
  Event e;
  e.type = Event::Connect;
  e.a = a;
  e.b = b;
  
  _eventQueue->push(e);

}

void Collector::RemoveEdge(Collectable* a, Collectable* b) {
  
  Event e;
  e.type = Event::Disconnect;
  e.a = a;
  e.b = b;
  
  _eventQueue->push(e);

}

void Collector::_ProcessEvents() {
  
  Event e;
  while(_eventQueue->pop(e)) {
    
    switch (e.type) {
      case Event::AddRoot: {
        _nodes.insert(e.a);
        e.a->gcRootCount++;
      }
      break;
      case Event::RemoveRoot: {
        
        e.a->gcRootCount--;
        
        // Root count must be positive.
        assert(e.a->gcRootCount >= 0);
      }
        break;
      case Event::Connect: {
        e.a->gcConnections.push_back(e.b);
      }
        break;
      case Event::Disconnect: {
        
        std::vector<Collectable*>& adj = e.a->gcConnections;
        
        auto iter = std::find(adj.begin(), adj.end(), e.b);
        
        // The connection must exist.
        assert(iter != e.a->gcConnections.end());
        
        adj.erase(iter);
      }
        break;
        
      default:
        break;
    }
  }
}

void Collector::Collect() {
    
  _ProcessEvents();
  
  static size_t sequence = 0;
  sequence++;
  
  std::vector<Collectable*> nodeStack;
  
  // Traverse starting with roots.
  for (auto node : _nodes) {
    
    if(node->gcRootCount) {
      nodeStack.push_back(node);
    }
  }
  
  // Mark.
  while(not nodeStack.empty()) {
    
    Collectable* node = nodeStack.back();
    nodeStack.pop_back();
    
    if(node->gcSequence != sequence) {
      node->gcSequence = sequence;
      
      for(auto adj : node->gcConnections) {
        nodeStack.push_back(adj);
      }
    }
  }
  
  // Sweep.
  std::set<Collectable*> newNodes;
  
  for(auto node : _nodes) {
    
    // Not visited.
    if (node->gcSequence != sequence) {
      delete node;
    } else {
      newNodes.insert(node);
    }
  }
  
  _nodes = newNodes;
  
}

Collector.hpp

//
//  Collector.h
//  Dev
//
//  Created by Taylor Holliday on 6/14/13.
//  This file is in the public domain.
//

#ifndef __Dev__Collector__
#define __Dev__Collector__

#include <set>
#include <vector>
#include <boost/lockfree/queue.hpp>

// Derive from Collectable if you'd like an object
// to be garbage collected.
struct Collectable {
  
  Collectable() : gcRootCount(0), gcSequence(0) { }
  virtual ~Collectable() { }

  // Connections as seen by the garbage collector.
  std::vector<Collectable*> gcConnections;
  
  // How many times is this node referenced as
  // a root.
  int gcRootCount;
  
  // Sequence number used to determine if
  // the Collectable has been visited in the
  // current round of GC.
  size_t gcSequence;

};

// The garbage collector. A singleton.
//
// Collector is a mark-sweep garbage collector
// that can be run concurrently in a background
// thread.
//
class Collector {
  
public:
  
  // Get the singleton instance.
  static Collector& GetInstance();
  
  // Add a reference to a root collectable.
  void AddRoot(Collectable*);
  
  // Remove a reference to a root collectable.
  void RemoveRoot(Collectable*);
  
  // Notify the collector of a new reference
  // between Collectables.
  void AddEdge(Collectable*, Collectable*);
  
  // Remove a reference between Collectables.
  void RemoveEdge(Collectable*, Collectable*);
  
  // Collect garbage. Make sure you only call
  // this from one thread at a time.
  void Collect();
  
private:
  
  Collector();
  
  // An event to update the collectors
  // own representation of the graph.
  struct Event {
    
    enum Type {
      AddRoot,
      RemoveRoot,
      Connect,
      Disconnect
    };
    
    Type type;
    Collectable* a;
    Collectable* b;
    
  };
  
  boost::lockfree::queue<Event>* _eventQueue;
  
  // All the nodes we've seen.
  std::set<Collectable*> _nodes;
  
  void _ProcessEvents();
  
  static Collector collector;
  
};

// When passing references to Collectables
// on the stack, always use RootPtr.
template<typename T>
struct RootPtr {
  
  T* _ptr;
  
  RootPtr() : _ptr(0) { }
  
  explicit RootPtr(T* ptr) : _ptr(ptr) {
    _Retain();
  }
  
  RootPtr(const RootPtr& other) : _ptr(other._ptr) {
    _Retain();
  }
  
  template<class T2>
  RootPtr(const RootPtr<T2>& other) : _ptr(other._ptr) {
    _Retain();
  }
  
  ~RootPtr() {
    _Release();
  }
  
  RootPtr& operator=(const RootPtr& other) {
    if(this != &other) {
      _Release();
      _ptr = other._ptr;
      _Retain();
    }
    return *this;
  }
  
  template<class T2>
  RootPtr& operator=(const RootPtr<T2>& other) {
    if(this != &other) {
      _Release();
      _ptr = other._ptr;
      _Retain();
    }
    return *this;
  }
  
  T& operator*() { return *_ptr; }
  T* operator->() const { assert(_ptr); return _ptr; }
  
  operator T*() { return _ptr; }
  
  operator bool() const { return _ptr != 0; }
  
  bool operator==(const RootPtr& other) const {
    return _ptr == other._ptr;
  }
  
  bool operator!=(const RootPtr& other) const {
    return _ptr != other._ptr;
  }
  
  bool operator<(const RootPtr& other) const {
    return _ptr < other._ptr;
  }
  
  void _Retain() {
    if(_ptr) {
      Collector::GetInstance().AddRoot(_ptr);
    }
  }
  
  void _Release() {
    if(_ptr) {
      Collector::GetInstance().RemoveRoot(_ptr);
    }
  }
  
}; // class RootPtr

#endif /* defined(__Dev__Collector__) */