Pointer lists for a C++ garbage collector

Question

The problem

My intention is to have a class A and class B. class B has a std::list from a pointers of class A. I need three operations to complete very fast:

1. Inserting new A elements into the list in B
2. Removing these very fast
3. Iterate through the A-s already registered in B sequentially. Their order is irrelevant.

My idea is that B contains an std::list from a pointers of A, and every A will contain its iterator in the list of B.

How does it look? (This code compiles without any warning with g++ -Wall -std=c++11)

#include <stdio.h>
#include <list>

class A;

class B {
  private:
    std::list<A*> aList;

  public:
    std::list<A*>::iterator addA(A* a);
    void removeA(A* a);
};

class A {
  friend B;
  private:
    B* b;
    std::list<A*>::iterator bIter;

  public:
    A(B* b) {
      this->b = b;
      bIter = b->addA(this);
    };
    ~A() {
      b->removeA(this);
      b = NULL;
    };
};

std::list<A*>::iterator B::addA(A* a) {
  return aList.insert(aList.end(), a);
};

void B::removeA(A* a) {
  aList.erase(a->bIter);
};

---

The operations are needed for my minimalistic garbage collector library. It is ready, some - not yet really complex - testcases run seamlessly. The whole source is reachable here. What here is important, it is the source of the library, which contains a lot of similar structures. Actually, it doesn't contain even a single O*log(O) data structure (i.e. set), exclusively lists.

The gc is so small that it contains a 4k header and a 5k source.

Unfortunately, even in the most important part I finally couldn't use the stl lists, because it had been extreme problematic. So I implemented a C-like linked list solution. Yes, I know, also I've seen better code. :-)

The header (gc.h) is:

#ifndef MaXXGC_h
#define MaXXGC_h

#include <list>

namespace MaXXGC {

typedef enum {
  STORAGE_ALREADY_SET = 0x3586,
  PARENT_MEMBEROF_INCONSISTENCY = 0x3587,
  GC_SHOULD_RUN = 0x3588,
  UNREACHABLE_CODE = 0x3589,
  CIRCULAR_MEMBEROF = 0x358a
} ErrorCode;

class GcException : public std::exception {
  public:
    ErrorCode errorCode;
    GcException(ErrorCode errorCode);
};

class Object {
  class Graph;
  friend Graph;
  friend void MaXXGC::gc();
  template<class Dst> class Ptr;
  template<class Dst> friend class Ptr;

  private:
    static Graph& graph();

    class iPtr;

    class Graph final {
      friend iPtr;
      friend Object;
      friend void ::MaXXGC::gc();

      private:
        static Graph *globalGraph;
        std::list<Object*> objs;
        std::list<Object::iPtr*> ptrs;
        bool isGcRunning = false;

        // for gc
        Object *border, *unknown, *ready;
        void llAdd(Object **ll, Object* obj);
        void llRemove(Object **ll, Object* obj);

        Graph();
        ~Graph();

        void assertGcRunning();
        void gc();
    };

    class iPtr {
      friend Object;
      friend Graph;

      private:
        Object *srcObj, *dstObj;
        std::list<iPtr*>::iterator srcIter, dstIter, graphIter;

      public:
        iPtr(Object* srcObj, Object* dstObj);
        ~iPtr();

        Object* getDst() const;
        void setDst(Object* dstObj);
    };

    std::list<iPtr*> inPtrs;
    std::list<iPtr*> outPtrs;
    std::list<Object*>::iterator graphIter;
    Object *prevCat, *nextCat;
    iPtr *parentPtr;

    typedef enum {
      UNDEFINED = 0,
      ONSTACK = 1,
      ONHEAP = 2,
      MEMBEROF = 3
    } Storage;
    Storage storage;

    typedef enum {
      UNSET = 0,
      UNKNOWN = 1,
      BORDER = 2,
      READY = 3
    } Category;
    Category category;

    Object* getParent();
    Object* getTop();
    bool isCategory(Category category) const;
    void setCategory(Category category);

  public:
    Object();
    virtual ~Object();

    void onHeap();
    void onStack();
    void memberOf(Object* obj);
    void memberOf(Object& obj);
};

// Actually syntactic sugar to the type-less Object::iPtr
template<class Dst> class Ptr final : protected Object::iPtr {
  public:
    Ptr(Object* srcObj, Dst* dstObj) : Object::iPtr(srcObj, dstObj) { };
    Ptr(Object* srcObj, Dst& dstObj) : Object::iPtr(srcObj, &dstObj) { };
    Ptr(Object& srcObj, Dst* dstObj) : Object::iPtr(&srcObj, dstObj) { };
    Ptr(Object& srcObj, Dst& dstObj) : Object::iPtr(&srcObj, &dstObj) { };
    ~Ptr() { };

    Dst& operator*() const {
      return getDst();
    };

    Ptr<Dst>& operator=(Ptr<Dst>* const ptr) {
      setDst(ptr);
      return *this;
    };

    Ptr<Dst>& operator=(const Ptr<Dst>& ptr) {
      setDst(&ptr);
      return *this;
    };

    bool operator==(Ptr<Dst>* const ptr) const {
      return dstObj == ptr->dstObj;
    };

    bool operator==(const Ptr<Dst>& ptr) const {
      return dstObj == ptr.dstObj;
    };

    bool isNull() const {
      return dstObj;
    };
};

template<class Dst> bool operator==(Dst* ptr1, Ptr<Dst>& ptr2) {
  return ptr1 == ptr2.dstObj;
};

class Members final {
  public:
    Members(Object* parent, const std::initializer_list<Object*>& children);
    Members(Object& parent, const std::initializer_list<Object*>& children);
};

void gc();

};

#endif

And the implementation:

#include <algorithm>

#include "gc.h"

using namespace MaXXGC;

Object::Graph *Object::Graph::globalGraph(NULL);

GcException::GcException(ErrorCode errorCode) {
  this->errorCode = errorCode;
};

Object::iPtr::iPtr(Object* srcObj, Object* dstObj) {
  this->srcObj = srcObj;
  this->dstObj = NULL;
  srcIter = srcObj->outPtrs.insert(srcObj->outPtrs.end(), this);
  graphIter = graph().ptrs.insert(graph().ptrs.end(), this);
  setDst(dstObj);
};

// We all love the wonderfully indeterministic c++ static initialization ordering
Object::Graph& Object::graph() {
  if (!Object::Graph::globalGraph)
    Object::Graph::globalGraph = new Object::Graph();
  return *Object::Graph::globalGraph;
};

Object::iPtr::~iPtr() {
  this->srcObj->outPtrs.erase(srcIter);
  if (this->dstObj)
    setDst(NULL);
  graph().ptrs.erase(graphIter);
};

Object* Object::iPtr::getDst() const {
  return dstObj;
};

void Object::iPtr::setDst(Object* dstObj) {
  if (this->dstObj)
    this->dstObj->inPtrs.erase(dstIter);
  this->dstObj = dstObj;
  if (dstObj)
    dstIter = dstObj->inPtrs.insert(dstObj->inPtrs.end(), this);
};

Object::Object() {
  storage = Object::UNDEFINED;
  category = Object::UNSET;
  prevCat = NULL;
  nextCat = NULL;
  setCategory(UNSET);
  parentPtr = NULL;
  graphIter = graph().objs.insert(graph().objs.end(), this);
};

Object::~Object() {
  if (parentPtr) {
    delete parentPtr;
    parentPtr = NULL;
  };

  setCategory(UNSET);

  while (!outPtrs.empty())
    delete *(outPtrs.begin());
  while (!inPtrs.empty())
    (*inPtrs.begin())->setDst(NULL);
  graph().objs.erase(graphIter);
};

Object* Object::getParent() {
  if (storage != MEMBEROF && parentPtr)
    throw GcException(PARENT_MEMBEROF_INCONSISTENCY);

  if (parentPtr)
    return parentPtr->getDst();
  else
    return NULL;
};

Object* Object::getTop() {
  Object* obj = this;
  while (Object* parent = obj->getParent()) // yes, really "="
    obj = parent;
  return obj;
};

bool Object::isCategory(Category category) const {
  return this->category == category;
};

void Object::setCategory(Category category) {
  switch (this->category) {
    case UNSET:
      break;
    case UNKNOWN:
      graph().llRemove(&graph().unknown, this);
      break;
    case BORDER:
      graph().llRemove(&graph().border, this);
      break;
    case READY:
      graph().llRemove(&graph().ready, this);
      break;
    default:
      throw GcException(UNREACHABLE_CODE);
  };  

  this->category = category;

  switch (category) {
    case UNSET:
      break;
    case UNKNOWN:
      graph().llAdd(&graph().unknown, this);
      break;
    case BORDER:
      graph().llAdd(&graph().border, this);
      break;
    case READY:
      graph().llAdd(&graph().ready, this);
      break;
    default:
      throw GcException(UNREACHABLE_CODE);
  };
};

void Object::onHeap() {
  if (storage != Object::UNDEFINED)
    throw GcException(STORAGE_ALREADY_SET);
  storage = ONHEAP;
};

void Object::onStack() {
  if (storage != Object::UNDEFINED)
    throw GcException(STORAGE_ALREADY_SET);
  storage = ONSTACK;
};

void Object::memberOf(Object* parent) {
  if (storage != Object::UNDEFINED)
    throw GcException(STORAGE_ALREADY_SET);

  for (Object* top = parent; top->storage != Object::MEMBEROF; top = top->getParent())
    if (top == this)
      throw GcException(CIRCULAR_MEMBEROF);

  storage = MEMBEROF;
  parentPtr = new iPtr(this, parent);
  new iPtr(parent, this);
};

void Object::memberOf(Object& parent) {
  memberOf(&parent);
};

Members::Members(Object* parent, const std::initializer_list<Object*>& children) {
  std::for_each(children.begin(), children.end(), [parent](Object* child){
    child->memberOf(parent);
  });
};

Members::Members(Object& parent, const std::initializer_list<Object*>& children) : Members(&parent, children) {
};

Object::Graph::Graph() {
  // nothing now
};

Object::Graph::~Graph() {
  while (!objs.empty())
    delete *(objs.begin());
  while (!ptrs.empty())
    delete *(ptrs.begin());
};

void Object::Graph::assertGcRunning() {
  if (!isGcRunning)
    throw GcException(GC_SHOULD_RUN);
};

void Object::Graph::llAdd(Object **ll, Object *obj) {
  if (!*ll) {
    *ll = obj;
    obj->prevCat = NULL;
    obj->nextCat = NULL;
  } else {
    (*ll)->prevCat = obj;
    obj->nextCat = *ll;
    obj->prevCat = NULL;
    *ll = obj;
  }
};

void Object::Graph::llRemove(Object** ll, Object* obj) {
  if (*ll == obj)
    *ll = obj->nextCat;
  if (obj->prevCat)
    obj->prevCat->nextCat = obj->nextCat;
  if (obj->nextCat)
    obj->nextCat->prevCat = obj->prevCat;
};

void Object::Graph::gc() {
  isGcRunning = true;

  border = NULL;
  unknown = NULL;
  ready = NULL;

  std::for_each(objs.begin(), objs.end(), [](Object* obj){
    if (obj->storage == Object::ONSTACK || obj->storage == Object::UNDEFINED)
      obj->setCategory(Object::BORDER);
    else
      obj->setCategory(Object::UNKNOWN);
  });

  while (border) {
    Object* obj=border;
    std::for_each(obj->outPtrs.begin(), obj->outPtrs.end(), [](Object::iPtr *outPtr){
      Object* out = outPtr->getDst();
      switch (out->category) {
        case Object::UNKNOWN:
          out->setCategory(Object::BORDER);
          break;
        case Object::BORDER:
        case Object::READY:
          break;
        default:
          throw GcException(UNREACHABLE_CODE);
      }
    });
    obj->setCategory(Object::READY);
  };

  while (unknown) {
    switch (unknown->storage) {
      case Object::UNDEFINED:
      case Object::MEMBEROF:
      case Object::ONSTACK:
        unknown->setCategory(Object::UNSET);
        break;
      case Object::ONHEAP:
        delete unknown;
        break;
      default:
        throw GcException(UNREACHABLE_CODE);
    };
  };

  isGcRunning = false;
};

void ::MaXXGC::gc() {
  Object::graph().gc();
};

Answer 1

Apart from the bad idea of garbage collection.

You are using pointers where you should be using references. Basically your code has no concept of Ownership Semantics.

    std::list<A*>::iterator addA(A* a);
    void removeA(A* a);
    A(B* b)

When adding A to a B in addA() you should not need to check if the value passed is a nullptr so you should pass by reference to indicate that the value is never nullptr (or you should explicitly check for nullptr but an object should know its not null). Same applies for removeA()

When building an A is there ever a possibility that the B will not exist? Your code does not check so I am assuming no. So you should pass the B by reference to again indicate that the B can not be nullptr.

This worries me:

Unfortunately, even in the most important part I finally couldn't use the stl lists, because it had been extreme problematic.

Since we know that there are no errors std::list this is an indication that you have problems somewhere in your code that still have not been found. A hand written C implementation of a list is not going to be quicker than std::list it is designed for efficiency.

Your exception should probably enhierit from std::runtime_error

 class GcException : public std::exception
                     //     std::runtime_error (I would use this).

A member class (like all other members) has access to any part of the object. So making it a friend is no required (this was required in original C++03 but was changed for C++11 and had been implemented by compilers long before C++11 was released).

class Object {
  class Graph;
  friend Graph;   // Not required.

  template<class Dst> class Ptr;
  template<class Dst> friend class Ptr;  // Not required.