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     RETURN_LT0(gc->lt);
  88 }
  89
  90 int gc_add_expr(Gc *gc, struct Expr expr)
  91 {
  92     assert(gc);
  93
  94     if (gc->size >= gc->capacity) {
  95         const size_t new_capacity = gc->capacity * 2;
  96         struct Expr *const new_exprs = realloc(
  97             gc->exprs,
  98             sizeof(struct Expr) * new_capacity);
  99
 100         if (new_exprs == NULL) {
 101             return -1;
 102         }
 103
 104         gc->capacity = new_capacity;
 105         gc->exprs = REPLACE_LT(gc->lt, gc->exprs, new_exprs);
 106     }
 107
 108     gc->exprs[gc->size++] = expr;
 109
 110     return 0;
 111 }
 112
 113 static long int gc_find_expr(Gc *gc, struct Expr expr)
 114 {
 115     assert(gc);
 116     (void) expr;
 117
 118     struct Expr *result =
 119         (struct Expr *) bsearch(&expr, gc->exprs, gc->size,
 120                                 sizeof(struct Expr), compare_exprs);
 121
 122     if (result == NULL) {
 123         return -1;
 124     }
 125
 126     return (long int) (result - gc->exprs);
 127 }
 128
 129 static void gc_traverse_expr(Gc *gc, struct Expr root)
 130 {
 131     assert(gc);
 132     const long int root_index = gc_find_expr(gc, root);
 133     assert(root_index >= 0);
 134
 135     if (gc->visited[root_index]) {
 136         return;
 137     }
 138
 139     if (cons_p(root)) {
 140         gc_traverse_expr(gc, root.cons->car);
 141         gc_traverse_expr(gc, root.cons->cdr);
 142     }
 143
 144     gc->visited[root_index] = 1;
 145 }
 146
 147 void gc_collect(Gc *gc, struct Expr root)
 148 {
 149     assert(gc);
 150     (void) root;
 151
 152     /* Sort gc->exprs O(nlogn) */
 153     qsort(gc->exprs, gc->size, sizeof(struct Expr), compare_exprs);
 154
 155     /* Defragment O(n) */
 156     while(gc->size > 0 && gc->exprs[gc->size - 1].type == EXPR_VOID) {
 157         gc->size--;
 158     }
 159
 160     /* Initialize visited array O(n) */
 161     memset(gc->visited, 0, sizeof(int) * gc->size);
 162
 163     /* Traverse root O(nlogn)  */
 164     gc_traverse_expr(gc, root);
 165
 166     /* Dealloc unvisted O(n)   */
 167     for (size_t i = 0; i < gc->size; ++i) {
 168         if (!gc->visited[i]) {
 169             destroy_expr(gc->exprs[i]);
 170             gc->exprs[i] = void_expr();
 171         }
 172     }
 173 }