binary-tree.tal (1846B)
1 ( 2 3 binary tree node layout: 4 5 +--+--+ 6 | ' | incoming-ptr* 7 +--+--+ key: null optional 8 v left right terminated binary 9 | ptr ptr string data 10 \ +--+--+--+--+---------+--+----- - - 11 ---> | ' | ' | U x n .00| 12 +--+--+--+--+---------+--+----- - - 13 14 All of the pointers (ptr) are shorts that have the value of the memory 15 location of the next node, or 0000 to mean that pointer is empty. The very 16 simplest tree is one where the incoming-ptr* is empty: 17 18 +--+--+ 19 |00'00| incoming-ptr* 20 +--+--+ 21 22 traverse-tree does two jobs at once, depending on whether the search-key is 23 found: 24 25 * if the search-key exists in the tree, return a pointer to the binary data 26 that follows that node's key string; 27 28 * if the search-key is not present in the key, return the incoming-ptr* that 29 should be written when adding this node yourself. 30 31 ) 32 33 @traverse-tree ( incoming-ptr* search-key* -- binary-ptr* 00 if key found 34 OR node-incoming-ptr* 01 if key not found ) 35 STH2 36 &loop ( incoming-ptr* / search-key* ) 37 LDA2k ORA ,&valid-node JCN 38 POP2r #01 JMP2r 39 40 &valid-node ( incoming-ptr* / search-key* ) 41 LDA2 ( node* / search-key* ) 42 DUP2 #0004 ADD2 ( node* node-key* / search-key* ) 43 STH2kr ( node* node-key* search-key* / search-key* ) 44 ,strcmp JSR ( node* node-end* search-end* order nomatch / search-key* ) 45 ,&nomatch JCN ( node* node-end* search-end* order / search-key* ) 46 POP POP2 ( node* node-end* / search-key* ) 47 INC2 NIP2 ( binary-ptr* / search-key* ) 48 POP2r #00 ( binary-ptr* 00 ) 49 JMP2r 50 51 &nomatch ( node* node-end* search-end* order / search-key* ) 52 #80 AND #06 SFT #00 SWP STH2 ( node* node-end* search-end* / search-key* node-offset^ ) 53 POP2 POP2 ( node* / search-key* node-offset^ ) 54 STH2r ADD2 ( incoming-ptr* / search-key* ) 55 ,&loop JMP 56