CodingGyan

Reference Counting Garbage Collector

hard JVM, Memory and Performance

Problem

Simulate reference counting. Every object has a count of how many holders point to it. Commands: new X creates object X with count 1 (the program holds it). ref A B means that object A now points to object B, so the count of B goes up by 1. drop X means that the program lets go of X, so the count of X goes down by 1. When a count becomes 0, print freed X; then the object lets go of all objects it points to (in the order they were added with ref), and the same rule applies to them. report prints alive: followed by the names of all objects that are not freed, in alphabetical order, or alive: none. Show that cycles of objects are never freed.

Constraints

  • 1 <= commands <= 10^4
  • Names are lowercase words
  • Only existing objects are dropped

Examples

Input

new a
new b
ref a b
drop b
drop a
report

Output

freed a
freed b
alive: none

Solutions

Best approachTime O(n)Space O(n)

Reference counting frees an object as soon as nobody points to it, but it can never free a cycle of objects (a points to b, b points to a), because each keeps the other's count above zero. The JVM uses tracing collectors (like mark and sweep) that do not have this problem; CPython uses reference counting plus a cycle detector.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process lines.
 * Input   : Several lines.
 * Output  : Freed objects and reports.
 * Approach: Reference counts.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: Every object has a count and a list of the objects it points to.
        static class Heap {
            final java.util.Map<String, Integer> counts = new java.util.HashMap<>();
            final java.util.Map<String, java.util.List<String>> pointers = new java.util.HashMap<>();
            final java.util.List<String> output = new java.util.ArrayList<>();

            void create(String name) {
                counts.put(name, 1);
                pointers.put(name, new java.util.ArrayList<>());
            }

            void reference(String from, String to) {
                pointers.get(from).add(to);
                counts.merge(to, 1, Integer::sum);
            }

            // Step 2: Lower the count. At 0 the object is freed and it lets go of everything it points to.
            void release(String name) {
                int left = counts.merge(name, -1, Integer::sum);
                if (left == 0) {
                    output.add("freed " + name);
                    counts.remove(name);
                    for (String child : pointers.remove(name)) {
                        release(child);
                    }
                }
            }

            void report() {
                java.util.List<String> names = new java.util.ArrayList<>(counts.keySet());
                java.util.Collections.sort(names);
                output.add("alive: " + (names.isEmpty() ? "none" : String.join(" ", names)));
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        Heap heap = new Heap();
        for (String line : lines) {
            String[] part = line.split(" ");
            if (part[0].equals("new")) {
                heap.create(part[1]);
            } else if (part[0].equals("ref")) {
                heap.reference(part[1], part[2]);
            } else if (part[0].equals("drop")) {
                heap.release(part[1]);
            } else {
                heap.report();
            }
        }
        return heap.output.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (1)
  1. Why can a cycle never reach count 0?

Try these next