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