Return to bm.c CVS log

Up to [Research Unix] / researchv10no / cmd / gre

Annotation of researchv10no/cmd/gre/bm.c, revision 1.1

1.1     ! root        1: #include       "re.h"
        !             2: #include       "lre.h"
        !             3: #include       "hdr.h"
        !             4: 
        !             5: /*
        !             6:        this next one is dirty but i can't think of a good way out now.
        !             7:        essentially, LARGE has to be a bit bigger than the biggest buffer
        !             8:        we are ever given by rdfn
        !             9: */
        !            10: #define                LARGE   (100000000+2)
        !            11: 
        !            12: static int bb(re_bm *, unsigned char*, unsigned char*);
        !            13: 
        !            14: re_bm *
        !            15: re_bmcomp(char *ppb, char *ppe, unsigned char *map)
        !            16: {
        !            17:        register unsigned char *pb = (unsigned char *)ppb;
        !            18:        register unsigned char *pe = (unsigned char *)ppe;
        !            19:        register int j;
        !            20:        int delta[256];
        !            21:        register re_bm *b;
        !            22: 
        !            23:        b = (re_bm *)malloc(sizeof *b);
        !            24:        if(b == 0){
        !            25:                re_error("b malloc fail");
        !            26:                return 0;
        !            27:        }
        !            28:        b->patlen = pe-pb;
        !            29:        memmove((char *)b->cmap, (char *)map, sizeof b->cmap);
        !            30:        b->bmpat = malloc(b->patlen);
        !            31:        if(b->bmpat == 0){
        !            32:                re_error("bmpat malloc fail");
        !            33:                free((char*)b);
        !            34:                return 0;
        !            35:        }
        !            36:        if (bb(b, pb, pe) == 0){
        !            37:                free((char*)b->bmpat);
        !            38:                free((char*)b);
        !            39:                return 0;
        !            40:        }
        !            41:        for(j = 0; pb+j < pe; j++)
        !            42:                b->bmpat[j] = b->cmap[pb[j]];
        !            43:        for(j = 0; j < 256; j++)
        !            44:                delta[j] = b->patlen;
        !            45:        for(pe--; pb < pe; pb++)
        !            46:                delta[b->cmap[*pb]] = pe-pb;
        !            47:        delta[b->cmap[*pb]] = LARGE;
        !            48:        for(j = 0; j < 256; j++)
        !            49:                b->delta0[j] = delta[b->cmap[j]];
        !            50:        return(b);
        !            51: }
        !            52: 
        !            53: static int
        !            54: bb(register re_bm *b, register unsigned char *pb, register unsigned char *pe)
        !            55: {
        !            56:        int *f;
        !            57:        register m = pe-pb;
        !            58:        register i, k, j;
        !            59: 
        !            60:        f = (int *)malloc(sizeof(int)*(m+1));
        !            61:        if(f == 0){
        !            62:                re_error("delta2 f malloc");
        !            63:                return 0;
        !            64:        }
        !            65:        pb--;
        !            66:        b->delta2 = (int *)malloc(sizeof(int)*(b->patlen+1));
        !            67:        if(b->delta2 == 0){
        !            68:                re_error("delta2 malloc");
        !            69:                free((char*)f);
        !            70:                return 0;
        !            71:        }               
        !            72:        for(i = 1; i <= m; i++)
        !            73:                b->delta2[i] = 2*m-i;
        !            74:        j = m;
        !            75:        k = m+1;
        !            76:        while(j > 0){
        !            77:                f[j] = k;
        !            78:                while((k <= m) && (pb[j] != pb[k])){
        !            79:                        if(m-j < b->delta2[k])
        !            80:                                b->delta2[k] = m-j;
        !            81:                        k = f[k];
        !            82:                }
        !            83:                j--;
        !            84:                k--;
        !            85:        }
        !            86:        for(i = 1; i <= k; i++){
        !            87:                if(b->delta2[i] > m+k-i)
        !            88:                        b->delta2[i] = m+k-i;
        !            89:        }
        !            90:        free((char *)f);
        !            91:        return 1;
        !            92: }
        !            93: 
        !            94: re_bmexec(void *re_b, RDFN rdfn, MATCHFN matchfn)
        !            95: {
        !            96:        register re_bm *b = (re_bm*)re_b;
        !            97:        register unsigned char *sp;
        !            98:        register unsigned char *e, *s;
        !            99:        unsigned char *re, *rs;
        !           100:        register k;
        !           101: 
        !           102:        for(rs = 0; (k = (*rdfn)((char**)&rs, (char**)&re)) > 0; rs = s, re = e){
        !           103:                e = re;
        !           104:                s = rs;
        !           105:                while(s < e){
        !           106:                        while((s += b->delta0[*s]) < e)
        !           107:                                ;
        !           108:                        if(s < e+b->patlen){    /* no match */
        !           109:                                s = e;
        !           110:                                break;
        !           111:                        }
        !           112:                        s -= LARGE;
        !           113:                        for(k = b->patlen-2, sp = s-1; k >= 0; k--)
        !           114:                                if(b->cmap[*sp--] != b->bmpat[k])
        !           115:                                        break;
        !           116: /*print("k=%d s=%d sp=%d\n", k, s, sp);/**/
        !           117:                        if(k < 0){
        !           118:                                unsigned char *bm = ++sp, *em = s+1;
        !           119:                                if((k = (*matchfn)((char**)&bm, (char**)&em)) <= 0)
        !           120:                                        return(k);
        !           121:                                s = bm;
        !           122:                                e = em;
        !           123:                        } else {
        !           124:                                /*j = b->delta2[k+1];
        !           125:                                k = b->delta0[cmap[*++sp]];
        !           126:                                if((j > k) || (k == LARGE))
        !           127:                                         k = j;
        !           128:                                s = sp+k;*/s++;
        !           129:                        }
        !           130:                }
        !           131:        }
        !           132:        return(k);
        !           133: }
        !           134: 
        !           135: void
        !           136: re_bmfree(re_bm *pat)
        !           137: {
        !           138:        free((char *)pat->delta2);
        !           139:        free(pat->bmpat);
        !           140:        free((char *)pat);
        !           141: }

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