Return to mtchstring.c CVS log

Up to [Research Unix] / researchv10no / cmd / odist / pax / src / lib / libodelta

Annotation of researchv10no/cmd/odist/pax/src/lib/libodelta/mtchstring.c, revision 1.1

1.1     ! root        1: #include       "update.h"
        !             2: 
        !             3: 
        !             4: /*
        !             5: **     Find the longest prefix of tar that match some substring of src
        !             6: **     This uses an inverted index for speed.
        !             7: */
        !             8: #define ALPHA  (256)   /* alphabet size */
        !             9: 
        !            10: static void freemem(n_index,index)
        !            11: long   *n_index;
        !            12: char   ***index;
        !            13: {
        !            14:        register int i;
        !            15:        if(n_index && index)
        !            16:        {
        !            17:                for(i = 0; i < ALPHA; ++i)
        !            18:                        if(n_index[i] > 0)
        !            19:                                free(index[i]);
        !            20:                free(index);
        !            21:                free(n_index);
        !            22:        }
        !            23: }
        !            24: 
        !            25: /* initial assumptions: src[0] == tar[0] && src+n_match <= endsrc */
        !            26: static long domatch(src,endsrc,tar,endtar,n_match)
        !            27: char   *src, *endsrc, *tar, *endtar;
        !            28: long   n_match;
        !            29: {
        !            30:        register char   *sp, *tp;
        !            31: 
        !            32:        /* see if this really improves on the current match */
        !            33:        for(sp = src+n_match, tp = tar+n_match; sp > src; --sp, --tp)
        !            34:                if(*sp != *tp)
        !            35:                        break;
        !            36: 
        !            37:        /* got an improvement, match as many more as we can */
        !            38:        if(sp == src)
        !            39:        {
        !            40:                sp = src+n_match+1;
        !            41:                tp = tar+n_match+1;
        !            42:                for(; sp < endsrc && tp < endtar; ++sp, ++tp)
        !            43:                        if(*sp != *tp)
        !            44:                                break;
        !            45:        }
        !            46:        return tp-tar;
        !            47: }
        !            48: 
        !            49: /* the real thing */
        !            50: long   mtchstring(src,n_src,tar,n_tar,match)
        !            51: char   *src;   /* the source string to match from */
        !            52: long   n_src;  /* the length of src */
        !            53: char   *tar;   /* the string a prefix of which is matched */
        !            54: long   n_tar;  /* the length of tar */
        !            55: char   **match; /* to return the matched address in src */
        !            56: {
        !            57:        char            *endsrc, *endtar;
        !            58:        long            n_match;
        !            59:        register int    i;
        !            60:        register long   n_ind;
        !            61:        register char   **ind;
        !            62:        static long     *N_index = NIL(long);
        !            63:        static char     *Cursrc = NIL(char), ***Index = NIL(char**);
        !            64:        static int      Alloced = 0;
        !            65:        char            **malloc(), **realloc();
        !            66: 
        !            67:        /* free old inverted indices if necessary */
        !            68:        if(src != Cursrc)
        !            69:        {
        !            70:                if(Alloced)
        !            71:                        freemem(N_index,Index);
        !            72:                Alloced = 0;
        !            73:                Cursrc = NIL(char);
        !            74:        }
        !            75: 
        !            76:        /* nothing to do */
        !            77:        if(!src || n_src <= 0 || !tar || n_tar <= 0)
        !            78:                return 0;
        !            79: 
        !            80:        endsrc = src + n_src;
        !            81:        endtar = tar + n_tar;
        !            82: 
        !            83:        /* build new index structure */
        !            84:        if(src != Cursrc)
        !            85:        {
        !            86:                Cursrc = src;
        !            87:                Alloced = 1;
        !            88:                if(N_index = (long*) malloc(ALPHA*sizeof(long)))
        !            89:                {
        !            90:                        register char   *sp;
        !            91: 
        !            92:                        memzero((char*)N_index,ALPHA*sizeof(long));
        !            93:                        if(!(Index = (char ***) malloc(ALPHA*sizeof(char**))))
        !            94:                        {
        !            95:                                free(N_index);
        !            96:                                N_index = NIL(long);
        !            97:                                Alloced = 0;
        !            98:                        }
        !            99:                        else for(sp = src; sp < endsrc; ++sp)
        !           100:                        {
        !           101:                                i = (int)(*((unsigned char *)(sp)));
        !           102:                                ind = Index[i];
        !           103:                                n_ind = N_index[i];
        !           104: 
        !           105:                                /* make sure we have space */
        !           106:                                if((n_ind%ALPHA) == 0)
        !           107:                                {
        !           108:                                        ind = n_ind == 0 ?
        !           109:                                              malloc(ALPHA*sizeof(char *)) :
        !           110:                                              realloc(ind,(n_ind+ALPHA)*sizeof(char*));
        !           111:                                        Index[i] = ind;
        !           112:                                }
        !           113:                                if(ind)
        !           114:                                {
        !           115:                                        ind[n_ind] = sp;
        !           116:                                        N_index[i] += 1;
        !           117:                                }
        !           118:                                else
        !           119:                                {
        !           120:                                        freemem(N_index,Index);
        !           121:                                        N_index = NIL(long);
        !           122:                                        Index = NIL(char**);
        !           123:                                        Alloced = 0;
        !           124:                                        break;
        !           125:                                }
        !           126:                        }
        !           127:                }
        !           128:        }
        !           129: 
        !           130:        /* find longest matching prefix */
        !           131:        i = (int)(*((unsigned char *)(tar)));
        !           132:        ind   = Alloced ? Index[i] : NULL;
        !           133:        n_ind = Alloced ? N_index[i] : -1;
        !           134:        n_match = 0;
        !           135:        while(1)
        !           136:        {
        !           137:                register long m;
        !           138: 
        !           139:                if(ind)
        !           140:                {
        !           141:                        src = n_ind > 0 ? *ind++ : endsrc;
        !           142:                        n_ind -= 1;
        !           143:                }
        !           144:                else for(; src+n_match < endsrc; ++src)
        !           145:                        if(*src == *tar)
        !           146:                                break;
        !           147:                if(src+n_match >= endsrc)
        !           148:                        break;
        !           149: 
        !           150:                if((m = domatch(src,endsrc,tar,endtar,n_match)) > n_match)
        !           151:                {
        !           152:                        n_match = m;
        !           153:                        *match = src;
        !           154:                        if(tar+n_match >= endtar)
        !           155:                                break;
        !           156:                }
        !           157:        }
        !           158: 
        !           159:        return n_match;
        !           160: }

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