Skip to content

Instantly share code, notes, and snippets.

@nomi-san

nomi-san/gc.c

Last active May 25, 2020
Embed
What would you like to do?
Simple Reference Counting GC for building [static typed] scripting language.
#include <stdio.h>
#include <stdlib.h>
typedef struct _Obj {
char data;
int ref;
struct _Obj *next;
} Obj;
// append obj to previous
Obj *appendObj(Obj *o, Obj **m) {
if (m != NULL && o != NULL) {
o->next = (*m);
(*m) = o;
}
return o;
}
// create new obj, append to previous if `m` is valid
Obj *newObj(char data, Obj **m) {
Obj *o = malloc(sizeof(Obj));
o->ref = 0;
o->data = data;
o->next = NULL;
if (m != NULL) {
appendObj(o, m);
}
return o;
}
// print obj list
void printObj(Obj *o) {
if (o == NULL) printf("Empty Obj!\n");
while (o != NULL) {
Obj *n = o->next;
if (o->ref <= 0)
printf("/X/ -> %c\n", o->data);
else
printf("/%d/ -> %c\n", o->ref, o->data);
o = n;
}
}
// clean obj list
// clean all if `m` is NULL
// otherwise, append valid obj (ref > 0) to `m`
void cleanObj(Obj **o, Obj **m) {
while (*o != NULL) {
Obj *n = (*o)->next;
(*o)->ref--; // decrease ref
if ((m == NULL) || ((*o)->ref <= 0)) {
free(*o);
}
else {
(*o)->next = *m;
(*m) = (*o);
}
*o = n;
}
(*o) = NULL;
}
// ref count
Obj *refObj(Obj *o, int ref)
{
if (ref == 0) {
o->ref = 0;
}
else {
o->ref += ref;
}
return o;
}
int main()
{
/* simulate scripting
new(...); // ref: 0, no assign
var $a; // $a: 1
{
var $b; // $b: 1
var $c; // $c: 1
$c = nil; // $c: 0
{
var $d = $b; // $b: 2
var $e; // $e: 1
$c = $e; // $e: 2
_ } |
_ } | \
| \ V
\ V [block_2]
V [block_1]
[global]
*/
Obj *global = NULL;
Obj *block_1 = NULL;
Obj *block_2 = NULL;
printf("\n=== #1 initialize all ====\n");
printf("\nglobal scope:\n");
Obj *$_ = newObj('?', &global); refObj($_, 0);
Obj *$a = newObj('a', &global); refObj($a, +1);
printObj(global);
printf("\nblock 1:\n");
Obj *$b = newObj('b', &block_1); refObj($b, +1);
Obj *$c = newObj('c', &block_1); refObj($c, +1);
refObj($c, 0); // or -1
printObj(block_1);
printf("\nblock 2:\n");
Obj *$d = $b; // no need to add red, bcz' block_1 > block_2
Obj *$e = newObj('e', &block_2); refObj($e, +1);
// $e will forward to block_1
$c = refObj($e, +1);
printObj(block_2);
printf("\n=== #2 gc block 2 ====\n");
cleanObj(&block_2, &block_1);
printf("\nblock 2:\n");
printObj(block_2);
printf("\nblock 1:\n");
printObj(block_1);
printf("\n=== #3 gc block 1 ====\n");
cleanObj(&block_1, &global);
printf("\nblock 1:\n");
printObj(block_1);
printf("\nglobal 1:\n");
printObj(global);
printf("\n=== #4 gc global (all) ====\n");
cleanObj(&global, NULL); // clean all
printf("\nglobal:\n");
printObj(global);
printf("\ndone!\n");
return 0;
}
$> gcc -w -O2 -o gc gc.c
$> ./gc
=== #1 initialize all ====
global scope:
/1/ -> a
/X/ -> ?
block 1:
/X/ -> c
/1/ -> b
block 2:
/2/ -> e
=== #2 gc block 2 ====
block 2:
Empty Obj!
block 1:
/1/ -> e
/X/ -> c
/1/ -> b
=== #3 gc block 1 ====
block 1:
Empty Obj!
global 1:
/1/ -> a
/X/ -> ?
=== #4 gc global (all) ====
global:
Empty Obj!
done!
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.