1 " ***********************************************************
  2 " *                                                         *
  3 " * Copyright, (C) Honeywell Information Systems Inc., 1982 *
  4 " *                                                         *
  5 " * Copyright (c) 1972 by Massachusetts Institute of        *
  6 " * Technology and Honeywell Information Systems, Inc.      *
  7 " *                                                         *
  8 " ***********************************************************
  9 
 10 "find_key: proc(indx_cb_ptr,(key_ptr),search_code);
 11           name      find_key
 12           segdef    find_key
 13 find_key: epp1      pr0|2,*             pr1<-->indx_cb_ptr
 14           epp1      pr1|0,*             pr1<-->indx_cb
 15           epp2      pr1|file_position_ptr,*  pr2<-->position_frame
 16           epp5      pr2|node_ptr,*      pr5<-->node_block
 17           epp3      pr0|4,*             pr3<-->key_ptr
 18           epp3      pr3|0,*             pr3<-->key
 19           lxl5      pr3|0               x5<-length(key)
 20 
 21 "q=branch(branch_num).if q=0 then return;
 22           eax2      0                   will be set if key found
 23 descent:  ldq       pr2|branch_num      ql<-position_frame.branch_num
 24           qls       1                   ql<-2*branch_num
 25           adq       pr2|branch_num      ql<-3*branch_num
 26           ldq       pr5|0,ql            q<-branch(branch_num)
 27           tnz       get_son             if branch(branch_num)^=0 ==>get_son
 28           stz       pr0|6,*             clear garbage in arg3
 29           stx2      pr0|6,*             set result in arg3
 30           short_return
 31 
 32 "pos_ptr=son_position_ptr;
 33 get_son:  epp2      pr2|son_position_ptr,*  pr2<-son_position_ptr
 34           spri2     pr1|file_position_ptr  pos_ptr<-son_position_ptr
 35 
 36 "node=q;
 37           stq       pr2|node            position_frame.node<-q
 38 
 39 "node_ptr=addr(seg_ptr_array(q.comp_num)->seg_array(q.offset));
 40           eaa       0,qu                au<-q.comp_num,al<-0
 41           als       1                   au<-2*q.comp_num
 42           epp5      pr1|seg_ptr_array_ptr,*au  pr5<-->seg_ptr_array(comp_num)
 43           epp5      pr5|0,*ql           pr5<-->seg_array(q.offset)
 44           spri5     pr2|node_ptr        node_ptr<-->seg_array(q.offset)
 45 
 46 "low=1
 47           eax3      1                   low<-1
 48 
 49 "high=last_branch_num-1;
 50           ldq       pr5|last_branch_num ql<-last_branch_num
 51           sbq       1,dl                ql<-last_branch_num-1
 52           qls       18                  qu<-last_branch_num, ql<-0
 53           epp1      pr0|6,*             pr1<-->arg3
 54           stq       pr1|0               high<-last_branch_num-1
 55           epp2      pr0|4,*             pr2<-->arg2
 56 
 57 "search:  i=(low+high)/2  ;
 58 search:   eaq       0,3                 qu<-low
 59           adq       pr1|0               qu<-(low+high)
 60           qrl       1                   i<-(low+high)/2
 61           eax4      0,qu                x4<-(low+high)/2
 62           stx4      pr2|0               arg2<-(low+high)/2
 63           adx4      pr2|0               x4<-2*i
 64           adx4      pr2|0               x4<-3*i
 65 
 66 "if substr(keys,key_pos(i),key_length(i))<key then low=i+1;
 67           ldx7      pr5|1,4             x7<-key_pos(i)
 68           lxl6      pr5|1,4             x6<-key_length(i)
 69           cmpc      (pr,rl,x7),(pr,rl),fill(040)  substr::key
 70           desc9a    pr5|-1(3),x6        addr(keys(0)),key_length(i)
 71           desc9a    pr3|1,x5            addr(key),length(key)
 72           trc       not_low             if substr>=key ==>not_low
 73           eax3      1,qu                low=i+1
 74           tra       continue            ==>continue
 75 
 76 "else if substr=key then search_code=1;
 77 not_low:  tnz       unequal             if substr>key ==>unequal
 78           eax2      1                   will be copied into arg
 79 
 80 "high=i-1;
 81 unequal:  eaq       -1,qu               qu<-i-1
 82           stq       pr1|0               high<-i-1
 83 
 84 "if low<=high then go to search;
 85 continue: cmpx3     pr1|0               low::high
 86           tmoz      search              if high>=low ==>search
 87 
 88 "branch_num=low. go to descent;
 89 done:     epp1      pr0|2,*             pr1<-->indx_cb_ptr
 90           epp1      pr1|0,*             pr1<-->indx_cb
 91           epp2      pr1|file_position_ptr,*  pr2<-->position_frame
 92           sxl3      pr2|branch_num      branch_num<-low
 93           tra       descent             descend to leaf
 94 
 95 
 96           entry     last
 97 last:
 98           epp1      pr0|2,*             pr1<-->indx_cb_ptr
 99           epp1      pr1|0,*             pr1<-->indx_cb
100           epp2      pr1|file_position_ptr,*  pr2<-->position_frame
101           epp5      pr2|node_ptr,*      pr5<-->node_block
102           epp3      pr0|4,*             pr3<-->key_ptr
103           epp3      pr3|0,*             pr3<-->key
104           lxl5      pr3|0               x5<-length(key)
105 
106 "q=branch(branch_num).if q=0 then return;
107           eax2      0                   will be set if key found
108 ldescent: ldq       pr2|branch_num      ql<-position_frame.branch_num
109           qls       1                   ql<-2*branch_num
110           adq       pr2|branch_num      ql<-3*branch_num
111           ldq       pr5|0,ql            q<-branch(branch_num)
112           tnz       lget_son            if branch(branch_num)^=0 ==>lget_son
113           stz       pr0|6,*             clear garbage in arg3
114           stx2      pr0|6,*             set result in arg3
115           short_return
116 
117 "pos_ptr=son_position_ptr;
118 lget_son: epp2      pr2|son_position_ptr,*  pr2<-son_position_ptr
119           spri2     pr1|file_position_ptr  pos_ptr<-son_position_ptr
120 
121 "node=q;
122           stq       pr2|node            position_frame.node<-q
123 
124 "node_ptr=addr(seg_ptr_array(q.comp_num)->seg_array(q.offset));
125           eaa       0,qu                au<-q.comp_num,al<-0
126           als       1                   au<-2*q.comp_num
127           epp5      pr1|seg_ptr_array_ptr,*au  pr5<-->seg_ptr_array(comp_num)
128           epp5      pr5|0,*ql           pr5<-->seg_array(q.offset)
129           spri5     pr2|node_ptr        node_ptr<-->seg_array(q.offset)
130 
131 "low=1
132           eax3      1                   low<-1
133 
134 "high=last_branch_num-1;
135           ldq       pr5|last_branch_num ql<-last_branch_num
136           sbq       1,dl                ql<-last_branch_num-1
137           qls       18                  qu<-last_branch_num, ql<-0
138           epp1      pr0|6,*             pr1<-->arg3
139           stq       pr1|0               high<-last_branch_num-1
140           epp2      pr0|4,*             pr2<-->arg2
141 
142 "lsearch: i=(low+high)/2  ;
143 lsearch:  eaq       0,3                 qu<-low
144           adq       pr1|0               qu<-(low+high)
145           qrl       1                   i<-(low+high)/2
146           eax4      0,qu                x4<-(low+high)/2
147           stx4      pr2|0               arg2<-(low+high)/2
148           adx4      pr2|0               x4<-2*i
149           adx4      pr2|0               x4<-3*i
150 
151 "if substr(keys,key_pos(i),key_length(i))<key then low=i+1;
152           ldx7      pr5|1,4             x7<-key_pos(i)
153           lxl6      pr5|1,4             x6<-key_length(i)
154           cmpc      (pr,rl,x7),(pr,rl),fill(040)  substr::key
155           desc9a    pr5|-1(3),x6        addr(keys(0)),key_length(i)
156           desc9a    pr3|1,x5            addr(key),length(key)
157           trc       lnot_low            if substr>=key ==>lnot_low
158 low:      eax3      1,qu                low=i+1
159           tra       lcontinue           ==>lcontinue
160 
161 "else if substr=key then do search_code=1 low=i+1 end;
162 lnot_low: tnz       lunequal            if substr>key ==>unequal
163           eax2      1                   will be copied into arg
164           tra       low                 set low=i+1
165 
166 "high=i-1;
167 lunequal: eaq       -1,qu               qu<-i-1
168           stq       pr1|0               high<-i-1
169 
170 "if low<=high then go to lsearch;
171 lcontinue:          cmpx3     pr1|0               low::high
172           tmoz      lsearch             if high>=low ==>lsearch
173 
174 "branch_num=low. go to ldescent;
175 ldone:    epp1      pr0|2,*             pr1<-->indx_cb_ptr
176           epp1      pr1|0,*             pr1<-->indx_cb
177           epp2      pr1|file_position_ptr,*  pr2<-->position_frame
178           sxl3      pr2|branch_num      branch_num<-low
179           tra       ldescent            descend to leaf
180 
181 
182 
183 
184 
185 "declarations:
186           equ       file_position_ptr,22  in indx_cb
187           equ       node_ptr,4          in position_frame
188           equ       branch_num,7        in position_frame
189           equ       son_position_ptr,2  in position_frame
190           equ       node,6              in position_frame
191           equ       seg_ptr_array_ptr,8 in indx_cb
192           equ       last_branch_num,0   in node_block
193 
194 "this routine depends upon having branch_and_descrip_size=3
195 
196           end