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