list.txt

来自「汇编编程艺术」· 文本 代码 · 共 873 行 · 第 1/2 页

Linked list manipulation routines
=================================

These routines manipulate items in a linked list.  Internally the system
represents the data as a doubly linked list, although your program should
not rely on the internal structure of the data structure.

There are two structures of interest defined in the LISTS.A file: LIST
and NODE.  Use variables of type LIST to create brand new lists.  Use
variables of type NODE to hold the entries in the list.

These structures take the following form:

List		struc
Size		dw	?		;Size, in bytes, of a node in the list
Head		dd	0		;Ptr to start of list
Tail		dd	0		;Ptr to end of list
Current		dd	0		;Pointer to current node
List		ends

Node		struc
Next		dd	?		;Ptr to next node in list
Prev		dd	?		;Ptr to prev node in list
NodeData	db	??		;Data immediately follows Prev
Node		ends


There are two ways to create a new list: statically or dynamically.
Consider static allocation first.  In this case, you create a list variable
by declaring an object of type LIST in a data segment, e.g.,

MyList		list	<25>

You *must* supply the size (in bytes) of a node in the list.  Note that the
size should *not* include the eight bytes required for the next and prev
pointers.  This allows you to change the internal structure of the list
(e.g., to a singly linked list) without having to change other code.  You
can easily compute this as follows:

MyList		list	<(sizeof MyNode) - (sizeof Node)>

When you declare lists in this fashion, the definition automatically
initializes the list to an empty list.

You can also create a list dynamically by calling the CreateList routine.
To CreateList you must pass the size of a Node (not including the pointers)
in the CX register.  It allocates storage for the list variable on the
heap and returns a pointer to this new (empty) list in es:di.

		mov	cx, (sizeof MyNode) - (sizeof Node)
		CreateList
		mov	word ptr MyListPtr, di
		mov	word ptr MyListPtr+2, es


To create nodes for your list, you should "overload" the NODE definition
appearing the in LISTS.A file.  This works best under MASM 6.0 and TASM 3.0,
which support object-oriented programming, though it isn't that difficult to
accomplish with other assemblers.  A mechanism compatible with *all*
assemblers follows:

To create a brand new node is easy,  just do the following:

MyNode		struc
		db	(size Node) dup (0) 	;Inherit all fields from NODE.
Field1		db	?			;User-supplied fields for this
Field2		dw	?			; particular node type.
Field3		dd	?			;  "    "     "    "
Field4		real4	3.14159			;  "    "     "    "
MyNode		ends

Note that the NODE fields must appear *first* in the data structure.
The list manipulation routines assume that the list pointers in NODE appear
at the beginning of the structure.

The CurrentNode field of the list data structure points at a "current" node
in the list.  The current node is the last node operated on in the case of
insert, append, peek, etc.  In the event a node is removed, the current node
will be the next node after the node removed.  In general, the current node
can be thought of as a "cursor" which wanders through the list according to
the operations occuring.  Since most list operations occur on the next node
in a list, keeping the CurrentNode field updated speeds up access to the
list.

You can use the following routines to implement the corresponding data
structures (which can all be implemented using lists):

FIFO Queues:

AppendLastm, AppendLast, Remove1st, and Peek1st (technically, using Peek1st
is cheating, but so what).



Deques (double ended queues):

All the FIFO routines plus InsertFirstm, InsertFirst, RemoveLast, and
PeekLast (PeekLast is cheating too).


Lists:

All of the above plus InsertCur, InsertmCur, AppendCur, AppendmCur,
RemoveCur, Insert, Insertm, Append, Appendm, Remove, SetCur, NextNode,
and PrevNode.

For those who care about such things, the UCR Standard Library implements
the list data structure using a doubly linked list.  However, it is a
true generic (encapsulated) data type and your code needed be at all
concerned about the internal structure.  Furthermore, assuming you treat
it like an encapsulated data structure, you can modify the internal list
structure and not break any programs which use the list data types.





Routine:  CreateList
--------------------

Author:		      Randall Hyde

Category:             List Manipulation

Registers on entry:   	CX-	Size of data (in bytes) to store at each node

Registers on return:  	ES:DI-	Pointer to new list variable on heap

Flags affected:       	Carry set if CreateList cannot allocate sufficient
			storage on the heap for the list variable.

Example of Usage:
			mov	cx, (sizeof MyNode) - (sizeof Node)
			CreateList
			jc	ListError
			mov	word ptr ListVarPtr, di
			mov	word ptr ListVarPtr+2, es

Description:

CreateList allocates storage for a list variable on the head and initializes
that variable to the empty list.  It also sets up the size field of the
list variable based on the value passed in the CX register.  It returns
a pointer to the newly created list in the ES:DI registers.

This routine initializes the CurrentNode field to NIL.  Any node inserted
before or after the current node will be inserted as the first node in this
case.

Include:	lists.a or stdlib.a



Routine:  AppendLast (m)
------------------------

Author:		      Randall Hyde

Category:             List Manipulation

Registers on entry:   	DX:SI-	Pointer to node to add to list (AppendLast)
			DX:SI-	Pointer to block of data (sans list stuff)
				to add to end of list (AppendLastm)
			ES:DI-	Pointer to list.

Registers on return:  	ES:DI-	Pointer to list.

Flags affected:       	Carry set if AppendLastm cannot allocate sufficient
			storage on the heap for the list variable.

Examples of Usage:

; Append data statically declared as ANode to the end of the list pointed at
; by the list variable "ListVar".

			ldxi	ANode
			les	di, ListVar
			AppendLast

; Create a node from the data at address "MyData".  Build the node on the
; heap and append this node to the end of the list pointed at by ListVar.

			ldxi	MyData
			les	di, ListVar
			AppendLastm
			jc	BadListError

Description:

AppendLast and AppendLastm add a node to the end of a list.  AppendLast works
with whole nodes.  It is useful, for example when moving a node from one
list to another or when dealing with nodes that were created statically in
the program.  It requires nodes properly declared using the NODE data type
in the LIST.A include file.

AppendLastm builds a new node on the heap and appends this node to the end
of the specified list.  The difference between AppendLastm and AppendLast is
that AppendLastm does not require a predefined node.  Instead, DX:SI points
at the data for the node (the number of bytes is specified by the ListSize
field of the LIST data type).  AppendLastm allocates memory, copies the data
from DX:SI to the data field of the new node, and then links in the new node
to the specified list.

The new node added to the list becomes the CurrentNode.

Include:	stdlib.a or lists.a



Routine:  Remove1st
-------------------

Author:		      	Randall Hyde

Category:             	List Manipulation

Registers on entry:   	ES:DI-	Pointer to list variable.

Registers on return:	DX:SI-	Pointer to node removed from the front of
				the list (NIL if nothing in list).

Flags affected:       	Carry set if the list was empty.

Examples of Usage:

; The following loop removes all the items from a list and processes each
; item.

DoAllOfList:		les	di, MyList
			Remove1st
			jc	DidItAll
			<manipulate this item>
			jmp	DoAllOfList
DidItAll:


Description:

Remove1st removes the first item from a list and returns a pointer to that
item in DX:SI.  If the list was empty, then it returns a NIL pointer in
DX:SI and returns with the carry flag set.

Note that you can use the AppendLast(m) and Remove1st routines to implement
and manipulate a FIFO queue data structure.  Peek1st is another useful
routine which returns the first item on a list without removing it from
the list.

The second node in the list (the one after the node just removed) becomes
the new CurrentNode.  If there are no additional nodes in the list, the
CurrentNode variable gets set to NIL.

Include:	stdlib.a or lists.a




Routine:  Peek1st
-----------------

Author:		      	Randall Hyde

Category:             	List Manipulation

Registers on entry:   	ES:DI-	Pointer to list variable.

Registers on return:	DX:SI-	Pointer to node at the beginning of
				the list (NIL if nothing in list).

Flags affected:       	Carry set if the list was empty.

Examples of Usage:

			les	di, MyList
			Peek1st
			jc	NothingThere

Description:

Peek1st is similar to Remove1st in that it returns a pointer to the first
item in a list (NIL if the list is empty).  However, it does not remove the
item from the list.  This is useful for performing a "non-destructive" read
of the first item in a FIFO queue.

This routine sets the CurrentNode field to the first node in the list.

Include:	stdlib.a or lists.a



Routine:  Insert1st (m)
-----------------------

Author:		      Randall Hyde

Category:             List Manipulation

Registers on entry:   	DX:SI-	Pointer to node to add to list (Insert1st)
			DX:SI-	Pointer to block of data (sans list stuff)
				to add to end of list (Insert1stm)
			ES:DI-	Pointer to list.

Registers on return:  	ES:DI-	Pointer to list.

Flags affected:       	Carry set if Insertm cannot allocate sufficient
			storage on the heap for the list variable.

Examples of Usage:

; Insert data statically declared as ANode to the beginning of the list
; pointed at by the list variable "ListVar".

			ldxi	ANode
			les	di, ListVar
			Insert1st

; Create a node from the data at address "MyData".  Build the node on the
; heap and insert this node to the beginning of the list pointed at by
; ListVar.

			ldxi	MyData
			les	di, ListVar
			Insert1stm
			jc	BadListError

Description:

Insert1st and Insert1stm add a node to the beginning of a list.  Insert1st
works with whole nodes.  It is useful, for example when moving a node from one
list to another or when dealing with nodes that were created statically in
the program.  It requires nodes properly declared using the NODE data type
in the LISTS.A include file.

Insert1stm builds a new node on the heap and inserts this node to the start
of the specified list.  The difference between Insert1stm and Insert1st is
that Insert1stm does not require a predefined node.  Instead, DX:SI points
at the data for the node (the number of bytes is specified by the ListSize
field of the LIST data type).  Insert1stm allocates memory, copies the data
from DX:SI to the data field of the new node, and then links in the new node
to the specified list.

Note that Insert1st/Insert1stm can be used to create Deque data structures.

The newly inserted node becomes the CurrentNode in the list.

Include:	stdlib.a or lists.a



Routine:  RemoveLast
--------------------

Author:		      	Randall Hyde

Category:             	List Manipulation

Registers on entry:   	ES:DI-	Pointer to list variable.

Registers on return:	DX:SI-	Pointer to node removed from the end of
				the list (NIL if nothing in list).

Flags affected:       	Carry set if the list was empty.

Examples of Usage:

; The following loop removes all the items from a list and processes each
; item.

DoAllOfList:		les	di, MyList
			RemoveLast
			jc	DidItAll
			<manipulate this item>
			jmp	DoAllOfList
DidItAll:


Description:

RemoveLast removes the last item from a list and returns a pointer to that
item in DX:SI.  If the list was empty, then it returns a NIL pointer in
DX:SI and returns with the carry flag set.

Note that you can use the Insert1st(m) and RemoveLast routines to implement
and manipulate a DEQUE queue data structure (along with the FIFO routines:
AppendLast(m), Rmv1st, and Peek1st).  PeekLast is another useful
routine which returns the last item on a list without removing it from
the list.

The last node in the list (the one before the node just removed) becomes the
new CurrentNode in the list.  If the list is empty, CurrentNode gets set to
NIL.

Include:	stdlib.a or lists.a




Routine:  PeekLast
------------------

Author:		      	Randall Hyde

Category:             	List Manipulation

Registers on entry:   	ES:DI-	Pointer to list variable.

Registers on return:	DX:SI-	Pointer to node at the end of
				the list (NIL if nothing in list).

Flags affected:       	Carry set if the list was empty.

Examples of Usage:

			les	di, MyList
			PeekLast
			jc	NothingThere

Description:

PeekLast is just like Peek1st except it looks at the last node on the list
rather than the first.  It does the same job as RemoveLast except it does
not remove the node from the list.  Great for implementing Deques.

This routine also sets the CurrentNode field to point at the last node in
the list.

Include:	stdlib.a or lists.a




Routine:  InsertCur
-------------------

Author:		      	Randall Hyde

Category:             	List Manipulation