Simple Reference Counting GC for building [static typed] scripting language.

gc.c

#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;
}

output

$> 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!