TITLE	"liststack.a by Douglas Jones -- linked-list stacks"
;		 Version A, uses named local variables
;		 Note that much of the code is copied from arraystack.a
;		 and also note that the style is largely lifted from there

	USE	"hawk.h"
	USE	"stdlib.h"
	USE	"exceptions.h"

	USE	"stack.h"	; the code here implements the stack interface

; configuration constants
			; none for lists

; All instances of stack have the following fields:
;EMPTY	=	0	; pointer to the empty method, see stack.h
;PUSH	=	4	; pointer to the push method, see stack.h
;POP	=	8	; pointer to the pop method, see stack.h

; additional fields defined for liststack objects
HEAD	=	12	; the list head points to the top element on the stack
OBJSIZE	=	16

; the linked lists making up a stack are made of elements
NEXT	=	0	; points to the next element down the stack
VALUE	=	4	; a value pushed on the stack in this element
ELEMSIZE=	8

;==========
	INT	NEWLISTSTACK; construct a new stack object, see liststack.h
			; given   nothing
			; returns R3 -- pointer to an initialized stack object
			; wipes	out R3-R7
; AR for NEWSTACK
;RETAD	=	0
ARSIZE	=	4
NEWLISTSTACK:
	STORES	R1,R2
	ADDSI	R2,ARSIZE
				; -- first, allocate a new stack object
	LIS	R3,OBJSIZE	; -- parameter
	LIL	R1,MALLOC
	JSRS	R1,R1		; retval = malloc( stacksize * 4 )

				; -- second, initialize the new object
				; -- start with the method pointers
	LEA	R4,LSEMPTY
	STORE	R4,R3,EMPTY	; retval->empty = asempty -- the empty method
	LEA	R4,LSPUSH
	STORE	R4,R3,PUSH	; retval->push = aspush -- the push method
	LEA	R4,LSPOP
	STORE	R4,R3,POP	; retval->pop = aspop -- the pop method

				; -- finish by making this new stack empty
	STORE	R0,R3,HEAD	; retval->head = NULL

	ADDSI	R2,-ARSIZE
	LOADS	PC,R2		; return retval

;==========
;		LSEMPTY ; test to see if a stack is empty
LSEMPTY:		; given   R3 -- s, a stack to test
			; returns R3 -- zero if not empty, nonzero if empty
			; may use R4-R7
	LOADCC	R3,R3,HEAD	; temp = s->head
				; -- here, temp = 0 if empty, we want opposite
	BZS	LSEZERO
	LIS	R3,-1		; -- tricky code: if it was nonzero, make it -1
LSEZERO:
	NOT	R3		; retval = (temp == 0)

	JUMPS	R1		; return retval
	
;==========
;		LSPUSH	; push a word on the stack
			; given   R3 -- s, stack to push on
			;         R4 -- v, word to push
			; returns nothing
			; wipes	out R3-R7
			; throws STACKEXCEPT if heap exhausted
; AR for LSPUSH
;RETAD	=	0
S	=	4
V	=	8
ARSIZE	=	12

LSPUSH:
	STORES	R1,R2
	STORE	R3,R2,S
	STORE	R4,R2,V
	ADDI	R2,R2,ARSIZE

	LIS	R3,ELEMSIZE	; -- parameter
	LIL	R1,MALLOC
	JSRS	R1,R1		; n = malloc( elemsize )
	TESTR	R3
	BZS	THROW		; if (n == NULL) throw stackexcept
	LOAD	R4,R2,S-ARSIZE
;				-- now, r3=n, r4=s, will use R5 for temp
	LOAD	R5,R4,HEAD
	STORE	R5,R3,NEXT	; n->next = s->head
	LOAD	R5,R2,V-ARSIZE
	STORE	R5,R3,VALUE	; n->value = v
	STORE	R3,R4,HEAD	; s->head = n

	ADDI	R2,R2,-ARSIZE
	LOADS	PC,R2		; return

;==========
;		LSPOP	; pop a word from the stack
			; given   R3 -- s, stack to push on
			; returns R3 -- v, a word popped from the stack
			; wipes	out R4-R6
; AR for LSPOP
;RETAD	=	0
V	=	4
ARSIZE	=	8

LSPOP:
	STORES	R1,R2
	ADDI	R2,R2,ARSIZE

	LOADCC	R4,R3,HEAD	; n = s->head
	BZS	THROW		; if (n == NULL) throw stackexcept
	LOAD	R5,R4,NEXT
	STORE	R5,R3,HEAD	; s->head = n->next
	LOAD	R5,R4,VALUE
	STORE	R5,R2,V-ARSIZE	; v = n->value

	MOVE	R3,R4		; -- parameter n
	LIL	R1,FREE
	JSRS	R1,R1		; free( n )

	LOAD	R3,R2,V-ARSIZE
	ADDI	R2,R2,-ARSIZE
	LOADS	PC,R2		; return v

;==========
;  shared code to throw a stack exception
THROW:
        EXTHROW STACKEXCEPT

	END