Cheney's Algorithm applet
Introduction: This applet graphically illustrates the Cheney's algorithm
for a copying, semispace garbage collecting algorithm. It allows for stepping forward and
backward through examples with associated text descriptions and for loading of arbitrary
Included in the applet are three source files ConsCell.java, CheneyPanel.java,
and CheneyApplet.java. The files hold the following purposes:
In addition there are two other files included in this submission:
- ConsCell.java: this class represents a cons cell, that is, a
simple structure which contains to pointers to other cons cells. This is the basic
unit of memory used in illustrating the Cheney's algorithm. This class will maintain
the state of the cons cell and the pointer values, as well as graphical features needed
for displaying the cons cell.
- CheneyPanel.java: this class contains all the logic for moving the
Cheney's algorithm forward and backward step-by-step. It maintains the information and
cons cells of the current collection example.
- CheneyApplet.java: this is the main applet class. It contains the UI
elements for interacting with the CheneyPanel and the current collection example. The class
can be run either as an applet or an application.
Once you start the applet, you are shown the default collection example which is built in. The
main component shows a graphical representation of memory of the example: the root cells are shown
in the top row of cons cells and the second row of cons cells shows the from-space of the heap. The
buttons on the left allow you to step the current example forward or backwards by clicking the
appropriate button. As you do so, the picture of the memory will update as new cons cells are
allocated in the bottom row (the to-space) and pointers are moved and updated. In addition, the
cons cells will change colors based upon what it happening:
- ex1.txt: a sample example file which may be loaded into the applet.
- cheney.html: a web page briefly describing Cheney's algorithm and
outlining how to use the applet.
Furthermore, at each step, a brief text description of what is taking place is added to the scrolling
text area at the bottom of the applet. The other two buttons allow you to reset the current
example to its beginning state, or to load a new example. To load a new example, you are prompted
for a filename giving a file which contains the example information: this allows you to prepare
beforehand then quickly load several different examples. The format of the input file is outlined
by the sample file below:
- white: default state
- yellow: marks the pointer that is currently being scanned/updated
- pink: indicates that the pointer has already been scanned
- green: indicates that the cons cell had a reference to it forwarded to the to-space
# Here is a sample example file; notice that comment lines begin with '#'
# The first line of the file is the number of root cons cells
# The second line are the pointers of the root cons cells; -1 means no
# pointer, other numbers are indexes into the from-space (0 points to
# first cells in from space, 1 points to next, etc...). Parens and commas
# are allowed.
((0 -1) (0 1) (-1 1))
# The third line is the number fo from-space cons cells; this has to be at
# least the greatest number from the previous line + 1
# The fourth line are the from-space cell pointers; these reference other cells
# in the from-space
((-1 -1) (0 -1) (1 -1))
# This file should end with a comment or blank line
Essentially, the input file has at least four lines with optional comment lines. Comment lines
begin with '#'. The four lines give the number of root cons cells, their pointers into the heap,
the number of heap cons cells, and the heap cells' pointers. If any of this data is missing,
improperly formatted, or inconsistent, then the new example will fail to load the current example
will remain unchanged.