RCGC.cpp

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <boost/filesystem.hpp>

unsigned next_id;

#define SANITY_CHECK

class GcObject{
public:
	unsigned id;
	bool is_super;
	bool allocated;
	unsigned times_freed;
	unsigned ref_count;
	unsigned invalid_accesses;
	std::vector<GcObject *> references;

	enum class NodeState{
		Undefined,
		RefsCounted,
		VisibilityConfirmed,
		VisibilityTransferred,
		AddedToFinalList,
		Unlinked,
		Freed,
	};
	NodeState freeing_state;
	uintptr_t aux;
	bool visible_from_outside;
	
	template <typename F1, typename F2>
	void traverse_reachable(GcObject *initial, std::vector<GcObject *> &stack, F1 &condition, F2 &operation){
		stack.clear();
		stack.push_back(initial);
		while (stack.size()){
			GcObject *obj = stack.back();
			stack.pop_back();
			if (!obj || !condition(obj))
				continue;
			operation(obj);
			for (auto p : obj->references)
				stack.push_back(p);
		}
	}

#define TR traverse_reachable

	void count_internal_references(std::vector<GcObject *> &stack){
		TR(
			this,
			stack,
			[](GcObject *p){
				p->aux++;
				return p->freeing_state != NodeState::RefsCounted;
			},
			[](GcObject *p){
				p->freeing_state = NodeState::RefsCounted;
				p->aux = 1;
			}
		);
		this->aux--;
	}
	GcObject *list_visible_nodes(std::vector<GcObject *> &stack){
		GcObject *head = nullptr;
		TR(
			this,
			stack,
			[](GcObject *p){ return p->freeing_state != NodeState::VisibilityConfirmed; },
			[&](GcObject *p){
				p->freeing_state = NodeState::VisibilityConfirmed;
				if (p->visible_from_outside = (p->aux != p->ref_count)){
					p->aux = (uintptr_t)head;
					head = p;
				}
			}
		);
		return head;
	}
	void transfer_visibilities(GcObject *list, std::vector<GcObject *> &stack){
		for (auto node = list; node; node = (GcObject *)node->aux){
			TR(
				node,
				stack,
				[](GcObject *p){ return p->freeing_state != NodeState::VisibilityTransferred; },
				[](GcObject *p){
					p->freeing_state = NodeState::VisibilityTransferred;
					p->visible_from_outside = 1;
				}
			);
		}
	}
	std::vector<GcObject *> step4(std::vector<GcObject *> &stack){
		std::vector<GcObject *> freeable;
		TR(
			this,
			stack,
			[](GcObject *p){ return p->freeing_state != NodeState::AddedToFinalList; },
			[&](GcObject *p){
				p->freeing_state = NodeState::AddedToFinalList;
				if (!p->visible_from_outside)
					freeable.push_back(p);
			}
		);
		return freeable;
	}
	GcObject *step4b(std::vector<GcObject *> &stack){
		GcObject *head = nullptr;
		TR(
			this,
			stack,
			[](GcObject *p){ return p->freeing_state != NodeState::AddedToFinalList; },
			[&](GcObject *p){
				p->freeing_state = NodeState::AddedToFinalList;
				if (!p->visible_from_outside){
					p->aux = (uintptr_t)head;
					head = p;
				}
			}
		);
		return head;
	}

	void full_collection(std::vector<GcObject *> &stack){
		TR(
			this,
			stack,
			[](GcObject *p){ return p->freeing_state != NodeState::Unlinked; },
			[](GcObject *p){
				p->freeing_state = NodeState::Unlinked;
				p->unlink();
			}
		);
		TR(
			this,
			stack,
			[](GcObject *p){ return p->freeing_state != NodeState::Freed; },
			[](GcObject *p){
				p->freeing_state = NodeState::Freed;
				p->free_resources();
			}
		);
	}

	void gced_free2(){
		std::vector<GcObject *> stack;
		this->count_internal_references(stack);
		{
			auto list = this->list_visible_nodes(stack);
			if (!list){
				this->full_collection(stack);
				return;
			}
			this->transfer_visibilities(list, stack);
		}
		auto to_be_released = this->step4(stack);
		for (auto p : to_be_released)
			p->unlink();
		for (auto p : to_be_released)
			p->free_resources();
	}
	void gced_free3(){
		std::vector<GcObject *> stack;
		this->count_internal_references(stack);
		auto list = this->list_visible_nodes(stack);
		if (!list){
			this->full_collection(stack);
			return;
		}
		this->transfer_visibilities(list, stack);
		list = this->step4b(stack);
		for (auto node = list; node; node = (GcObject *)node->aux)
			node->unlink();
		for (auto node = list; node; node = (GcObject *)node->aux)
			node->free_resources();
	}
	void unlink(){
		for (auto p : this->references){
			if (!p)
				continue;
#ifdef SANITY_CHECK
			if (!p->allocated)
				this->invalid_accesses++;
#endif
			p->non_recursive_unref();
		}
	}
	void free_resources(){
#ifdef SANITY_CHECK
		this->allocated = 0;
		this->times_freed++;
#endif
		this->ref_count = 0;
	}
	virtual void free(){
		if (this->is_super){
			return;
		}
		for (auto p : this->references){
			if (!p)
				continue;
#ifdef SANITY_CHECK
			if (!p->allocated)
				this->invalid_accesses++;
#endif
			p->unref();
		}
		this->free_resources();
	}
	void non_recursive_unref(){
		--this->ref_count;
	}
public:
	GcObject():
		id(next_id++),
		is_super(0),
		allocated(1),
		ref_count(0),
		times_freed(0),
		invalid_accesses(0),
		freeing_state(NodeState::Undefined){}
	void mark_super(){
		this->is_super = 1;
	}
	void ref(){
		this->ref_count++;
	}
	void unref(){
		this->ref_count--;
		if (this->is_super)
			this->gced_free3();
		else if (!this->ref_count)
			this->free();
	}
	bool is_allocated() const{
		return this->allocated;
	}
	void add_reference(GcObject *ref){
		this->references.push_back(ref);
		if (ref)
			ref->ref();
	}
	unsigned get_times_freed() const{
		return this->times_freed;
	}
	unsigned get_invalid_accesses() const{
		return this->invalid_accesses;
	}
};

typedef boost::filesystem::wpath path_t;

std::ofstream output;

void get_file_list(std::list<GcObject> &objects, boost::filesystem::directory_iterator i){
	typedef boost::filesystem::directory_iterator DirIt;
	DirIt e;
	auto &up = objects.back();
	for (; i != e; ++i){
		objects.push_back(GcObject());
		auto &New = objects.back();
		output
			<<New.id<<' '<<up.id<<std::endl
			<<up.id<<' '<<New.id<<std::endl;
		New.add_reference(&up);
		up.add_reference(&New);
		path_t path = *i;
		try{
			//std::cout <<path<<std::endl;
			bool dir = boost::filesystem::is_directory(path);
			if (dir)
				get_file_list(objects, DirIt(path));
		}catch (...){}
	}
}

void get_file_list(std::list<GcObject> &objects){
	boost::filesystem::directory_iterator it(L"\\");
	objects.clear();
	objects.resize(1);
	objects.back().add_reference(nullptr);
	output.open("output.txt");
	get_file_list(objects, it);
	output.close();
	exit(0);
}

template <typename T>
void analyze_results(const T &objects, int test_case_no, unsigned expected_objects){
	unsigned remaining_objects = 0;
	unsigned incorrect_deallocations = 0;
	unsigned invalid_accesses = 0;
	for (auto &o : objects){
		if (o.is_allocated())
			remaining_objects++;
		incorrect_deallocations += o.get_times_freed() > 1;
		invalid_accesses += o.get_invalid_accesses();
	}
	std::cout <<"\nTest case "<<test_case_no<<".\n";
	if (remaining_objects == expected_objects)
		std::cout <<"OK\n";
	else
		std::cout <<"Objects remaining (should be "<<expected_objects<<"): "<<remaining_objects<<std::endl;
	if (!incorrect_deallocations)
		std::cout <<"OK\n";
	else
		std::cout <<"There were "<<incorrect_deallocations<<" incorrect deallocations.\n";
	if (!invalid_accesses)
		std::cout <<"OK\n";
	else
		std::cout <<"There were "<<invalid_accesses<<" invalid accesses.\n";
}

#define REF(x, y) objectsp[x].add_reference(objectsp + (y))

std::vector<std::pair<unsigned, unsigned> > load_graph(){
	std::vector<std::pair<unsigned, unsigned> > ret;
	std::ifstream input("output.txt");
	while (1){
		std::string line;
		std::getline(input, line);
		if (!input)
			break;
		std::stringstream stream(line);
		unsigned a, b;
		stream >>a >>b;
		ret.push_back(std::make_pair(a, b));
	}
	return ret;
}

std::vector<GcObject> build_graph(std::vector<std::pair<unsigned, unsigned> > &pairs){
	unsigned max = 0;
	std::for_each(pairs.begin(), pairs.end(), [&](const std::pair<unsigned, unsigned> &pair){
		max = std::max(max, pair.first);
		max = std::max(max, pair.second);
	});
	std::vector<GcObject> ret;
	ret.resize(max + 1);
	auto objectsp = &ret[0];
	for (auto &p : pairs){
		objectsp[p.first].add_reference(objectsp + p.second);
	}
	return ret;
}

int main(){
#if 0
	{
		std::vector<std::pair<unsigned, unsigned> > pairs;
		{
			std::ifstream input("output2.txt");
			while (1){
				std::string line;
				std::getline(input, line);
				if (!input)
					break;
				std::stringstream stream(line);
				unsigned a, b;
				stream >>a >>b;
				pairs.push_back(std::make_pair(a, b));
			}
		}
		std::map<unsigned, std::list<unsigned> > map;
		for (auto &p : pairs){
			auto it = map.find(p.first);
			map[p.first].push_back(p.second);
		}
		{
			std::ofstream output("output3.txt");
			output <<"graph {\n";
			for (auto &p : map){
				if (p.second.size() > 1){
					output <<'n'<<p.first<<" -- { ";
					bool skip = 1;
					unsigned limit = 10;
					for (auto n : p.second){
						if (skip){
							skip = 0;
							continue;
						}
						output <<'n' <<n <<' ';
						if (!--limit)
							break;
					}
					output <<"};\n";
				}
			}
			output <<"}\n";
		}
		return 0;
	}
#endif
	srand(time(nullptr));
#if 1
	//test case 1
	//stack->Super->A->B->A
	{
		next_id = 0;
		std::vector<GcObject> objects(2);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		REF(0, 1);
		REF(1, 0);
		objects[0].unref();
		analyze_results(objects, 1, 0);
	}
	//test case 2
	//stack->Super->A->B->C->B
	{
		next_id = 0;
		std::vector<GcObject> objects(3);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		REF(0, 1);
		REF(1, 2);
		REF(2, 1);
		objects[0].unref();
		analyze_results(objects, 2, 0);
	}
	//test case 3
	//stack->Super->A->B->C->B
	//                 B->D->B
	//                    D->E
	{
		next_id = 0;
		std::vector<GcObject> objects(5);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		REF(0, 1);
		REF(1, 2);
		REF(2, 1);
		REF(1, 3);
		REF(3, 1);
		REF(3, 4);
		objects[0].unref();
		analyze_results(objects, 3, 0);
	}
	//test case 4
	//stack->Super->A->B->C->B
	//                 B->D->B
	//                    D->E
	//                 B->E
	{
		next_id = 0;
		std::vector<GcObject> objects(5);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		REF(0, 1);
		REF(1, 2);
		REF(2, 1);
		REF(1, 3);
		REF(3, 1);
		REF(3, 4);
		REF(1, 4);
		objects[0].unref();
		analyze_results(objects, 4, 0);
	}
	//test case 5
	//stack->Super->A->B->C->B
	//                 B->D->B
	//                    D->E
	//                 B->E
	//stack->E
	//test case 6
	//stack->E
	{
		next_id = 0;
		std::vector<GcObject> objects(5);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		REF(0, 1);
		REF(1, 2);
		REF(2, 1);
		REF(1, 3);
		REF(3, 1);
		REF(3, 4);
		REF(1, 4);
		objects[4].ref();
		objects[0].unref();
		analyze_results(objects, 5, 1);
		objects[4].unref();
		analyze_results(objects, 6, 0);
	}
#if 0
	//stack->Super->A->B->C->B
	//                 B->D->B
	//                    D->E
	//                 B->E->B
	//stack->E
	//test case 7
	//stack->E
	{
		next_id = 0;
		std::vector<GcObject> objects(5);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		REF(0, 1);
		REF(1, 2);
		REF(2, 1);
		REF(1, 3);
		REF(3, 1);
		REF(3, 4);
		REF(1, 4);
		REF(4, 1);
		objects[4].ref();
		objects[0].unref();
		objects[4].unref();
		analyze_results(objects, 7, 0);
	}
#endif
	//test case 8
	//test case 9
	{
		next_id = 0;
		std::vector<GcObject> objects(10);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		REF(0, 1);
		REF(1, 2);
		REF(2, 3);
		REF(3, 1);
		REF(3, 4);
		REF(4, 2);
		REF(4, 0);
		objects[5].ref();
		objects[5].mark_super();
		REF(5, 6);
		REF(5, 9);
		REF(6, 7);
		REF(7, 8);
		REF(8, 6);
		REF(8, 9);
		REF(9, 7);

		REF(0, 9);

		objects[5].unref();
		analyze_results(objects, 8, 9);
		objects[0].unref();
		analyze_results(objects, 9, 0);
	}
#endif
#if 1
	//test case 10: randomized graph without cycles, with graph slicing
	{
		next_id = 0;
		std::vector<GcObject> objects(1 << 20);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		for (size_t i = 0; i < objects.size() - 1; i++)
			REF(i, i + 1);
		for (unsigned i = 1 << 22; i--; ){
			unsigned n1 = rand() | (rand() << 15);
			n1 %= objects.size() - 1;
			unsigned n2 = rand() | (rand() << 15);
			auto max = objects.size();
			auto min = n1 + 1;
			n2 = min + n2 % (max - min);
			REF(n1, n2);
		}
		unsigned n = rand() | (rand() << 15);
		n %= objects.size();
		objects[n].ref();
		objects[n].mark_super();
		clock_t t0 = clock();
		objects[0].unref();
		clock_t t1 = clock();
		analyze_results(objects, 10, 0);
		std::cout <<t1 - t0<<std::endl;
		t0 = clock();
		objects[n].unref();
		t1 = clock();
		analyze_results(objects, 11, 0);
		std::cout <<t1 - t0<<std::endl;
	}
	//test case 12: randomized graph
	{
		next_id = 0;
		std::vector<GcObject> objects(1 << 20);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		for (size_t i = 0; i < objects.size() - 1; i++)
			REF(i, i + 1);
		for (unsigned i = 1 << 22; i--; ){
			unsigned n1 = rand() | (rand() << 15);
			n1 %= objects.size();
			unsigned n2 = rand() | (rand() << 15);
			n2 %= objects.size();
			REF(n1, n2);
		}
		unsigned n = rand() | (rand() << 15);
		n %= objects.size();
		//objects[n].ref();
		objects[n].mark_super();
		clock_t t0 = clock();
		objects[0].unref();
		clock_t t1 = clock();
		analyze_results(objects, 12, 0);
		std::cout <<t1 - t0<<std::endl;
		//t0 = clock();
		//objects[n].unref();
		//t1 = clock();
		//analyze_results(objects, 13, 0);
		//std::cout <<t1 - t0<<std::endl;
	}
#endif
#if 0
	//test case 14: self-reference
	{
		next_id = 0;
		std::vector<GcObject> objects(1);
		auto objectsp = &objects[0];
		objects[0].ref();
		objects[0].mark_super();
		REF(0, 0);
		objects[0].unref();
		analyze_results(objects, 14, 0);
	}
#endif
	auto graph_description = load_graph();
	//test case 15: realistic graph, no slicing
	{
		next_id = 0;
		auto objects = build_graph(graph_description);
		objects.front().ref();
		objects.front().mark_super();
		clock_t t0 = clock();
		objects.front().unref();
		clock_t t1 = clock();
		analyze_results(objects, 14, 0);
		std::cout <<t1 - t0<<std::endl;
	}
	//test case 15: realistic graph with slicing
	{
		next_id = 0;
		auto objects = build_graph(graph_description);
		objects.front().ref();
		objects.front().mark_super();
		GcObject *o;
		{
			int j = objects.size() / 2;
			o = &objects[1];
		}
		o->ref();
		o->mark_super();
		o->references.front()->unref();
		o->references.front() = nullptr;
		{
			clock_t t0 = clock();
			objects.front().unref();
			clock_t t1 = clock();
			analyze_results(objects, 15, 0);
			std::cout <<t1 - t0<<std::endl;
		}
		{
			clock_t t0 = clock();
			o->unref();
			clock_t t1 = clock();
			analyze_results(objects, 16, 0);
			std::cout <<t1 - t0<<std::endl;
		}
	}
	return 0;
}