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, ;LOAD NEXT RIGHT LINK IFL DIR, ;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