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