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 :
NEXT(Root) copied to NEXT(NewNode)
Root address copied to PRIOR(NewNode)
NewNode address copied to NEXT(Root)
If this is not the very first node in the list then :
Get address of NEXT(NewNode)
NewNode address copied to PRIOR(NextNode).
* ----------------------------------------------------------------------- * 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.
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.