Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.