TITLE	"MP3 by Douglas Jones"
;	a function to traverse a binary tree concatenate the strings in it.
;	this version is based on the first posted solution to Homework 6.
;	this version frees unused space on the heap.
;       this version uses the activation record as a register save area.
;       this version uses R8 and up as local variables

	USE	"hawk.h"
	USE	"stdio.h"
	USE	"string.h"
	USE	"stdlib.h"

; activation record for TRAVERS
;RETAD	=	0
R8SAVE	=	4
R9SAVE	=	8
R10SAVE	=	12
R11SAVE	=	16
ARSIZE	=	20

TRAVERS:; expects R3 = p, pointer to the root
	; returns nothing	; void travers( node * p ) {
	STORES	R1,R2
	STORE	R8,R2,R8SAVE	;   -- saves R8 for local use as p
	STORE	R9,R2,R9SAVE	;   -- saves R9 for local use as left string
	STORE	R10,R2,R10SAVE	;   -- saves R10 for local use as right string
	STORE	R11,R2,R11SAVE	;   -- saves R11 for local use as length
	ADDI	R2,R2,ARSIZE

	TESTR	R3
	BZS	TRAVEL		;   if (p != NULL) {

	MOVE	R8,R3		;     -- move p

	LOAD	R3,R8,LEFT	;     -- param
	JSR	R1,TRAVERS	;     left_string = travers( p->left )
	MOVE	R9,R3
				;     -- param already in R3
	LIL	R1,STRLEN
	JSRS	R1,R1
	MOVE	R11,R3		;     length = strlen( left_string )

	LOAD	R3,R8,RIGHT	;     -- param
	JSR	R1,TRAVERS	;     right_string = travers( p->right )
	MOVE	R10,R3
				;     -- param already in R3
	LIL	R1,STRLEN
	JSRS	R1,R1
	ADD	R11,R11,R3	;     length = length + strlen( right_string )

	LOAD	R3,R8,DATA	;     -- param
	LIL	R1,STRLEN
	JSRS	R1,R1
	ADD	R3,R11,R3	;     length = length + strlen( p->data )
	ADDSI	R3,1		;     length = length + 1 -- allow for '\0'
	
				;     -- param already in R3
	LIL	R1,MALLOC
	JSRS	R1,R1		;     buf = malloc( length )

	MOVE	R4,R9		;     -- param
	LIL	R1,STRCPY
	JSRS	R1,R1		;     buf = strcpy( buf, left_string )
	MOVE	R11,R3		;     -- use R11 for buf so can call free

	MOVE	R3,R9
	LIL	R1,FREE
	JSRS	R1,R1		;     free( left_string )

	MOVE	R3,R11		;     -- param buf
	LOAD	R4,R8,DATA	;     -- param
	LIL	R1,STRCAT
	JSRS	R1,R1		;     buf = strcat( buf, p->data )
	
	MOVE	R4,R10		;     -- param
	LIL	R1,STRCAT
	JSRS	R1,R1		;     buf = strcat( buf, right_string )

	MOVE	R3,R10
	LIL	R1,FREE
	JSRS	R1,R1		;     free( right_string )

	MOVE	R3,R11		;     -- put buf back

	BR	TRAVQT
TRAVEL:				;   } else { -- empty tree

	LIS	R3,1		;     -- param, the length of an empty string
	LIL	R1,MALLOC	
	JSRS	R1,R1		;     buf = malloc( 1 )

	STORES	R0,R3		;     *buf = '\0' -- cheat a bit, zero 4 bytes

TRAVQT:				;   } -- end of if
	ADDI	R2,R2,-ARSIZE
	LOAD	R11,R2,R11SAVE	;   -- recover saved registers
	LOAD	R10,R2,R10SAVE
	LOAD	R9,R2,R9SAVE
	LOAD	R8,R2,R8SAVE
	LOADS	R1,R2
	JUMPS	R1		;   return buf
				; } -- end of travers
EMPTY:	ASCII	"",0

; the assignment said to put the following at the very end
	USE	"/mnt/nfs/clasnetappvm/fs3/dwjones/2630mp3.h"

	END