| Programming with Ophis | ||
|---|---|---|
| <<< Previous | Structured Programming | Next >>> |
To demonstrate these techniques, we will now produce code to perform insertion sort on a linked list. We'll start by defining our data structure, then defining the routines we want to write, then producing actual code for those routines. A downloadable version that will run unmodified on a Commodore 64 closes the chapter.
We don't really want to have to deal with pointers if we can possibly avoid it, but it's hard to do a linked list without them. Instead of pointers, we will use cursors: small integers that represent the index into the array of values. This lets us use the many-small-byte-arrays technique for our data. Furthermore, our random data that we're sorting never has to move, so we may declare it as a constant and only bother with changing the values of head and the next arrays. The data record definition looks like this:
head : byte;
data : const int[16] = [838, 618, 205, 984, 724, 301, 249, 946,
925, 43, 114, 697, 985, 633, 312, 86];
next : byte[16]; |
Exactly how this gets represented will vary from assembler to assembler. Ophis does it like this:
.data
.space head 1
.space next 16
.text
lb: .byte <$838,<$618,<$205,<$984,<$724,<$301,<$249,<$946
.byte <$925,<$043,<$114,<$697,<$985,<$633,<$312,<$086
hb: .byte >$838,>$618,>$205,>$984,>$724,>$301,>$249,>$946
.byte >$925,>$043,>$114,>$697,>$985,>$633,>$312,>$086 |
To do an insertion sort, we clear the list by setting the 'head' value to -1, and then insert each element into the list one at a time, placing each element in its proper order in the list. We can consider the lb/hb structure alone as an array of 16 integers, and just insert each one into the list one at a time.
procedure insertion_sort
head := -1;
for i := 0 to 15 do
insert_elt i
end
end |
This translates pretty directly. We'll have insert_elt take its argument in the X register, and loop with that. However, given that insert_elt is going to be a complex procedure, we'll save the value first. The assembler code becomes:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; insertion'sort: Sorts the list defined by head, next, hb, lb.
; Arguments: None.
; Modifies: All registers destroyed, head and next array sorted.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
insertion'sort:
lda #$FF ; Clear list by storing the terminator in 'head'
sta head
ldx #$0 ; Loop through the lb/hb array, adding each
insertion'sort'loop: ; element one at a time
txa
pha
jsr insert_elt
pla
tax
inx
cpx #$10
bne insertion'sort'loop
rts |
The pseudocode for inserting an element is a bit more complicated. If the list is empty, or the value we're inserting goes at the front, then we have to update the value of head. Otherwise, we can iterate through the list until we find the element that our value fits in after (so, the first element whose successor is larger than our value). Then we update the next pointers directly and exit.
procedure insert_elt i
begin
if head = -1 then begin
head := i;
next[i] := -1;
return;
end;
val := data[i];
if val < data[i] then begin
next[i] := head;
head := i;
return;
end;
current := head;
while (next[current] <> -1 and val < data[next[current]]) do
current := next[current];
end;
next[i] := next[current];
next[current] := i;
end; |
This produces the following rather hefty chunk of code:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; insert_elt: Insert an element into the linked list. Maintains the
; list in sorted, ascending order. Used by
; insertion'sort.
; Arguments: X register holds the index of the element to add.
; Modifies: All registers destroyed; head and next arrays updated
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.data
.space lbtoinsert 1
.space hbtoinsert 1
.space indextoinsert 1
.text
insert_elt:
ldy head ; If the list is empty, make
cpy #$FF ; head point at it, and return.
bne insert_elt'list'not'empty
stx head
tya
sta next,x
rts
insert_elt'list'not'empty:
lda lb,x ; Cache the data we're inserting
sta lbtoinsert
lda hb,x
sta hbtoinsert
stx indextoinsert
ldy head ; Compare the first value with
sec ; the data. If the data must
lda lb,y ; be inserted at the front...
sbc lbtoinsert
lda hb,y
sbc hbtoinsert
bmi insert_elt'not'smallest
tya ; Set its next pointer to the
sta next,x ; old head, update the head
stx head ; pointer, and return.
rts
insert_elt'not'smallest:
ldx head
insert_elt'loop: ; At this point, we know that
lda next,x ; argument > data[X].
tay
cpy #$FF ; if next[X] = #$FF, insert arg at end.
beq insert_elt'insert'after'current
lda lb,y ; Otherwise, compare arg to
sec ; data[next[X]]. If we insert
sbc lbtoinsert ; before that...
lda hb,y
sbc hbtoinsert
bmi insert_elt'goto'next
insert_elt'insert'after'current: ; Fix up all the next links
tya
ldy indextoinsert
sta next,y
tya
sta next,x
rts ; and return.
insert_elt'goto'next: ; Otherwise, let X = next[X]
tya ; and go looping again.
tax
jmp insert_elt'loop |
The full application, which deals with interfacing with CBM BASIC and handles console I/O and such, is in structuredemo.oph.
| <<< Previous | Home | Next >>> |
| Data structures | Up | Pointers and Indirection |