Implementation of binary tree copy algorithm, ex 2.3.2-13 (Knuth. The Art of Computer Programming, Volume 1)

See more:

ASM

Can somebody explain in details how this program work.

The folowing program implements Algorithm 2.3.1C with rI1 = P, rI2 = Q, rI3 = R, and with the appropriate changes to the initialization and termination conditions:

064		ST3	6F(O:2)		Save contents of rI3, rI2.
065		ST2	7F(O:2)		C1. Initialize.
066		ENT2	8F		Start by creating NODE(U) with
067		JMP	1F		RLINK(U) = null
068	8H	CON	0		Zero constant for initialization
069	4H	LD1	0,1(LLINK)	Set P <- LLINK(P) = P*
070	1H	LD3	AVAIL		R <= AVAIL
071		J3Z	OVERFLOW
072		LDA	0,3(LLINK)
073		STA	AVAIL
074		ST3	0,2(LLINK)	LLINK(Q) <- R
075		ENNA	0,2
076		STA	0,3(RLINKT)	RLINK(R) <- Q, RTAG(R) <- 1.
077		INCA	8B		rA <- LOC(init node) - Q
078		ENT2	0,3		Set Q <- R = Q*.
079		JAZ	C3		To C3, the first time.
080	C2	LDA	0,1		C2. Anything to right?
081		JAN	C3		Jump if RTAG(P) = 1.
082		LD3	AVAIL		R <= AVAIL	
083		J3Z	OVERFLOW
084		LDA	0,3(LLINK)
085		STA	AVAIL
086		LDA	0,2(RLINKT)
087		STA	0,3(RLINKT)	Set RLINKT(R) <- RLINKT(Q).
088		ST3	0,2(RLINKT)	RLINK(Q) <-R, RTAG(Q) <- 0.
089	C3 	LDA	1,1		C3. Copy INFO		
090		STA	1,2		INFO field copied.
091		LDA	0,1(TYPE)
092		STA	0,2(TYPE)	TYPE field copied.
093	C4 	LDA	0,1(LLINK)	C4. Anything to left?
094		JANZ	4B		Jump if LLINK(P) != null
095		STZ	0,2(LLINK)	LLINK(Q) <- null
096	C5	LD2N	0,2(RLINKT)	C5. Advance. Q <- -RLINKT(Q)
097		LD1	0,1(RLINK)	P <- RLINK(P).
098		J2P	C5		Jump if RTAG(Q) was 1.
099		ENN2	0,2		Q <- -Q
100	C6	J2NZ	C2		C6. Test if complete
101		LD1	8B(LLINK)	rI1 <- location of first node created.
102	6H	ENT3	*		Restore index registers.
103	7H	ENT2	*

Particulary I cant figure out following things:
1)

068	8H	CON	0
...
075		ENNA	0,2 (put in rA variable Q with negative sign)
...
077		INCA	8B (as far as I understand we have to increment Q by 0 (zero))
...
079		JAZ	C3 (program jump to C3 only if rA iz empty but we have Q in rA, so we never jump to C3??????????)

2)

070	1H	LD3	AVAIL (What is initial value of AVAIL???????)

Does AVAIL changes on line 097

097		LD1	0,1(RLINK)	P <- RLINK(P).

Ragards Sam.