Return to hunt2.c CVS log

Up to [CSRG BSD Unix] / 43BSD / usr.bin / refer

Annotation of 43BSD/usr.bin/refer/hunt2.c, revision 1.1

1.1     ! root        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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.