9 #include "system/error.h"
10 #include "system/lt.h"
12 #define GC_INITIAL_CAPACITY 256
23 static long int value_of_expr(struct Expr expr)
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;
34 static int compare_exprs(const void *a, const void *b)
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;
59 Gc *gc = PUSH_LT(lt, malloc(sizeof(Gc)), free);
61 throw_error(ERROR_TYPE_LIBC);
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);
72 gc->visited = PUSH_LT(lt, malloc(sizeof(int) * GC_INITIAL_CAPACITY), free);
73 if (gc->visited == NULL) {
74 throw_error(ERROR_TYPE_LIBC);
79 gc->capacity = GC_INITIAL_CAPACITY;
84 void destroy_gc(Gc *gc)
88 for (size_t i = 0; i < gc->size; ++i) {
89 destroy_expr(gc->exprs[i]);
95 int gc_add_expr(Gc *gc, struct Expr expr)
99 if (gc->size >= gc->capacity) {
100 const size_t new_capacity = gc->capacity * 2;
101 struct Expr *const new_exprs = realloc(
103 sizeof(struct Expr) * new_capacity);
105 if (new_exprs == NULL) {
109 gc->capacity = new_capacity;
110 gc->exprs = REPLACE_LT(gc->lt, gc->exprs, new_exprs);
113 gc->exprs[gc->size++] = expr;
118 static long int gc_find_expr(Gc *gc, struct Expr expr)
123 struct Expr *result =
124 (struct Expr *) bsearch(&expr, gc->exprs, gc->size,
125 sizeof(struct Expr), compare_exprs);
127 if (result == NULL) {
131 return (long int) (result - gc->exprs);
134 static void gc_traverse_expr(Gc *gc, struct Expr root)
137 const long int root_index = gc_find_expr(gc, root);
138 assert(root_index >= 0);
140 if (gc->visited[root_index]) {
145 gc_traverse_expr(gc, root.cons->car);
146 gc_traverse_expr(gc, root.cons->cdr);
149 gc->visited[root_index] = 1;
152 void gc_collect(Gc *gc, struct Expr root)
157 /* Sort gc->exprs O(nlogn) */
158 qsort(gc->exprs, gc->size, sizeof(struct Expr), compare_exprs);
160 /* Defragment O(n) */
161 while(gc->size > 0 && gc->exprs[gc->size - 1].type == EXPR_VOID) {
165 /* Initialize visited array O(n) */
166 memset(gc->visited, 0, sizeof(int) * gc->size);
168 /* Traverse root O(nlogn) */
169 gc_traverse_expr(gc, root);
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();
180 void gc_inspect(const Gc *gc)
182 for (size_t i = 0; i < gc->size; ++i) {
183 if (gc->exprs[i].type == EXPR_VOID) {