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

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.