2. How Does The Code Work?

Much of the demo code is identical to last time, so I'll save even space and paper by only showing you routines that are changed or new additions.

As with the SinglList demo, 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. Each node is linked to the one after it and to the one before it.

The list contents are then printed on the screen showing the node address, the prior pointer, 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. Sounds very familiar doesn't it ?

I've had to trim the informational part of the screen output for each node to accomodate the extra address in the PRIOR pointer and to make sure that it all fits on one screen line.

As with the demo code for singly linked lists, I'm not physically deleting the allocated heap areas used for each node. This reduces the amount of code that appears in the magazine and reduces the need to chop down a few more trees. However, bear in mind that if you create programs which don't delete the heap areas when a node is deleted, that your memory usage will remain high thorought the run of the program.

In my case, this is a small demo and QDOSMSQ does the tidying up for me at the end of the demo.

The first part of the code which has changed is the definition of the root node. In the single linked list, this was a single long word initialised to zero. In this demo we have a pair of long words initialised to zero. To make life easier, we also define a number of equates for use throughout the remainder of the code.

The root node must be initialised to zero in both its NEXT and PRIOR areas 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. The PRIOR pointer will always be zero because there is never a previous node to the root.

* -----------------------------------------------------------------------
* 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,0                  ; This is our root node with two pointers.

NodeSize   equ     12                   ; Length in bytes of each node in the list
Next       equ     0                    ; Offset to NEXT pointer in a node
Prior      equ     4                    ; Offset to PRIOR pointer in a node
NData      equ     8                    ; Offset to the data portion of a node

The code in BuildList has been changed slightly too. In the single list version, the offsets were hard coded as numbers. This isn't very clever - if you change the offsets at any future point, you have to find all the places where the numbers are hard coded. In the new version, I use equates instead of hard coded values. This way, if I change my node structure, I only have to change the equates once.

* -----------------------------------------------------------------------
* 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   #NodeSize,d1         ; Each node is 12 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,NData(a1)         ; Store data value - which is just our counter
           bsr.s   AddNode              ; Add to list
           dbra    d7,BuildLoop         ; Do the rest
           rts                          ; Done

AddNode has been changed to cater for the doubly linked list by initialising the NEXT and PRIOR pointers in the new nmode and in the root node, then checking if there was already any nodes in the list. If there were any nodes, the previous 'first' nmode in the list ( ie, the most recent one aded) needs to have its PRIOR pointer set to be our brand new node. This is done by loading A0 with the new node's NEXT pointer and testing that for zero, if the new node has no NEXT address, it can only be the very first node in the list.

We initialise as follows :

If this is not the very first node in the list then :

* -----------------------------------------------------------------------
* AddNode - Adds a new node to a list. See text for details.
*
* Entry : A0.L = root node address, A1.L = New node address.
* Exit  :Preserves all registers, no error codes 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  a0,Prior(a1)         ; Set the PRIOR node for this new node
           move.l  a1,(a0)              ; Store address of new node in root's NEXT area
           cmpa.l  #0,(a1)              ; Nothing to do if this is the very first node
           beq.s   AddExit              ; Exit with Z set = First node added to list
           move.l  a0,-(a7)             ; Preserve working register (root pointer)
           move.l  (a1),a0              ; A0 = address of original first node in list
           move.l  a1,prior(a0)         ; Store address of new first node in PRIOR pointer
           move.l  (a7)+,a0             ; Restore working register (root pointer)
AddExit    rts

The ShowNode code is the next part that has changed. It has had a couple of lines added to call a new routine - ShowPrior - which, as its name suggests, displays the address of the PRIOR pointer for the node being displayed on screen.

Warning

The line 'BSR.S ShowNext' must also be changed to remove the '.S' from the BSR instruction. We've slipped out of range of a short jump now, so you'll get an error message 'Number Too Big' if you don't.

* -----------------------------------------------------------------------
* 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    ShowNext             ; Print NEXT pointer
            move.l Prior(a5),d4         ; The PRIOR pointer
            bsr.s  ShowPrior            ; Print PRIOR pointer
            move.l NData(a5),d4         ; The node data
            bsr    ShowData             ; Print the data
            rts

In addition, I've abbreviated the message printed by ShowAddr to the following :

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

The following short routine should be added just above ShowNext in the original code. It is called by ShowNode to display the address in a node's PRIOR pointer.

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

MsgPrior   dc.w    PriorEnd-MsgPrior-2
           dc.b    '  PRIOR : '
PriorEnd   equ     *

The code in the ShowNext and ShowData routines hasn't changed, but the messages they display have. I needed to shorten the text to get everything on screen in one line per node. Please make the following changes :

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


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

The code in DelANode has been reduced quite dramatically to the following. As before we don't allow deletion of the root node itself and exit quietly if any attempt is made to do so.

Next we check to ensure that we actually have a list to delete from. If the root node's NEXT pointer is still zero, we have no nodes in the list and again, we exit quietly. In both these exit situations, we clear the Z flag to indicate a node not deleted error.

Deleting the node from the list (but, as before, not from memory) is actually quite simple. As A1 points to the node to be deleted we can find the node before it from the PRIOR(a1) address, and the node after it by the NEXT(A1) address. All we do to delete the node from the list is set the prior node's NEXT address to the current value in the deleted node's NEXT address and then set the next node's PRIOR address to the PRIOR address of the deleted node.

However, if we are deleteing the very last node in the list, we must not attempt to change the (non-existent) next node's pointers as we may well end up writing to random locations in memory. In the last node, the NEXT pointer is always zero.

* -----------------------------------------------------------------------
* 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.
* Trashes A0 and D0 on exit.
* -----------------------------------------------------------------------
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.

DelList     cmpi.l  #0,(a0)             ; If this is true, we have an empty list !
            beq.s   DelExit             ; Exit not found - we have an empty list.
            move.l  Prior(a1),a0        ; A0 points at the node before the 'deleted' one
            move.l  (a1),(a0)           ; Make the prior node point to the deleted node's
*                                       ; NEXT node, thus deleting the node from the NEXT
*                                       ; chain through the list.
            cmpi.l  #0,(a1)             ; Deleting final node in list ?
            beq.s   DelDone             ; Yes, nothing more to do.
            move.l  (a1),a0             ; A0 now points after the 'deleted' node.
            move.l  Prior(a1),Prior(a0) ; Make the next node point to the deleted node's
*                                       ; PRIOR node, thus deleting the node from the
*                                       ; PRIOR chain through the list.
DelDone     moveq   #0,d0               ; Indicate a node was deleted successfully

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

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

And that is all the changes you have to make. The DoubleList 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.