[C++] 增量式垃圾回收

gc.hpp

#pragma once

#include <stack>
#include <vector>

class GCObject;

class GC
{
public:
    static GC gc;

public:
    std::vector<GCObject *> all_objects;
    std::stack<GCObject *> grey_objects;
    bool is_running = true;

public:
    void add_object(GCObject *object);
    void start(const std::vector<GCObject *> &roots);
    void step(std::size_t max);
    void sweep();
    void clear_all();
};

GC GC::gc = GC();

gcobject.hpp

#pragma once

#include <cstdlib>
#include "gc.hpp"

enum class Color
{
    White,
    Grey,
    Black,
};

class GCObject
{
public:
    Color color = Color::White;

public:
    GCObject() = default;
    virtual ~GCObject() = default;

public:
    virtual std::vector<GCObject *> trace() = 0;

public:
    static void *operator new(std::size_t size)
    {
        void *memory = std::malloc(size);
        GC::gc.add_object((GCObject *)memory);
        return memory;
    }
};

gc.cpp

#include "gc.hpp"
#include "gcobject.hpp"

void GC::add_object(GCObject *object)
{
    all_objects.push_back(object);
}

void GC::start(const std::vector<GCObject *> &roots)
{
    while (!grey_objects.empty())
        grey_objects.pop();

    for (auto &obj : all_objects)
        obj->color = Color::White;

    for (auto &obj : roots)
    {
        obj->color = Color::Grey;
        grey_objects.push(obj);
    }

    is_running = true;
}

void GC::step(std::size_t max)
{
    if (!is_running)
        return;

    std::size_t count = 0;
    while (count < max && !grey_objects.empty())
    {
        auto current = grey_objects.top();
        grey_objects.pop();

        auto objects = current->trace();
        for (auto obj : objects)
        {
            if (obj->color != Color::White)
                continue;

            obj->color = Color::Grey;
            grey_objects.push(obj);
        }

        current->color = Color::Black;
        count++;
    }

    if (grey_objects.empty())
        is_running = false;
}

void GC::sweep()
{
    for (auto iter = all_objects.begin(); iter != all_objects.end();)
        if ((*iter)->color == Color::White)
        {
            delete *iter;
            iter = all_objects.erase(iter);
        }
        else
        {
            iter++;
        }
}

void GC::clear_all()
{
    for (auto iter = all_objects.begin(); iter != all_objects.end(); iter++)
        delete *iter;
    all_objects.clear();
}

测试程序：

#include <iostream>
#include "gc.hpp"
#include "gc.cpp"

struct ObjectA : public GCObject
{
    int id = 0;
    ObjectA(int i) : id(i) { std::cout << "ObjectA(id: " << id << ")" << std::endl; }
    ~ObjectA() override { std::cout << "~ObjectA(id: " << id << ")" << std::endl; }

    std::vector<GCObject *> trace() override { return {}; }
};

struct ObjectB : public GCObject
{
    int id = 0;
    ObjectB(int i) : id(i) { std::cout << "ObjectB(id: " << id << ")" << std::endl; }
    ~ObjectB() override { std::cout << "~ObjectB(id: " << id << ")" << std::endl; }

    ObjectA *obj = nullptr;
    std::vector<GCObject *> trace() override
    {
        if (obj)
            return {obj};
        else
            return {};
    }
};

int main()
{
    ObjectA *obj1 = new ObjectA(1);
    ObjectA *obj2 = new ObjectA(2);
    ObjectB *obj3 = new ObjectB(3);
    ObjectA *obj4 = new ObjectA(4);
    obj3->obj = obj4;

    GC::gc.start({obj2, obj3});
    GC::gc.step(10);

    std::cout << "-----sweep-----" << std::endl;

    GC::gc.sweep();

    std::cout << "-----clear all-----" << std::endl;

    GC::gc.clear_all();

    return 0;
}