1 /*-
2 * %sccs.include.proprietary.c%
3 */
4
5 #ifndef lint
6 static char sccsid[] = "@(#)hunt2.c 4.6 (Berkeley) 04/18/91";
7 #endif /* not lint */
8
9 #include "refer..c"
10
11 static int *coord = 0;
12 int hh[50];
13 extern int *hfreq, hfrflg, hcomp(), hexch();
14 extern int prfreqs;
15
doquery(hpt,nhash,fb,nitem,qitem,master)16 doquery(hpt, nhash, fb, nitem, qitem, master)
17 long *hpt;
18 FILE *fb;
19 char *qitem[];
20 unsigned *master;
21 {
22 union ptr {
23 unsigned *a;
24 long *b;
25 } umaster;
26 long k;
27 union ptr prevdrop;
28 int nf = 0, best = 0, nterm = 0, i, g, j;
29 int *prevcoord;
30 long lp;
31 extern int lmaster, colevel, reached;
32 long getl();
33 extern int iflong;
34
35 # if D1
36 fprintf(stderr, "entering doquery nitem %d\n",nitem);
37 fprintf(stderr, "first few hashes are %ld %ld %ld %ld %ld\n", hpt[0],hpt[1],hpt[2],hpt[3],hpt[4]);
38 fprintf(stderr, "and frequencies are %d %d %d %d %d\n",hfreq[0],hfreq[1],hfreq[2],hfreq[3],hfreq[4]);
39 # endif
40 if (iflong)
41 umaster.b = (long *) master;
42 else
43 umaster.a = master;
44 _assert (lmaster>0);
45 if (coord==0)
46 coord = (int *) zalloc(lmaster, sizeof(lmaster));
47 if (colevel>0)
48 {
49 if (iflong)
50 prevdrop.b = (long *) zalloc(lmaster, sizeof(long));
51 else
52 prevdrop.a = (unsigned *) zalloc(lmaster, sizeof(int));
53 prevcoord = (int *) zalloc(lmaster, sizeof(lmaster));
54 }
55 else
56 {
57 prevdrop.a=umaster.a;
58 prevcoord=coord;
59 }
60 # if D1
61 fprintf(stderr, "nitem %d\n",nitem);
62 # endif
63 for(i=0; i<nitem; i++)
64 {
65 hh[i] = hash(qitem[i])%nhash;
66 # if D1
67 fprintf(stderr,"query wd X%sX has hash %d\n", qitem[i], hh[i]);
68 # endif
69 }
70 # if D1
71 fprintf(stderr, "past that loop nhash %d hpt is %lo\n", nhash, hpt);
72 # endif
73 if (prfreqs)
74 for(i=0; i<nitem; i++)
75 fprintf(stderr,"item %s hash %d hfreq %d\n",qitem[i], hh[i], hfreq[hh[i]]);
76 /* if possible, sort query into decreasing frequency of hashes */
77 if (hfrflg)
78 shell (nitem, hcomp, hexch);
79 # if D1
80 for(i=0; i<nitem; i++)
81 fprintf(stderr, "item hash %d frq %d\n", hh[i], hfreq[hh[i]]);
82 # endif
83 lp = hpt [hh[0]];
84 # if D1
85 fprintf(stderr,"first item hash %d lp %ld 0%lo\n", hh[0],lp,lp);
86 # endif
87 _assert (fb!=NULL);
88 _assert (fseek(fb, lp, 0) != -1);
89 for(i=0; i<lmaster; i++)
90 {
91 if (iflong)
92 umaster.b[i] = getl(fb);
93 else
94 umaster.a[i] = getw(fb);
95 coord[i]=1;
96 # if D2
97 if (iflong)
98 fprintf(stderr,"umaster has %ld\n",(umaster.b[i]));
99 else
100 fprintf(stderr,"umaster has %d\n",(umaster.a[i]));
101 # endif
102 _assert (i<lmaster);
103 if (iflong)
104 {
105 if (umaster.b[i] == -1L) break;
106 }
107 else
108 {
109 if (umaster.a[i] == -1) break;
110 }
111 }
112 nf= i;
113 for(nterm=1; nterm<nitem; nterm++)
114 {
115 # ifdef D1
116 fprintf(stderr, "item %d, hash %d\n", nterm, hh[nterm]);
117 # endif
118 if (colevel>0)
119 {
120 for(j=0; j<nf; j++)
121 {
122 if (iflong)
123 prevdrop.b[j] = umaster.b[j];
124 else
125 prevdrop.a[j] = umaster.a[j];
126 prevcoord[j] = coord[j];
127 }
128 }
129 lp = hpt[hh[nterm]];
130 _assert (fseek(fb, lp, 0) != -1);
131 # if D1
132 fprintf(stderr,"item %d hash %d seek to %ld\n",nterm,hh[nterm],lp);
133 # endif
134 g=j=0;
135 while (1)
136 {
137 if (iflong)
138 k = getl(fb);
139 else
140 k = getw(fb);
141 if (k== -1) break;
142 # if D2
143 fprintf(stderr,"next term finds %ld\n",k);
144 # endif
145 # if D3
146 if (iflong)
147 fprintf(stderr, "bfwh j %d nf %d master %ld k %ld\n",j,nf,prevdrop.b[j],(long)(k));
148 else
149 fprintf(stderr, "bfwh j %d nf %d master %ld k %ld\n",j,nf,prevdrop.a[j],(long)(k));
150 # endif
151 while (j<nf && (iflong?prevdrop.b[j]:prevdrop.a[j])<k)
152 {
153 # if D3
154 if (iflong)
155 fprintf(stderr, "j %d nf %d prevdrop %ld prevcoord %d colevel %d nterm %d k %ld\n",
156 j,nf,prevdrop.b[j], prevcoord[j], colevel, nterm, (long)(k));
157 else
158 fprintf(stderr, "j %d nf %d prevdrop %ld prevcoord %d colevel %d nterm %d k %ld\n",
159 j,nf,prevdrop.a[j], prevcoord[j], colevel, nterm, (long)(k));
160 # endif
161 if (prevcoord[j] + colevel <= nterm)
162 j++;
163 else
164 {
165 _assert (g<lmaster);
166 if (iflong)
167 umaster.b[g] = prevdrop.b[j];
168 else
169 umaster.a[g] = prevdrop.a[j];
170 coord[g++] = prevcoord[j++];
171 # if D1
172 if (iflong)
173 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]);
174 else
175 fprintf(stderr, " not skip g %d doc %ld coord %d nterm %d\n",g,umaster.a[g-1], coord[g-1],nterm);
176 # endif
177 continue;
178 }
179 }
180 if (colevel==0 && j>=nf) break;
181 if (j<nf && (iflong? prevdrop.b[j]: prevdrop.a[j]) == k)
182 {
183 if (iflong)
184 umaster.b[g]=k;
185 else
186 umaster.a[g]=k;
187 coord[g++] = prevcoord[j++]+1;
188 # if D1
189 if (iflong)
190 fprintf(stderr, " at g %d item %ld coord %d note %ld\n",g,umaster.b[g-1],coord[g-1],umaster.b[j-1]);
191 else
192 fprintf(stderr, " at g %d item %d coord %d note %d\n",g,umaster.a[g-1],coord[g-1],umaster.a[j-1]);
193 # endif
194 }
195 else
196 if (colevel >= nterm)
197 {
198 if (iflong)
199 umaster.b[g]=k;
200 else
201 umaster.a[g]=k;
202 coord[g++] = 1;
203 }
204 }
205 # if D1
206 fprintf(stderr,"now have %d items\n",g);
207 # endif
208 if (colevel>0)
209 for ( ; j<nf; j++)
210 if (prevcoord[j]+colevel > nterm)
211 {
212 _assert(g<lmaster);
213 if (iflong)
214 umaster.b[g] = prevdrop.b[j];
215 else
216 umaster.a[g] = prevdrop.a[j];
217 coord[g++] = prevcoord[j];
218 # if D3
219 if(iflong)
220 fprintf(stderr, "copied over %ld coord %d\n",umaster.b[g-1], coord[g-1]);
221 else
222 fprintf(stderr, "copied over %d coord %d\n",umaster.a[g-1], coord[g-1]);
223 # endif
224 }
225 nf = g;
226 }
227 if (colevel>0)
228 {
229 best=0;
230 for(j=0; j<nf; j++)
231 if (coord[j]>best) best = coord[j];
232 # if D1
233 fprintf(stderr, "colevel %d best %d\n", colevel, best);
234 # endif
235 reached = best;
236 for(g=j=0; j<nf; j++)
237 if (coord[j]==best)
238 {
239 if (iflong)
240 umaster.b[g++] = umaster.b[j];
241 else
242 umaster.a[g++] = umaster.a[j];
243 }
244 nf=g;
245 # if D1
246 fprintf(stderr, "yet got %d\n",nf);
247 # endif
248 }
249 # ifdef D1
250 fprintf(stderr, " returning with %d\n",nf);
251 # endif
252 if (colevel)
253 {
254 free(prevdrop, lmaster, iflong?sizeof(long): sizeof(int));
255 free(prevcoord, lmaster, sizeof (lmaster));
256 }
257 # if D3
258 for(g=0;g<nf;g++)
259 if(iflong)
260 fprintf(stderr,":%ld\n",umaster.b[g]);
261 else
262 fprintf(stderr,":%d\n",umaster.a[g]);
263 # endif
264 return(nf);
265 }
266
267 long
getl(fb)268 getl(fb)
269 FILE *fb;
270 {
271 return(getw(fb));
272 }
273
putl(ll,f)274 putl(ll, f)
275 long ll;
276 FILE *f;
277 {
278 putw(ll, f);
279 }
280
hcomp(n1,n2)281 hcomp( n1, n2)
282 {
283 return (hfreq[hh[n1]]<=hfreq[hh[n2]]);
284 }
285
hexch(n1,n2)286 hexch( n1, n2 )
287 {
288 int t;
289 t = hh[n1];
290 hh[n1] = hh[n2];
291 hh[n2] = t;
292 }
293