Machine Problem 3, due Mar 18 25

Background: Consider the problem of representing a tree where each item in the tree has a value and an arbitrary number of children. There are many possible solutions to this problem:

• Attach a linked list to each item in the tree, where the list contains pointers to the children.

• Include an array of pointers to the children in each item in the tree, where a null pointer marks the end of the array.

• Include an array of pointers, as above, but also include a count of the number of children so that there are no null pointers.

All of the above alternatives can be made to work. The first midterm will definitely include questions focused on at least two of these alternatives.

For this assignment, focus specifically on the second alternative, where each node contains a pointer to a null-terminated character string as the value of each item. Here is SMAL code to construct a 3-node binary tree using this representation:

NULL    =       0

ROOT:   W       ROSTR   ; value
        W       LEFT    ; child[0]
        W       RIGHT   ; child[1]
        W       NULL    ; child[2]
ROSTR:  ASCII   "This ",0

        ALIGN   4
LEFT:   W       LESTR   ; value
        W       NULL    ; child[0]
LESTR:  ASCII   "might ",0

        ALIGN   4
RIGHT:  W       RISTR   ; value
        W       NULL    ; child[0]
RISTR:  ASCII   "work.",0

Traversing the above tree in pre-order (that is, listing the value of the child before the values of each of its children) would output "This might work." If you were writing the traverse routine in C or C++ using Hawk monitor routines for output, it might look something like this:

traverse( node * p ) {
        int i = 0;
        puts( p->value );
        while ( p->child[i] != NULL ) {
                traverse( p->child[i] );
                i = i + 1;
        }
}

A minimal SMAL Hawk main program that calls the traverse routine and passes it the above test data might look like this:

MAIN:   STORES  R1,R2
        LIL     R3,ROOT         ; -- parameter
        ADDI    R2,R2,ARSIZE
        LIL     R1,TRAVERSE
        JSRS    R1,R1           ; traverse( root )
        ADDI    R2,R2,-ARSIZE
        LOADS   R1,R2
        JUMPS   R1              ; return

The Assignment: Write a well commented SMAL Hawk subroutine called TRAVERSE that functions as described above. That function, should sit, by itself, in a file structured as follows:

        TITLE   "mp3.a -- Your Name Here"
        USE     "hawk.h"
        USE     "monitor.h"
        INT     TRAVERSE

; your code goes here

        END

Testing Your Code: To test your program, you will need to link it with the test program. To do so, use the following line to link your code:

link mp3.o mp3test.o

We have written the mp3test program to provide test data for your program. It is based on the suggested main program given above, but with more ornate test data. It is the main progra, so your file mp3.a only needs to hold the subroutine, with no need for its own main program. The object file mp3test.o is in the Hawk system library so you don't need a copy of it in your own directory. Feel free, however, to write your own main program with your own test data to test your subroutine. Do not include your test program in your submission!

Hints: The high-level language code given above contains the expression: p->child[i]. This means: The ith element of the array which makes up the child field of the structure (or object) pointed to by p. To compute this, you will need to do the following:

1. Get the address of the object p into register r.
2. Computer the address r+child where child is a constant, the displacement into the object of the start of the array. The result is the address of the first element of the array.
3. Get the value of i into a register.
4. Multiply i by 4 because each array element is 4 bytes.
5. Add i*4 to r+child to compute the address of the desired array element.
6. Actually load the addressed array element from RAM.

Multiplication by 4 can be done with SL Rd,2. This is much faster than calling a multiply subroutine (and it involves writing much less code). The instruction ADDSL Rd,Rs,2 combines an add with a shift, adding 4 times Rd to Rs and putting the result in Rd.

Turn In Your Work: Use the divms coursework submission tools to submit your solved work. Your assignment must be in a file named mp3.a and you must submit it as a solution for mp3 in the course c_060. You may re-submit your work, so if you have something you think might be worth submitting, submit it, and if you improve on that solution, submit again.

Half of the credit for this assignment will be based on whether your code works. The other half will be based on the quality of your code, readability and clean concise comments are more important than efficiency, but code that serves no purpose will be penalized.

A major penalty will be assessed for failing to follow the basic requirement for a TITLE line on your program that gives your name!