Homework #8

Q: What is the expected output?

A: My solution has:

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

Garbage collecting...(debug): found block of size 18 at Pointer(13)

0! = 1
i is now 0, l is now Pointer(-1)
1! = 1
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(20)
2! = 2
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(14)
Garbage collecting...(debug): found block of size 13 at Pointer(0)
(debug): found block of size 15 at Pointer(16)

i is now 2, l is now Pointer(29)
3! = 6
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(23)
i is now 2, l is now Pointer(20)
i is now 3, l is now Pointer(17)
4! = 24
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(8)
i is now 2, l is now Pointer(5)
i is now 3, l is now Pointer(1)
Garbage collecting...(debug): found block of size 21 at Pointer(10)

i is now 4, l is now Pointer(29)
5! = 120
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(23)
i is now 2, l is now Pointer(20)
i is now 3, l is now Pointer(17)
i is now 4, l is now Pointer(14)
i is now 5, l is now Pointer(11)
Garbage collecting...(debug): found block of size 10 at Pointer(0)
(debug): found block of size 6 at Pointer(25)

6! = 720
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(26)
i is now 2, l is now Pointer(8)
i is now 3, l is now Pointer(5)
i is now 4, l is now Pointer(1)
Garbage collecting...(debug): found block of size 15 at Pointer(10)
(debug): found block of size 3 at Pointer(28)

i is now 5, l is now Pointer(29)
i is now 6, l is now Pointer(23)
7! = 5040
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(17)
i is now 2, l is now Pointer(14)
i is now 3, l is now Pointer(11)
Garbage collecting...(debug): found block of size 10 at Pointer(0)
(debug): found block of size 12 at Pointer(19)

i is now 4, l is now Pointer(29)
i is now 5, l is now Pointer(26)
i is now 6, l is now Pointer(23)
i is now 7, l is now Pointer(20)
8! = 40320
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(5)
i is now 2, l is now Pointer(1)
Garbage collecting...(debug): found block of size 24 at Pointer(7)

i is now 3, l is now Pointer(29)
i is now 4, l is now Pointer(26)
i is now 5, l is now Pointer(23)
i is now 6, l is now Pointer(20)
i is now 7, l is now Pointer(17)
i is now 8, l is now Pointer(14)
9! = 362880
i is now 0, l is now Pointer(-1)
i is now 1, l is now Pointer(8)
Garbage collecting...(debug): found block of size 7 at Pointer(0)
(debug): found block of size 21 at Pointer(10)

i is now 2, l is now Pointer(29)
i is now 3, l is now Pointer(26)
i is now 4, l is now Pointer(23)
i is now 5, l is now Pointer(20)
i is now 6, l is now Pointer(17)
i is now 7, l is now Pointer(14)
i is now 8, l is now Pointer(11)
i is now 9, l is now Pointer(5)
10! = 3628800
i is now 0, l is now Pointer(-1)
Garbage collecting...(debug): found block of size 31 at Pointer(0)

i is now 1, l is now Pointer(29)
i is now 2, l is now Pointer(26)
i is now 3, l is now Pointer(23)
i is now 4, l is now Pointer(20)
i is now 5, l is now Pointer(17)
i is now 6, l is now Pointer(14)
i is now 7, l is now Pointer(11)
i is now 8, l is now Pointer(8)
i is now 9, l is now Pointer(5)
i is now 10, l is now Pointer(1)
Garbage collecting...
Warning: Couldn't allocate any memory.
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
        at HeapManager$Pointer.poke(HeapManager.java:62)
        at Client.computeFactorial(Client.java:80)
        at Client.main(Client.java:22)

Q: I keep getting an IndexOutOfBoundsException in peek. I can't figure out why it happens.

A: It happens if

1. The client (mis-)uses a null pointer returned by allocate. If the allocator returns a null pointer, the client will crash. This will happen eventually. The allocator should have printed a warning that it couldn't allocate any memory.
2. The HeapManager class itself misused a null pointer. This is a bug in your code.

NB: You can assume that any pointer you encounter during the mark phase is either null or points to a block returns by the allocator. In the latter case, if you implemented the allocator correctly to keep track of how big the block was, you can use p.peek(-1) to get the size of the block.