Enter your search terms Submit search form
	Web pdp-10.trailing-edge.com

	TITLE	LNKLST	NODE POINTER MANIPULATION IN DOUBLY LINKED LISTS
	SUBTTL	ERNIE PETRIDES, WESLEYAN UNIVERSITY, JANUARY, 1979


;IMPORTANT INFORMATION FOR THE USER:
;		UNLIKE MOST LINKED LIST IMPLEMENTATIONS WHERE ONE HALF
;	IS THE LINK AND THE OTHER IS THE DATA OR POINTER TO IT, THESE
;	ROUTINES OPERATE ON DOUBLE-LINK FORWARD/BACKWARD LINKED LISTS
;	WHERE THE NODES ARE ASSUMED TO BE MULTI-WORD BLOCKS.  THE 1ST
;	(OR LINK) WORD CONTAINS A POINTER TO THE PREVIOUS NODE IN THE
;	LEFT HALF AND A POINTER TO THE NEXT NODE OF THE LIST IN THE
;	RIGHT HALF.  THIS ALLOWS FORWARD OR BACKWARD SCANNING OF THE
;	STRUCTURE AND COMPLETE SINGLE NODE REMOVAL.  AT ALL TIMES, A
;	ZERO POINTER SPECIFIES NO LINK (WHOSE POINTERS ARE ALSO DEFINED
;	TO BE ZERO) AND THEREFORE AC 0 CAN NEVER BE LINKED (OR ACCIDENTALLY
;	MODIFIED).  ALL POINTERS ARE MEMORY ADDRESSES AND ONLY LINKAGE
;	WORDS ARE MODIFIED.  A WORKING STACK DEPTH OF TWO IS EXPECTED
;	BY EACH LINKED LIST ROUTINE.  FOLLOWING IS A DESCRIPTION OF THE
;	ARGUMENTS PASSED IN AC 16:
;
;	ROUTINE		SENT				RETURNED
;	 LNK	LEFT NODE ADR,,RIGHT NODE ADR	(SAME AS SENT)
;	 REM	(IGNORED),,NODE ADDRESS		NODE'S PREVIOUS LINKAGE
;	 INR	NEW NODE ADR,,LINKED NODE ADR	NEW NODE'S LINKAGE
;	 INL	NEW NODE ADR,,LINKED NODE ADR	NEW NODE'S LINKAGE
;	 APR	NEW NODE ADR,,ANY NODE ADR	NEW NODE'S LINKAGE
;	 APL	NEW NODE ADR,,ANY NODE ADR	NEW NODE'S LINKAGE


	SUBTTL	DEFINITIONS AND PARAMETERS

	SALL		;MAKE CLEAN LISTINGS

	TWOSEG		;AND A TWO-SEGMENT PROGRAM

	ENTRY	LL$LNK,LL$REM,LL$INR,LL$INL,LL$APR,LL$APL

	RELOC	400000	;BUT PUT EVERTHING IN THE HISEG

	A==16		;ARGUMENT PASSER
	P==17		;PUSH DOWN STACK POINTER
	ALL==777777	;HALF WORD MASK FOR TESTING FOR ZERO LINKS
	LNKMAX==^D1000	;MAXIMUM NUMBER OF END SEARCHES ON APPEND
			;(TO AVOID INFINITE LOOP ON CIRCULAR LIST)

	SUBTTL	LINKED LIST ROUTINES --- LNK,REM,INX

;LINKED LIST ROUTINE TO LINK LEFT NODE TO RIGHT NODE
LL$LNK:	PUSH	P,A			;SAVE LEFT-NODE-ADR,,RIGHT-NODE-ADR
	TRNE	A,ALL			;AS LONG AS RIGHT NODE ADR IS GIVEN,
	  HLR	A,(A)			;  LOAD RIGHT NODE'S LEFT LINK
	TRNE	A,ALL			;AS LONG AS THERE REALLY IS ONE,
	  HLLZS	(A)			;  ZERO ITS RIGHT NODE POINTER
	HLRZS	A			;PUT LEFT NODE ADR IN RIGHT
	TRNE	A,ALL			;AS LONG AS LEFT NODE ADR IS GIVEN,
	  HRR	A,(A)			;  LOAD LEFT NODE'S RIGHT LINK
	TRNE	A,ALL			;AS LONG AS THERE REALLY IS ONE,
	  HRRZS	(A)			;  ZERO ITS LEFT NODE POINTER
	POP	P,A			;RESTORE ORIGINAL LEFT,,RIGHT ARGS
	TRNE	A,ALL			;AS LONG AS THERE IS A RIGHT PNTR,
	  HLLM	A,(A)			;  RE-LINK ITS LEFT SUCCESSOR
	MOVSS	A			;SWAP LINKAGE POINTERS
	TRNE	A,ALL			;AS LONG AS THERE IS A LEFT PNTR,
	  HLRM	A,(A)			;  RE-LINK ITS RIGHT SUCCESSOR
	MOVSS	A			;RE-SWAP LINKAGE POINTERS
	POPJ	P,			;AND RETURN TO CALLER

;LINKED LIST ROUTINE TO REMOVE NODE FROM LIST
LL$REM:	MOVEI	A,(A)			;CLEAR LEFT HALF OF ARG
	TRNN	A,ALL			;MAKE SURE WE'VE GOT AN ADR
	  POPJ	P,			;OTHERWISE, JUST RETURN A ZERO
	PUSH	P,A			;SAVE ADR OF NODE TO BE REMOVED
	MOVE	A,(A)			;LOAD THE NODE'S LINKAGE
	TRNE	A,ALL			;IF THERE IS A RIGHT SUCCESSOR,
	  HLLM	A,(A)			;  REPLACE ITS LEFT WITH OURS
	MOVSS	A			;SWAP LINKAGE POINTERS
	TRNE	A,ALL			;IF THERE IS A LEFT SUCCESSOR,
	  HLRM	A,(A)			;  REPLACE ITS RIGHT WITH OURS
	MOVSS	A			;RE-SWAP LINKAGE POINTERS
	EXCH	A,(P)			;SAVE THEM AND RECOVER NODE ADR
	SETZM	(A)			;CLEAR THE NODE'S LINKAGE
	POP	P,A			;BUT PROVIDE IT FOR CALLER
	POPJ	P,			;RETURN

;HERE FOR EXIT OF BOTH INSERT AND APPEND ROUTINES
LL$INX:	HLRZS	A			;PUT NEW NODE ADR IN RIGHT HALF
	JUMPE	A,.+4			;CHECK TO SEE IF IT'S REALLY THERE
	POP	P,(A)			;ENTER ITS LINKAGE IF IT REALLY IS
	MOVE	A,(A)			;AND PROVIDE IT TO CALLER
	POPJ	P,			;AND RETURN
	POP	P,A			;OTHERWISE, JUST PROVIDE IT TO CALLER
	POPJ	P,			;AND RETURN

	SUBTTL	LINKED LIST ROUTINES --- INS,APP (BOTH R AND L)


;THE FOLLOWING MACRO GENERATES CODE FOR BOTH RIGHT AND LEFT ROUTINES
;
DEFINE	RLGEN (DIR)<
IFG	DIR,<
LL$APR:>;LINKED LIST ROUTINE TO APPEND NODE TO THE RIGHT END OF LIST
IFL	DIR,<
LL$APL:>;LINKED LIST ROUTINE TO APPEND NODE TO THE LEFT END OF LIST
	TRNN	A,ALL			;MAKE SURE WE HAVE A LEGIT NODE
IFG DIR,< JRST	LL$INR>			;OTHERWISE, DO DUMMY INSERT
IFL DIR,< JRST	LL$INL>			;OTHERWISE, DO DUMMY INSERT
	PUSH	P,A			;FIRST SAVE THE ARGS ON STACK
	MOVEI	A,LNKMAX		;LOAD MAX NUMBER OF END SEARCHES
	EXCH	A,(P)			;PUT IT ON STACK AND RECOVER ARGS
	PUSH	P,A			;HEAD OF LOOP--SAVE THIS POSITION
IFG DIR,<HRR	A,(A)>			;LOAD NEXT RIGHT LINK
IFL DIR,<HLR	A,(A)>			;LOAD NEXT LEFT LINK
	TRNE	A,ALL			;REACHED END OF LIST?
	SOSG	-1(P)			;NO--BUT RUN OUT OF TIME?
	  JRST	.+3			;YES FOR EITHER--EXIT FROM LOOP
	MOVEM	A,(P)			;OTHERWISE, SAVE THIS POSITION
	JRST	.-5			;AND LOOP TO LOAD NEXT LINK
	POP	P,A			;HERE WHEN DONE--RELOAD LAST LINK
	POP	P,(P)			;ADJUST STACK POINTER (RID COUNTER)
					;FALL THROUGH TO INSERT
IFG	DIR,<
LL$INR:>;LINKED LIST ROUTINE TO INSERT NODE TO THE RIGHT OF GIVEN NODE
IFL	DIR,<
LL$INL:>;LINKED LIST ROUTINE TO INSERT NODE TO THE LEFT OF GIVEN NODE
	PUSH	P,A			;SAVE NEW-NODE-ADR,,OLD-NODE-ADR
	TRNN	A,ALL			;SEE IF OLD NODE ADR IS GIVEN
	 TLZA	A,ALL			;USE ZERO LINK IF NOT
IFG DIR,< HRL	A,(A)			;ELSE LOAD ITS RIGHT LINK
	MOVSS	A>			;SWAP POINTERS TO CORRECT POSITION
IFL DIR,< HLL	A,(A)>			;ELSE LOAD ITS LEFT LINK
	EXCH	A,(P)			;SAVE LINKAGE AND RECOVER ARGS
	TRNE	A,ALL			;CHECK OLD NODE ADR AGAIN
IFG DIR,< HLRM	A,(A)			;LINK NODE TO US IF GIVEN
	HRR	A,(P)			;LOAD OUR RIGHT NODE POINTER
	TRNE	A,ALL			;CHECK ON OUR RIGHT SUCCESSOR
	  HLLM	A,(A)>			;LINK IT TO US IF WE'VE GOT ONE
IFL DIR,< HLLM	A,(A)			;LINK NODE TO US IF GIVEN
	HLR	A,(P)			;LOAD OUR LEFT NODE POINTER
	TRNE	A,ALL			;CHECK ON OUR LEFT SUCCESSOR
	  HLRM	A,(A)>			;LINK IT TO US IF WE'VE GOT ONE
	JRST	LL$INX			;DO IDENTICAL EXIT ROUTINE
>;END OF RLGEN MACRO

	PAGE		;FOR NICE LISTING FORMAT
	RLGEN	+1	;GENERATE RIGHT INSERT AND APPEND ROUTINES
	RLGEN	-1	;GENERATE LEFT INSERT AND APPEND ROUTINES

	END