Mark and Sweep GC

Mark-and-sweep takes a completely different approach from reference counting: instead of tracking counts continuously, it periodically pauses the program and asks one question directly, "starting from everything currently reachable, what's still alive?" Anything left over gets swept away.

It runs in two phases:

1. Mark: starting from a set of "roots" (global variables, local variables currently on the stack), recursively visit every object reachable from them, flagging each one as marked.
2. Sweep: walk every object the allocator has ever handed out, free any that weren't marked, then clear the marks for next time.

#include <stdio.h>
#include <stdlib.h>

typedef enum { OBJ_INT, OBJ_STRING } ObjType;

typedef union {
    int intValue;
    char *stringValue;
} ObjValue;

typedef struct Obj {
    ObjType type;
    int marked;        // replaces refCount
    struct Obj *next;   // every object, linked so sweep can walk them all
    ObjValue as;
} Obj;

void markObject(Obj *obj) {
    if (obj == NULL || obj->marked) return; // already visited, avoid infinite loops on cycles
    obj->marked = 1;
    // if this object type could reference other Objs, mark those too here
}

void sweep(Obj **allObjects) {
    Obj **current = allObjects;
    while (*current != NULL) {
        if (!(*current)->marked) {
            Obj *unreached = *current;
            *current = unreached->next; // unlink it
            free(unreached);
        } else {
            (*current)->marked = 0; // reset for next collection
            current = &(*current)->next;
        }
    }
}

int main(void) {
    // build a small chain: a -> b, only a is reachable from our "root"
    Obj *a = malloc(sizeof(Obj));
    a->type = OBJ_INT;
    a->marked = 0;
    a->as.intValue = 1;

    Obj *b = malloc(sizeof(Obj));
    b->type = OBJ_INT;
    b->marked = 0;
    b->as.intValue = 2;

    a->next = b;
    b->next = NULL;

    markObject(a); // b is never marked, nothing roots it

    sweep(&a); // b gets freed, a survives

    printf("a->as.intValue: %d\n", a->as.intValue);
    printf("a->next was freed and unlinked: %d\n", a->next == NULL);
    return 0;
}

Notice markObject checks obj->marked before recursing, this is exactly what solves the cycle problem from the last lesson: two objects referencing each other both simply get marked once each, then correctly swept together if nothing external points to either.

The tradeoff

Neither is strictly "better", refcounting is used where memory needs to be freed the instant it's unreachable (like Swift's ARC), mark-and-sweep is used where occasional pauses are acceptable in exchange for never leaking cycles (like most JavaScript engines).

Final project

Combine everything from this course: write a small C program with an Obj type (int and string, like the earlier lessons), a way to track "roots", and a working mark + sweep pair that correctly frees unreached objects, including a deliberate reference cycle to prove it doesn't leak. Submit a link to your repository below, an instructor will review it before you can mark this lesson complete.