! Solution to ICS 331 assignment 3
! by David N. Chin
! This is a translation of an 80x86 assembly language program to compute
! the size (number of nodes) of a tree.  The original 80x86 program was
! written by Kate Forbes-Riley, Univ. of Dartmouth and available at
! http://www.cs.dartmouth.edu/~cs37/CS37_2005S/x86/examples/tree.s
!
! the tree - the first value associated with each tree represents
! the data contents of the tree node (and is not used in this
! program); the second field is the address of (or a pointer to)
! the left subtree for that node; and the third value is the 
! address of the right subtree. The tree represented below is
!
!                      node1
!                     /     \
!                    /       \
!                 node2     node5
!                /     \
!               /       \
!            node3     node4
!
! you might try setting up other tree by changing the data
! definitions, and seeing what happens.

!====================
! The data section
.section ".data"
label:	.asciz "Tree size is %d\n"
string:	.asciz "Inspecting node %d\n"
	.align 4
node1:	.word 11, 2f, 5f
2:	.word 22, 3f, 4f
3:	.word 33, 0, 0
4:	.word 44, 0, 0
5:	.word 55, 0, 0
6:	.word 66, 0, 0	
7:	.word 77, 0, 0	
8:	.word 88, 0, 0	
9:	.word 99, 0, 0	

!==== Minimal prologue ====
.section ".text"
.global main
.align 4
main:	save	%sp,-96,%sp !minimum!
!=====================
	set	node1,%L1	! store the address of node1 in %L1
	call	tree_size	! call the function
	mov	%L1,%o0		! set parameter to recursive function
! after the function call, the tree's size will be in %o0
! Call a routine (printf) to print a message.
	mov	%o0,%o1
	set	label,%o0
	call	printf
nop			!Always fill the "delay slot"!
!====Standard epilogue ====
	ret	!Return to the OS.
	restore	!Delay slot - done first

tree_size:
! high level pseudocode:
! int tree_size(tree *t) {
!     int size;
!     if(t == null) size = 0;
!     else size = 1 + tree_size(t->left) + tree_size(t->right);
!     return size;
! }

! arguments:
!   %i0 = pointer to root of tree.
! return values:
!   %i0 = size of the tree
! local variables:
!   %L0 = size so far


	save	%sp,-96,%sp	! need a stack frame
!	set	string,%o0
!	call	printf
!	ld	[%i0],%o1
	mov	%g0,%L0		! assume that the tree is empty
	cmp	%i0,%g0		! if the tree is empty, just jump and
				! return the size 0
	be	tree_size_done
	nop
	set	1,%L0		! size is 1 since we at least have this node
	call	tree_size	! then call tree_size recursively on the
	ld	[%i0+4],%o0	! right branch
	add	%L0,%o0,%L0	! and add that to the result
	call	tree_size	! call tree_size recursively on 
	ld	[%i0+8],%o0	! the left branch
	add	%L0,%o0,%L0	! and add that to the result
tree_size_done:	
	ret
	restore	%L0,%g0,%o0