home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / refer / hunt2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  5.7 KB  |  275 lines
  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 = ≪
  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. }
  275.