You will write a memory management package for storing variablelength records in a large memory
space. For background on this project, view the tutorial on sequential fit memory managers available
at OpenDSA Chapter 11.
Your memory pool will consist of a large array of bytes. You will use a doubly linked list to keep
track of the free blocks in the memory pool. This list will be referred to as the freeblock list. You
will use the circular first fit rule for selecting which free block to use for a memory request. That
is, the keep track of the ”current” free block, and the first free block in the linked list that is large
enough to store the requested space will be used to service the request (if any such block exists).
If not all space of this block is needed, then the remaining space will make up a new free block and
be returned to the free list.
Be sure to merge adjacent free blocks whenever a block is released. To do the merge, it will be
necessary to search through the freeblock list, looking for blocks that are adjacent to either the
beginning or the end of the block being returned. Do not consider the first and last memory
positions of the memory pool to be adjacent. That is, the memory pool itself is not considered to
The records that you will store will contain the xycoordinates and name for a city. Aside from the
memory manager’s memory pool and freeblock list, the other major data structure for your project
will be a hash table that supports search on the city names. The hash function will work on the city
name, but the table will actually store the ”handles” to the data records that are currently stored in
the memory pool. A handle is the value returned by the memory manager when a request is made
to insert a new record into the memory pool. This handle is used to recover the record. For a review
on hashing, please read chapter 10 from OpenDSA. You should adopt the character summation
hashing function. You will use closed hashing with linear probing as a collision resolution policy.
Invocation and I/O Files
The program will be invoked from the command-line as:
The name of the program is Memman. Parameter is the initial size of the
memory pool (in bytes) that is to be allocated. (Note that if the memory pool is ever not large
enough, then you will increase the size of the array by an increment of initial-pool-size).
Parameter is the size of the hash table that holds the handles to the records stored in
the memory pool. (You will not be expected to increase the size of the hash table). Your program
will read from text file a series of commands, with one command per line. The
program should terminate after reading the end of the file. No command line will require more than
80 characters. The formats for the commands are as follows. The commands are free-format in that
any number of spaces may come before, between, or after the command name and its parameters.
All coordinates will be signed values small enough to fit in an integer variable. All commands
should generate a suitable output message (some have specific requirements defined below). All
output should be written to standard output.
insert x y name
Insert a new city record into the hash table and the memory manager. Parameters x and y are teh
xy-coordinates for the record, and name is the name of the city for this record. Name may consist of
upper and lower case letters and the underscore symbol. If there is no room in the memory pool to
handle the request, then grow the array size by creating a new array that is from the hash table. If there is no such record, print a suitable
message. Make sure to also remove the record from the memory manager.
Print out all records (coordinates and name) that matches name . If there is no such record,
then print a suitable message.
Dump out a complete listting of the contents of the data base. This listing should contain two
parts. The first part is a listing of the hash table’s contents, one record per line. If a given slot in
the table has no record, then print [EMPTY]. Print the value of the position handle along with the
record. The second part is a listing of a the free blocks, in order of their occurence in the freeblock
Your main design concern for this project will be how to construct the interface for the memory
manager class. While you are not required to do it exactly this way, we recommend that your
memory manager class include something equivalent to the following methods:
// Constructor. poolSize is the size of the memory pool in bytes
// Insert a record and return its position handle // space contains the record to be inserted, of
length size Handle insert(byte space, int size)
// Free a block at the position specified by theHandle
// Merge adjacent free blocks
void remove(Handle theHandle)
// Return the number of butes actually copied into space int get(byte, Handle theHandle,
// Dump a printout of the freeblock list
Another design consideration is how to deal with the fact that the records are variable length. One
option is to store the record’s handle and length in the record array. An alternative is to store the
record’s length in the memory pool along with the record. Both implementations have advantages
and disadvantages. We will adopt the second approach.
The records stored in the memory pool must have the following format. The first byte will be the
length of the record, in bytes. Thus, the total length of a record may not be more than 255 bytes.
The next four bytes will be the xcoordinate. The following four bytes will be the y coordinate.
Note that the coordinates are stored in binary format, not ASCII. The city name then follows the
coordinates. You should not store a NULL terminator byte for the string in the memory pool
For this project, you may only use standard Java classes, Java code that you have written yourself,
and Java code supplied by the CS3114 instructor. You may not use other thirdparty Java code.
You may not use any builtin Java list classes for this assignment.
Programming Standards You must conform to good programming/documentation standards.
Web-CAT will provide feedback on its evaluation of your coding style, and be used for style grading. Beyond meeting Web-CAT’s checkstyle requirements, here are some additional requirements
regarding programming standards:
• You should include a comment explaining the purpose of every instance variable or named
constant you use in your program.
• You should use meaningful identifier names that suggest the meaning or purpose of the
constant, variable, function, etc. Use a consistent convention for how identifier names appear,
such as “camelCasing”.
• Always use named constants or enumerated types instead of literal constants in the code.
• Source files should be under 600 lines.
• There should be a single class in each source file. You can make an exception for small inner
classes (less than 100 lines including comments) if the total file length is less than 600 lines.
We can’t help you with your code unless we can understand it. Therefore, you should no bring
your code to the GTAs or the instructors for debugging help unless it is properly documented and
exhibits good programming style. Be sure to begin your internal documentation right from the
You may only use code you have written, either specically for this project or for earlier programs,
or code provided by the instructor. Note that the OpenDSA code is not designed for the specific
purpose of this assignment, and is therefore likely to require modi cation. It may, however, provide
a useful starting point.
You will implement your project using Eclipse, and you will submit your project using the Eclipse
plugin to WebCAT. Links to the WebCAT client are posted at the class website. If you make
multiple submissions, only your last submission will be evaluated. There is no limit to the number
of submissions that you may make. You will submit the zip file of your project on Canvas as well.
You are required to submit your own test cases with your program, and part of your grade will be
determined by how well your test cases test your program, as defined by Web-CAT’s evaluation
of code coverage. The names of your test files should include the word “Test”, so that Web-CAT
knows what they are. Of course, your program must pass your own test cases. Part of your grade
will also be determined by test cases that are provided by the graders. WebCAT will report to you
which test les have passed correctly, and which have not. Note that you will not be given a copy
of these test files, only a brief description of what each accomplished in order to guide your own
testing process in case you did not pass one of our tests.
When structuring the source files of your project, use a flat directory structure; that is, your source
files will all be contained in the project “src” directory. Any subdirectories in the project will be
ignored. You are permitted to work with a partner on this project. When you work with a partner,
then only one member of the pair will make a submission. Be sure both names are included in the
documentation. Whatever is the final submission from either of the pair members is what we will
grade unless you arrange otherwise with the GTA.
Your project submission must include a statement, pledging your conformance to the Honor Code
requirements for this course. Specifically, you must include the following pledge statement near the
beginning of the file containing the function main() in your program. The text of the pledge will
also be posted online.
// On my honor:
// I have not used source code obtained from another student,
// or any other unauthorized source, either modified or unmodified.
// All source code and documentation used in my program is
// either my original work, or was derived by me from the
// source code published in the textbook for this course.
// I have not discussed coding details about this project with
// anyone other than my partner (in the case of a joint
// submission), instructor, ACM/UPE tutors or the TAs assigned
// to this course. I understand that I may discuss the concepts
// of this program with other students, and that another student
// may help me debug my program so long as neither of us writes
// anything during the discussion or modifies any computer file
// during the discussion. I have violated neither the spirit nor
// letter of this restriction.
Programs that do not contain this pledge will not be graded.