;
; llistMan.s
;
; Linked List Management (TMA)
;
;  1994-1998 Straylight
;

;----- Licensing note -------------------------------------------------------
;
; This file is part of Straylight's Sapphire library.
;
; Sapphire is free software; you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation; either version 2, or (at your option)
; any later version.
;
; Sapphire is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
; GNU General Public License for more details.
;
; You should have received a copy of the GNU General Public License
; along with Sapphire.  If not, write to the Free Software Foundation,
; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

;----- Standard header ------------------------------------------------------

		GET	libs:header
		GET	libs:swis

;----- External dependencies ------------------------------------------------

		GET	sapphire:alloc
		GET	sapphire:fastMove
		GET	sapphire:sapphire

;----- Main code ------------------------------------------------------------

		AREA	|Sapphire$$Code|,CODE,READONLY

; --- llist_create ---
;
; On entry:	R0 == pointer to 12 byte list head to fill in
;		R1 == sort routine to use (0 for none)
;
; On exit:	List head filled in appropriately
;
; Use:		This call set up list. It must be made just once, before
;		and other list alls are made. On entry, R0 must point to
;		12 bytes in memory, which is filled in by this call.
;		Example code may look like:
;
;			ADR	R0,myList
;			LDR	R1,=myStrCmp
;			BL	llist_create
;
;			  .
;                         .
;			  .
;
; 			mylist	DCD	0,0

		EXPORT	llist_create
llist_create	ROUT

		STMFD	R13!,{R12,R14}		;Stack some registers
		WSPACE	llist__wSpace		;Locate my workspace

		ADR	R14,ws__z		;Point to list terminator
		STR	R14,[R0,#ll__first]	;Store in the list head
		STR	R1,[R0,#ll__sort]	;The sort routine
		MOV	R14,#0			;Number of items so far
		STR	R14,[R0,#ll__items]	;Stor that in the block

		LDMFD	R13!,{R12,PC}^		;Return to caller

		LTORG

; --- llist_destroy ---
;
; On entry:	R0 == pointer to list head
;
; On exit:	R0 corrupted
;
; Use:		Destroys the given list.

		EXPORT	llist_destroy
llist_destroy	ROUT

		STMFD	R13!,{R1,R2,R12,R14}	;Stack registers
		WSPACE	llist__wSpace		;Locate my workspace
		ADR	R1,ws__z		;Point to terminator

		LDR	R0,[R0,#ll__first]	;Get the first item
00llist_destroy	LDR	R2,[R0,#ll__next]	;Get the next item
		CMP	R0,R1			;Are we at the end?
		BLNE	free			;No -- free item
		MOVNE	R0,R2			;Get the next item
		BNE	%00llist_destroy	;And destroy that too

		LDMFD	R13!,{R1,R2,R12,PC}^	;Return to caller

		LTORG

; --- llist__insert ---
;
; On entry:	R0 == pointer to the list head
;		R1 == pointer to the item (user data)
;
; On exit:	--
;
; Use:		Insert the given item into the list, assuming that the list
;		is already sorted.

llist__insert	ROUT

		STMFD	R13!,{R0-R5,R12,R14}	;Stack some registers
		WSPACE	llist__wSpace		;Find workspace
		ADR	R2,ws__z		;The list terminator

		LDR	R5,[R0,#ll__sort]	;The sort routine
		MOV	R3,R0			;The previous item

		; --- Scan through the items, until comparison is GT ---

00llist__insert	MOV	R4,R3			;The previous item
		LDR	R3,[R3,#ll__next]	;Get the next item
		CMP	R3,R2			;Is there one?
		BEQ	%20llist__insert	;No -- insert at end
		ADD	R0,R3,#ll__blockSize	;Point to user data
		CMP	R5,#0			;Is there a sort routine?
		CMPEQ	R0,R0			;No -- make LE condition
		MOVNE	R14,PC			;Yes -- set up return address
		MOVNE	PC,R5			;...and branch to sort routn
		BLE	%00llist__insert	;Keep looking

		; --- Insert the item ---

20llist__insert	SUB	R1,R1,#ll__blockSize	;Point to full item desc
		STR	R1,[R4,#ll__next]	;Store in previous next ^
		STR	R3,[R1,#ll__next]	;Update this next pointer
		STR	R1,[R3,#ll__prev]	;Update next previous pointer
		STR	R4,[R1,#ll__prev] 	;Update this previous pointer

                ; --- Return to the caller ---

99llist__insert	LDMFD	R13!,{R0-R5,R12,PC}^	;Return

		LTORG

; --- llist_addItem ---
;
; On entry:	R0 == pointer to list head
;		R1 == pointer to user data (or 0 if none to copy)
;		R2 == size of user data
;
; On exit:	R0 preserved
;		R1 == pointer to the new user data
;		May return an error
;
; Use:		This call will add an item to a list. Notice that the
;		item is entirely allocated by the list manager, it does not
;		point to the data that you supply it, instead it
;		copies the data into the newly created item. For this reason
;		if 0 is supplied as the user data, nothing is copied.
;		It is the returned user data pointer, that must be
;		used to reference the item in other llist calls.

		EXPORT	llist_addItem
llist_addItem	ROUT

		BIC	R14,R14,#V_flag		;No error yet
		STMFD	R13!,{R0,R2,R3,R12,R14}	;Stack some registers
		WSPACE	llist__wSpace		;Locate workspace

		MOV	R3,R2			;Size of user data
		ADD	R2,R2,#ll__blockSize+3	;The blocksize required
		BIC	R2,R2,#3		;Word align
		MOV	R0,R2			;Allocate this much
		BL	alloc			;Try to allocate the block
		BCS	alloc_error		;No memory? Get message
		BVS	%99llist_addItem	;And return with error

		STR	R2,[R0,#ll__size]	;Store the item size
		MOV	R2,R3			;Just copy this much
		MOV	R3,R0			;Remember this pointer
		ADD	R0,R0,#ll__blockSize	;Point to user data
		CMP	R1,#0			;Any data supplied?
		BLNE	fastMove		;Yes -- copy it over
		MOV	R2,#0			;The flags word
		STR	R2,[R3,#ll__flags]	;Store them nicely
		BEQ	%10llist_addItem	;...and insert at beginning
		MOV	R1,R0			;Point to the list item block
		LDMIA	R13,{R0}		;Get list head back
		BL	llist__insert		;Insert the item in the list
		LDR	R2,[R0,#ll__items]	;Get the item count
		ADD	R2,R2,#1		;Increment it
		STR	R2,[R0,#ll__items]	;Store it back again
		B	%99llist_addItem	;Return to caller

		; --- Just insert at the beginning ---

10llist_addItem	MOV	R1,R0			;Point to the item data
		SUB	R0,R0,#ll__blockSize	;Point to full item desc
		LDMIA	R13,{R2}		;Get list head back
		STR	R2,[R0,#ll__prev] 	;Store head in item
		LDR	R14,[R2,#ll__first]	;Get the first item
		STR	R14,[R0,#ll__next]	;Store this as second item
		STR	R0,[R2,#ll__first]	;Store this as first item
		STR	R0,[R14,#ll__prev]	;Finish off the insertion
		LDR	R14,[R2,#ll__items]	;Get the item count
		ADD	R14,R14,#1		;Increment it
		STR	R14,[R2,#ll__items]	;Store it back again

99llist_addItem	LDMFD	R13!,{R0,R2,R3,R12,R14}	;Get registers back
		ORRVSS	PC,R14,#V_flag		;Return either with...
		BICVCS	PC,R14,#V_flag		;...or without error

		LTORG

; --- llist__removeItem ---
;
; On entry:	R1 == pointer to item to remove (as returned by addItem)
;
; On exit:	--
;
; Use:		This call removes the item from the given list. The
;		item in question is not freed.

llist__removeItem ROUT

		STMFD	R13!,{R1,R2,R14}	;Stack some registers

		SUB	R1,R1,#ll__blockSize	;Point to the real item block
		LDR	R2,[R1,#ll__next]	;Get next item in list
		LDR	R14,[R1,#ll__prev]	;And the previous item
		STR	R2,[R14,#ll__next]	;Update previous next pointer
		STR	R14,[R2,#ll__prev]	;Update next previous pointer

		LDMFD	R13!,{R1,R2,PC}^	;Return to caller

		LTORG

; --- llist_removeItem ---
;
; On entry:	R0 == list head pointer
;		R1 == pointer to item to remove (as returned by addItem)
;
; On exit:	--
;
; Use:		This call removes the item from the given list. All
;		memory taken up by the item is freed. If the value
;		passed in R1 is not an item in the list, then all hell is
;		likely to break loose, so I don't advise making this mistake.

		EXPORT	llist_removeItem
llist_removeItem ROUT

		STMFD	R13!,{R0,R1,R14}	;Stack some registers

		BL	llist__removeItem	;Remove the item
		LDR	R14,[R0,#ll__items]	;Get the item count
		SUB	R14,R14,#1		;Reduce it
		STR	R14,[R0,#ll__items]	;Store it back again
		SUB	R1,R1,#ll__blockSize	;Point to the allocated block
		MOV	R0,R1			;Point to item to remove
		BL	free			;Free it nicely

		LDMFD	R13!,{R0,R1,PC}^	;Return to caller

		LTORG

; --- llist_reinsert ---
;
; On entry:	R0 == pointer to list head
;		R1 == item to reinsert
;
; On exit:	--
;
; Use:		Reinserts the given item into the list. This call is
;		used if the item is updated in such a way that its
;		position in the list may change.

		EXPORT	llist_reinsert
llist_reinsert	ROUT

		STMFD	R13!,{R14}		;Stack the link register
		BL	llist__removeItem	;Remove the item from list
		BL	llist__insert		;Insert it into the list
		LDMFD	R13!,{PC}^		;Return to caller

		LTORG

; --- llist_setFlags ---
;
; On entry:	R1 == pointer to list item
;		R2 == BIC word
;		R3 == EOR word
;
; On exit:	R2 == the new flags word
;
; Use:		Sets the flags associated with the given item. If you
;		just wish to read them, set R2 and R3 to 0.

		EXPORT	llist_setFlags
llist_setFlags	ROUT

		STMFD	R13!,{R0,R14}		;Stack registers
		SUB	R0,R1,#ll__blockSize	;Point to real item
		LDR	R14,[R0,#ll__flags]	;Get the flags word
		BIC	R14,R14,R2		;Do the BIC operation
		EOR	R14,R14,R3		;Now the EOR op
		STR	R14,[R0,#ll__flags]	;Set the flags word
		MOV	R2,R14			;Return these flags
		LDMFD	R13!,{R0,PC}^		;Return to caller

		LTORG

; --- llist_items ---
;
; On entry:	R0 == pointer to list head
;
; On exit:	R1 == number of items in list
;
; Use:		Returns the number of items in the list given. This is
;		a cached value, and so is very fast.

		EXPORT	llist_items
llist_items	ROUT

		LDR	R1,[R0,#ll__items]	;Get the number of items
		MOVS	PC,R14			;And return

; --- llist_enumerate ---
;
; On entry:	R0 == pointer to list head
;		R1 == pointer to item (0 for first)
;		R2 == mask word
;		R3 == test word
;
; On exit:	CS and R1 == next item that matches
;		CC and R1 corrupted if no more items
;
; Use:		This calls return each item in the list, one at a time,
;		as long as the item matches the pattern given.

		EXPORT	llist_enumerate
llist_enumerate	ROUT

		STMFD	R13!,{R4,R12,R14}	;Stack some registers
		WSPACE	llist__wSpace		;Locate my workspace
		ADR	R4,ws__z		;The last item in list

		; --- Find first item to search from ---

		CMP	R1,#0			;Is this the first call?
		LDREQ	R1,[R0,#ll__first]	;Yes -- get first item
		LDRNE	R1,[R1,#ll__next-ll__blockSize]	;No -- get the next

		; --- Keep looking for an item that matches ---

00		CMP	R1,R4			;Are we at the end
		BEQ	%95llist_enumerate	;Yes -- return failure
		LDR	R14,[R1,#ll__flags]	;Get the flags word
		AND	R14,R14,R2		;Clear un-interesting bits
		CMP	R14,R3			;Is this a match?
		BEQ	%90llist_enumerate	;Yes -- return it then
		LDR	R1,[R1,#ll__next]	;Get the next item in list
		B	%00llist_enumerate	;No -- test it then

		;--- We have found an item which matches ---

90		ADD	R1,R1,#ll__blockSize	;Point to user data
		LDMFD	R13!,{R4,R12,R14}	;Get registers back
		ORRS	PC,R14,#C_flag		;Return with carry set

		; --- There are no more matching items ---

95		LDMFD	R13!,{R4,R12,R14}	;Get registers back
		BICS	PC,R14,#C_flag		;Return with carry clear

		LTORG

; --- llist_itemToIndex ---
;
; On entry:	R0 == pointer to list head
;		R1 == point to the item
;
; On exit:	R1 == index of the item, -1 if it's not there
;
; Use:		Returns the index of the item given, indexed from 0.

		EXPORT	llist_itemToIndex
llist_itemToIndex ROUT

		STMFD	R13!,{R2,R3,R12,R14}	;Stack some registers
		WSPACE	llist__wSpace		;Find my workspace
		ADR	R14,ws__z		;Terminator -- (I'll be back)

		SUB	R2,R1,#ll__blockSize	;Point to real item
		MOV	R1,#0			;Index so far
		MOV	R3,R0			;Start from here
00		LDR	R3,[R3,#ll__next]	;The next item in the list
		CMP	R3,R2			;Is this the one we want?
		BEQ	%99llist_itemToIndex	;Yes -- return
		CMP	R3,R14			;Are we at the end?
		MOVEQ	R1,#-1			;Yes -- no valid index then
		BEQ	%99llist_itemToIndex	;...and return
		ADD	R1,R1,#1		;Increment index
		B	%00llist_itemToIndex	;Keep on looking

99		LDMFD	R13!,{R2,R3,R12,PC}^	;Return to caller

		LTORG

; --- llist_indexToItem ---
;
; On entry:	R0 == pointer to list head
;		R1 == point to the index (indexed from 0)
;
; On exit:	R1 == the item itself, or 0 if index doesn't exist
;
; Use:		Returns the index of the item given, indexed from 0.

		EXPORT	llist_indexToItem
llist_indexToItem ROUT

		STMFD	R13!,{R2,R3,R12,R14}	;Stack some registers

		LDR	R2,[R0,#ll__items]	;The number ot items in list
		CMP	R1,R2			;How do they compare?
		MOVGE	R1,#0			;No such index -- return 0
		BGE	%99llist_indexToItem	;And actually return

		MOV	R2,R1			;Get the index in R2
		LDR	R1,[R0,#ll__first]	;The first item
		CMP	R2,#0			;Is this the one we want?
		BEQ	%98llist_indexToItem	;Yes -- return
00		LDR	R1,[R1,#ll__next]	;Get the next in the list
		SUBS	R2,R2,#1		;Decrement the index
		BNE	%00llist_indexToItem	;And keep looking

98		ADD	R1,R1,#ll__blockSize
99		LDMFD	R13!,{R2,R3,R12,PC}^	;Return to caller

		LTORG

; --- llist__merge ---
;
; On entry:	R1 == sort routine
;		R2 == list a
;		R3 == list b
;		R8 == z
;		R9 == list c
;
; On exit:	c^.next = merge of a and b
;		R9 == last item in list
;
; Use:		Used in the mergesort routine to merge two lists.

llist__merge	ROUT

		STMFD	R13!,{R0-R5,R14}	;Stack some registers

		MOV	R5,R1			;Keep pointer to sort routine
		MOV	R4,R8			;c:=z

		; --- The main loop ---

00llist__merge	ADD	R0,R2,#ll__blockSize	;Point to user data for a
		ADD	R1,R3,#ll__blockSize	;Point to user data for b
		CMP	R5,#0			;Is there a sort routine?
		CMPEQ	R0,R0			;No -- make LE condition
		MOVNE	R14,PC			;Yes -- set up return address
		MOVNE	PC,R5			;...and branch to sort routn
		BGT	%10llist__merge		;If a^.key>b^.key

		STR	R2,[R4,#ll__next]	;c^.next=a
		STR	R4,[R2,#ll__prev]	;a^.prev=c
		MOV	R4,R2			;c:=a
		LDR	R2,[R2,#ll__next]	;a:=a^.next
		B	%20llist__merge		;Jump ahead

10llist__merge	STR	R3,[R4,#ll__next]	;c^.next=b
		STR	R4,[R3,#ll__prev]	;b^.prev=c
		MOV	R4,R3			;c:=b
		LDR	R3,[R3,#ll__next]	;b:=b^.next

20llist__merge	CMP	R4,R8			;c=z?
		BNE	%00llist__merge		;No -- keep looping

		LDR	R14,[R8,#ll__next]	;z^.next
		STR	R14,[R9,#ll__next]	;Update next for 'entry c'
		LDR	R9,[R4,#ll__prev]	;Return last item
		STR	R8,[R8,#ll__next]	;z^.next:=z

		LDMFD	R13!,{R0-R5,PC}^	;Return to caller

		LTORG

; --- llist__mergeSort ---
;
; On entry:	R0 == pointer to list head
;		R1 == pointer to sort routine
;
; On exit:	--
;
; Use:		Sort the given list very quickly. Ref Sedgewick P.170

llist__mergeSort ROUT

		STMFD	R13!,{R0-R10,R12,R14}	;Stack some registers
		WSPACE	llist__wSpace		;Find my workspace

		; --- Initialise some variables ---

		ADR	R8,ws__z		;The terminator
		MOV	R7,#1			;N:=1

		; --- The outer loop ---

00		LDR	R5,[R0,#ll__next]	;todo:=head^.next
		MOV	R9,R0			;c:=head

		; --- The inner loop ---

10		MOV	R4,R5			;t:=todo
		MOV	R2,R4			;a:=t
		SUB	R10,R7,#1		;R10=N-1

		MOV	R6,#1			;i:=1
15		CMP	R6,R10			;Do an iteration?
		LDRLE	R4,[R4,#ll__next]	;Yes -- t:=t^.next
		ADDLE	R6,R6,#1		;...i:=i+1
		BLE	%15llist__mergeSort	;...continue the loop

		LDR	R3,[R4,#ll__next]	;b:=t^.next
		STR	R8,[R4,#ll__next]	;t^.next=z
		MOV	R4,R3			;t:=b

		MOV	R6,#1			;i:=1
20		CMP	R6,R10			;Do an iteration?
		LDRLE	R4,[R4,#ll__next]	;Yes -- t:=t^.next
		ADDLE	R6,R6,#1		;...i:=i+1
		BLE	%20llist__mergeSort	;...continue the loop

		LDR	R5,[R4,#ll__next]	;todo:=t^.next
		STR	R8,[R4,#ll__next]	;t^.next=z

		BL	llist__merge		;c^.next:=merge(a,b)
						;c points to last item

		CMP	R5,R8			;todo=z?
		BNE	%10llist__mergeSort	;No -- keep looping

		ADD	R7,R7,R7		;N:=N+N

		LDR	R14,[R0,#ll__next]	;head^.next
		CMP	R14,R2			;a=head^.next?
		BNE	%00llist__mergeSort	;No -- keep looping

		LDMFD	R13!,{R0-R10,R12,PC}^	;Return to caller

		LTORG

; --- llist_registerSort ---
;
; On entry:	R0 == pointer to list head
;		R1 == pointer to new sort routine
;
; On exit:	--
;
; Use:		Registers a new sort routine to be used on the given
;		list. This call will also cause a complete resort
;		of the given list using a mergesort algorithm -- O(n log n).

		EXPORT	llist_registerSort
llist_registerSort ROUT

		STMFD	R13!,{R12,R14}		;Stack registers
		WSPACE	llist__wSpace		;Locate my workspace

		STR	R1,[R0,#ll__sort]	;Store the sort routine
		CMP	R1,#0			;Is there one now?
		LDMEQFD	R13!,{R12,PC}^		;No -- return
		LDR	R14,[R0,#ll__items]	;Get number of items in list
		CMP	R14,#2			;2 or more items?
		BLGE	llist__mergeSort	;Yes -- do the merge sort

		LDMFD	R13!,{R12,PC}^		;Return to caller

		LTORG

; --- llist_init ---
;
; On entry:	--
;
; On exit:	--
;
; Use:		Initialises the llistMan unit.

		EXPORT	llist_init
llist_init	ROUT

		STMFD	R13!,{R12,R14}		;Stack some registers
		WSPACE	llist__wSpace		;Locate my workspace

		; --- Ensure that we are not already initialised ---

		LDR	R14,ws__flags		;Get the flags word
		TST	R14,#wsFlag__inited	;Are we initialised?
		BNE	%99llist_init		;Yes -- return
		ORR	R14,R14,#wsFlag__inited	;We are initialised now
		STR	R14,ws__flags		;Store back modified flags

		; --- Set up the workspace ---

		ADR	R14,ws__z		;Point to terminating item
		STR	R14,[R14,#ll__next]	;Set up the next field

		; --- Return to caller ---

99llist_init	LDMFD	R13!,{R12,PC}^		;Return to caller

		LTORG

llist__wSpace	DCD	0

;----- Workspace layout -----------------------------------------------------

; --- The list head description ---

		^	0

ll__first	#	4			;The first item
ll__sort	#	4			;The sort routine
ll__items	#	4			;The number of items

; --- The list item description ---

		^	0

ll__next	#	4			;The next item in the list
ll__prev	#	4			;The previous item in list
ll__flags	#	4			;Various item flags
ll__size	#	4			;Total size of this item
ll__blockSize	#	0			;Size without user data
ll__userData	#	4			;The user data itself

; --- The workspace ---

		^	0,R12

ws__start	#	0			;Workspace start

ws__flags	#	4			;The flags word
ws__z		#	8			;The end node of a list

ws__size	EQU	{VAR}-ws__start		;The workspace size

wsFlag__inited	EQU	(1<<0)			;We have been initialised

		AREA	|Sapphire$$LibData|,CODE,READONLY

		DCD	ws__size
		DCD	llist__wSpace
		DCD	0
		DCD	llist_init

;----- That's all, folks ----------------------------------------------------

		END
