Created
January 19, 2024 04:02
-
-
Save tjdevries/290e8682b1e299064cab350b58314d85 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // TODOs offstream: | |
| // - differences between typedeft shenanigans | |
| // Jokes: | |
| // - mark-and-sweep you off your feet | |
| // For eductional purposes, should we implement | |
| // both a mark-and-sweep, as well as a ref-count? | |
| #include "garbage.h" | |
| #include <assert.h> | |
| #include <stdbool.h> | |
| #include <stddef.h> | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| // When we work with objects, we're really | |
| // working with pointers to objects. | |
| // | |
| // This keeps everything the same size and | |
| // has some nice properties later that we will see :) | |
| typedef struct object_t *object; | |
| typedef enum ObjectKind { | |
| INTEGER, | |
| FLOAT, | |
| STRING, | |
| VEC_3, | |
| TUPLE, | |
| } object_kind_t; | |
| typedef struct { | |
| size_t size; | |
| char *characters; | |
| } obj_string; | |
| typedef struct { | |
| object *x; | |
| object *y; | |
| object *z; | |
| } obj_vector_3; | |
| typedef struct { | |
| size_t size; | |
| object **elements; | |
| } obj_tuple; | |
| typedef union ObjectData { | |
| int v_int; | |
| float v_float; | |
| obj_vector_3 v_vec_3; | |
| obj_string v_string; | |
| obj_tuple v_tuple; | |
| } object_data_t; | |
| typedef struct object_t { | |
| int ref_count; | |
| object_kind_t obj_kind; | |
| object_data_t obj_data; | |
| } object_t; | |
| void gc_object_dec(object *ref); | |
| void gc_object_free(object *ref) { | |
| object obj = *ref; | |
| assert(obj->ref_count == 0); | |
| // decrement all the things this is holding | |
| switch (obj->obj_kind) { | |
| case INTEGER: | |
| // Integers are allocated within the object, so nothing to free | |
| break; | |
| case FLOAT: | |
| // Floats are allocated within the object, so nothing to free | |
| break; | |
| case STRING: { | |
| // Free the allocated characters for the string. | |
| obj_string *str = &obj->obj_data.v_string; | |
| free(str->characters); | |
| break; | |
| } | |
| case VEC_3: { | |
| // We don't have to *free* the objects, | |
| // we simply decrement their reference counts. | |
| // | |
| // If they go to 0, decrement will handle freeing them. | |
| obj_vector_3 *vec = &obj->obj_data.v_vec_3; | |
| gc_object_dec(vec->x); | |
| gc_object_dec(vec->y); | |
| gc_object_dec(vec->z); | |
| break; | |
| } | |
| case TUPLE: { | |
| obj_tuple *tuple = &obj->obj_data.v_tuple; | |
| // decrement all the references in our tuple | |
| for (size_t i = 0; i < tuple->size; i++) { | |
| object *elt = tuple->elements[i]; | |
| gc_object_dec(elt); | |
| } | |
| // (tricky to remember) Free the element list | |
| free(tuple->elements); | |
| break; | |
| } | |
| default: | |
| assert(false); | |
| } | |
| // Free the memory that we allocated for an object. | |
| free(obj); | |
| // Mark our object as NULL. | |
| // This makes sure that we can never reference it again | |
| // (and that we can assert that it has been freed easily) | |
| *ref = NULL; | |
| return; | |
| } | |
| void gc_object_inc(object *ref) { | |
| if (ref == NULL || *ref == NULL) { | |
| return; | |
| } | |
| object obj = *ref; | |
| // Should only increment live objects | |
| assert(obj->ref_count >= 1); | |
| obj->ref_count++; | |
| return; | |
| } | |
| void gc_object_dec(object *ref) { | |
| if (ref == NULL || *ref == NULL) { | |
| return; | |
| } | |
| object obj = *ref; | |
| obj->ref_count--; | |
| // Should never get a negative ref count | |
| assert(obj->ref_count >= 0); | |
| if (obj->ref_count == 0) { | |
| return gc_object_free(ref); | |
| } | |
| return; | |
| } | |
| object make_int(int i) { | |
| object obj = malloc(sizeof(object_t)); | |
| assert(obj != NULL); | |
| obj->ref_count = 1; | |
| obj->obj_kind = INTEGER; | |
| obj->obj_data = (object_data_t){.v_int = i}; | |
| return obj; | |
| } | |
| object make_tuple_2(object *a, object *b) { | |
| obj_tuple tuple = {0}; | |
| gc_object_inc(a); | |
| gc_object_inc(b); | |
| tuple.size = 2; | |
| tuple.elements = malloc(sizeof(object_t) * 2); | |
| tuple.elements[0] = a; | |
| tuple.elements[1] = b; | |
| object obj = malloc(sizeof(object_t)); | |
| obj->ref_count = 1; | |
| obj->obj_kind = TUPLE; | |
| obj->obj_data = (object_data_t){.v_tuple = tuple}; | |
| return obj; | |
| } | |
| void test_free_int_first() { | |
| object i1 = make_int(1); | |
| object i2 = make_int(2); | |
| object obj = make_tuple_2(&i1, &i2); | |
| gc_object_inc(&obj); | |
| gc_object_dec(&obj); | |
| // Free i1 before freeing list | |
| gc_object_dec(&i1); | |
| assert(i1 != NULL); | |
| // Now there are no references to i1, so it should be freed. | |
| gc_object_dec(&obj); | |
| assert(obj == NULL); | |
| // i1 also magically gets updated! | |
| assert(i1 == NULL); | |
| // Clean up last memory | |
| gc_object_dec(&i2); | |
| assert(i2 == NULL); | |
| } | |
| void test_free_tuple_first() { | |
| object i1 = make_int(1); | |
| object i2 = make_int(2); | |
| object obj = make_tuple_2(&i1, &i2); | |
| gc_object_inc(&obj); | |
| gc_object_dec(&obj); | |
| gc_object_dec(&obj); | |
| assert(obj == NULL); | |
| // Free i1 after freeing list | |
| assert(i1 != NULL); | |
| gc_object_dec(&i1); | |
| assert(i1 == NULL); | |
| // Clean up last memory | |
| gc_object_dec(&i2); | |
| assert(i2 == NULL); | |
| } | |
| void test() { | |
| test_free_int_first(); | |
| test_free_tuple_first(); | |
| } | |
| // Plan: | |
| // 1. Write a refcount gc | |
| // 2. Talk about where refcount fails | |
| // 3. Write a mark-and-sweep gc | |
| // 4. Compare & Contrast | |
| // (in the course): Introduce ownership as a concept |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment