src/script/gc.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6 #include "builtins.h"
   7 #include "expr.h"
   8 #include "gc.h"
   9 #include "system/error.h"
  10 #include "system/lt.h"
  11
  12 #define GC_INITIAL_CAPACITY 256
  13
  14 struct Gc
  15 {
  16     Lt *lt;
  17     struct Expr *exprs;
  18     int *visited;
  19     size_t size;
  20     size_t capacity;
  21 };
  22
  23 static long int value_of_expr(struct Expr expr)
  24 {
  25     if (expr.type == EXPR_CONS) {
  26         return (long int) expr.cons;
  27     } else if (expr.type == EXPR_ATOM) {
  28         return (long int) expr.atom;
  29     } else {
  30         return 0;
  31     }
  32 }
  33
  34 static int compare_exprs(const void *a, const void *b)
  35 {
  36     assert(a);
  37     assert(b);
  38
  39     const long int ptr_a = value_of_expr(*(const struct Expr *)a);
  40     const long int ptr_b = value_of_expr(*(const struct Expr *)b);
  41     const long int d = ptr_b - ptr_a;
  42
  43     if (d < 0) {
  44         return -1;
  45     } else if (d > 0) {
  46         return 1;
  47     } else {
  48         return 0;
  49     }
  50 }
  51
  52 Gc *create_gc(void)
  53 {
  54     Lt *lt = create_lt();
  55     if (lt == NULL) {
  56         return NULL;
  57     }
  58
  59     Gc *gc = PUSH_LT(lt, malloc(sizeof(Gc)), free);
  60     if (gc == NULL) {
  61         throw_error(ERROR_TYPE_LIBC);
  62         RETURN_LT(lt, NULL);
  63     }
  64     gc->lt = lt;
  65
  66     gc->exprs = PUSH_LT(lt, malloc(sizeof(struct Expr) * GC_INITIAL_CAPACITY), free);
  67     if (gc->exprs == NULL) {
  68         throw_error(ERROR_TYPE_LIBC);
  69         RETURN_LT(lt, NULL);
  70     }
  71
  72     gc->visited = PUSH_LT(lt, malloc(sizeof(int) * GC_INITIAL_CAPACITY), free);
  73     if (gc->visited == NULL) {
  74         throw_error(ERROR_TYPE_LIBC);
  75         RETURN_LT(lt, NULL);
  76     }
  77
  78     gc->size = 0;
  79     gc->capacity = GC_INITIAL_CAPACITY;
  80
  81     return gc;
  82 }
  83
  84 void destroy_gc(Gc *gc)
  85 {
  86     assert(gc);
  87
  88     for (size_t i = 0; i < gc->size; ++i) {
  89         destroy_expr(gc->exprs[i]);
  90     }
  91
  92     RETURN_LT0(gc->lt);
  93 }
  94
  95 int gc_add_expr(Gc *gc, struct Expr expr)
  96 {
  97     assert(gc);
  98
  99     if (gc->size >= gc->capacity) {
 100         const size_t new_capacity = gc->capacity * 2;
 101         struct Expr *const new_exprs = realloc(
 102             gc->exprs,
 103             sizeof(struct Expr) * new_capacity);
 104
 105         if (new_exprs == NULL) {
 106             return -1;
 107         }
 108
 109         gc->capacity = new_capacity;
 110         gc->exprs = REPLACE_LT(gc->lt, gc->exprs, new_exprs);
 111     }
 112
 113     gc->exprs[gc->size++] = expr;
 114
 115     return 0;
 116 }
 117
 118 static long int gc_find_expr(Gc *gc, struct Expr expr)
 119 {
 120     assert(gc);
 121     (void) expr;
 122
 123     struct Expr *result =
 124         (struct Expr *) bsearch(&expr, gc->exprs, gc->size,
 125                                 sizeof(struct Expr), compare_exprs);
 126
 127     if (result == NULL) {
 128         return -1;
 129     }
 130
 131     return (long int) (result - gc->exprs);
 132 }
 133
 134 static void gc_traverse_expr(Gc *gc, struct Expr root)
 135 {
 136     assert(gc);
 137     const long int root_index = gc_find_expr(gc, root);
 138     assert(root_index >= 0);
 139
 140     if (gc->visited[root_index]) {
 141         return;
 142     }
 143
 144     if (cons_p(root)) {
 145         gc_traverse_expr(gc, root.cons->car);
 146         gc_traverse_expr(gc, root.cons->cdr);
 147     }
 148
 149     gc->visited[root_index] = 1;
 150 }
 151
 152 void gc_collect(Gc *gc, struct Expr root)
 153 {
 154     assert(gc);
 155     (void) root;
 156
 157     /* Sort gc->exprs O(nlogn) */
 158     qsort(gc->exprs, gc->size, sizeof(struct Expr), compare_exprs);
 159
 160     /* Defragment O(n) */
 161     while(gc->size > 0 && gc->exprs[gc->size - 1].type == EXPR_VOID) {
 162         gc->size--;
 163     }
 164
 165     /* Initialize visited array O(n) */
 166     memset(gc->visited, 0, sizeof(int) * gc->size);
 167
 168     /* Traverse root O(nlogn)  */
 169     gc_traverse_expr(gc, root);
 170
 171     /* Dealloc unvisted O(n)   */
 172     for (size_t i = 0; i < gc->size; ++i) {
 173         if (!gc->visited[i]) {
 174             destroy_expr(gc->exprs[i]);
 175             gc->exprs[i] = void_expr();
 176         }
 177     }
 178 }
 179
 180 void gc_inspect(const Gc *gc)
 181 {
 182     for (size_t i = 0; i < gc->size; ++i) {
 183         if (gc->exprs[i].type == EXPR_VOID) {
 184             printf(".");
 185         } else {
 186             printf("+");
 187         }
 188     }
 189     printf("\n");
 190 }