Loading page…
Master the fundamental concepts of garbage collection through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksReference counting increments on alias creation, decrements on drop. At zero, recurse into children. Swift ARC and Python's primary mechanism use refcounting. Cycles (a->b->a) need a separate cycle breaker or weak refs. Objective-C and COM also built industrial-strength systems on refcounting before tracing GC went mainstream.
inc(obj): header count++. dec(obj): count--; if zero, free children then object. Combine with cycle detection (Python's gc module) for completeness. Thread-safe refcounting uses atomic increment and decrement on every pointer copy.
cLoading…
Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.
You will implement reference counting garbage collection. This exercise requires increment and decrement on pointer operations and recursive freeing when counts reach zero.
Implement reference counting: every object counts the references to it, is freed the moment its count drops to zero, releasing its own references in turn, and you'll see the one thing reference counting can't do on its own: reclaim cycles.
| Command | Effect on counts |
|---|---|
new NAME | create NAME with count 1: the program holds it as a root |
root NAME | +1 on NAME (another root reference) |
unroot NAME | −1 on NAME (drop one root reference) |
link A B | A now points to B: +1 on B |
unlink A B | remove one A → B pointer: −1 on B |
When a decrement brings an object's count to 0, print free NAME, then release each of its outgoing pointers in the order they were linked (each release is a decrement, which may free further objects: depth-first). A freed object's name may be reused by a later new.
The free lines as they happen, then:
cLoading…
An object is a root while it holds at least one root reference (from new or root, not yet undone by unroot). Reachability follows pointers from roots.
Input:
cLoading…
Output:
cLoading…
decrement() function that frees recursively.Hidden tests cover a two-object cycle and a self-loop that leak, extra root references, and reuse of a freed name.