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