SMAL32 (rev 9/03) Tree Traversal Program 16:46:53 Page 1 Wed Sep 27 2006 28 SUBTITLE "traversal routine" 73 SUBTITLE "main program" SMAL32 (rev 9/03) Tree Traversal Program 16:46:53 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:46:53 Page 3 "traversal routine" Wed Sep 27 2006 28 SUBTITLE "traversal routine" 29 ; this version is highly optimized 30 ; the traversal subroutine activation record 31 RETAD = 0 32 R8SV = 4 33 ARSIZE = 8 34 35 ; the traversal subroutine code 36 TRAVERSE: 37 ; expects RA in R1 38 ; expect R2 as stack pointer 39 ; expect R3 as pointer to a node 40 ; allowed to wipe out R3-7 41 ; does not use R9-15 42 ; preserves R8, used locally as parameter 43 44 STORES R1,R2 ; save return addr +000080: F1A2 45 STORE R8,R2,R8SV ; save register 8 +000082: F822 0004 46 ADDI R2,R2,ARSIZE ; push the activation record +000086: F262 0008 47 MOVECC R8,R3 ; save parameter (and test it) +00008A: F8E3 48 49 ; if (node != NULL) { 50 BZS TRAVQT +00008C: 020E 51 52 ; traverse( node->left ); 53 LOAD R3,R8,LEFT ; get node's left field +00008E: F358 0000 54 JSR R1,TRAVERSE ; call +000092: F130 FFEA 55 56 ; print( node->value ); 57 LOAD R3,R8,VALUE ; first parameter is value field +000096: F358 0008 58 LIS R4,2 ; second parameter is field width +00009A: D402 59 LOAD R1,PDSPDEC +00009C: F150 FF78 60 JSRS R1,R1 ; dspdec( node->value, 2 ) +0000A0: F1B1 61 62 ; traverse( node->right ); 63 LOAD R3,R8,RIGHT ; get node's right field +0000A2: F358 0004 64 JSR R1,TRAVERSE ; call +0000A6: F130 FFD6 65 66 ; } 67 TRAVQT: 68 ADDI R2,R2,-ARSIZE ; pop the activation record +0000AA: F262 FFF8 69 LOAD R8,R2,R8SV ; restore register 8 +0000AE: F852 0004 70 LOADS R1,R2 ; restore return addr +0000B2: F1D2 71 JUMPS R1 +0000B4: F0B1 72 SMAL32 (rev 9/03) Tree Traversal Program 16:46:53 Page 4 "main program" Wed Sep 27 2006 73 SUBTITLE "main program" 74 ; the main program starts here! 75 START: LOAD R2,PSTACK ; set up the stack +0000B6: F250 FF76 76 ; --- begin application code 77 LOAD R1,PDSPINI +0000BA: F150 FF46 78 JSRS R1,R1 ; dspini() -- init the display +0000BE: F1B1 79 80 LOAD R3,PROOT +0000C0: F350 FF70 81 JSR R1,TRAVERSE ; traverse( root ) +0000C4: F130 FFB8 82 83 LOAD R1,PEXIT +0000C8: F150 FF34 84 JSRS R1,R1 ; exit() -- terminate the program +0000CC: F1B1 85 86 ALIGN 4 ; --- begin application constants 87 END no errors