4.3BSD - /usr/src/usr.bin/refer/hunt2.c

   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: }

Defined functions

Defined variables

Defined union's