CSE 303: Autumn 2006, Assignment 4

Due: Monday 6 November 2006, 2:00pm

Updates

• Saturday, October 28: Made numerous clarifying changes to the "Description" section. Also added the constraint that no line of input will have more than 126 characters.
• Friday, October 27: Changed the assignment to make working in pairs optional. Added some hints to the description of heaptest.c. Changed assumed compile flags to add -std=c99.

Assignment Overview

In this assignment, you will create a small simulation of the C heap. This assignment may be done individually or in pairs. If two people wish to work together, each should send an e-mail to Lincoln Ritter (lritter@cs) with the subject line "HW4 Pair" that contains both students' names and usernames. We suggest you choose a partner early and choose carefully. Once you decide to start working in pairs, you cannot change your mind.

If working in pairs, you will both receive the same grade. Pairs need turn in only one solution, but put both names in readme.txt, as explained in the standard turn-in instructions. Working in pairs is helpful to split up coding work. However, we suggest that paris of students work together to understand the concepts, because everyone will be responsible for understanding the concepts on exams.

Description

Your program must take a single command-line argument which should be interpreted as the size of a heap (heapsize), and simulate the action of allocating and freeing sections of this heap. The heap will be indexed by byte starting at 0 and continuing to heapsize-1. If your program is not given a single argument, or if heapsize is 0, print an error message on stderr and exit with a non-zero exit code.

While running, your program will process lines of input (separated by a newline character: '\n') received on stdin. You are guaranteed to receive no more than 126 characters between each newline character. Each line will be interpreted in one of four ways. If the first characters of a line match one of three commands (free, quit, or print) it will trigger an action described below. Otherwise, you should consider it to be an arbitrary string and copy it to your simulated heap. The following is a detailed description of each of these four cases.

• string: In this case, your program should use your heap simulator to allocate a new chunk of memory and copy string into it. Your heap allocator must return the first chunk of memory (i.e., the chunk with the lowest index) that is large enough to hold this string. When allocating/copying, do not include the newline character ('\n') , but remember to include the null terminator ('\0'). If there is no chunk large enough to hold the string, print an error message to stderr and do nothing.
• free index: If an input line starts with "free ", interpret the remaining characters as the index of a chunk of memory to be freed. If the index was not returned earlier by your heap allocator (as the index of a chunk of memory), the behavior of this command is undefined. If the index is valid, your heap simulator should free the chunk of memory and make it available for future allocations.
• quit: If an input line contains this command by itself, the program should exit.
• print: If an input line contains this command by itself, the program should print the status of the heap to stdout in the following format:
  • First print "----------------------------------------\n" (40 dashes followed by a newline).
  • Then print "Used:\n".
  • Then print a record for each chunk of memory that is currently in use. These records must be of the form "     [i: s bytes]\n" where "i" is the index returned by your heap allocator and "s" is the size of that chunk. Note: in the above string, there are five spaces before the "[" character.
  • Then print "Free:\n".
  • Then print a record for each chunk of memory the is available for allocation. These records must have the same format as the "used" record described above.
  • Then print "Contents:\n".
  • Then print the entire contents of your heap with eight bytes per line. Each line should have the following format:
    
    "aaaa:  nnn  nnn  nnn  nnn  nnn  nnn  nnn  nnn  \n"
    
    Where "aaaa" is the index of the first byte on that line (padded with zeros), and "nnn" is a three character record of the data stored at that byte. "nnn" should be in one of three forms:
    • If the data stored at that location has not been allocated, this record should be "-- ".
    • If the data has been allocated, but it is less than 32 or greater than 126, then this record should be the letter "x" followed by a two character hexadecimal representation of the data (with the letters A-F in capitals).
    • Otherwise, the record should be in the form 'c' where "c" is the character representation of that byte. Two spaces appear before each record and after the last.
  • Finally, print "----------------------------------------\n" (same as first line).

You are fee to implement this assignment in any way you wish, as long as it has the correct behavior and produces correct output as described above. However, you are required to put structurally separate pieces of code in different files. For example, if you implement a linked list, you should put code for this linked list in a source file by itself. Also, your main function should appear in a source file by itself. If you do not use the file names and organization described below, you should describe the contents of each file in your program in readme.txt. You are also free to borrow code from any (legal) source other than students currently taking this course. If you borrow source code, describe the code and where it came from in readme.txt.

For testing, try running your program with a heap size of 50, entering the following sequence of commands, and directing your output to a file. If you diff your file with this one, they should be exactly the same.

a
b
c
free 2
free 0
dd
print
quit

Advice

Though you are free to implement your solution in any way you wish, this section describes how the sample solution was made. If you are unsure how to proceed, we suggest that you structure your program as we did.

The sample solution to this problem is spread across five files:

• allocreclist.c: This file is based on list.c presented in lecture. It implements a data structure that holds a list of "allocation records" (AllocRec). Each AllocRec defines a region in memory. Each record contains a "start index" (the index of first byte of data), a length, and a link to another instance of itself so that it can be kept in a list. It is assumed that lists of records are ordered by start index. In the sample solution, this file has 109 lines of code and 25 lines of comments. It implements the following functions:
  • ARLNew: Takes a start index and a length and stores them in a new AllocRec structure allocated with malloc. Returns a pointer to this structure.
  • ARLFree: Takes a pointer to an AllocRec structure and frees it using free.
  • ARLPrint: Prints a list of AllocRec structures in the format defined above.
  • ARLFind: Takes a list and a start index and returns a pointer to the first AllocRec that contains the start index. Returns NULL if none is found.
  • ARLInsert: Inserts an AllocRec into a list in the proper order. The list may be NULL, but the inserted element must not. Returns the first element of the new list, since it may change.
  • ARLRemove: Removes an AllocRec from a list. If the item is not in the list, the behavior is undefined. Returns the first element of the new list, since it may change.
  • ARLMerge: Scans a list and merges elements if they are adjacent (i.e., if they are next to each other in the list, and if one ends just before the other begins). Any elements that are removed from the list are freed using ARLFree. Returns the first element of the new list, since it may change.
• allocreclist.h: A header file for allocreclist.c. In the sample solution, this file has 19 lines. It contains prototypes for all functions and a definition of the AllocRec structure.
• heap.c: Implements a Heap data structure and declares one global instance of it. This data structure contains a lists of "free" AllocRecs, a list of "used" AllocRecs, the size of the heap, and a pointer to char array that is the heap itself. In the sample solution, this file has 110 lines of code and 11 lines of comments. It implements the following functions:
  • HeapInit: Takes a size parameter, initializes the heap data structure, and uses malloc to allocate a char array with size elements for the heap.
  • HeapAlloc: Takes a size parameter and allocates a chunk of that length, returning the start index of the chunk. Memory is allocated as defined above using the helper functions ARLNew, ARLInsert, and ARLRemove.
  • HeapFree: Frees the chunk of memory with a given start index. This function uses ARLFind, ARLRemove, ARLInsert, and ARLMerge.
  • HeapStartIdxToPtr: Converts a heap start index to a char pointer that can be used to perform string operations on the allocated memory.
  • HeapPrintElement: Takes an index into the heap and a pointer to an AllocRec (which may be NULL). The function assumes that the given index is either before the given AllocRec or inside it, and the element is printed as appropriate. This function also prints the index once every eight elements as defined above.
  • HeapPrint: Prints the status of the heap as defined above. This function uses ARLPrint and HeapPrintElement.
• heap.h: A header file for heap.c. In the sample solution, this file has 11 lines. It contains prototypes for the heap functions that are used in main.c.
• heaptest.c: Holds the function main, which handles erroneous input, parses commands, and calls the appropriate function. This function uses HeapAlloc, HeapFree, HeapStartIdxToPtr, and HeapPrint. In the sample solution, this file has 46 lines of code and 1 line of comments. Hint: You main find fgets and atoi easier to use than than scanf for this problem.

Programs like these can be very hard to debug! You might consider adding debugging code that prints lots of extra information. Be sure to remove this from the final version or make it so that the code is not compiled unless a particular flag is defined (as shown in class).

Note: You can get a Ph.D. in computer science by writing a good heap allocator. It is a very hard problem! Don't be surprised or disappointed if your implementation is inefficient.

Extra Credit

Remember the course policy on extra credit. You may do either or both of the following problems.

• The "Allocation Record List" described in the "Advice" section above exposes the definition of the AllocRec structure to every other file that uses this data type. Under the heading "Extra Credit #1" in readme.txt, describe a strategy for hiding this information that does not require the creation of any new files and implement this strategy in the files you turn in.
• The "Allocation Record List" described in the "Advice" section above is very slow. The time needed to allocate or free memory grows with O(n) where n is the number or AllocRecs in the used and free lists. Under the heading "Extra Credit #2" in readme.txt, describe a strategy for speeding up this process and implement this strategy in the files you turn in. Strategies that result O(n) time will receive no extra credit. Strategies that that result in O(1) time will receive more credit than strategies that result in O(log n) time.

Assessment

Your solutions should be

• Correct C programs that compile without errors or warnings using gcc -Wall -std=c99 on attu.cs.washington.edu
• In good style, including indentation and line breaks
• Of reasonable size

Turn-in instructions

Use the standard turn-in instructions described here. If you use the structure we described, your directory should contain the files allocreclist.c, allocreclist.h, heap.c, heap.h, and heaptest.c. If you do not use the structure we described, you should include a description of the files in readme.txt. If you do any extra credit problems, you should also turn in readme.txt.