1 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 2 /* All Rights Reserved */ 3 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 11 /* 12 * Copyright (c) 1983, 1984 1985, 1986, 1987, 1988, Sun Microsystems, Inc. 13 * All Rights Reserved. 14 */ 15 16 #pragma ident "%Z%%M% %I% %E% SMI" 17 18 #include "refer..c" 19 20 static int *coord = 0; 21 int hh[50]; 22 extern int *hfreq, hfrflg, hcomp(), hexch(); 23 extern int prfreqs; 24 union ptr { 25 unsigned *a; 26 long *b; 27 }; 28 29 doquery(hpt, nhash, fb, nitem, qitem, mptr) 30 long *hpt; 31 FILE *fb; 32 char *qitem[]; 33 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; 41 long getl(); 42 extern int iflong; 43 44 if (iflong) { 45 master.b = (long *) mptr; 46 } 47 else { 48 master.a = mptr; 49 } 50 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 { 61 if (iflong) 62 prevdrop.b = (long *) zalloc(lmaster, sizeof(long)); 63 else 64 prevdrop.a = (unsigned *) zalloc(lmaster, sizeof(int)); 65 prevcoord = (int *) zalloc(lmaster, sizeof(lmaster)); 66 } 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 { 77 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 81 } 82 # if D1 83 fprintf(stderr, "past that loop nhash %d hpt is %lo\n", nhash, hpt); 84 # endif 85 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]]); 88 /* if possible, sort query into decreasing frequency of hashes */ 89 if (hfrflg) 90 shell (nitem, hcomp, hexch); 91 # if D1 92 for(i=0; i<nitem; i++) 93 fprintf(stderr, "item hash %d frq %d\n", hh[i], hfreq[hh[i]]); 94 # endif 95 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 { 103 if (iflong) 104 master.b[i] = getl(fb); 105 else 106 master.a[i] = getw(fb); 107 coord[i]=1; 108 # if D2 109 if (iflong) 110 fprintf(stderr,"master has %ld\n",(master.b[i])); 111 else 112 fprintf(stderr,"master has %d\n",(master.a[i])); 113 # endif 114 assert (i<lmaster); 115 if (iflong) 116 { 117 if (master.b[i] == -1L) break; 118 } 119 else 120 { 121 if (master.a[i] == -1) break; 122 } 123 } 124 nf= i; 125 for(nterm=1; nterm<nitem; nterm++) 126 { 127 # ifdef D1 128 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 { 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]]; 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 { 149 if (iflong) 150 k = getl(fb); 151 else 152 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 158 if (iflong) 159 fprintf(stderr, "bfwh j %d nf %d master %ld k %ld\n",j,nf,prevdrop.b[j],(long)(k)); 160 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 166 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)); 169 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 173 if (prevcoord[j] + colevel <= nterm) 174 j++; 175 else 176 { 177 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++]; 183 # if D1 184 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]); 186 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 189 continue; 190 } 191 } 192 if (colevel==0 && j>=nf) break; 193 if (j<nf && (iflong? prevdrop.b[j]: prevdrop.a[j]) == k) 194 { 195 if (iflong) 196 master.b[g]=k; 197 else 198 master.a[g]=k; 199 coord[g++] = prevcoord[j++]+1; 200 # if D1 201 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]); 203 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 { 210 if (iflong) 211 master.b[g]=k; 212 else 213 master.a[g]=k; 214 coord[g++] = 1; 215 } 216 } 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); 225 if (iflong) 226 master.b[g] = prevdrop.b[j]; 227 else 228 master.a[g] = prevdrop.a[j]; 229 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]); 233 else 234 fprintf(stderr, "copied over %d coord %d\n",master.a[g-1], coord[g-1]); 235 # endif 236 } 237 nf = g; 238 } 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 245 fprintf(stderr, "colevel %d best %d\n", colevel, best); 246 # endif 247 reached = best; 248 for(g=j=0; j<nf; j++) 249 if (coord[j]==best) 250 { 251 if (iflong) 252 master.b[g++] = master.b[j]; 253 else 254 master.a[g++] = master.a[j]; 255 } 256 nf=g; 257 # if D1 258 fprintf(stderr, "yet got %d\n",nf); 259 # endif 260 } 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)); 267 free(prevcoord, lmaster, sizeof (lmaster)); 268 } 269 # if D3 270 for(g=0;g<nf;g++) 271 if(iflong) 272 fprintf(stderr,":%ld\n",master.b[g]); 273 else 274 fprintf(stderr,":%d\n",master.a[g]); 275 # endif 276 return(nf); 277 } 278 279 long 280 getl(fb) 281 FILE *fb; 282 { 283 return(getw(fb)); 284 } 285 286 putl(ll, f) 287 long ll; 288 FILE *f; 289 { 290 putw(ll, f); 291 } 292 293 hcomp( n1, n2) 294 { 295 return (hfreq[hh[n1]]<=hfreq[hh[n2]]); 296 } 297 298 hexch( n1, n2 ) 299 { 300 int t; 301 t = hh[n1]; 302 hh[n1] = hh[n2]; 303 hh[n2] = t; 304 } 305