lodus.gc.mark.sweep.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

#if WIN32
#define strdup _strdup
#endif

struct val;

struct list {
	size_t capacity;
	size_t length;
	struct val** values;
};

struct kvp {
	char* name;
	struct val* value;
};

struct map {
	size_t capacity;
	size_t length;
	struct kvp* values;
};

struct val {
	char type;
	union {
		char* str;
		struct list* list;
		int i;
		struct map* map;
	};
	struct val *next, *prev;
	int mark;
};

struct context;
typedef struct val* (*allocate_value_method)(struct context* ctx, char type);
typedef void (*free_value_method)(struct context* ctx, struct val* p);
typedef void (*ref_value_method)(struct context* ctx, struct val* p);

struct context {
	allocate_value_method alloc;
	free_value_method free;

	struct val* allocated;
	int mark;
};


void ctx_val_free(struct context* ctx,struct val* v) {
	if (!v) return;

	if (!v->prev) {
		assert(v == ctx->allocated);
		ctx->allocated = v->next;
	}
	else {
		v->prev->next = v->next;
	}
	if (v->next) {
		v->next->prev = v->prev;
	}

	switch (v->type)
	{
	case 's':
		free(v->str);
		break;
	case 'l':
		for (size_t i = 0; i < v->list->length; i++)
		{
			ctx->free(ctx, v->list->values[i]);
		}
		free(v->list->values);
		free(v->list);
		break;
	case 'm':
		for (size_t i = 0; i < v->map->length; i++)
		{
			free(v->map->values[i].name);
			ctx_val_free(ctx, v->map->values[i].value);
		}
		free(v->map->values);
		free(v->map);
		break;
	}
	free(v);
}

struct val* ctx_val_allocate(struct context* ctx, char type) {
	struct val* v = malloc(sizeof(struct val));
	v->type = type;
	v->next = ctx->allocated;
	ctx->allocated = v;
	v->mark = ctx->mark;
	v->prev = NULL;
	if(v->next)
		v->next->prev = v;
	return v;
}


struct val* str_create(struct context* ctx, char* s) {
	struct val* v = ctx->alloc(ctx, 's');
	v->str = strdup(s);
	return v;
}

struct val* int_create(struct context* ctx, int i) {
	struct val* v = ctx->alloc(ctx, 'i');
	v->i = i;
	return v;
}

struct val* list_create(struct context* ctx, int capacity) {
	struct val* v = ctx->alloc(ctx, 'l');
	v->list = malloc(sizeof(struct list));
	v->list->capacity = capacity;
	v->list->length = 0;
	v->list->values = malloc(sizeof(struct val*) * capacity);
	return v;
}

struct val* map_create(struct context* ctx, int capacity) {
	struct val* v = ctx->alloc(ctx, 'm');
	v->map = malloc(sizeof(struct map));
	v->map->capacity = capacity;
	v->map->length = 0;
	v->map->values = malloc(sizeof(struct kvp) * capacity);
	return v;
}

struct val* list_append(struct context* ctx, struct val* l, struct val* val) {
	assert(l->type == 'l');
	if (l->list->length + 1 > l->list->capacity) {
		printf("Out of capacity!");
		exit(1);
	}
	l->list->values[l->list->length++] = val;
	return l;
}

struct val* list_index(struct context* ctx, struct val* l, size_t index) {
	assert(l->type == 'l');
	if (index >= l->list->length) {
		printf("Out of range!");
		exit(1);
	}
	return l->list->values[index];
}

struct val* map_set(struct context* ctx, struct val* m, char* name, struct val* val) {
	assert(m->type == 'm');
	
	struct kvp* loc = NULL;
	for (size_t i = 0; i < m->map->length; i++)
	{
		if (!strcmp(name, m->map->values[i].name)) {
			m->map->values[i].value = val;

			return m;
		}
		if (!loc && !m->map->values[i].name) {
			loc = &m->map->values[i];
		}
	}
	if(loc) {
		loc->name = strdup(name);
		loc->value = val;
		return m;
	}

	if (m->map->length + 1 > m->map->capacity) {
		printf("Out of range!");
		exit(1);
	}
	m->map->values[m->map->length].name = strdup(name);
	m->map->values[m->map->length].value = val;
	m->map->length++;

	return m;
}

struct val* map_get(struct context* ctx, struct val* m, char* name) {
	assert(m->type == 'm');
	for (size_t i = 0; i < m->map->length; i++)
	{
		if (!strcmp(name, m->map->values[i].name)) {
			return m->map->values[i].value;
		}
	}
	return NULL;
}

struct val* map_del(struct context* ctx, struct val* m, char* name) {
	assert(m->type == 'm');

	for (size_t i = 0; i < m->map->length; i++)
	{
		if (!strcmp(name, m->map->values[i].name)) {

			free(m->map->values[i].name);
			m->map->values[i].name = NULL;
			m->map->values[i].value = NULL;
			return m;
		}
	}

	return m;
}

void val_print(struct context* ctx, struct val* v) {
	if (!v) {
		printf("null");
		return;
	}

	switch (v->type)
	{
	case 's':
		printf("%s", v->str);
		break;
	case 'i':
		printf("%i", v->i);
		break;
	case 'l':
		printf("[");
		for (size_t i = 0; i < v->list->length; i++)
		{
			if (i) printf(", ");
			val_print(ctx, v->list->values[i]);
		}
		printf("]");
		break;
	case 'm':
		printf("{\n");
		for (size_t i = 0; i < v->map->length; i++)
		{
			printf("\t%s: ", v->map->values[i].name);
			val_print(ctx, v->map->values[i].value);
			if (i != v->map->length - 1)
				printf(",");
			printf("\n");
		}
		printf("}");
		break;
	}
}

struct context* ctx_create() {
	struct context* ctx = malloc(sizeof(struct context));
	ctx->alloc = ctx_val_allocate;
	ctx->free = ctx_val_free;
	ctx->allocated = NULL;
	ctx->mark = 0;
	return ctx;
}

void val_raw_free(struct val* v);
void mark(struct context* ctx, struct val* v);

void collect(struct context* ctx, struct val* root) {

	ctx->mark++;

	mark(ctx, root);

	// sweep
	struct val* v = ctx->allocated;
	while (v) {

		struct val* next = v->next;

		if (ctx->mark != v->mark) {
			if (!v->prev) {
				assert(v == ctx->allocated);
				ctx->allocated = v->next;
			}
			else {
				v->prev->next = v->next;
			}
			if (v->next) {
				v->next->prev = v->prev;
			}
			val_raw_free(v);
		}

		v = next;
	}
}


void ctx_free(struct context* ctx) {
	/*
	// why not this?
	while (ctx->allocated) {
		ctx->free(ctx, ctx->allocated);
	}*/

	collect(ctx, NULL);

	free(ctx);
}

void val_raw_free(struct val* v)
{
	switch (v->type)
	{
	case 's':
		free(v->str);
		break;
	case 'l':
		free(v->list->values);
		free(v->list);
		break;
	case 'm':
		for (size_t i = 0; i < v->map->length; i++)
		{
			free(v->map->values[i].name);
		}
		free(v->map->values);
		free(v->map);
		break;
	}
	free(v);
}

void mark(struct context* ctx, struct val* v) {
	if (!v) return;

	if (v->mark == ctx->mark) return;

	switch (v->type)
	{
	case 's':
	case 'i':
		v->mark++;
		break;
	case 'l':
		v->mark++;
		for (size_t i = 0; i < v->list->length; i++)
		{
			mark(ctx, v->list->values[i]);
		}
		break;
	case 'm':
		v->mark++;
		for (size_t i = 0; i < v->map->length; i++)
		{
			mark(ctx, v->map->values[i].value);
		}
		break;
	}
}


int main()
{
	struct context* ctx = ctx_create();
	struct val* person = map_create(ctx, 3);
	map_set(ctx, person, "name", str_create(ctx, "Oren Eini"));
	map_set(ctx, person, "favPrime", int_create(ctx, 17));
	map_set(ctx, person, "dogs",
		list_append(ctx,
			list_append(ctx,
				list_append(ctx,
					list_create(ctx, 3),
					str_create(ctx, "Arava")),
				str_create(ctx, "Pheobe")),
				str_create(ctx, "Oscar")
			)
		);

	struct val* old_dogs = map_get(ctx, person, "dogs");

	map_set(ctx, person, "name", str_create(ctx, "Ayende Rahien"));
	map_set(ctx, person, "dogs",
		list_append(ctx,
		list_append(ctx,
			list_append(ctx,
				list_create(ctx, 3),
				str_create(ctx, "Oscar")),
			str_create(ctx, "Arava")),
		str_create(ctx, "Pheobe")
		));

	val_print(ctx, person);
	printf("\n");

	collect(ctx, person);

	// old_dogs has been collected here!

	ctx_free(ctx);

	// free everything
}