6809_Queue.s

	.macro	CLC
		ANDCC	#$FE
	.endm

	.macro	SEC
		ORCC	#$01
	.endm
    
; Title:	Queue Manager
; Name:		INITQ, INSRTQ, REMOVQ
; Purpose:	This program consists of three subroutines that manage a queue.
;
;		INITQ initializes the empty queue.
;		INSRTQ inserts a 16-bit element into the queue.
;		REMOVQ removes a 16-bit element from the queue.
;
; Entry:
;
;		INITQ	Base address of queue in X
;			Size of data area in words in A
;		INSRTQ	Base address of queue in X
;			Element to be inserted in U
;		REMOVQ	Base address of queue in X
;
; Exit:
;		INITQ
;
;			Head pointer	= Base address of data area
;			Tail pointer	= Base address of data area
;			Queue length	= 0
;			End pointer	= Base address of data area
;					+ 2 * Size of data area in words
;
;		INSRTQ
;
;			If queue length is not buffer size,
;				Element added to queue
;				Tail pointer = Tail pointer + 2
;				Queue Length = Queue Length + 1
;				Carry = 0
;			else
;				Carry = 1
;
;		REMOVQ
;			If queue Length is not zero,
;				Element removed from queue in X
;				Head pointer = Head pointer + 2
;				Queue length = Queue Length 1
;				Carry = 0
;			else
;				Carry = 1
;
;	Registers used:		INITQ:	A,CC,U,X
;
;				INSRTQ:	A,CC,X,Y
;
;				REMOVQ:	A,CC,U,X,Y
;
;	Time:
;				INITQ 65 cycles
;
;				INSRTQ 65 or 70 cycles, depending on whether wraparound is necessary
;
;				REMOVQ 66 or 71 cycles, depending on whether wraparound is necessary
;
;	Size:
;				Program	79 bytes
;
; INITIALIZE AN EMPTY QUEUE
;
; HEADER CONTAINS:
;	1) SIZE OF DATA AREA IN WORDS	(1 BYTE)
;	2) QUEUE LENGTH			(1 BYTE)
;	3) HEAD POINTER			(2 BYTES)
;	4) TAIL POINTER			(2 BYTES)
;	5) END POINTER			(2 BYTES)
;
INITQ:
	;
	; SET SIZE OF DATA AREA TO SPECIFIED VALUE
	; SET QUEUE LENGTH TO ZERO
	;
	LEAU	8,X		; POINT TO START OF DATA AREA
	STA	,X+		; SET SIZE OF DATA AREA IN WORDS
	CLR	,X+		; QUEUE LENGTH = ZERO
	;
	; INITIALIZE HEAD AND TAIL POINTERS TO START OF DATA AREA
	;    
	STU	,X++		; HEAD POINTER = START OF DATA AREA
	STU	,X++		; TAIL POINTER = START OF DATA AREA
	;
	; INITIALIZE END POINTER TO ADDRESS JUST BEYOND DATA AREA
	;
	TFR	A,B		; EXTEND SIZE OF DATA AREA TO 16 BITS
	CLRA
	ASLB			; MULTIPLY SIZE OF DATA AREA TIMES 2
	ROLA			; SINCE SIZE IS IN WORDS
	LEAU	D,U		; POINT JUST BEYOND END OF DATA AREA
	STU	,X		; END POINTER = ADDRESS JUST BEYOND
	RTS			; END OF DATA AREA
	;
	; INSERT AN ELEMENT INTO A QUEUE
	;
INSRTQ:
	;
	; EXIT WITH CARRY SET IF DATA AREA IS FULL
	;
	LDA	1,X		; GET QUEUE LENGTH
	CMPA	,X		; COMPARE TO SIZE OF DATA AREA
	SEC			; INDICATE DATA AREA FULL
	BEQ	EXITIS		; BRANCH (EXIT) IF DATA AREA IS FULL
	;
	; DATA AREA NOT FULL,
	; SO STORE ELEMENT AT TAIL
	; ADD 1 TO QUEUE LENGTH
	;
	LDY	4,X		; GET TAIL POINTER
	STU	,Y		; INSERT ELEMENT AT TAIL
	INC	1,X		; ADD 1 TO QUEUE LENGTH
	;
	; INCREASE TAIL POINTER BY ONE ELEMENT (2 BYTES)
	; IF TAIL POINTER HAS REACHED END OF DATA AREA, SET IT
	; BACK TO BASE ADDRESS
	;
	LEAY	2,Y		; MOVE TAIL POINTER UP ONE ELEMENT
	CMPY	6,X		; COMPARE TO END OF DATA AREA
	BNE	STORTP		; BRANCH IF TAIL NOT 
				; AT END OF DATA AREA
	LEAY	8,X		; OTHERWISE, MOVE TAIL POINTER BACK TO
				; BASE ADDRESS OF DATA AREA
STORTP:
	STY	4,X		; SAVE UPDATED TAIL POINTER
	CLC			; CLEAR CARRY (GOOD EXIT)
EXITIS:
	RTS
;
; REMOVE AN ELEMENT FROM A QUEUE
;
REMOVQ:
	;
	; EXIT WITH CARRY SET IF QUEUE IS EMPTY
	;
	LDA	1,X		; GET QUEUE LENGTH
	SEC			; INDICATE QUEUE EMPTY
	BEQ	EXITRQ		; BRANCH (EXIT) IF QUEUE IS EMPTY
	;
	; QUEUE NOT EMPTY, SO SUBTRACT 1 FROM QUEUE LENGTH
	; REMOVE ELEMENT FROM HEAD OF QUEUE
	;
; DATA
	DEC	1,X		; SUBTRACT 1 FROM QUEUE LENGTH
	LDU	2,X		; GET HEAD POINTER
	LDY	,U		; GET ELEMENT FROM HEAD OF QUEUE
;
; MOVE HEAD POINTER UP ONE ELEMENT (2 BYTES)
; IF HEAD POINTER HAS REACHED END OF DATA AREA, SET IT BACK
; TO BASE ADDRESS OF DATA AREA
;
	LEAU	2,U		; MOVE HEAD POINTER UP ONE ELEMENT
	CMPU	6,X		; COMPARE TO END OF DATA AREA
	BNE	STORHP		; BRANCH IF NOT AT END OF DATA AREA
	LEAU	8,X		; OTHERWISE, MOVE HEAD POINTER BACK
				; TO BASE ADDRESS OF DATA AREA
STORHP:
	STU	2,X		; SAVE NEW HEAD POINTER
	TFR	Y,X		; MOVE ELEMENT TO X
	CLC			; INDICATE QUEUE NONEMPTY,
				; ELEMENT FOUND
EXITRQ:
	RTS			; EXIT
				; CARRY INDICATES WHETHER
				; ELEMENT HAS FOUND (0 IF SO,
				; 1 IF NOT)
;
; SAMPLE EXECUTION
;
SC7A:
	;
	; INITIALIZE EMPTY QUEUE
	;
	LDA	#5		; DATA AREA HAS ROOM FOR 5 WORD-LENGTH
				; ELEMENTS
	LDX	#QUEUE		; GET BASE ADDRESS OF QUEUE BUFFER
	JSR	INITQ		; INITIALIZE QUEUE
	;
	; INSERT ELEMENTS INTO QUEUE
	;
	LDU	#$AAAA		; ELEMENT TO BE INSERTED IS AAAA
	LDX	#QUEUE		; GET BASE ADDRESS OF QUEUE
	JSR	INSRTQ		; INSERT ELEMENT INTO QUEUE
	LDU	#$BBBB		; ELEMENT TO BE INSERTED IS BBBB
	LDX	#QUEUE		; GET BASE ADDRESS OF QUEUE
	JSR	INSRTQ		; INSERT ELEMENT INTO QUEUE
	;
	; REMOVE ELEMENT FROM QUEUE
	;
	LDX	#QUEUE		; GET BASE ADDRESS OF QUEUE
	JSR	REMOVQ		; REMOVE ELEMENT FROM QUEUE
				; (X) = $AAAA (FIRST ELEMENT
				; INSERTED)
	BRA	SC7A		; REPEAT TEST

QUEUE:	RMB	18		; QUEUE BUFFER CONSISTS OF AN 8 BYTE HEADER
				; FOLLOWED BY 10 BYTES FOR
				; DATA (FIVE WORD-LENGTH ELEMENTS)
	END