;   EXTENDED LIST/NODE HANDLING
		;
		;   (C)CopyRight May 1988, Matthew Dillon, All Rights Reserved
		;


		;NOTE:	These routines accomodate structures where the
		;	NODE used to traverse the list is not necessarily
		;	at the beginning of the structure.  This, 'sptr'
		;	refers to the structure pointer (not the node
		;	pointer, unless the node is at the beginning), and
		;	'off' offset refers to the offset into the structure
		;	where the NODE resides.

		public	_lGetHead	     ; node = GetHead(list)
		public	_lGetTail	     ; node = GetTail(list)
		public	_lGetSucc	     ; node = GetSucc(node)
		public	_lGetPred	     ; node = GetPred(node)
		public	_lGetHeadOff	     ; sptr = GetHeadOff(list, off)
		public	_lGetTailOff	     ; sptr = GetTailOff(list, off)
		public	_lGetSuccOff	     ; sptr = GetSuccOff(sptr, off)
		public	_lGetPredOff	     ; sptr = GetPredOff(sptr, off)
		public	_lEnqueueLong	     ; (void)EnqueueLong(list, start, sptr, valoff)
		public	_lEnqueueOffLong     ; (void)EnqueueOffLong(list, start, sptr, off, valoff)
		public	_lSearchFwdNode      ; ret  = SearchFwdNode(sptr, func, arg)      ->  func(somesptr,arg)
		public	_lSearchRvsNode      ; ret  = SearchRvsNode(sptr, func, arg)             (ditto)
		public	_lSearchFwdList      ; ret  = SearchFwdList(list, func, arg)             (ditto)
		public	_lSearchRvsList      ; ret  = SearchRvsList(list, func, arg)             (ditto)
		public	_lSearchFwdNodeOff   ; ret  = SearchFwdNode(sptr, func, off, arg) ->  func(somesptr,arg)
		public	_lSearchRvsNodeOff   ; ret  = SearchRvsNode(sptr, func, off, arg)        (ditto)
		public	_lSearchFwdListOff   ; ret  = SearchFwdList(list, func, off, arg)        (ditto)
		public	_lSearchRvsListOff   ; ret  = SearchRvsList(list, func, off, arg)        (ditto)

		;   GETHEAD(list:A0)
		;   GETSUCC(node:A0)
_lGetSucc:
_lGetHead:	move.l	(A0),A0
		tst.l	(A0)
		beq	.gh0
		move.l	A0,D0
		rts

		;   GETTAIL(list:A0)

_lGetTail:	move.l	8(A0),A0
		tst.l	4(A0)
		beq	.gh0
		move.l	A0,D0
		rts

		;   GETPRED(node:A0)

_lGetPred:	move.l	4(A0),A0
		tst.l	4(A0)
		beq	.gh0
		move.l	A0,D0
		rts

.gh0		moveq.l #0,D0
		rts

		;   GETHEADOFF(list:D0, offset:D1)

_lGetHeadOff:	move.l	D0,A0
		move.l	(A0),A0
		tst.l	(A0)
		beq	.gh0
		sub.l	D1,A0
		move.l	A0,D0
		rts

		;   GETTAILOFF(list:D0, offset:D1)

_lGetTailOff:	move.l	D0,A0
		move.l	8(A0),A0
		tst.l	4(A0)
		beq	.gh0
		sub.l	D1,A0
		move.l	A0,D0
		rts

		;   SPTR is a structure pointer, where the node is offset
		;   OFFSET from the base of the structure.

		;   GETSUCCOFF(sptr:D0, offset:D1)

_lGetSuccOff:	move.l	D0,A0
		move.l	(A0,D1.L),A0
		tst.l	(A0)
		beq	.gh0
		suba.l	D1,A0
		move.l	A0,D0
		rts

		;   GETPREDOFF(sptr:D0, offset:D1)

_lGetPredOff:	move.l	D0,A0
		move.l	4(A0,D1.L),A0
		tst.l	4(A0)
		beq	.gh0
		suba.l	D1,A0
		move.l	A0,D0
		rts

		;   ENQUEUELONG(list:D0, start:D1, sptr:D2, valoff:D4)
		;   ENQUEUEOFFLONG(list:D0, start:D1, sptr:D2, off:D3, valoff:D4)
		;
		;   list:	list to queue the object in
		;   start:	sptr to start search at (NULL=beginning of list)
		;   sptr:	pointer to the structure to queue, where
		;   off:	offset into the structure where the embedded Node is
		;   valoff:	offset into structure where the longword holding
		;		the sorting priority of the object is.
		;
		;   The list is already assumed to be sorted.  The search
		;   progresses either forward or reverse along the list until
		;   the proper place is found, then the object is inserted into
		;   the list.  The object is placed AFTER any objects of equal
		;   priority (whether the list is searched forward or backwards).

_lEnqueueLong:
		movem.l D3/A2/A3,-(sp)
		moveq.l #0,D3
		bra	.eol1
_lEnqueueOffLong:
		movem.l D3/A2/A3,-(sp)
.eol1		move.l	D2,A3	    ; A3 = structure to add
		move.l	D1,A2	    ; A2 = roving structure in search
		tst.l	D1
		bne	.eol2
		move.l	D0,A2	    ; use list head instead
		move.l	(A2),A1
		tst.l	(A1)
		beq	.eol100     ; add structure to empty list
		move.l	A1,A2
		sub.l	D3,A2	    ; retrieve structure pointer

		;   D0 = D4(A3)
		;   D3 = offset into A2/A3 of node
		;   D4 = offset into A2/A3 of longword value
		;   A2 = roving structure ptr
		;   A3 = structure to add
		;
		;   Sequence:	if D4(A3) > D4(A2), forward search
		;		if D4(A3) < D4(A2), reverse search

.eol2		move.l	(A3,D4.L),D0    ; Search forwards or backwards?
		cmp.l	(A2,D4.L),D0
		blt	.eol50
.eol10		move.l	(A2,D3.L),A2    ; SEARCH FORWARDS (A2 = next node)
		tst.l	(A2)            ; reached list tail
		beq	.eol30		; Add to tail
		sub.l	D3,A2		; A2 = structure
		cmp.l	(A2,D4.L),D0
		bge	.eol10		; loop while value > roving_value
		add.l	D3,A2		; ADDBEFORE current node, A2 = listnode
		add.l	D3,A3		; A3 = node to add

		move.l	A2,(A3)         ; INSERT BEFORE (listnode:A2, node:A3)
		move.l	4(A2),A0        ; A0 is node before A2  (seq A0-A3-A2)
		move.l	A0,4(A3)
		move.l	A3,4(A2)
		move.l	A3,(A0)
		bra	.eolend
					; (A2 points to lh_Tail here)
.eol30		move.l	4(A2),A2        ; ADDTOEND, A2 = tail element
		bra	.eol100
.eol50		move.l	4(A2,D3.L),A2   ;SEARCH BACKWARDS (A2 = prev. node)
		tst.l	4(A2)           ;reached list head .. AddHead()
		beq	.eol100
		sub.l	D3,A2		;A2 = structure pointer
		cmp.l	(A2,D4.L),D0    ;loop while value < roving_value
		blt	.eol50
		add.l	D3,A2		;add after NODE A2
.eol100 	add.l	D3,A3		;INSERT AFTER(list/node:A2, structure:A3)
		move.l	(A2),A0
		move.l	A0,(A3)
		move.l	4(A0),4(A3)
		move.l	A3,(A2)
		move.l	A3,4(A0)
.eolend 	movem.l (sp)+,D3/A2/A3
		rts

		;   SEARCHFWDLIST[OFF](list:D0, func:D1, [offset:A0,] funcarg:A1)
		;   SEARCHRVSLIST[OFF](list:D0, func:D1, [offset:A0,] funcarg:A1)
		;
		;	Get head/tail of list then call Search???Node

_lSearchFwdList:
		sub.l	A0,A0
_lSearchFwdListOff:
		movem.l D2-D5/A2/A3/A6,-(sp)
		move.l	D0,A2
		move.l	(A2),A2             ; get head of list
		tst.l	(A2)                ; empty list?
		bne	SFN
		bra	.sfn0

_lSearchRvsList:
		sub.l	A0,A0
_lSearchRvsListOff:
		movem.l D2-D5/A2/A3/A6,-(sp)
		move.l	D0,A2
		move.l	8(A2),A2            ; get tail of list
		tst.l	4(A2)               ; empty list?
		bne	SRN
		bra	.sfr0

		;   For compatibility with various C compilers, neither
		;   A4 or A5 is touched.  D2,D3, and A6 are also assumed
		;   to be destroyed by the function.
		;
		;   The search ends when the function returns a non-NULL
		;   value or the list is exhausted (NULL is returned)
		;
		;   SEARCHFWDNODE(sptr:D0, func:D1, offset:A0, funcarg:A1)


_lSearchFwdNode:
		sub.l	A0,A0
_lSearchFwdNodeOff:
		movem.l D2-D5/A2/A3/A6,-(sp)
		move.l	D0,A2
SFN:		move.l	D1,A3
		move.l	A0,D4
		move.l	A1,D5
		move.l	A2,D0		    ; test for initial NULL
		beq	.sfndone
		adda.l	D4,A2
.sfnloop	suba.l	D4,A2
		move.l	D5,-(sp)            ; call function(sptr, funcarg)
		move.l	A2,-(sp)
		jsr	(A3)
		addq.l	#8,sp
		tst.l	D0		    ; non-zero ret. value
		bne	.sfndone
		adda.l	D4,A2		    ; GetSuccOff()
		move.l	(A2),A2
		tst.l	(A2)
		bne	.sfnloop
.sfn0		moveq.l #0,D0
.sfndone	movem.l (sp)+,D2-D5/A2/A3/A6
		rts

		;   SEARCHRVSNODE(node:D0, func:D1, offset:A0, funcarg:A1)

_lSearchRvsNode:
		sub.l	A0,A0

_lSearchRvsNodeOff:
		movem.l D2-D5/A2/A3/A6,-(sp)
		move.l	D0,A2
SRN:		move.l	D1,A3
		move.l	A0,D4
		move.l	A1,D5
		move.l	A2,D0		    ; test for initial NULL
		beq	.sfrdone
		adda.l	D4,A2
.sfrloop	suba.l	D4,A2
		move.l	D5,-(sp)            ; call function(sptr, funcarg)
		move.l	A2,-(sp)            ; args also in A2 and D5
		jsr	(A3)
		addq.l	#8,sp
		tst.l	D0		    ; non-zero ret. value
		bne	.sfrdone
		adda.l	D4,A2		    ; GetPredOff()
		move.l	4(A2),A2
		tst.l	4(A2)
		bne	.sfrloop
.sfr0		moveq.l #0,D0
.sfrdone	movem.l (sp)+,D2-D5/A2/A3/A6
		rts