MC68030 Datasheet, PDF (106/602 Pages) Motorola, Inc – ENHANCED 32-BIT MICROPROCESSOR

Instruction Set Summary
The CAS2 instruction can also be used to correctly maintain a first-in-first-out doubly linked
list. A doubly linked list needs two controlled locations, LIST_PUT and LIST_GET, which
contain pointers to the last element inserted in the list and the next to be removed,
respectively. If the list is empty, both pointers are NULL (0).
The code fragment shown in Figure 3–4 illustrates the insertion of an element in a doubly
linked list. The first two instructions load the effective addresses of LIST_PUT and
LIST_GET into registers A0 and A1, respectively. The next instruction moves the address
of the new element into register D2. Another MOVE instruction moves the address in
LIST_PUT into register D0. At label DILOOP, a TST instruction tests the value in D0, and
the BEQ instruction branches to the MOVE instruction when D0 is equal to zero. Assuming
the list is empty, this MOVE instruction is executed next; it moves the zero in D0 into the
NEXT and LAST pointers of the new element. Then the CAS2 instruction moves the address
of the new element into both LIST_PUT and LIST_GET, assuming that both of these
pointers still contain zero. If not, the BNE instruction branches to the TST instruction at label
DILOOP to try again. This time, the BEQ instruction does not branch, and the following
MOVE instruction moves the address in D0 to the NEXT pointer of the new element. The
CLR instruction clears register D1 to zero, and the MOVE instruction moves the zero into
the LAST pointer of the new element. The LEA instruction loads the address of the LAST
pointer of the most recently inserted element into register A1. Assuming the LIST_PUT
pointer and the pointer in A1 have not been changed, the CAS2 instruction stores the
address of the new element into these pointers.
The code fragment to delete an element from a doubly linked list is similar (see Figure 3–5).
The first two instructions load the effective addresses of pointers LIST_PUT and LIST_GET
into registers A0 and A1, respectively. The MOVE instruction at label DDLOOP moves the
LIST_GET pointer into register D1. The BEQ instruction that follows branches out of the
routine when the pointer is zero. The MOVE instruction moves the LAST pointer of the
element to be deleted into register D2. Assuming this is not the last element in the list, the
Z condition code is not set, and the branch to label DDEMPTY does not occur. The LEA
instruction loads the address of the NEXT pointer of the element at the address in D2 into
register A2. The next instruction, a CLR instruction, clears register D0 to zero. The CAS2
instruction compares the address in D1 to the LIST-GET pointer and to the address in
register A2. If the pointers have not been updated, the CAS2 instruction loads the address
in D2 into the LIST_GET pointer and zero into the address in register A2.
3-28
MC68030 USER’S MANUAL
MOTOROLA