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 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 268 getl(fb) 269 FILE *fb; 270 { 271 return(getw(fb)); 272 } 273 274 putl(ll, f) 275 long ll; 276 FILE *f; 277 { 278 putw(ll, f); 279 } 280 281 hcomp( n1, n2) 282 { 283 return (hfreq[hh[n1]]<=hfreq[hh[n2]]); 284 } 285 286 hexch( n1, n2 ) 287 { 288 int t; 289 t = hh[n1]; 290 hh[n1] = hh[n2]; 291 hh[n2] = t; 292 } 293