Assignment 6, due Oct 10Solutions
Part of
the homework for CS:2630, Fall 2019
|
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.
There are always multiple ways to solve a problem. Version one returns an empty string when it encounters an empty tree.
char * traverse( struct treenode * n ) { if (n != NULL) { /* the following two calls can be done in any order */ char * left = traverse( n->left ); char * right = traverse( n->right ); int leftlen = 0; leftlen = strlen( left ); int rightlen = 0; rightlen = strlen( right ); int midlen = strlen( n->data ); char * retval = malloc( leftlen + midlen + rightlen + 1 ); retval[0] = '\0'; /* make it into a well-formed empty string */ strcat( retval, left ); strcat( retval, n->data ); strcat( retval, right ); return retval; } else { /* empty tree */ return ""; } }
Version two returns NULL (a null pointer, not an empty string) when it traverses an empty tree. The result is ugly code checking for NULL string pointers in the concatenation.
char * traverse( struct treenode * n ) { if (n != NULL) { /* the following two calls can be done in any order */ char * left = traverse( n->left ); char * right = traverse( n->right ); int leftlen = 0; if (left != NULL) leftlen = strlen( left ); int rightlen = 0; if (right != NULL) rightlen = strlen( right ); int midlen = strlen( n->data ); char * retval = malloc( leftlen + midlen + rightlen + 1 ); retval[0] = '\0'; /* make it into a well-formed empty string */ if (left != NULL) strcat( retval, left ); strcat( retval, n->data ); if (right != NULL) strcat( retval, right ); return retval; } else { /* empty tree */ return NULL; } }
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).
strcat( retval, left ); strcat( retval, n->data ); strcat( retval, right );
with the following 5 lines:
strcat( retval, left ); free( left ); strcat( retval, n->data ); strcat( retval, right ); free( right );
This looks easy, but it doesn't work. You get an free(): invalid pointer error. The cause is simple. When traverse is given an empty tree, it returns a pointer to a constant empty string. That constant string was not allocated on the heap, and the heap manager always checks to see if the object you are trying to deallocate is actually on the heap. To make this nice-looking code work, we need to replace this code:
} else { /* empty tree */ return ""; }
with something like this much uglier code:
} else { /* empty tree */ char * empty = malloc( 1 ); /* or malloc( strlen( "" ) ); */ *empty = '\0'; /* or strcpy( empty, "" ); */ return empty; }
In the code given for part a), version 2 where traversing an empty tree returned a null pointer, the solution is a bit nicer looking. Replace the following 3 lines:
if (left != NULL) strcat( retval, left ); strcat( retval, n->data ); if (right != NULL) strcat( retval, right );
with the following 9 lines:
if (left != NULL) { strcat( retval, left ); free( left ); } strcat( retval, n->data ); if (right != NULL) { strcat( retval, right ); free( right ); }
All of the above code has been tested using a variation on the framework used to test the traversal code from homework 5; it really works.
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.
Here is a straightforward version:
MACRO LOADSNA rd,x LOADS R1,x ; get the least significant byte (byte 0) EXTB rd,R1,x ADDSI x,1 LOADS R1,x ; get byte 1 EXTB R1,R1,x SL R1,8 ; shift it over OR rd,r1 ; merge it in ADDSI x,1 LOADS R1,x ; get byte 2 EXTB R1,R1,x SL R1,16 OR rd,r1 ADDSI x,1 LOADS R1,x ; get byte 3 EXTB R1,R1,x SL R1,12 SL R1,12 ; note that the maximum shift count is 16 OR rd,r1 ADDSI x,-3 ; undo changes to x register ENDMAC
Here is a slightly more sophisticated version:
MACRO LOADSNA rd,x ADDSI x,3 LOADS R1,x ; get the most significant byte (byte3) EXTB rd,R1,x ADDSI x,-1 LOADS R1,x ; get byte 2 EXTB R1,R1,x ADDSL rd,R1,8 ; shift it into the result ADDSI x,-1 LOADS R1,x ; get byte 1 EXTB R1,R1,x ADDSL rd,R1,8 ; shift it into the result ADDSI x,-1 LOADS R1,x ; get byte 0 EXTB R1,R1,x ADDSL rd,R1,8 ; shift it into the result ENDMAC
While it is better than the first version, the above code is still wasteful. The data in memory occupies at most 2 words, yet we load 4 times, once per byte. More clever code would look at the least significant 2 bits of register x and then load exactly the required data.
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)
Each time you call strcat(x,y) you compute the length of string x. So, the above code must have computed the length of strings a, b, and c in order to allocate buf, and then it to do strcat(...,b) is recomputes the length of a, and when it does strcat(...,c) is recomputes the length of a concatenated with b.
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.
/* first do this, unless you did so before calling MALLOC */ int alen = strlen( a ); int blen = strlen( b ); /* then do the concatenation */ strcpy( buf, a ); strcpy( buf + alen, b ); strcpy( buf + alen + blen, c );
Note that the above code was tested by modifying it to fit in the solution to problem 1 above; it really works.