1 /* $MirOS: src/usr.bin/oldroff/hunt/hunt2.c,v 1.3 2008/11/08 23:04:30 tg Exp $ */
2
3 /*-
4 * Copyright (c) 1979, 1980, 1981, 1986, 1988, 1990, 1991, 1992
5 * The Regents of the University of California.
6 * Copyright (C) Caldera International Inc. 2001-2002.
7 * Copyright (c) 2003, 2004, 2005
8 * Thorsten "mirabilos" Glaser <tg@mirbsd.org>
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms,
12 * with or without modification, are permitted provided
13 * that the following conditions are met:
14 *
15 * Redistributions of source code and documentation must retain
16 * the above copyright notice, this list of conditions and the
17 * following disclaimer. Redistributions in binary form must
18 * reproduce the above copyright notice, this list of conditions
19 * and the following disclaimer in the documentation and/or other
20 * materials provided with the distribution.
21 *
22 * All advertising materials mentioning features or use of this
23 * software must display the following acknowledgement:
24 * This product includes software developed or owned by
25 * Caldera International, Inc.
26 *
27 * Neither the name of Caldera International, Inc. nor the names
28 * of other contributors may be used to endorse or promote products
29 * derived from this software without specific prior written permission.
30 *
31 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
32 * INTERNATIONAL, INC. AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
33 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35 * ARE DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE
36 * LIABLE FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR
37 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
38 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
39 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
41 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
42 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43 */
44
45 #ifndef lint
46 static char sccsid[] = "@(#)hunt2.c 4.6 (Berkeley) 4/18/91";
47 #endif /* not lint */
48
49 #include "refer..c"
50
51 static int *coord = 0;
52 int hh[50];
53 extern int *hfreq, hfrflg, hcomp(), hexch();
54 extern int prfreqs;
55
doquery(hpt,nhash,fb,nitem,qitem,master)56 doquery(hpt, nhash, fb, nitem, qitem, master)
57 long *hpt;
58 FILE *fb;
59 char *qitem[];
60 unsigned *master;
61 {
62 union ptr {
63 unsigned *a;
64 long *b;
65 } umaster;
66 long k;
67 union ptr prevdrop;
68 int nf = 0, best = 0, nterm = 0, i, g, j;
69 int *prevcoord;
70 long lp;
71 extern int lmaster, colevel, reached;
72 long getl();
73 extern int iflong;
74
75 # if D1
76 fprintf(stderr, "entering doquery nitem %d\n",nitem);
77 fprintf(stderr, "first few hashes are %ld %ld %ld %ld %ld\n", hpt[0],hpt[1],hpt[2],hpt[3],hpt[4]);
78 fprintf(stderr, "and frequencies are %d %d %d %d %d\n",hfreq[0],hfreq[1],hfreq[2],hfreq[3],hfreq[4]);
79 # endif
80 if (iflong)
81 umaster.b = (long *) master;
82 else
83 umaster.a = master;
84 assert (lmaster>0);
85 if (coord==0)
86 coord = (int *) zalloc(lmaster, sizeof(lmaster));
87 if (colevel>0)
88 {
89 if (iflong)
90 prevdrop.b = (long *) zalloc(lmaster, sizeof(long));
91 else
92 prevdrop.a = (unsigned *) zalloc(lmaster, sizeof(int));
93 prevcoord = (int *) zalloc(lmaster, sizeof(lmaster));
94 }
95 else
96 {
97 prevdrop.a=umaster.a;
98 prevcoord=coord;
99 }
100 # if D1
101 fprintf(stderr, "nitem %d\n",nitem);
102 # endif
103 for(i=0; i<nitem; i++)
104 {
105 hh[i] = hash(qitem[i])%nhash;
106 # if D1
107 fprintf(stderr,"query wd X%sX has hash %d\n", qitem[i], hh[i]);
108 # endif
109 }
110 # if D1
111 fprintf(stderr, "past that loop nhash %d hpt is %lo\n", nhash, hpt);
112 # endif
113 if (prfreqs)
114 for(i=0; i<nitem; i++)
115 fprintf(stderr,"item %s hash %d hfreq %d\n",qitem[i], hh[i], hfreq[hh[i]]);
116 /* if possible, sort query into decreasing frequency of hashes */
117 if (hfrflg)
118 shell (nitem, hcomp, hexch);
119 # if D1
120 for(i=0; i<nitem; i++)
121 fprintf(stderr, "item hash %d frq %d\n", hh[i], hfreq[hh[i]]);
122 # endif
123 lp = hpt [hh[0]];
124 # if D1
125 fprintf(stderr,"first item hash %d lp %ld 0%lo\n", hh[0],lp,lp);
126 # endif
127 assert (fb!=NULL);
128 assert (fseek(fb, lp, 0) != -1);
129 for(i=0; i<lmaster; i++)
130 {
131 if (iflong)
132 umaster.b[i] = getl(fb);
133 else
134 umaster.a[i] = getw(fb);
135 coord[i]=1;
136 # if D2
137 if (iflong)
138 fprintf(stderr,"umaster has %ld\n",(umaster.b[i]));
139 else
140 fprintf(stderr,"umaster has %d\n",(umaster.a[i]));
141 # endif
142 assert (i<lmaster);
143 if (iflong)
144 {
145 if (umaster.b[i] == -1L) break;
146 }
147 else
148 {
149 if (umaster.a[i] == -1) break;
150 }
151 }
152 nf= i;
153 for(nterm=1; nterm<nitem; nterm++)
154 {
155 # ifdef D1
156 fprintf(stderr, "item %d, hash %d\n", nterm, hh[nterm]);
157 # endif
158 if (colevel>0)
159 {
160 for(j=0; j<nf; j++)
161 {
162 if (iflong)
163 prevdrop.b[j] = umaster.b[j];
164 else
165 prevdrop.a[j] = umaster.a[j];
166 prevcoord[j] = coord[j];
167 }
168 }
169 lp = hpt[hh[nterm]];
170 assert (fseek(fb, lp, 0) != -1);
171 # if D1
172 fprintf(stderr,"item %d hash %d seek to %ld\n",nterm,hh[nterm],lp);
173 # endif
174 g=j=0;
175 while (1)
176 {
177 if (iflong)
178 k = getl(fb);
179 else
180 k = getw(fb);
181 if (k== -1) break;
182 # if D2
183 fprintf(stderr,"next term finds %ld\n",k);
184 # endif
185 # if D3
186 if (iflong)
187 fprintf(stderr, "bfwh j %d nf %d master %ld k %ld\n",j,nf,prevdrop.b[j],(long)(k));
188 else
189 fprintf(stderr, "bfwh j %d nf %d master %ld k %ld\n",j,nf,prevdrop.a[j],(long)(k));
190 # endif
191 while (j<nf && (iflong?prevdrop.b[j]:prevdrop.a[j])<k)
192 {
193 # if D3
194 if (iflong)
195 fprintf(stderr, "j %d nf %d prevdrop %ld prevcoord %d colevel %d nterm %d k %ld\n",
196 j,nf,prevdrop.b[j], prevcoord[j], colevel, nterm, (long)(k));
197 else
198 fprintf(stderr, "j %d nf %d prevdrop %ld prevcoord %d colevel %d nterm %d k %ld\n",
199 j,nf,prevdrop.a[j], prevcoord[j], colevel, nterm, (long)(k));
200 # endif
201 if (prevcoord[j] + colevel <= nterm)
202 j++;
203 else
204 {
205 assert (g<lmaster);
206 if (iflong)
207 umaster.b[g] = prevdrop.b[j];
208 else
209 umaster.a[g] = prevdrop.a[j];
210 coord[g++] = prevcoord[j++];
211 # if D1
212 if (iflong)
213 fprintf(stderr, " not skip g %d doc %d coord %d note %d\n",g,umaster.b[g-1], coord[g-1],umaster.b[j-1]);
214 else
215 fprintf(stderr, " not skip g %d doc %ld coord %d nterm %d\n",g,umaster.a[g-1], coord[g-1],nterm);
216 # endif
217 continue;
218 }
219 }
220 if (colevel==0 && j>=nf) break;
221 if (j<nf && (iflong? prevdrop.b[j]: prevdrop.a[j]) == k)
222 {
223 if (iflong)
224 umaster.b[g]=k;
225 else
226 umaster.a[g]=k;
227 coord[g++] = prevcoord[j++]+1;
228 # if D1
229 if (iflong)
230 fprintf(stderr, " at g %d item %ld coord %d note %ld\n",g,umaster.b[g-1],coord[g-1],umaster.b[j-1]);
231 else
232 fprintf(stderr, " at g %d item %d coord %d note %d\n",g,umaster.a[g-1],coord[g-1],umaster.a[j-1]);
233 # endif
234 }
235 else
236 if (colevel >= nterm)
237 {
238 if (iflong)
239 umaster.b[g]=k;
240 else
241 umaster.a[g]=k;
242 coord[g++] = 1;
243 }
244 }
245 # if D1
246 fprintf(stderr,"now have %d items\n",g);
247 # endif
248 if (colevel>0)
249 for ( ; j<nf; j++)
250 if (prevcoord[j]+colevel > nterm)
251 {
252 assert(g<lmaster);
253 if (iflong)
254 umaster.b[g] = prevdrop.b[j];
255 else
256 umaster.a[g] = prevdrop.a[j];
257 coord[g++] = prevcoord[j];
258 # if D3
259 if(iflong)
260 fprintf(stderr, "copied over %ld coord %d\n",umaster.b[g-1], coord[g-1]);
261 else
262 fprintf(stderr, "copied over %d coord %d\n",umaster.a[g-1], coord[g-1]);
263 # endif
264 }
265 nf = g;
266 }
267 if (colevel>0)
268 {
269 best=0;
270 for(j=0; j<nf; j++)
271 if (coord[j]>best) best = coord[j];
272 # if D1
273 fprintf(stderr, "colevel %d best %d\n", colevel, best);
274 # endif
275 reached = best;
276 for(g=j=0; j<nf; j++)
277 if (coord[j]==best)
278 {
279 if (iflong)
280 umaster.b[g++] = umaster.b[j];
281 else
282 umaster.a[g++] = umaster.a[j];
283 }
284 nf=g;
285 # if D1
286 fprintf(stderr, "yet got %d\n",nf);
287 # endif
288 }
289 # ifdef D1
290 fprintf(stderr, " returning with %d\n",nf);
291 # endif
292 if (colevel)
293 {
294 free(prevdrop, lmaster, iflong?sizeof(long): sizeof(int));
295 free(prevcoord, lmaster, sizeof (lmaster));
296 }
297 # if D3
298 for(g=0;g<nf;g++)
299 if(iflong)
300 fprintf(stderr,":%ld\n",umaster.b[g]);
301 else
302 fprintf(stderr,":%d\n",umaster.a[g]);
303 # endif
304 return(nf);
305 }
306
307 long
getl(fb)308 getl(fb)
309 FILE *fb;
310 {
311 return(getw(fb));
312 }
313
putl(ll,f)314 putl(ll, f)
315 long ll;
316 FILE *f;
317 {
318 putw(ll, f);
319 }
320
hcomp(n1,n2)321 hcomp( n1, n2)
322 {
323 return (hfreq[hh[n1]]<=hfreq[hh[n2]]);
324 }
325
hexch(n1,n2)326 hexch( n1, n2 )
327 {
328 int t;
329 t = hh[n1];
330 hh[n1] = hh[n2];
331 hh[n2] = t;
332 }
333