SMAL32 (rev 9/03) Tree Traversal Program 16:35:40 Page 1 Wed Sep 27 2006 28 SUBTITLE "traversal routine" 78 SUBTITLE "main program" SMAL32 (rev 9/03) Tree Traversal Program 16:35:40 Page 2 Wed Sep 27 2006 1 TITLE Tree Traversal Program 2 S START 3 USE "hawk.macs" 4 USE "monitor.h" +000000:+00000000 5 +00000000 +00000000 +00000000 +00000000 +00000000 +00000000 +00000000 +00000000 +00000000 +00000000 +00000000 6 COMMON STACK,#1000 +000030:+00000000 7 PSTACK: W STACK 8 9 ; the null pointer 10 NULL = 0 11 12 ; an example tree to traverse +000034:+00000038 13 PROOT: W ROOT 14 +000038:+00000044 15 ROOT: W RLEFT,RRIGHT,4 +00000068 00000004 +000044:+00000050 16 RLEFT: W RLLEFT,RLRIGHT,2 +0000005C 00000002 +000050: 00000000 17 RLLEFT: W NULL,NULL,1 00000000 00000001 +00005C: 00000000 18 RLRIGHT:W NULL,NULL,3 00000000 00000003 +000068: 00000000 19 RRIGHT: W NULL,RRRIGHT,5 +00000074 00000005 +000074: 00000000 20 RRRIGHT:W NULL,NULL,6 00000000 00000006 21 22 ; the tree record structure 23 LEFT = 0 ; pointer to a tree node 24 RIGHT = 4 ; pointer to a tree node 25 VALUE = 8 ; integer 26 TSIZE = 12 ; tree node size 27 SMAL32 (rev 9/03) Tree Traversal Program 16:35:40 Page 3 "traversal routine" Wed Sep 27 2006 28 SUBTITLE "traversal routine" 29 ; the traversal subroutine activation record 30 RETAD = 0 31 NODE = 4 32 ARSIZE = 8 33 34 ; the traversal subroutine code 35 TRAVERSE: 36 ; expects RA in R1 37 ; expect R2 as stack pointer 38 ; expect R3 as pointer to a node 39 ; allowed to wipe out R3-7 40 ; if used, preserves R8-15 41 42 STORE R1,R2,RETAD ; save return addr +000080: F122 0000 43 STORE R3,R2,NODE ; save parameter (node pointer) +000084: F322 0004 44 45 ; if (node != NULL) { 46 LOAD R3,R2,NODE ; restore node pointer +000088: F352 0004 47 TESTR R3 +00008C: F0E3 48 BZS TRAVQT +00008E: 0220 49 50 ; traverse( node->left ); 51 LOAD R3,R2,NODE ; restore node pointer +000090: F352 0004 52 LOAD R3,R3,LEFT ; get left pointer of node +000094: F353 0000 53 ADDI R2,R2,ARSIZE ; push an activation record +000098: F262 0008 54 JSR R1,TRAVERSE ; actual call +00009C: F130 FFE0 55 ADDI R2,R2,-ARSIZE ; pop an activation record +0000A0: F262 FFF8 56 57 ; print( node->value ); 58 LOAD R3,R2,NODE ; restore node pointer +0000A4: F352 0004 59 LOAD R3,R3,VALUE ; first parameter is value field +0000A8: F353 0008 60 LIS R4,2 ; second parameter is field width +0000AC: D402 61 ADDI R2,R2,ARSIZE ; push an activation record +0000AE: F262 0008 62 LOAD R1,PDSPDEC +0000B2: F150 FF62 63 JSRS R1,R1 ; dspdec( node->value, 2 ) +0000B6: F1B1 64 ADDI R2,R2,-ARSIZE ; pop an activation record +0000B8: F262 FFF8 65 66 ; traverse( node->right ); 67 LOAD R3,R2,NODE ; restore node pointer +0000BC: F352 0004 68 LOAD R3,R3,RIGHT ; get right pointer of node +0000C0: F353 0004 69 ADDI R2,R2,ARSIZE ; push an activation record +0000C4: F262 0008 70 JSR R1,TRAVERSE ; actual call +0000C8: F130 FFB4 71 ADDI R2,R2,-ARSIZE ; pop an activation record +0000CC: F262 FFF8 72 73 ; } 74 TRAVQT: 75 LOAD R1,R2,RETAD ; restore return addr +0000D0: F152 0000 76 JUMPS R1 +0000D4: F0B1 77 SMAL32 (rev 9/03) Tree Traversal Program 16:35:40 Page 4 "main program" Wed Sep 27 2006 78 SUBTITLE "main program" 79 ; the main program starts here! 80 START: LOAD R2,PSTACK ; set up the stack +0000D6: F250 FF56 81 ; --- begin application code 82 LOAD R1,PDSPINI +0000DA: F150 FF26 83 JSRS R1,R1 ; dspini() -- init the display +0000DE: F1B1 84 85 LOAD R3,PROOT +0000E0: F350 FF50 86 JSR R1,TRAVERSE ; traverse( root ) +0000E4: F130 FF98 87 88 LOAD R1,PEXIT +0000E8: F150 FF14 89 JSRS R1,R1 ; exit() -- terminate the program +0000EC: F1B1 90 91 ALIGN 4 ; --- begin application constants 92 END no errors