repos / gcs.git

mark_sweep.c

  1#include <stdio.h>
  2#include <stdlib.h>
  3
  4// To simplify things sizes are statically defined
  5#define FIELDS_SIZE 4
  6#define HEAP_SIZE 8
  7#define ROOTS_SIZE 4
  8#define WORKLIST_SIZE 100
  9
 10struct Object;
 11
 12typedef struct Object {
 13  int val;
 14  int field_size;
 15  int isMarked;
 16  struct Object* fields[FIELDS_SIZE];
 17} Object;
 18
 19typedef struct {
 20  int size;
 21  Object** objects;
 22} Heap;
 23
 24typedef struct {
 25  int size;
 26  Object* objects[ROOTS_SIZE];
 27} Roots;
 28
 29typedef struct {
 30  int current;
 31  Object* objects[WORKLIST_SIZE];
 32} Worklist;
 33
 34void push(Worklist* w, Object* o) {
 35  w->current += 1;
 36  w->objects[w->current] = o;
 37}
 38
 39int isEmpty(Worklist *w) {
 40  if (w->current == -1) return 1;
 41
 42  return 0;
 43}
 44
 45Object* pop(Worklist *w) {
 46  Object* item = w->objects[w->current];
 47  w->current -= 1;
 48  return item;
 49}
 50
 51Heap* mkHeap () {
 52  Heap* h = malloc(sizeof(Heap));
 53  h->size = HEAP_SIZE;
 54  h->objects = calloc(h->size, sizeof(Object*));
 55  return h;
 56}
 57
 58int heapObjectsNumber(Heap* h) {
 59  int c = 0;
 60  for (int i = 0; i < h->size; i++) {
 61    if (h->objects[i] != NULL) c++;
 62  }
 63  return c;
 64}
 65
 66void freeHeap (Heap* h) {
 67  for (int i = 0; i < h->size; i++) {
 68    if (h->objects[i] != NULL) {
 69      free(h->objects[i]);
 70    }
 71  }
 72  free(h->objects);
 73  free(h);
 74}
 75
 76Object* allocate(int val, Heap* h) {
 77  Object* p = NULL;
 78  for (int i = 0; i < h->size; i++) {
 79    if (h->objects[i] == NULL && p == NULL) {
 80      p = malloc(sizeof(Object));
 81      *p = (Object){val, FIELDS_SIZE, 0, NULL};
 82      h->objects[i] = p;
 83    }
 84  }
 85  return p;
 86}
 87
 88void mark(Heap* h, Roots* roots, Worklist* w) {
 89  while (isEmpty(w) == 0) {
 90    Object *ref = pop(w);
 91    for (int i = 0; i < ref->field_size; i++) {
 92       Object* child = ref->fields[i];
 93      if (child != NULL && child->isMarked != 1) {
 94        child->isMarked = 1;
 95        push(w, child);
 96      }
 97    }
 98  }
 99}
100
101void markFromRoots(Heap* h, Roots* roots) {
102  Worklist worklist;
103  worklist.current = -1;
104
105  for (int i = 0; i < roots->size; i++) {
106    Object* ref = roots->objects[i];
107    if (ref != NULL && ref->isMarked != 1) {
108      ref->isMarked = 1;
109      push(&worklist, ref);
110      mark(h, roots, &worklist);
111    }
112  }
113}
114
115void sweep(Heap *h) {
116  for (int i = 0; i < h->size; i++) {
117    if (h->objects[i] != NULL) {
118      if (h->objects[i]->isMarked == 1) {
119        h->objects[i]->isMarked = 0; 
120      } else {
121        free(h->objects[i]);
122        h->objects[i] = NULL;
123      }
124    }
125  }
126}
127
128void collect(Heap* h, Roots* roots) {
129  markFromRoots(h, roots);
130  sweep(h);
131}
132
133Object* new(int val, Heap* h, Roots* roots) {
134  Object* ref = allocate(val, h);
135  if (ref == NULL) {
136    printf("Running collect");
137    collect(h, roots);
138    ref = allocate(val, h);
139    if (ref == NULL) {
140      printf("Out of memory\n");
141      exit(0);
142    }
143  }
144  return ref;
145}
146
147int main() {
148  Heap* h = mkHeap();
149  Roots roots;
150  roots.size = ROOTS_SIZE;
151  for (int i = 0; i < roots.size; i++) {
152    roots.objects[i] = NULL;
153  }
154
155  // mutator
156  roots.objects[0] = new(7, h, &roots);
157  roots.objects[0] = new(5, h, &roots);
158
159  roots.objects[0]->fields[0] = new(8, h, &roots);
160
161  printf("heap size before collect: %d\n", heapObjectsNumber(h));
162  printf("heap third obj value: %d\n", h->objects[2]->val);
163
164  collect(h, &roots);
165
166  printf("heap second obj value: %d\n", h->objects[1]->val);
167
168  printf("heap size after collect: %d\n", heapObjectsNumber(h));
169
170  freeHeap(h);
171  return 0;
172}