src/script/gc.c

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