hunt2.c

unix v7是最后一个广泛发布的研究型UNIX版本

# include "refer..c"
static int *coord 0;
int hh[50]; extern int *hfreq, hfrflg, hcomp(), hexch();
extern int prfreqs;

doquery(hpt, nhash, fb, nitem, qitem, master)
	union ptr {unsigned *a; long *b;} master;
	long *hpt;
	FILE *fb;
	char *qitem[];
{
long k;
union ptr prevdrop;
int nf 0, best 0, nterm 0, i, g, j;
int *prevcoord;
long lp;
extern int lmaster, colevel, reached;
long getl(); unsigned getw(); extern int iflong;

# if D1
fprintf(stderr, "entering doquery nitem %d\n",nitem);
fprintf(stderr, "first few hashes are %ld %ld %ld %ld %ld\n", hpt[0],hpt[1],hpt[2],hpt[3],hpt[4]);
fprintf(stderr, "and frequencies are  %d %d %d %d %d\n",hfreq[0],hfreq[1],hfreq[2],hfreq[3],hfreq[4]);
# endif
_assert (lmaster>0);
if (coord==0)
	coord = zalloc(lmaster, sizeof(lmaster));
if (colevel>0)
	{
	prevdrop.a=zalloc(lmaster,iflong?4:2);
	prevcoord = zalloc(lmaster, sizeof(lmaster));
	}
else
	{
	prevdrop.a=master.a;
	prevcoord=coord;
	}
# if D1
fprintf(stderr, "nitem %d\n",nitem);
# endif
for(i=0; i<nitem; i++)
	{
	hh[i] = hash(qitem[i])%nhash;
# if D1
	fprintf(stderr,"query wd X%sX has hash %d\n", qitem[i], hh[i]);
# endif
	}
# if D1
fprintf(stderr, "past that loop nhash %d hpt is %lo\n", nhash, hpt);
# endif
if (prfreqs)
	for(i=0; i<nitem; i++)
		fprintf(stderr,"item %s hash %d hfreq %d\n",qitem[i], hh[i], hfreq[hh[i]]);
/* if possible, sort query into decreasing frequency of hashes */
if (hfrflg)
	shell (nitem, hcomp, hexch);
# if D1
for(i=0; i<nitem; i++)
 fprintf(stderr, "item hash %d frq %d\n", hh[i], hfreq[hh[i]]);
# endif
	lp = hpt [hh[0]];
# if D1
fprintf(stderr,"first item hash %d lp %ld 0%lo\n", hh[0],lp,lp);
# endif
_assert (fb!=NULL);
_assert (fseek(fb,lp,0)==NULL);
for(i=0; i<lmaster; i++)
	{
	if (iflong)
		master.b[i] = getl(fb);
	else
		master.a[i] = getw(fb);
	coord[i]=1;
# if D2
	if (iflong)
	fprintf(stderr,"master has %ld\n",(master.b[i]));
	else
	fprintf(stderr,"master has %d\n",(master.a[i]));
# endif
	_assert (i<lmaster);
	if (iflong)
		{
		if (master.b[i] == -1L) break;
		}
	else
		{
		if (master.a[i] == -1) break;
		}
	}
nf= i;
for(nterm=1; nterm<nitem; nterm++)
	{
# ifdef D1
	fprintf(stderr, "item %d, hash %d\n", nterm, hh[nterm]);
# endif
	if (colevel>0)
		{
		for(j=0; j<nf; j++)
			{
			if (iflong)
			prevdrop.b[j] = master.b[j];
			else
			prevdrop.a[j] = master.a[j];
			prevcoord[j] = coord[j];
			}
		}
	lp = hpt[hh[nterm]];
	_assert (fseek(fb, lp, 0)==0);
# if D1
	fprintf(stderr,"item %d hash %d seek to %ld\n",nterm,hh[nterm],lp);
# endif
	g=j=0;
	while (1)
		{
		if (iflong)
			k = getl(fb);
		else
			k = getw(fb);
		if (k== -1) break;
# if D2
		fprintf(stderr,"next term finds %ld\n",k);
# endif
# if D3
		if (iflong)
		fprintf(stderr, "bfwh j %d nf %d master %ld k %ld\n",j,nf,prevdrop.b[j],(long)(k));
		else
		fprintf(stderr, "bfwh j %d nf %d master %ld k %ld\n",j,nf,prevdrop.a[j],(long)(k));
# endif
		while (j<nf && (iflong?prevdrop.b[j]:prevdrop.a[j])<k)
			{
# if D3
			if (iflong)
			fprintf(stderr, "j %d nf %d prevdrop %ld prevcoord %d colevel %d nterm %d k %ld\n",
			j,nf,prevdrop.b[j], prevcoord[j], colevel, nterm, (long)(k));
			else
			fprintf(stderr, "j %d nf %d prevdrop %ld prevcoord %d colevel %d nterm %d k %ld\n",
			j,nf,prevdrop.a[j], prevcoord[j], colevel, nterm, (long)(k));
# endif
			if (prevcoord[j] + colevel <= nterm)
				j++;
			else
				{
				_assert (g<lmaster);
				if (iflong)
				master.b[g] = prevdrop.b[j];
				else
				master.a[g] = prevdrop.a[j];
				coord[g++] = prevcoord[j++];
# if D1
if (iflong)
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]);
else
fprintf(stderr, " not skip g %d doc %ld coord %d nterm %d\n",g,master.a[g-1], coord[g-1],nterm);
# endif
				continue;
				}
			}
		if (colevel==0 && j>=nf) break;
		if (j<nf && (iflong? prevdrop.b[j]: prevdrop.a[j]) == k)
			{
			if (iflong)
			master.b[g]=k;
			else
			master.a[g]=k;
			coord[g++] = prevcoord[j++]+1;
# if D1
if (iflong)
			fprintf(stderr, " at g %d item %ld coord %d note %ld\n",g,master.b[g-1],coord[g-1],master.b[j-1]);
else
			fprintf(stderr, " at g %d item %d coord %d note %d\n",g,master.a[g-1],coord[g-1],master.a[j-1]);
# endif
			}
		else
		if (colevel >= nterm)
			{
			if (iflong)
			master.b[g]=k;
			else
			master.a[g]=k;
			coord[g++] = 1;
			}
		}
# if D1
fprintf(stderr,"now have %d items\n",g);
# endif
	if (colevel>0)
	for ( ; j<nf; j++)
		if ((iflong?prevcoord.b[j]:prevcoord.a[j])+colevel > nterm)
			{
			_assert(g<lmaster);
			if (iflong)
			master.b[g] = prevdrop.b[j];
			else
			master.a[g] = prevdrop.a[j];
			coord[g++] = prevcoord[j];
# if D3
if(iflong)
fprintf(stderr, "copied over %ld coord %d\n",master.b[g-1], coord[g-1]);
else
fprintf(stderr, "copied over %d coord %d\n",master.a[g-1], coord[g-1]);
# endif
			}
	nf = g;
	}
if (colevel>0)
	{
	best=0;
	for(j=0; j<nf; j++)
		if (coord[j]>best) best = coord[j];
# if D1
	fprintf(stderr, "colevel %d best %d\n", colevel, best);
# endif
	reached = best;
	for(g=j=0; j<nf; j++)
		if (coord[j]==best)
			{
			if (iflong)
			master.b[g++] = master.b[j];
			else
			master.a[g++] = master.a[j];
			}
	nf=g;
# if D1
	fprintf(stderr, "yet got %d\n",nf);
# endif
	}
# ifdef D1
	fprintf(stderr, " returning with %d\n",nf);
# endif
if (colevel)
	{
	free(prevdrop, lmaster, iflong?4:2);
	free(prevcoord, lmaster, sizeof (lmaster));
	}
# if D3
for(g=0;g<nf;g++)
if(iflong)
fprintf(stderr,":%ld\n",master.b[g]);
else
fprintf(stderr,":%d\n",master.a[g]);
# endif
return(nf);
}
long
getl(fb)
	FILE *fb;
{
int x[2];
long *lp;
x[0] = getw(fb);
x[1] = getw(fb);
lp= x;
return(*lp);
}
putl(ll, f)
	long ll;
	FILE *f;
{
int *x;
x = &ll;
putw(x[0], f);
putw(x[1], f);
}
hcomp( n1, n2)
{
return (hfreq[hh[n1]]<=hfreq[hh[n2]]);
}
hexch( n1, n2 )
{
int t;
t = hh[n1];
hh[n1] = hh[n2];
hh[n2] = t;
}