2. How Does The Code Work?

The code is a small example of creating and navigating a linked list. The demo starts by creating a list of 5 nodes, each holding one long word of data being simply the node number 0 to 4.

The list contents are then printed on the screen shoing the node address, the next pointer and the data stored in that node. Once this is done, the node with data contents of 3 is located and deleted prior to the new list being printed out again.

Finally, each node in the list is deleted.

The first part of the code simply controls the whole demo by calling various sub-routines to do the hard work, display messages etc on screen.

* =======================================================================
* The DEMO code starts here.
*
* This demo does the following :
*
* Creates a number of nodes and stores a LONG value in each one.
* Lists each node address, it's NEXT pointer and data value on screen.
* Deletes a node.
* Lists each node address, it's NEXT pointer and data value on screen.
* Finds a node based on its data value and displays its details on screen.
* Deletes all the nodes from the list.
* =======================================================================
Demo       bsr     BuildList            ; Build a linked list
           bsr     Before               ; Display 'BEFORE :'
           bsr     ShowList             ; Display list details
           bsr     FindNode             ; Locate a single node
           bne.s   DemoAfter            ; Failed to find node with data = 3
           bsr     DeleteNode           ; Delete a single node

DemoAfter  bsr     After                ; Display 'AFTER : '
           bsr     ShowList             ; Show details again
           bsr     KillList             ; Delete entire list
           rts                          ; Done

Following on from the main control section of the demo, we have our much beloved root node which must be initialised to zero as outlined in the original article. This is the pointer we will be loading into A0 quite often in the demo and it holds the address of the first node in the list. At present, there is no list, so the contents are set to zero to indicate the very end of the list.

* -----------------------------------------------------------------------
* A location to hold a single long word pointing to the first 'real'
* node in our linked list. This must be initialized to zero.
* -----------------------------------------------------------------------
RootNode   dc.l    0                    ; This is our root node.

The first of our sub-routines follows on. This part builds a list of 5 nodes in the most simple manner possible - it runs a loop which calls the sub-routine to create a single node and link it into the list. If you want a bigger list, change the counter loaded into D7 to one less than the number of node you want. Don't forget to adjust the height of your window as wll if you want to see all the results on screen at the same time.

* -----------------------------------------------------------------------
* Build a list of 5 nodes each holding a long word of data.
* -----------------------------------------------------------------------
BuildList  lea     RootNode,a0          ; Pointer to root node address
           moveq   #4,d7                ; How many nodes in D7 = 5 (DBRA remember ?)
           moveq   #8,d1                ; Each node is 8 bytes long

BuildLoop  bsr.s   BuildNode            ; Create a new node, address is in A1.L
           bne     all_done             ; Just die on errors
           move.l  d7,4(a1)             ; Store data value - just our counter
           bsr.s   AddNode              ; Add to list
           dbra    d7,BuildLoop         ; Do the rest
           rts                          ; Done

Here's the first of the real list routines. We add a new node into the list in the manner outlined in the article. We reject attempts to add the rot node into the list - but without flagging any errors - and, as explained, we don't attempt to check if the new node already exists in the list because we are creating the node on the heap, so the chances of the new node being present already are pretty slim to say the least.

* -----------------------------------------------------------------------
* AddNode - Adds a new node to a list. See text for details.
* Preserves all regsiters.
* No errors returned.
* -----------------------------------------------------------------------
AddNode    cmpa.l  a0,a1                ; Don't allow the root node to be added again
           beq.s   AddExit              ; Bale out quietly if attempted
           move.l (a0),(a1)             ; Save current first node in new node's NEXT area
           move.l  a1,(a0)              ; Store address of new node in FIRST storage area
AddExit    rts

A new node is built by allocating some space on the common heap but we must preserve the working registers, the following code does this for us.

* -----------------------------------------------------------------------
* Allocate a single new node
* On entry, D1.L is amount of memory required.
* On exit, A1 holds the address of the new node, with D0 holding errors.
* All registers preserved - unless otherwise stated.
* -----------------------------------------------------------------------
BuildNode  movem.l d1-d3/a0/a2-a3,-(a7) ; Save working registers
           moveq   #MT_ALCHP,d0         ; Set the trap
           moveq   #me,d2               ; I want it for me
           trap    #1                   ; Do it
           move.l  a0,a1                ; Get the node address where we need it
           movem.l (a7)+,d1-d3/a0/a2-a3 ; Restore working registers
           tst.l   d0                   ; Set flags
           rts                          ; Exit

The following sub-routine is called once to display the linked list before we do the deletions and again after we have deleteing a node. The code simply walks through the entire list and prints out the node address, the next pointer and the data value by calling other sub-routines.

* -----------------------------------------------------------------------
* Walk through a linked list displaying the details of each node as we
* go.
* On entry, A0 = root node of the list.
* -----------------------------------------------------------------------
ShowList    lea    RootNode,a0          ; Root node address

ShowLoop    move.l (a0),a0              ; Get address of the next node
            cmpa.l #0,a0                ; Done ?
            beq.s  ShowExit             ; Yes
            move.l a0,-(a7)             ; We must preserve A0 - it's our node pointer
            bsr.s  ShowNode             ; Display that node's details
            move.l (a7)+,a0             ; Restore the node pointer again
            bra.s  ShowLoop             ; Do the rest of the list

ShowExit    rts                         ; Done

This next short routine is called with the address of a node in A0.L and prints the details of that node to the screen.

* -----------------------------------------------------------------------
* Display the details of a single node in the linked list.
* On entry A0 = the node address.
* -----------------------------------------------------------------------
ShowNode    move.l a0,a5                ; The node address
            move.l con_id2(a4),a0       ; The channel address
            move.l a5,d4                ; The node address
            bsr.s  ShowAddr             ; Print node address
            move.l (a5),d4              ; The NEXT pointer
            bsr.s  ShowNext             ; Print NEXT pointer
            move.l 4(a5),d4             ; The node data
            bsr    ShowData             ; Print the data
            rts

Obviously, just displaying the list contents isn't very user firiendly, so the next couple of routines display a title which informs the user if the list being displyed is ' before' or ' after' the deletion of a node.

* -----------------------------------------------------------------------
* Display 'BEFORE :' in the output channel.
* -----------------------------------------------------------------------
Before     lea     BeforeAddr,a1        ; The prompt
           movea.l con_id2(a4),a0       ; Needs channel id
           bsr     Prompt               ; Print it
           rts

BeforeAddr dc.w    B4End-BeforeAddr-2
           dc.b    'BEFORE :',linefeed
B4End      equ     *

* -----------------------------------------------------------------------
* Display 'AFTER :' in the output channel
* -----------------------------------------------------------------------
After      lea     AfterAddr,a1         ; The prompt
           movea.l con_id2(a4),a0       ; Needs channel id
           bsr     Prompt               ; Print it
           rts

AfterAddr  dc.w    AftEnd-AfterAddr-2
           dc.b    linefeed,linefeed,'AFTER :',linefeed
AftEnd     equ     *

There now follows one of three separate but short routines to display on screen, the various parts of a list node. This one simply displays the node's address in memory. Following after this routine is a number of small sub-routines which assist in the displaying of node data by converting the contents of D4 to hex and printing it to the screen.

* -----------------------------------------------------------------------
* Display the node's actual address in memory.
* On entry D4 = the node address.
* -----------------------------------------------------------------------
ShowAddr   lea     MsgAddr,a1           ; Our prompt

ShowPrompt bsr     Prompt               ; Print it
           bsr.s   D4ToHex              ; Convert D4.L to hex
           bsr.s   PrintHex             ; Print it and a linefeed
           rts

MsgAddr    dc.w    AddrEnd-MsgAddr-2
           dc.b    linefeed,'Node address : '
AddrEnd    equ     *

* -----------------------------------------------------------------------
* Print the contents of the buffer to screen.
* -----------------------------------------------------------------------
PrintHex   lea     Buffer,a1            ; What to print
           move.l  con_id2(a4),a0       ; Channel to print to
           bsr     Prompt               ; Do it
           rts

* -----------------------------------------------------------------------
* Convert the long word in D4 to hex ready for printing
* -----------------------------------------------------------------------
D4ToHex    lea     buffer+2,a1          ; Buffer address
           bsr     hex_l                ; Do all 4 bytes = 8 characters
           lea     buffer,a1            ; Buffer again
           move.w  #8,(a1)              ; Store text length
           rts

The second and third routines to diplsy the details of a node now follow. Starting with the code to show the node's NEXT pointer address closely followed by the code to print the actual data stored in the node.

* -----------------------------------------------------------------------
* Display the node's NEXT address in memory.
* On entry D4 = the node's NEXT pointer.
* -----------------------------------------------------------------------
ShowNext   lea     MsgNext,a1           ; Our prompt
           bra.s   ShowPrompt           ; Print it

MsgNext    dc.w    NextEnd-MsgNext-2
           dc.b    '  NEXT pointer : '
NextEnd    equ     *

* -----------------------------------------------------------------------
* Display the node's actual data content.
* On entry D4 = the data.
* -----------------------------------------------------------------------
ShowData   lea     MsgData,a1           ; Our prompt
           bra.s   ShowPrompt           ; Print it

MsgData    dc.w    DataEnd-MsgData-2
           dc.b    '  Data value : '
DataEnd    equ     *

Next we have the code to locate a single node in the linked list based upon the data part of the node. This part is simply the setup routine for the following code at FindANode which does the actual scanning of the node and calling the compare routine as described in the previous chapter.

* -----------------------------------------------------------------------
* Locate a node in the list based on it's data value.
* On exit, A1 is the required node's address plus Z set - if found.
*          A1 is undefined plus Z clear - if not found.
* -----------------------------------------------------------------------
FindNode   lea     RootNode,a0          ; Pointer to root node in list
           lea     Compare,a1           ; Address of node comparison routine
           moveq   #3,d1                ; The data value we are looking for
           bsr.s   FindANode            ; Go find it, or not
           rts

* -----------------------------------------------------------------------
* This routine expects the following input registers so that it can scan
* a linked list for the required data value and return the address of the
* node holding that data value with the Z flag set if found, or the Z flag
* cleared for not found.
*
* A0.L = Rootnode of the list.
* A1.L = Address of Compare routine.
* D1.L = Value to look for in list.
* -----------------------------------------------------------------------
FindANode  moveq   #oops,d0             ; Assume not found (yet)

FindLoop   cmpa.l  #0,a0                ; Reached the end yet ?
           beq.s   FindExit             ; Yes, node not found, exit with error

           move.l  (a0),a3              ; Fetch the NEXT node address into A3.L
           jsr     (a1)                 ; And jump into the comparison routine
           beq.s   FindFound            ; Looks like we found our node

FindNext   move.l  (a0),a0              ; A0 now holds the NEXT node in the list
           bra.s   FindLoop             ; Go around again

FindFound  movea.l a3,a1                ; This is the required node
           moveq   #0,d0                ; Clear error flag

FindExit   tst.l   d0                   ; Set zero flag for success, unset for error
           rts

* -----------------------------------------------------------------------
* This is the simple compare routine for our FindNode code. On entry, we
* have the following registers set :
*
* D1.L = The value we want to find in a node in the list.
* A3.L = The address of a node which we are checking for the data value.
*
* We must preserve A0, A1 and D1.
*------------------------------------------------------------------------
NData      equ   4                      ; Offset into a node to the data part.
Compare    cmp.l NData(a3),d1           ; Is the data in the node = the value we want?
           rts                          ; Exit with Z set if so, unset otherwise.

This next routine is not really required on QDOSMSQ as a terminating job always has any allocated heap areas returned to the system by the job scheduler routines. Because I'm a lazy typist and in order that I reduce the large amounts of code in the magazine, I'm not writing any code here !

If you wish to carry out the list tidying explicitly for yourself as an exercise, feel free to do so. As a suggestion, start a loop which keep going around the list fetching the NEXT node pointer and deleting that from the list using the routines in this code. Once the node has been unlinked from the list, you may deallocate it's heap area - but don't forget to preserve those registers.

* -----------------------------------------------------------------------
* QDOSMSQ tidies up rather nicely for us on exit - so we don't have to !!
* -----------------------------------------------------------------------
KillList    rts

The folowing code sets up the demo to delete the node that was just 'found' by searching for the node holding data 3. This code is called with the address of the '3' node in A1.L and it simply sets up the following routine which actually scans the list looking to make sure that the node we are deleting exists in the list.

* -----------------------------------------------------------------------
* A demo routine to delete the node whose address is passed in A1.L. Sets
* Z if found & deleted, clears it otherwise.
* -----------------------------------------------------------------------
DeleteNode  lea     rootnode,a0         ; Address of the root node
            bsr.s   DelANode
            rts

This is the node deletion code itself. As described in the article, we must not delete the root node itself - as this isn't allocated on the heap. We must also check that the node is in the list by scanning from start to finish looking for the node in the list which has a NEXT pointer holding the address of the node we want to delete.

We remove a node from the list by copying the soon to be deleted node's NEXT pointer into the NEXT pointer of the node before it, thus bypassing the node we want to delete.

Warning

This code only deletes a node from the linked list. It does not deallocate the memory on the common heap that was allocated to create the node. QDOSMSQ will do this at the end of the demo, but in real life, you would need to cary out this task yourslef - expecially as you may not want a number of deleted heap areas hanging around in memory fragmenting your heap.

* -----------------------------------------------------------------------
* Routine to delete a node whose address is passed in A1.L from the list
* whose address is passed in A0.L. On exit, Z flag will be set if deleted
* or cleared if not.
* -----------------------------------------------------------------------
DelANode    moveq   #oops,d0            ; Assume it's going to fail
            cmpa.l  a1,a0               ; Trying to delete the rootnode ?
            beq.s   DelExit             ; Exit if so.

DelLoop     cmpi.l  #0,(a0)             ; Finished yet ?
            beq.s   DelExit             ; Exit not found
            cmpa.l  (a0),a1             ; Found the previous node to the one
*                                       ; we want to delete ?
            bne.s   DelNext             ; Not yet, try again

DelFound    move.l  (a1),(a0)           ; Delete the node by setting the NEXT
*                                       ; pointer to the node BEFORE the one to
*                                       ; be deleted to the NEXT pointer of the
*                                       ; node that is being deleted.
            moveq   #0,d0               ; Indicate found and deleted
            bra.s   DelExit             ; Set Z flag on the way out

DelNext     move.l  (a0),a0             ; Get the next node in the list
            bra.s   DelLoop             ; And try again

DelExit     tst.l   d0                  ; Set or clear Z flag
            rts

* =======================================================================
* The DEMO code ends here.
* =======================================================================

And that is all there is to it. The SingleList demo code should be assembled and run in the normal fashion. You'll be able to see that there are indeed 5 nodes in the list (in the BEFORE section at the top of the screen) then under that, the AFTER section shows a missing node with data content 3 - we have deleted it from the list.