Goals

These exercises are intended to give you practice implementing a dynamically resizeable structure (useful for handling the create command in project 1). and to familiarize you with the K&R storage allocation code.

Reading

Section 8.7 in K&R.

Initial preparation

Find a partner, someone different from the person(s) you worked with in previous weeks. Introduce yourself to him or her, and tell each other your favorite book.

Copy the directory ~cs61c/files/lab/3/ to your home directory.

Exercise 1 (2 points)

The file vector.c contains a framework for implementing a variable-length array (an ArrayList in Java). This exercise is designed to help familiarize you with C structs and memory management.

Fill in the missing code in vector.c and test it with the main program in test.c by typing

    make test

If the test breaks, use gdb on the created executable (vector.test) or printf statements to find your bugs.

Comments in the code describe how the functions should work. Look at the functions we've filled in to see how the data structures should be used. Note in particular that a request in vector_get for the value of a vector element not previously set by vector_set should always return 0. This implies that you'll need to do some extra work in vector_set after a call to malloc. Consider using the memxxx() functions in string.h rather than writing your own for loops, but be careful that you calulate memory sizes in chars, bytes, or ints as appropriate.

When you resize the vector, keep two things in mind:

• You should at least double the size of your old vector, in order to reduce the number of times you have to resize the vector. This ties back into asymptotic running time in CS61B.
• You must make sure you have enough space to store all the old elements, plus any new ones.

For checkoff, show your TA the output of vector.test along with the changes you made to the code. Also explain why the statement

	free(v->size);

isn't needed in vector_delete ( ).

Exercise 2 (2 points)

This exercise involves experimenting with the K&R storage allocation code. The code, augmented by a main function that repeatedly requests allocation and free requests from the user, is in the file stgmgmt.c. The format of user input is

    a numberOfBytes
    f addressOfAllocReturn

The argument to the f command is a hexadecimal address previously returned by an a command. (This information is printed in the program's response to the allocation request.)

Answer the following questions about this code, and show your answers to your t.a. for checkoff. To find the answers, either add printf statements to the program or use gdb.

1. How many bytes of header information are there per block?
2. How does the size displayed for a block in the output of the printFreeList function relate to its size in bytes?
3. What's the size of the smallest allocatable block?
4. Pick one of the following:
   1. Show, using gdb, that the size of an allocated block is stored at the address immediately prior to the block's address.
   2. What happens when you try to free an already free block? Be specific.