Assignment 6, due Oct 10

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper in discussion section on Thursday. Some parts of assignments may be submitted on-line and completed in discussion section. Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. Background: Study machine problem 3, and look at the solutions to Homework 5, problem 1.

   a) Write a traverse routine in C that meets the requirements for MP3; that is, it traverses the tree and returns a string, the result of concatenating all of the strings in the tree in order. It will need to call strlen several times to find how much space to allocate, malloc to allocate space for the string it returns, then copy or concatenate the strings into the allocated space. (1 point)

   Note: You are welcome to test it, a little main program that calls traverse and then prints the resulting string is easy to write, and you can test it with the test data that worked for Homework 5. All we want to see, though, is clean, well formatted and appropriately commented code for traverse.

   b) The above problem did not ask you to deallocate any of the strings you allocated during tree traversal. As a result, your code has a memory leak. Fix this by inserting calls to free in the appropriate places in the code. Note that it is illegal to try to free any block of code that was not originally allocated by malloc; you may need to be careful about this. (0.5 point)

   You may turn in a single copy of traverse that solves both parts a) and b) of this problem. We will ignore calls to free in assigning credit for part a) and count them (if correct) toward part b).

2. Background: The Hawk load and store instructions all require that the address be aligned. Some applications, however, require access to non-aligned data. This is particularly true for very large data structures that threaten to exhaust all of RAM unless they are tightly packed with no wasted space.

   A problem: Write a macro called LOADSNA (meaning LOADS but Not Aligned) so that LOADSNA r,x will load register r with the word pointed to by regiter x, where x may be any address and a word is just the 4 bytes starting at that address. Your macro may use R1 as a temporary, and it may alter x so long as it undoes any alterations to x before it finished. (1 point)

   Advice: Don't try to write fancy optimal code, keep it dumb and simple.

3. Background: Suppose you have to concatenate the strings a, b, c in a C program. If buf is the destination buffer, allocated to be big enough, you can write strcat(strcat(srcpy(buf,a),b),c)

   a) How is this inefficient? Hint: Is there any redundant copying or measuring done in this code, given what you know about the implementation of the C string library? (0.2 points)

   b) Rewrite the code, using the C string library, to eliminate this inefficiency. (0.3 points)

   Note: Don't bother addressing this inefficiency in your answer to question 1, but there's no harm in addressing it in your solution to MP3.