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