Logo Search packages:      
Sourcecode: ksh version File versions

mtchstring.c

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*           Copyright (c) 1989-2007 AT&T Knowledge Ventures            *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                      by AT&T Knowledge Ventures                      *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                   Phong Vo <kpv@research.att.com>                    *
*                                                                      *
***********************************************************************/
#pragma prototyped
#include    "update.h"


/*
**    Find the longest prefix of tar that match some substring of src
**    This uses an inverted index for speed.
*/
#define ALPHA     (256) /* alphabet size */

static void freemem(long* n_index, char*** index)
{
      register int i;
      if(n_index && index)
      {
            for(i = 0; i < ALPHA; ++i)
                  if(n_index[i] > 0)
                        free(index[i]);
            free(index);
            free(n_index);
      }
}

/* initial assumptions: src[0] == tar[0] && src+n_match <= endsrc */
static long domatch(char* src, char* endsrc, char* tar, char* endtar, long n_match)
{
      register char     *sp, *tp;

      /* see if this really improves on the current match */
      for(sp = src+n_match, tp = tar+n_match; sp > src; --sp, --tp)
            if(*sp != *tp)
                  break;

      /* got an improvement, match as many more as we can */
      if(sp == src)
      {
            sp = src+n_match+1;
            tp = tar+n_match+1;
            for(; sp < endsrc && tp < endtar; ++sp, ++tp)
                  if(*sp != *tp)
                        break;
      }
      return tp-tar;
}

/* the real thing */
long  mtchstring(char* src, long n_src, char* tar, long n_tar, char** match)
{
      char        *endsrc, *endtar;
      long        n_match;
      register int      i;
      register long     n_ind;
      register char     **ind;
      static long *N_index = 0;
      static char *Cursrc = 0, ***Index = 0;
      static int  Alloced = 0;

      /* free old inverted indices if necessary */
      if(src != Cursrc)
      {
            if(Alloced)
                  freemem(N_index,Index);
            Alloced = 0;
            Cursrc = 0;
      }

      /* nothing to do */
      if(!src || n_src <= 0 || !tar || n_tar <= 0)
            return 0;

      endsrc = src + n_src;
      endtar = tar + n_tar;

      /* build new index structure */
      if(src != Cursrc)
      {
            Cursrc = src;
            Alloced = 1;
            if(N_index = (long*) malloc(ALPHA*sizeof(long)))
            {
                  register char     *sp;

                  memzero(N_index,ALPHA*sizeof(long));
                  if(!(Index = (char ***) malloc(ALPHA*sizeof(char**))))
                  {
                        free(N_index);
                        N_index = 0;
                        Alloced = 0;
                  }
                  else for(sp = src; sp < endsrc; ++sp)
                  {
                        i = (int)(*((unsigned char *)(sp)));
                        ind = Index[i];
                        n_ind = N_index[i];

                        /* make sure we have space */
                        if((n_ind%ALPHA) == 0)
                        {
                              ind = n_ind == 0 ?
                                    (char**)malloc(ALPHA*sizeof(char *)) :
                                    (char**)realloc(ind,(n_ind+ALPHA)*sizeof(char*));
                              Index[i] = ind;
                        }
                        if(ind)
                        {
                              ind[n_ind] = sp;
                              N_index[i] += 1;
                        }
                        else
                        {
                              freemem(N_index,Index);
                              N_index = 0;
                              Index = 0;
                              Alloced = 0;
                              break;
                        }
                  }
            }
      }

      /* find longest matching prefix */
      i = (int)(*((unsigned char *)(tar)));
      ind   = Alloced ? Index[i] : (char**)0;
      n_ind = Alloced ? N_index[i] : -1;
      n_match = 0;
      while(1)
      {
            register long m;

            if(ind)
            {
                  src = n_ind > 0 ? *ind++ : endsrc;
                  n_ind -= 1;
            }
            else for(; src+n_match < endsrc; ++src)
                  if(*src == *tar)
                        break;
            if(src+n_match >= endsrc)
                  break;

            if((m = domatch(src,endsrc,tar,endtar,n_match)) > n_match)
            {
                  n_match = m;
                  *match = src;
                  if(tar+n_match >= endtar)
                        break;
            }
      }

      return n_match;
}

Generated by  Doxygen 1.6.0   Back to index