CS 4004 (Spring 2003)

PROGRAMMING ASSIGNMENT #1

Due: April 2, 2003

Policy:

A programming assignment turned in late will be penalized 10% off for each day late. After a week late, the late assignment will be 100% off.
Any Java programs not passing the javac compiler will be counted 0.
Any Java programs not able to generate any output on execution by java will be counted 0.
Partial credits will be given to programs which generate partially correct outputs
All students must observe the Graduate Honor Code. No cheating, plagiarism, falsification, or academic sabotage allowed in this class. Violated students will be reported to Virginia Tech's Graduate Honor System. All assignments turned in should add a Pledge for Assignment clause as follows at the beginning: I pledge that this assignment has been completed in compliance with the Graduate Honor Code and that I have neither given nor received any unauthorized aid on this assignment.

Signed ______________________________________________________

How to Turn in Your Assignment:

Your assignment should be emailed to the class instrcutor at irchen@cs.vt.edu in a ZIP file by the midnight of the specified due date. The ZIP file should contain only the source file, data file and a readme file explaining how to compile and execute the program. Internal documentation of the source file should follow the programming standards (stated later) but is not required.

Assignment:

You will write a memory management package for storing variable-length records in a large memory space. Your memory pool will consist of a large array of characters. You will use a doubly linked list to keep track of the free blocks in the memory pool, which will be referred to as the freeblock list. The freeblock list should store the free blocks in descending order by size of the free block. If two multiple blocks are of the same length, then they should appear in ascending order of their position in the memory pool. You will use the first-fit rule for selecting which free block to use for a memory request. That is, the first free block in the linked list with a size larger than or equal to the the requested size will be used to serve the request, if it 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 merge the free blocks at the beginning and end of the memory pool. That is, the memory pool itself is not considered to be circular.

The records that you will store will contain the xy-coordinates and name of a city. Aside from the memory manager's memory pool and freeblock list, the other major data structure for your project will be the record array, an array that stores the ``handles'' to 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 retrieve the record. Note that the record array is something of an artificial construct that is being used to simplify the testing procedures for the project. The idea is that the record array gives us an easy way to give an identification number to the records independent of their placement in the memory pool.

Invocation and I/O files:

The program will read command-line arguments and be invoked from the command-line as:

Java memman <pool-size> <num-recs>

The name of the program is memman. Parameter <pool-size> is the size of the memory pool (in bytes) that is to be allocated. Parameter <num-recs> is the size of the record array that holds the handles to the records stored in the memory pool. Your program will read and process a series of commands from the standard input. The formats for the commands are as follows. All coordinates will be signed values small enough to fit in a 32-bit int variable.

Insert recnum, x, y, name

Parameter recnum specifies which slot in the record array will hold the handle for this record. An error should be reported in the value of recnum is outside of the range 0 to num-recs-1. Parameters x and y are the 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 underscore symbol. If the insert command is to a recnum that is already used, then the first step will be to delete the old record, and the second step will be to attempt to insert the new record. Should this attempt to insert fail, then print an error message with the old record remained deleted.

Remove recunum

Remove the record whose handle is stored in position recnum of the record array. If there is no record there, print a suitable message. An error should be reported if the value of recnum is outside of the range 0 to num-recs-1.

Print recnum

Print out the record (coordinates and name) whose handle is stored in position recnum of the record array. If there is no record there, print a suitable message. An error should be reported if the value of recnum is outside of the range 0 to num-recs-1

Dump out a complete listing of the contents of the memory pool. This listing should contain two parts. The first part is the listing of city records currently stored in the memory pool, in order of the record ID. Print the value of the position handle along with the record. The second part is a listing of the free blocks, in order of their occurrence in the freeblock list.

Record Format

One 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 256 bytes. The next four bytes will be the x-coordinate. 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. Check the example Java code posted here illustrating how to manipulate binary data.

A Trace and Analysis Example

Invocation: memman 100 20

Sample data file:

insert 5 100 30 Blacksburg

  insert    7 1024   798 Christiansburg

 remove 5

print 7

print

insert 7 100 100 Radford

print

Analysis:

The first record inserted requires 4 + 4 + 10 + 1 = 19 bytes.

So, the first 19 bytes of the 100-byte array looks like:

#xxxxyyyyBlacksburg

where # is the number of bytes in the record (18), xxxx is the binary

value for the x-coordinate (100) and yyyy is the binary value for the

y-coordinate (30).

At this point, the freeblock list contains a single free block with

start position 19 and size 81.

The second record inserted requires 4 + 4 + 14 + 1 = 23 bytes.

Now, the first 42 bytes of the 100-byte array looks like:

#xxxxyyyyBlacksburg#xxxxyyyyChristiansburg

At this point, the freeblock list contains a single free block with

start position 42 and size 58.

The delete statement will free the first 19 bytes of the array. Now,

the freeblock list contains two entries, in the following order:

(42, 58);(0, 19).

At this point, the memory array looks as:

...................#xxxxyyyyChristiansburg

The first print statement should provide print coordinate (1024, 798)

and name Christiansburg.

The second print statement should show the following:

  * The records (Christiansburg is the only record remaining)

  * The free blocks.  The two free blocks at this point are

    (42, 58) and (0, 19).

The last insert statement happens to be to a location in the record

array that already contains a record.  Thus, the first action is to

delete the record.  Since it is the only record currently existing,

the net effect is to collapse the memory space back to a single free

block (0, 100).  Then, the first 16 bytes are allocated to hold the

record.  The freeblock list will now store a single record (16, 84)

and the memory array will appear as:

#xxxxyyyyRadford

Progamming standards

You must conform to good programming/documentation standards such as:

You must include a header comment, preceding main(), specifying the compiler and operating system used and the date completed.
Your header comment must describe what your program does; don't just plagiarize language from this spec.
You must use meaningful identifier names that suggest the meaning or purpose of the constant, variable, function, etc.
Always use named constants or enumerated types instead of literal constants in the code.
Precede every major block of your code with a comment explaining its purpose. You don't have to describe how it works unless you do something so sneaky it deserves special recognition.
You must use indentation and blank lines to make control structures more readable.
Precede each function and/or class method with a header comment describing what the function does, the logical significance of each parameter (if any), and pre- and post-conditions.
Decompose your design logically, identifying which components should be objects and what operations should be encapsulated for each.

Neither the class GTA nor the instructors will help any student debug an implementation, unless it is properly documented and exhibits good programming style. Be sure to begin your internal documentation right from the start.

You can use code you have written, either specifically for this assignment, or for earlier programs, or code taken from the textbook. Note that the textbook code is not designed for the specific purpose of this assignment, and is therefore likely to require modification. It may, however, provide a useful starting point. You may use Java 2 Platform API for this assignment if you like.

Test Date Files

Several test data files posted below can help you test your program. This is not necessarily the data file that will be used in grading your program. While the test data files are provided, you should also test your program using your own test data to ensure that your program works correctly.

Test file 1 (memman 1000 50) Output 1
Test file 2 (memman 200 10) Output 2
Test file 3 (memman 140 10) Output 3
Test file 4 (memman 50 5) Output 4