You are probably in need of a Garbage Collector technique such as Mark and Sweep. The idea of this algorithm is:
- Keep a list with references to all memory blocks allocated.
- At some point you start the garbage collector:
- It first marks all the blocks it can still access without using the reference list.
- It goes through the list erasing each item that could not be marked, implying it is not reachable anymore so it is not useful.
Since you are using shared_ptr any still existing pointers you fail to reach should be considered as members of a cycle.
Implementation
Below I describe a very naive example of how to implement the sweep() part of the algorithm, but it will reset() all remaining pointers on the collector.
This code stores shared_ptr<Cycle_t> pointers. The class Collector is responsible for keeping track of all the pointers and deleting them when sweep() is executed.
#include <vector>
#include <memory>
class Cycle_t;
typedef std::shared_ptr<Cycle_t> Ref_t;
// struct Cycle;
struct Cycle_t {
Ref_t cycle;
Cycle_t() {}
Cycle_t(Ref_t cycle) : cycle(cycle) {}
};
struct collector {
// Note this vector will grow endlessy.
// You should find a way to reuse old links
std::vector<std::weak_ptr<Cycle_t>> memory;
// Allocate a shared pointer keeping
// a weak ref on the memory vector:
inline Ref_t add(Ref_t ref) {
memory.emplace_back(ref);
return ref;
}
inline Ref_t add(Cycle_t value) {
Ref_t ref = std::make_shared<Cycle_t>(value);
return add(ref);
}
inline Ref_t add() {
Ref_t ref = std::make_shared<Cycle_t>();
return add(ref);
}
void sweep() {
// Run a sweep algorithm:
for (auto& ref : memory) {
// If the original shared_ptr still exists:
if (auto ptr = ref.lock()) {
// Reset each pointer contained within it:
ptr->cycle.reset();
// Doing this will trigger a deallocation cascade, since
// the pointer it used to reference will now lose its
// last reference and be deleted by the reference counting
// system.
//
// The `ptr` pointer will not be deletd on the cascade
// because we still have at least the current reference
// to it.
}
// When we leave the loop `ptr` loses its last reference
// and should be deleted.
}
}
};
You can then use it like this:
Collector collector;
int main() {
// Build your shared pointers:
{
// Allocate them using the collector:
Ref_t c1 = collector.add();
Ref_t c2 = collector.add(c1);
// Then create the cycle:
c1.get()->cycle = c2;
// A normal block with no cycles:
Ref_t c3 = collector.add();
}
// In another scope:
{
// Note: if you run sweep an you still have an existing
// reference to one of the pointers in the collector
// you will lose it since it will be reset().
collector.sweep();
}
}
I tested it with Valgrind and no memory leaks or "still reachable" blocks were listed, so it is probably working as expected.
Some notes on this implementation:
- The memory vector will grow endlessly, you should use some memory allocation technique to make sure it does not occupy all your working memory.
- One may argue that there is no need of using
shared_ptr (that works like a Reference Counting GC) to implement such a Garbage Collector since the Mark and Sweep algorithm would already take care of the job.
- I did not implement the mark() function because it would complicate the example but it is possible and I will explain it below.
Finally, if you are concerned with (2), this kind of implementation is not unheard of. CPython (the main implementation of Python) does use a mixture of Reference Counting and Mark and Sweep, but mostly for historical reasons.
Implementing the mark() function:
To implement the mark() function you will need to make some modifications:
It would be required to add a bool marked; attribute to Cycle_t, and use it to check whether the pointer is marked or not.
You will need to write the Collector::mark() function that would look like this:
void mark(Ref_t root) {
root->marked = true;
// For each other Ref_t stored on root:
for (Ref_t& item : root) {
mark(item);
}
}
And then you should modify the sweep() function to remove the mark if the pointer is marked or else reset() the pointer:
void sweep() {
// Run a sweep algorithm:
for (auto& ref : memory) {
// If it still exists:
if (auto ptr = ref.lock()) {
// And is marked:
if (ptr->marked) {
ptr->marked = false;
} else {
ptr->cycle.reset();
}
}
}
}
It was a lengthy explanation, but I hope it helps someone.
