2.9BSD - /usr/src/cmd/refer/util/hunt2.c

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

Defined functions

Defined variables

Defined union's