; AltoQueue.asm - linked list routines
; Copyright Xerox Corporation 1979, 1982
; Last modified August 25, 1982  9:34 AM by Taft

; 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; however, procedures
; in this package that remove Items from queues leave this word pointing to
; the most recent Item which, when removed, caused the queue to become empty.

; Item is a pointer to an object that begins thus:
;   structure Item:
;      [
;      next word	// pointer to next item on queue (0 => no more)
;      rest word ??	// rest of object
;      ]
; The value of the link word of an Item not on any queue is undefined;
; however, procedures in this package that remove Items from queues
; set this word to -1 for debugging purposes.


	.titl queue


.bext Enqueue
.bext Dequeue
.bext Unqueue
.bext InsertBefore
.bext InsertAfter
.bext QueueLength

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

	.nrel

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

.Enqueue:
	sta 3 1 2	;save return
	mov# 1 1 snr	;swat if attempt to queue zero
	 SWAT
	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; return zero if empty
;-----------------------------------------------------------------

.Dequeue:
	sta 3 1 2	;save return
	sta 0 2 2	;pointer to Q
	dir		;critical section
	lda 3 @2 2	;get head of Q
	mov 3 0 snr	;Q empty?
	 jmp eirret	;yes, return zero
	lda 1 0 3	;get successor
	sta 1 @2 2	;put at head of Q
	adc 1 1		;put -1 in removed item's link word
	sta 1 0 3
	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
	adc 1 1		;put -1 in removed item's link
	sta 1 @0 3
	sta 0 0 3	;put successor 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
	dir		;critical section

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


	.end