CS:2630, Homework 6, 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).

In the code given for part a), version 1, where traversing an empty tree returned an empty string, start by replacing the following 3 lines:

        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.

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.

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.

Background: Suppose you have to concatenate the strings a, b, and 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)

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.

Assignment 6, due Oct 10

Solutions