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: procindx_cb_ptrkey_ptrsearch_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<-lengthkey
20
21 "q=branchbranch_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<-branchbranch_num
27 tnz get_son if branchbranch_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=addrseg_ptr_arrayq.comp_num->seg_arrayq.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_arraycomp_num
43 epp5 pr5|0,*ql pr5<-->seg_arrayq.offset
44 spri5 pr2|node_ptr node_ptr<-->seg_arrayq.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 substrkeyskey_posikey_lengthi<key then low=i+1;
67 ldx7 pr5|1,4 x7<-key_posi
68 lxl6 pr5|1,4 x6<-key_lengthi
69 cmpc prrlx7,prrl,fill040 substr::key
70 desc9a pr5|-13,x6 addrkeys0,key_lengthi
71 desc9a pr3|1,x5 addrkey,lengthkey
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<-lengthkey
105
106 "q=branchbranch_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<-branchbranch_num
112 tnz lget_son if branchbranch_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=addrseg_ptr_arrayq.comp_num->seg_arrayq.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_arraycomp_num
128 epp5 pr5|0,*ql pr5<-->seg_arrayq.offset
129 spri5 pr2|node_ptr node_ptr<-->seg_arrayq.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 substrkeyskey_posikey_lengthi<key then low=i+1;
152 ldx7 pr5|1,4 x7<-key_posi
153 lxl6 pr5|1,4 x6<-key_lengthi
154 cmpc prrlx7,prrl,fill040 substr::key
155 desc9a pr5|-13,x6 addrkeys0,key_lengthi
156 desc9a pr3|1,x5 addrkey,lengthkey
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