Last active
August 16, 2016 11:33
-
-
Save bit-hack/ee467d990828dc9319ef85ce71770621 to your computer and use it in GitHub Desktop.
Minimal example mark and sweep garbage collector.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cassert> | |
#include <list> | |
#include <set> | |
#include <functional> | |
struct object_t { | |
object_t() : child_(nullptr) {} | |
virtual ~object_t() {}; | |
object_t * child_; | |
protected: | |
friend class gc_t; | |
virtual void enumerate__(std::function<void(object_t *)> & func) { | |
func(child_); | |
} | |
}; | |
struct gc_t { | |
template <class T, class... Types> | |
object_t * alloc(Types && ... args) { | |
// check allocation derives from object_t | |
static_assert(std::is_base_of<object_t, T>::value, "type must derive from object_t"); | |
// perform the allocation and call constructor | |
object_t * obj = new T(std::forward<Types>(args) ...); | |
// add to 'allocated' list | |
allocs_.push_back(obj); | |
return obj; | |
} | |
gc_t(); | |
void collect(); | |
void check_in(object_t *); | |
protected: | |
std::list<object_t*> allocs_; | |
std::set<object_t*> valid_; | |
std::set<object_t*> mark_; | |
std::function<void (object_t*)> bounce_; | |
void follow(object_t * obj, std::set<object_t*> & out); | |
}; | |
gc_t::gc_t() { | |
bounce_ = [&](object_t * obj) { | |
if (obj) { | |
follow(obj, mark_); | |
} | |
}; | |
} | |
void gc_t::follow(object_t * obj, std::set<object_t*> & out) { | |
if (obj && out.find(obj) == out.end()) { | |
out.insert(obj); | |
obj->enumerate__(bounce_); | |
} | |
} | |
void gc_t::collect() { | |
for (auto & obj : valid_) { | |
if (obj) { | |
follow(obj, mark_); | |
} | |
} | |
for (auto itt = allocs_.begin(); itt != allocs_.end();) { | |
if (mark_.find(*itt) == mark_.end()) { | |
assert(*itt); | |
delete *itt; | |
itt = allocs_.erase(itt); | |
} | |
else { | |
++itt; | |
} | |
} | |
valid_.clear(); | |
} | |
void gc_t::check_in(object_t * obj) { | |
valid_.insert(obj); | |
} | |
int main(int argc, char ** args) { | |
gc_t gc; | |
// simple alloc chain | |
object_t * obj1 = gc.alloc<object_t>(); | |
obj1->child_ = gc.alloc<object_t>(); | |
// lost allocation chain | |
object_t * obj2 = gc.alloc<object_t>(); | |
obj2->child_ = gc.alloc<object_t>(); | |
obj2->child_->child_ = gc.alloc<object_t>(); | |
obj2 = nullptr; | |
// cyclic reference | |
object_t * obj3 = gc.alloc<object_t>(); | |
obj3->child_ = gc.alloc<object_t>(); | |
obj3->child_->child_ = obj3; | |
// check in discoverable root | |
gc.check_in(obj1); | |
// collect any unreachable allocations | |
gc.collect(); | |
return 0; | |
} |
note: The member 'valid_' is a list of currently known valid allocations, typically the root of any data graph. Allocations can be added via the check_in() method. Known valid allocations must be checked in before any collection; any allocations not reachable from those checked in will be collected when collect() is called.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
note: If the check-ins' are kept up to date, a collection could be triggered every x number of allocs. Question is, how do you keep the check-ins' up to date?