;-----------------------------------------------------------------
 ;AltoQueue.asm - linked list routines
 ;Nova compatible file is NovaQueue.sr
;-----------------------------------------------------------------

; The following conventions apply to all routines:
; Q is a pointer to the following structure:
;	structure Q: [
;		head word	//pointer to head item (0=>empty)
;		tail word	//pointer to tail item
;		]
; If the queue is empty, the tail word is undefined.
; Item is a pointer to an object whose first word may be used
; as a link to another Item (0 => no more items).


	.titl queue


.bext Enqueue
.bext Dequeue
.bext Unqueue
.bext InsertBefore
.bext InsertAfter
.bext LengthQ

	.srel
Enqueue:	.Enqueue
Dequeue:	.Dequeue
Unqueue:	.Unqueue
InsertBefore:	.InsertBefore
InsertAfter:	.InsertAfter
LengthQ:	.QueueLength

	.nrel

SWAT=77400


;-----------------------------------------------------------------
 ;Enqueue(Q,Item) - Place item on tail of Queue
;-----------------------------------------------------------------

.Enqueue:
	sta 3 1 2	;save return
	mov 0 3		;pointer to Q
	dir		;interrupts off
	lda 0 0 3	;get head of Q
	mov 0 0 snr	;Q empty?
	 sta 3 1 3	;yes, make tail point to Q
	sta 1 @1 3	;put pointer to Item in tail item's link
	sta 1 1 3	;Item is new tail
	sub 0 0		;zero Item's link
	sta 0 @1 3
	jmp eirret	;reenable interrupts and return


;-----------------------------------------------------------------
 ;Dequeue(Q) - Take item from front of Queue
;-----------------------------------------------------------------

.Dequeue:
	sta 3 1 2	;save return
	mov 0 3		;point at Q
	dir		;protect
	lda 0 0 3	;get head of Q
	lda 1 @0 3	;get successor if any
	mov 0 0 szr	;Q empty?
	 sta 1 0 3	;no, put successor at head of Q
	jmp eirret	;reenable interrupts and return

;-----------------------------------------------------------------
 ;InsertBefore(Q,Successor,Item) - Put Item before Successor on Q
;-----------------------------------------------------------------

.InsertBefore:
	sta 3 1 2	;save return
	dir		;critical section
insblp:	mov 0 3 snr	;predecessor pointer to usable ac
	 jmp eirret	;return false if fail to find Successor
	lda 0 0 3	;get next item
	sub# 0 1 szr	;is it the desired Successor?
	 jmp insblp	;no, keep looking
	sta 0 @3 2	;yes, put it in new Item's link
	lda 0 3 2	;get pointer to Item
	sta 0 0 3	;put in predecessor's link
	jmp truret	;reenable interrupts and return true


;-----------------------------------------------------------------
 ;InsertAfter(Q,Predecessor,Item) - Put Item after Predecessor on Q
;-----------------------------------------------------------------

.InsertAfter:
	sta 3 1 2	;save return
	mov 0 3		;put Q pointer in 3
	sta 1 2 2	;put Predecessor pointer in frame temp
	dir		;critical section
	lda 0 @2 2	;get successor of Predecessor
	sta 0 @3 2	;store in Item's link
	lda 1 3 2	;get pointer to Item
	sta 1 @2 2	;store in Predecessor's link
	mov# 0 0 snr	;was Predecessor the tail item?
	 sta 1 1 3	;yes, now Item is tail, update Q
	jmp truret	;reenable interrupts and return true

;-----------------------------------------------------------------
 ;Unqueue(Q,Item) - Remove specific Item from Q, return true if found
;-----------------------------------------------------------------

.Unqueue:
	sta 3 1 2	;save return
	inc 0 3		;make pointer to tail
	sta 3 2 2	;save for later
	dir		;critical section
unqlp:	mov 0 3 snr	;predecessor pointer to usable ac
	 jmp eirret	;return false if fail to find item
	lda 0 0 3	;get next item
	sub# 0 1 szr	;is it the one?
	 jmp unqlp	;no, keep looking
	lda 0 @0 3	;yes, get successor
	sta 0 0 3	;put in predecessor's link
	mov# 0 0 snr	;was item the tail?
	 sta 3 @2 2	;yes, update tail pointer
truret:	adc 0 0		;return true
eirret:	eir
	lda 3 1 2	;get return
	jmp 1 3


;-----------------------------------------------------------------
 ;QueueLength(Q) - Count number of items in Q
;-----------------------------------------------------------------

.QueueLength:
	sta 3 1 2	;save return
	mov 0 3		;point at Q
	sub 0 0		;count items for result in 0

QLNxt:	lda 3 0 3	;next item
	mov 3 3 snr	;end?
	 jmp QLEnd	;yes, return count
	incz 0 0 snc	;count item, punt if stuck
	 jmp QLNxt	;get next
	SWAT		;Ran off wild probably

QLEnd:	lda 3 1 2
	jmp 1 3		;return, resultis count


	.end