Возможно, вам нужна техника сбора мусора, такая как Mark and Sweep . Идея этого алгоритма:
- Хранить список со ссылками на все выделенные блоки памяти.
- В какой-то момент вы запускаете сборщик мусора:
- Сначала отмечаются все блоки, к которым он все еще имеет доступ, без использования списка ссылок.
- Он просматривает список, стирая каждый элемент, который не может быть помечен, подразумевая, что он больше недоступен, поэтому он бесполезен.
Поскольку вы используете shared_ptr, любые все еще существующие указатели, которых вы не можете найти, должны рассматриваться как члены цикла.
Осуществление
Ниже я опишу очень наивный пример реализации части алгоритма sweep(), но он будет reset() всеми остальными указателями на коллекторе.
В этом коде хранятся shared_ptr<Cycle_t> указатели. Класс Collector отвечает за отслеживание всех указателей и удаление их при выполнении sweep().
#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.
}
}
};
Затем вы можете использовать его так:
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();
}
}
Я проверил его с помощью Valgrind, и в списке не было утечек памяти или «все еще доступных» блоков, поэтому он, вероятно, работает как ожидалось.
Некоторые замечания по этой реализации:
- Вектор памяти будет бесконечно увеличиваться, вы должны использовать некоторую технику выделения памяти , чтобы убедиться, что он не занимает всю вашу рабочую память.
- Можно утверждать, что нет необходимости использовать
shared_ptr (который работает как GC подсчета ссылок) для реализации такого сборщика мусора, поскольку алгоритм Mark and Sweep уже позаботится о работе.
- Я не реализовал функцию mark (), потому что это усложнит пример, но это возможно, и я объясню это ниже.
Наконец, если вас интересует (2), такого рода реализация не является неслыханной. CPython (основная реализация Python) действительно использует смесь подсчета ссылок, Mark и Sweep, но в основном по историческим причинам .
Реализация функции mark():
Для реализации функции mark() вам потребуется внести некоторые изменения:
Требуется добавить атрибут bool marked; к Cycle_t и использовать его для проверки, отмечен ли указатель или нет.
Вам нужно написать функцию Collector::mark(), которая будет выглядеть следующим образом:
void mark(Ref_t root) {
root->marked = true;
// For each other Ref_t stored on root:
for (Ref_t& item : root) {
mark(item);
}
}
А затем вы должны изменить функцию sweep(), чтобы удалить метку, если указатель помечен, или reset() указатель:
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();
}
}
}
}
Это было длинное объяснение, но я надеюсь, что оно кому-нибудь поможет.