annotate lab4/test/ptr.p @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
rev   line source
mike@0 1 (* Pointer-linked trees *)
mike@0 2
mike@0 3 type
mike@0 4 tree = pointer to node;
mike@0 5 node = record left, right: tree end;
mike@0 6
mike@0 7 proc build(n: integer): tree;
mike@0 8 var t: tree;
mike@0 9 begin
mike@0 10 if n <= 1 then
mike@0 11 return nil
mike@0 12 else
mike@0 13 new(t);
mike@0 14 t^.left := build(n-2);
mike@0 15 t^.right := build(n-1);
mike@0 16 return t
mike@0 17 end
mike@0 18 end;
mike@0 19
mike@0 20 proc print(t: tree);
mike@0 21 var tt: tree;
mike@0 22 begin
mike@0 23 tt := t;
mike@0 24 if tt = nil then
mike@0 25 print_char('.')
mike@0 26 else
mike@0 27 print_char('(');
mike@0 28 print(tt^.left);
mike@0 29 print(tt^.right);
mike@0 30 print_char(')')
mike@0 31 end
mike@0 32 end;
mike@0 33
mike@0 34 proc count(t: tree): integer;
mike@0 35 var tt: tree;
mike@0 36 begin
mike@0 37 tt := t;
mike@0 38 if tt = nil then
mike@0 39 return 1
mike@0 40 else
mike@0 41 return count(tt^.left) + count(tt^.right)
mike@0 42 end
mike@0 43 end;
mike@0 44
mike@0 45 var n: integer; p: tree;
mike@0 46
mike@0 47 begin
mike@0 48 for n := 0 to 7 do
mike@0 49 p := build(n);
mike@0 50 print_num(count(p)); print_char(' ');
mike@0 51 print(p); newline()
mike@0 52 end
mike@0 53 end.
mike@0 54
mike@0 55 (*<<
mike@0 56 1 .
mike@0 57 1 .
mike@0 58 2 (..)
mike@0 59 3 (.(..))
mike@0 60 5 ((..)(.(..)))
mike@0 61 8 ((.(..))((..)(.(..))))
mike@0 62 13 (((..)(.(..)))((.(..))((..)(.(..)))))
mike@0 63 21 (((.(..))((..)(.(..))))(((..)(.(..)))((.(..))((..)(.(..))))))
mike@0 64 >>*)
mike@0 65
mike@0 66 (*[[
mike@0 67 @ picoPascal compiler output
mike@0 68 .include "fixup.s"
mike@0 69 .global pmain
mike@0 70
mike@0 71 @ proc build(n: integer): tree;
mike@0 72 .text
mike@0 73 _build:
mike@0 74 mov ip, sp
mike@0 75 stmfd sp!, {r0-r1}
mike@0 76 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 77 mov fp, sp
mike@0 78 @ if n <= 1 then
mike@0 79 ldr r0, [fp, #40]
mike@0 80 cmp r0, #1
mike@0 81 bgt .L3
mike@0 82 @ return nil
mike@0 83 mov r0, #0
mike@0 84 b .L1
mike@0 85 .L3:
mike@0 86 @ new(t);
mike@0 87 mov r0, #8
mike@0 88 bl new
mike@0 89 mov r4, r0
mike@0 90 @ t^.left := build(n-2);
mike@0 91 ldr r0, [fp, #40]
mike@0 92 sub r0, r0, #2
mike@0 93 bl _build
mike@0 94 str r0, [r4]
mike@0 95 @ t^.right := build(n-1);
mike@0 96 ldr r0, [fp, #40]
mike@0 97 sub r0, r0, #1
mike@0 98 bl _build
mike@0 99 str r0, [r4, #4]
mike@0 100 @ return t
mike@0 101 mov r0, r4
mike@0 102 .L1:
mike@0 103 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 104 .ltorg
mike@0 105
mike@0 106 @ proc print(t: tree);
mike@0 107 _print:
mike@0 108 mov ip, sp
mike@0 109 stmfd sp!, {r0-r1}
mike@0 110 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 111 mov fp, sp
mike@0 112 @ tt := t;
mike@0 113 ldr r4, [fp, #40]
mike@0 114 @ if tt = nil then
mike@0 115 cmp r4, #0
mike@0 116 bne .L7
mike@0 117 @ print_char('.')
mike@0 118 mov r0, #46
mike@0 119 bl print_char
mike@0 120 b .L5
mike@0 121 .L7:
mike@0 122 @ print_char('(');
mike@0 123 mov r0, #40
mike@0 124 bl print_char
mike@0 125 @ print(tt^.left);
mike@0 126 ldr r0, [r4]
mike@0 127 bl _print
mike@0 128 @ print(tt^.right);
mike@0 129 ldr r0, [r4, #4]
mike@0 130 bl _print
mike@0 131 @ print_char(')')
mike@0 132 mov r0, #41
mike@0 133 bl print_char
mike@0 134 .L5:
mike@0 135 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 136 .ltorg
mike@0 137
mike@0 138 @ proc count(t: tree): integer;
mike@0 139 _count:
mike@0 140 mov ip, sp
mike@0 141 stmfd sp!, {r0-r1}
mike@0 142 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 143 mov fp, sp
mike@0 144 @ tt := t;
mike@0 145 ldr r4, [fp, #40]
mike@0 146 @ if tt = nil then
mike@0 147 cmp r4, #0
mike@0 148 bne .L11
mike@0 149 @ return 1
mike@0 150 mov r0, #1
mike@0 151 b .L9
mike@0 152 .L11:
mike@0 153 @ return count(tt^.left) + count(tt^.right)
mike@0 154 ldr r0, [r4]
mike@0 155 bl _count
mike@0 156 mov r5, r0
mike@0 157 ldr r0, [r4, #4]
mike@0 158 bl _count
mike@0 159 add r0, r5, r0
mike@0 160 .L9:
mike@0 161 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 162 .ltorg
mike@0 163
mike@0 164 pmain:
mike@0 165 mov ip, sp
mike@0 166 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 167 mov fp, sp
mike@0 168 @ for n := 0 to 7 do
mike@0 169 mov r0, #0
mike@0 170 set r1, _n
mike@0 171 str r0, [r1]
mike@0 172 mov r4, #7
mike@0 173 .L14:
mike@0 174 set r0, _n
mike@0 175 ldr r5, [r0]
mike@0 176 cmp r5, r4
mike@0 177 bgt .L13
mike@0 178 @ p := build(n);
mike@0 179 mov r0, r5
mike@0 180 bl _build
mike@0 181 set r1, _p
mike@0 182 str r0, [r1]
mike@0 183 @ print_num(count(p)); print_char(' ');
mike@0 184 bl _count
mike@0 185 bl print_num
mike@0 186 mov r0, #32
mike@0 187 bl print_char
mike@0 188 @ print(p); newline()
mike@0 189 set r0, _p
mike@0 190 ldr r0, [r0]
mike@0 191 bl _print
mike@0 192 bl newline
mike@0 193 set r5, _n
mike@0 194 ldr r0, [r5]
mike@0 195 add r0, r0, #1
mike@0 196 str r0, [r5]
mike@0 197 b .L14
mike@0 198 .L13:
mike@0 199 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 200 .ltorg
mike@0 201
mike@0 202 .comm _n, 4, 4
mike@0 203 .comm _p, 4, 4
mike@0 204 @ End
mike@0 205 ]]*)