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
19static int *coord = 0;
20int hh[50];
21extern int *hfreq, hfrflg;
22extern int prfreqs;
23union ptr {
24	unsigned *a;
25	long *b;
26};
27
28extern int hash();
29extern void shell();
30extern void *zalloc();
31
32static long getl(FILE *);
33static int hcomp(int, int);
34static void hexch(int, int);
35
36int
37doquery(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
294static long
295getl(FILE *fb)
296{
297	return (getw(fb));
298}
299
300static int
301hcomp(int n1, int n2)
302{
303	return (hfreq[hh[n1]] <= hfreq[hh[n2]]);
304}
305
306static void
307hexch(int n1, int n2)
308{
309	int t;
310	t = hh[n1];
311	hh[n1] = hh[n2];
312	hh[n2] = t;
313}
314