Create a gist now

Instantly share code, notes, and snippets.

@devshorts /gc.java
Last active Feb 20, 2016

What would you like to do?
A toy generational garbage collector
public enum Mode {
Gen0,
Gen1
}
//=============================
@Data
@EqualsAndHashCode(of = "id")
public class Node {
private final String id;
public Node(String id) {
this.id = id;
}
private final List<Node> references = new ArrayList<>();
public void addReference(Node node) {
references.add(node);
}
public void removeReference(Node node) {
references.removeIf(i -> i.getId().equals(node.getId()));
}
}
//=============================
//=============================
public class Gc {
private final Allocator allocator;
public Gc(Allocator allocator) {
this.allocator = allocator;
}
public void collect(Node root, Mode mode) {
final Allocator.Marker marker = allocator.markBuilder(mode);
mark(root, marker, mode);
marker.sweep();
}
private void mark(Node root, Allocator.Marker marker, Mode mode) {
final Mode found = allocator.locateNode(root);
if (found.ordinal() > mode.ordinal()) {
return;
}
marker.mark(root);
root.getReferences().forEach(ref -> mark(ref, marker, mode));
}
}
//=============================
//=============================
public class Allocator {
@Getter
private Set<Node> gen0 = new HashSet<>();
@Getter
private Set<Node> gen1 = new HashSet<>();
public Node newNode() {
return newNode("");
}
public Node newNode(String tag) {
final Node node = new Node(tag + UUID.randomUUID());
getGen0().add(node);
return node;
}
public Mode locateNode(Node tag) {
if (gen1.contains(tag)) {
return Mode.Gen1;
}
return Mode.Gen0;
}
public Marker markBuilder(final Mode mode) {
return new Marker(this, mode);
}
private void promote(final Mode mode) {
switch (mode) {
case Gen0:
gen1.addAll(gen0);
gen0.clear();
break;
case Gen1:
break;
}
}
public static class Marker {
private final Set<String> marks;
private final Allocator allocator;
private final Mode mode;
public Marker(Allocator allocator, final Mode mode) {
this.allocator = allocator;
this.mode = mode;
marks = new HashSet<>();
}
public void mark(Node node) {
marks.add(node.getId());
}
public void sweep() {
Predicate<Node> remove = node -> !marks.contains(node.getId());
allocator.getGen0().removeIf(remove);
allocator.promote(Mode.Gen0);
switch (mode) {
case Gen0:
break;
case Gen1:
allocator.getGen1().removeIf(remove);
allocator.promote(Mode.Gen1);
break;
}
}
}
}
//=============================
//=============================
@Test
public void test() {
final Allocator allocator = new Allocator();
final Gc gc = new Gc(allocator);
final Node root = allocator.newNode();
root.addReference(allocator.newNode());
root.addReference(allocator.newNode());
root.addReference(allocator.newNode());
final Node removable = allocator.newNode("remove");
removable.addReference(allocator.newNode("dangle1"));
removable.addReference(allocator.newNode("dangle2"));
root.addReference(removable);
gc.collect(root, Mode.Gen0);
assertThat(allocator.getGen0().size()).isEqualTo(0);
assertThat(allocator.getGen1().size()).isEqualTo(7);
root.removeReference(removable);
gc.collect(root, Mode.Gen1);
assertThat(allocator.getGen0().size()).isEqualTo(0);
assertThat(allocator.getGen1().size()).isEqualTo(4);
final Node gen1Remove = allocator.newNode();
root.addReference(gen1Remove);
gc.collect(root, Mode.Gen1);
assertThat(allocator.getGen0().size()).isEqualTo(0);
assertThat(allocator.getGen1().size()).isEqualTo(5);
root.removeReference(gen1Remove);
gc.collect(root, Mode.Gen1);
assertThat(allocator.getGen0().size()).isEqualTo(0);
assertThat(allocator.getGen1().size()).isEqualTo(4);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment