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();
};

• peterh: I've also have a test.cc which contains a main() function and it runs some test cases. If needed, I am happy to include this as well.
• Loki Astari: C++ already has garbage collection built into the language. You just need to use the language correctly. std::shared_ptr and std::unique_ptr provide deterministic fine grain garbage collection of object when they are no longer in use.
• Loki Astari: The disadvantage of garbage collectors in languages like Java is that they are not deterministic in when they will be run. So you can not tell when your object will be destroyed. An important concept in C++ is RAII which sort of relies on the deterministic destruction of objects. So using a garbage collector is a really a bad (and ugly) idea for such a beautiful language like C++.
• peterh: @LokiAstari Yes, I know, and I don't like them, because they can't handle the isolated sub-graphes of objects. A real garbage collector must use some type of graph walking. RAII is okay, but it also can't handle that, although it makes the code quite beautiful (imho). The main problem is that my "parent project" works specifically with a graph of objects on the heap, so these solutions surely wouldn't work. This graph will change also non-deterministic, thus it is not a big problem if the gc is also not.

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.

• peterh: I disagree that GC is always a bad idea in C++. If your data structure becomes graph-like, where you have no control over its structure, finding the separated sub-graphes become an essential problem. Most C++ problems has not such a structure, and most C++ libraries are avoiding it, but there is no way to do it always so. But your answer is useful and acceptable, thanks.
• Loki Astari: @peterh I also agree that GC is **always** a bad idea is not a very good argument (glad I never actually said that (I suppose I hinted it)). I am sure there are situation were GC would be more appropriate. But I disagree that the use use case you present is a good one for GC (arbitrary graphs like that are better handle by C++ weak pointers than by Java like GC).