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

	LNKLST	Node pointer manipulation in doubly linked lists
	Written by Ernie Petrides, Wesleyan University, January, 1979


	Abstract

	LNKLST is a software package designed to handle the manipulation
of the node pointers in doubly linked lists.  The six linked list opera-
tions are implemented as MACRO subroutines using the standard PUSHJ/POPJ
calling procedure.  The nodes are assumed to be multi-word blocks, of
which a linkage word is a member.  Only the linkage words are modified,
and they contain no information concerning the rest of the node.  The
linkage word contains a pointer to the linkage word of the previous node
in the left half, and a pointer to the linkage word of the following node
in the right half.  This double link allows forward or backward scanning
of the list and list patch-up for node removal.  All pointers are memory
addresses and a zero link specifies no link (whose pointers are defined
to be zero).  Note that AC 0 can never be linked or accidentally modified.

	Using the linked list routines

	To use LNKLST, the user must "EXTERN" the required entry points
and execute the standard PUSHJ P,LL$XXX subroutine call where the stack
pointer P is accumulator 17 and XXX is the three-letter abbreviation of
the linked list routine.  Arguments must be passed in accumulator 16 and
the user's stack should provide a usable depth of at least 3 levels.

	There are no detectable errors that can occur in any of the linked
list subroutines.

	Here is a list of the linked list routines with the specification
of the arguments passed in AC 16 followed by a brief description of the
functions of each routine.  All references to "successors" refer to the
left and right neighbors of a node; specifically, this isn't a binary tree!

	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

LNK -- Link; link any two nodes together; if left node already has a
	right pointer, zero the right successor's left link; if right
	node already has a left pointer, zero the left successor's
	right link.
REM -- Remove; remove node from list, patching its left and right
	successor's together.
INR -- Insert to the right; insert a new node directly to the right of
	the specified node, adopting its right successor as ours.
INL -- Insert to the left; insert a new node directly to the left of
	the specified node, adopting its left successor as ours.
APR -- Append to the right; append a new node to the right end of the
	list of which the specified node is a member, limiting the search
	to 1000 tries to avoid an infinite loop on circular structures.
APL -- Append to the left; append a new node to the left end of the
	list of which the specified node is a member, limiting the search
	to 1000 tries to avoid an infinite loop on circular structures.


	All of the user's accumulators (except for the argument passer)
are always preserved by each linked list subroutine.


	End of LNKLST.DOC