home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / extra / replace.c < prev    next >
C/C++ Source or Header  |  2000-08-31  |  29KB  |  1,081 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    
  3.    This library is free software; you can redistribute it and/or
  4.    modify it under the terms of the GNU Library General Public
  5.    License as published by the Free Software Foundation; either
  6.    version 2 of the License, or (at your option) any later version.
  7.    
  8.    This library is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11.    Library General Public License for more details.
  12.    
  13.    You should have received a copy of the GNU Library General Public
  14.    License along with this library; if not, write to the Free
  15.    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  16.    MA 02111-1307, USA */
  17.  
  18. /* Replace strings in textfile
  19.   This program replace strings in a file or on stdin/stdout.
  20.   It accepts a list of from-strings and to-strings and replaces all
  21.   occurents of from-strings to to-strings.
  22.   The first occurents of a found string is matched. If there are more than
  23.   one possibly replace the longer from-string is replaced.
  24.   Special characters in from string:
  25.   \^    Match start of line.
  26.   \$    Match end of line.
  27.   \b    Match space-character, start of line or end of line.
  28.         For end \b the next replace starts locking at the end space-character.
  29.         An \b alone or in a string matches only a space-character.
  30.   \r, \t, \v as in C.
  31.   The programs make a DFA-state-machine of the strings and the speed isn't
  32.   dependent on the count of replace-strings (only of the number of replaces).
  33.   A line is assumed ending with \n or \0.
  34.   There are no limit exept memory on length of strings.
  35.  
  36.   Written by Monty.
  37.   fill_buffer_retaining() is taken from gnu-grep and modified.
  38. */
  39.  
  40. #define DONT_USE_RAID
  41. #include <global.h>
  42. #include <m_ctype.h>
  43. #include <my_sys.h>
  44. #include <m_string.h>
  45. #include <errno.h>
  46.  
  47. #define PC_MALLOC        256    /* Bytes for pointers */
  48. #define PS_MALLOC        512    /* Bytes for data */
  49.  
  50. typedef struct st_pointer_array {        /* when using array-strings */
  51.   TYPELIB typelib;                /* Pointer to strings */
  52.   byte    *str;                    /* Strings is here */
  53.   int7    *flag;                    /* Flag about each var. */
  54.   uint  array_allocs,max_count,length,max_length;
  55. } POINTER_ARRAY;
  56.  
  57. #define SPACE_CHAR    256
  58. #define START_OF_LINE    257
  59. #define END_OF_LINE    258
  60. #define LAST_CHAR_CODE    259
  61.  
  62. typedef struct st_replace {
  63.   bool   found;
  64.   struct st_replace *next[256];
  65. } REPLACE;
  66.  
  67. typedef struct st_replace_found {
  68.   bool found;
  69.   char *replace_string;
  70.   uint to_offset;
  71.   int from_offset;
  72. } REPLACE_STRING;
  73.  
  74. #ifndef WORD_BIT
  75. #define WORD_BIT (8*sizeof(uint))
  76. #endif
  77.  
  78.     /* functions defined in this file */
  79.  
  80. extern int main(int argc,char * *argv);
  81. static int static_get_options(int *argc,char * * *argv);
  82. static int get_replace_strings(int *argc,char * * *argv,
  83.                    POINTER_ARRAY *from_array,
  84.                    POINTER_ARRAY *to_array);
  85. int insert_pointer_name(POINTER_ARRAY *pa, my_string name);
  86. void free_pointer_array(POINTER_ARRAY *pa);
  87. static int convert_pipe(REPLACE *,FILE *,FILE *);
  88. static int convert_file(REPLACE *, my_string);
  89. REPLACE *init_replace(my_string *from, my_string *to,uint count, my_string
  90.               word_end_chars);
  91. uint replace_strings(REPLACE *rep, my_string *start,uint *max_length,
  92.              my_string from);
  93. static int initialize_buffer(void);
  94. static void reset_buffer(void);
  95. static void free_buffer(void);
  96.  
  97. static int silent=0,verbose=0,updated=0;
  98.  
  99.     /* The main program */
  100.  
  101. int main(argc,argv)
  102. int argc;
  103. char *argv[];
  104. {
  105.   int i,error;
  106.   char word_end_chars[256],*pos;
  107.   POINTER_ARRAY from,to;
  108.   REPLACE *replace;
  109.   MY_INIT(argv[0]);
  110.  
  111.   if (static_get_options(&argc,&argv))
  112.     exit(1);
  113.   if (get_replace_strings(&argc,&argv,&from,&to))
  114.     exit(1);
  115.  
  116.   for (i=1,pos=word_end_chars ; i < 256 ; i++)
  117.     if (isspace(i))
  118.       *pos++=i;
  119.   *pos=0;
  120.   if (!(replace=init_replace((char**) from.typelib.type_names,
  121.                  (char**) to.typelib.type_names,
  122.                  (uint) from.typelib.count,word_end_chars)))
  123.     exit(1);
  124.   free_pointer_array(&from);
  125.   free_pointer_array(&to);
  126.   if (initialize_buffer())
  127.     return 1;
  128.  
  129.   error=0;
  130.   if (argc == 0)
  131.     error=convert_pipe(replace,stdin,stdout);
  132.   else
  133.   {
  134.     while (argc--)
  135.     {
  136.       error=convert_file(replace,*(argv++));
  137.     }
  138.   }
  139.   free_buffer();
  140.   my_end(verbose ? MY_CHECK_ERROR | MY_GIVE_INFO : MY_CHECK_ERROR);
  141.   exit(error ? 2 : 0);
  142.   return 0;                    /* No compiler warning */
  143. } /* main */
  144.  
  145.  
  146.     /* reads options */
  147.     /* Initiates DEBUG - but no debugging here ! */
  148.  
  149. static int static_get_options(argc,argv)
  150. register int *argc;
  151. register char **argv[];
  152. {
  153.   int help,version,opt;
  154.   char *pos;
  155.  
  156.   silent=verbose=help=0;
  157.  
  158.   while (--*argc > 0 && *(pos = *(++*argv)) == '-' && pos[1] != '-') {
  159.     while (*++pos)
  160.     {
  161.       version=0;
  162.       switch((opt= *pos)) {
  163.       case 's':
  164.     silent=1;
  165.     break;
  166.       case 'v':
  167.     verbose=1;
  168.     break;
  169.       case '#':
  170.     DBUG_PUSH (++pos);
  171.     pos= (char*) " ";            /* Skipp rest of arguments */
  172.     break;
  173.       case 'V':
  174.     version=1;
  175.       case 'I':
  176.       case '?':
  177.     help=1;                    /* Help text written */
  178.     printf("%s  Ver 1.3 for %s at %s\n",my_progname,SYSTEM_TYPE,
  179.            MACHINE_TYPE);
  180.     if (version)
  181.       break;
  182.     puts("This software comes with ABSOLUTELY NO WARRANTY. This is free software,\nand you are welcome to modify and redistribute it under the GPL license\n");
  183.     puts("This program replace strings in a file or on stdin/stdout.\n"
  184.          "It accepts a list of from-strings and to-strings and replaces\n"
  185.          "all occurents of from-strings to to-strings.\n"
  186.          "The first occurents of a found string is matched. Longer matches\n"
  187.          "are prefered before shorter matches.\n\n"
  188.          "Special characters in from string:\n"
  189.          "  \\^      Match start of line.\n"
  190.          "  \\$      Match end of line.\n"
  191.          "  \\b      Match space-character, start of line or end of line.\n"
  192.          "          For a end \\b the next replace starts locking at the end\n"
  193.          "          space-character. A \\b alone in a string matches only a\n"
  194.          "          space-character.\n");
  195.       printf("Usage: %s [-?svIV] from to from to ... -- [files]\n", my_progname);
  196.     puts("or");
  197.       printf("Usage: %s [-?svIV] from to from to ... < fromfile > tofile\n", my_progname);
  198.     puts("");
  199.     puts("Options: -? or -I \"Info\"  -s \"silent\"      -v \"verbose\"");
  200.     break;
  201.       default:
  202.     fprintf(stderr,"illegal option: -%c\n",*pos);
  203.     break;
  204.       }
  205.     }
  206.   }
  207.   if (*argc == 0)
  208.   {
  209.     if (!help)
  210.       my_message(0,"No replace options given",MYF(ME_BELL));
  211.     exit(0);                    /* Don't use as pipe */
  212.   }
  213.   return(0);
  214. } /* static_get_options */
  215.  
  216.  
  217. static int get_replace_strings(argc,argv,from_array,to_array)
  218. register int *argc;
  219. register char **argv[];
  220. POINTER_ARRAY *from_array,*to_array;
  221. {
  222.   char *pos;
  223.  
  224.   bzero((char*) from_array,sizeof(from_array[0]));
  225.   bzero((char*) to_array,sizeof(to_array[0]));
  226.   while (*argc > 0 && (*(pos = *(*argv)) != '-' || pos[1] != '-' || pos[2]))
  227.   {
  228.     insert_pointer_name(from_array,pos);
  229.     (*argc)--;
  230.     (*argv)++;
  231.     if (!*argc || !strcmp(**argv,"--"))
  232.     {
  233.       my_message(0,"No to-string for last from-string",MYF(ME_BELL));
  234.       return 1;
  235.     }
  236.     insert_pointer_name(to_array,**argv);
  237.     (*argc)--;
  238.     (*argv)++;
  239.   }
  240.   if (*argc)
  241.   {                    /* Skipp "--" argument */
  242.     (*argc)--;
  243.     (*argv)++;
  244.   }
  245.   return 0;
  246. }
  247.  
  248. int insert_pointer_name(reg1 POINTER_ARRAY *pa,my_string name)
  249. {
  250.   uint i,length,old_count;
  251.   byte *new_pos;
  252.   const char **new_array;
  253.   DBUG_ENTER("insert_pointer_name");
  254.  
  255.   if (! pa->typelib.count)
  256.   {
  257.     if (!(pa->typelib.type_names=(const char **)
  258.       my_malloc(((PC_MALLOC-MALLOC_OVERHEAD)/
  259.              (sizeof(my_string)+sizeof(*pa->flag))*
  260.              (sizeof(my_string)+sizeof(*pa->flag))),MYF(MY_WME))))
  261.       DBUG_RETURN(-1);
  262.     if (!(pa->str= (byte*) my_malloc((uint) (PS_MALLOC-MALLOC_OVERHEAD),
  263.                      MYF(MY_WME))))
  264.     {
  265.       my_free((gptr) pa->typelib.type_names,MYF(0));
  266.       DBUG_RETURN (-1);
  267.     }
  268.     pa->max_count=(PC_MALLOC-MALLOC_OVERHEAD)/(sizeof(byte*)+
  269.                            sizeof(*pa->flag));
  270.     pa->flag= (int7*) (pa->typelib.type_names+pa->max_count);
  271.     pa->length=0;
  272.     pa->max_length=PS_MALLOC-MALLOC_OVERHEAD;
  273.     pa->array_allocs=1;
  274.   }
  275.   length=(uint) strlen(name)+1;
  276.   if (pa->length+length >= pa->max_length)
  277.   {
  278.     if (!(new_pos= (byte*) my_realloc((gptr) pa->str,
  279.                       (uint) (pa->max_length+PS_MALLOC),
  280.                       MYF(MY_WME))))
  281.       DBUG_RETURN(1);
  282.     if (new_pos != pa->str)
  283.     {
  284.       my_ptrdiff_t diff=PTR_BYTE_DIFF(new_pos,pa->str);
  285.       for (i=0 ; i < pa->typelib.count ; i++)
  286.     pa->typelib.type_names[i]= ADD_TO_PTR(pa->typelib.type_names[i],diff,
  287.                           char*);
  288.       pa->str=new_pos;
  289.     }
  290.     pa->max_length+=PS_MALLOC;
  291.   }
  292.   if (pa->typelib.count >= pa->max_count-1)
  293.   {
  294.     int len;
  295.     pa->array_allocs++;
  296.     len=(PC_MALLOC*pa->array_allocs - MALLOC_OVERHEAD);
  297.     if (!(new_array=(const char **) my_realloc((gptr) pa->typelib.type_names,
  298.                            (uint) len/
  299.                      (sizeof(byte*)+sizeof(*pa->flag))*
  300.                      (sizeof(byte*)+sizeof(*pa->flag)),
  301.                      MYF(MY_WME))))
  302.       DBUG_RETURN(1);
  303.     pa->typelib.type_names=new_array;
  304.     old_count=pa->max_count;
  305.     pa->max_count=len/(sizeof(byte*) + sizeof(*pa->flag));
  306.     pa->flag= (int7*) (pa->typelib.type_names+pa->max_count);
  307.     memcpy((byte*) pa->flag,(my_string) (pa->typelib.type_names+old_count),
  308.        old_count*sizeof(*pa->flag));
  309.   }
  310.   pa->flag[pa->typelib.count]=0;            /* Reset flag */
  311.   pa->typelib.type_names[pa->typelib.count++]= pa->str+pa->length;
  312.   pa->typelib.type_names[pa->typelib.count]= NullS;    /* Put end-mark */
  313.   VOID(strmov(pa->str+pa->length,name));
  314.   pa->length+=length;
  315.   DBUG_RETURN(0);
  316. } /* insert_pointer_name */
  317.  
  318.  
  319.     /* free pointer array */
  320.  
  321. void free_pointer_array(pa)
  322. reg1 POINTER_ARRAY *pa;
  323. {
  324.   if (pa->typelib.count)
  325.   {
  326.     pa->typelib.count=0;
  327.     my_free((gptr) pa->typelib.type_names,MYF(0));
  328.     pa->typelib.type_names=0;
  329.     my_free((gptr) pa->str,MYF(0));
  330.   }
  331.   return;
  332. } /* free_pointer_array */
  333.  
  334.  
  335.     /* Code for replace rutines */
  336.  
  337. #define SET_MALLOC_HUNC 64
  338.  
  339. typedef struct st_rep_set {
  340.   uint  *bits;                /* Pointer to used sets */
  341.   short    next[LAST_CHAR_CODE];        /* Pointer to next sets */
  342.   uint    found_len;            /* Best match to date */
  343.   int    found_offset;
  344.   uint  table_offset;
  345.   uint  size_of_bits;            /* For convinience */
  346. } REP_SET;
  347.  
  348. typedef struct st_rep_sets {
  349.   uint        count;            /* Number of sets */
  350.   uint        extra;            /* Extra sets in buffer */
  351.   uint        invisible;        /* Sets not chown */
  352.   uint        size_of_bits;
  353.   REP_SET    *set,*set_buffer;
  354.   uint        *bit_buffer;
  355. } REP_SETS;
  356.  
  357. typedef struct st_found_set {
  358.   uint table_offset;
  359.   int found_offset;
  360. } FOUND_SET;
  361.  
  362. typedef struct st_follow {
  363.   int chr;
  364.   uint table_offset;
  365.   uint len;
  366. } FOLLOWS;
  367.  
  368.  
  369. static int init_sets(REP_SETS *sets,uint states);
  370. static REP_SET *make_new_set(REP_SETS *sets);
  371. static void make_sets_invisible(REP_SETS *sets);
  372. static void free_last_set(REP_SETS *sets);
  373. static void free_sets(REP_SETS *sets);
  374. static void set_bit(REP_SET *set, uint bit);
  375. static void clear_bit(REP_SET *set, uint bit);
  376. static void or_bits(REP_SET *to,REP_SET *from);
  377. static void copy_bits(REP_SET *to,REP_SET *from);
  378. static int cmp_bits(REP_SET *set1,REP_SET *set2);
  379. static int get_next_bit(REP_SET *set,uint lastpos);
  380. static int find_set(REP_SETS *sets,REP_SET *find);
  381. static int find_found(FOUND_SET *found_set,uint table_offset,
  382.               int found_offset);
  383. static uint start_at_word(my_string pos);
  384. static uint end_of_word(my_string pos);
  385. static uint replace_len(my_string pos);
  386.  
  387. static uint found_sets=0;
  388.  
  389.  
  390.     /* Init a replace structure for further calls */
  391.  
  392. REPLACE *init_replace(my_string *from, my_string *to,uint count,
  393.               my_string word_end_chars)
  394. {
  395.   uint i,j,states,set_nr,len,result_len,max_length,found_end,bits_set,bit_nr;
  396.   int used_sets,chr,default_state;
  397.   char used_chars[LAST_CHAR_CODE],is_word_end[256];
  398.   my_string pos,to_pos,*to_array;
  399.   REP_SETS sets;
  400.   REP_SET *set,*start_states,*word_states,*new_set;
  401.   FOLLOWS *follow,*follow_ptr;
  402.   REPLACE *replace;
  403.   FOUND_SET *found_set;
  404.   REPLACE_STRING *rep_str;
  405.   DBUG_ENTER("init_replace");
  406.  
  407.   /* Count number of states */
  408.   for (i=result_len=max_length=0 , states=2 ; i < count ; i++)
  409.   {
  410.     len=replace_len(from[i]);
  411.     if (!len)
  412.     {
  413.       errno=EINVAL;
  414.       my_message(0,"No to-string for last from-string",MYF(ME_BELL));
  415.       DBUG_RETURN(0);
  416.     }
  417.     states+=len+1;
  418.     result_len+=(uint) strlen(to[i])+1;
  419.     if (len > max_length)
  420.       max_length=len;
  421.   }
  422.   bzero((char*) is_word_end,sizeof(is_word_end));
  423.   for (i=0 ; word_end_chars[i] ; i++)
  424.     is_word_end[(uchar) word_end_chars[i]]=1;
  425.  
  426.   if (init_sets(&sets,states))
  427.     DBUG_RETURN(0);
  428.   found_sets=0;
  429.   if (!(found_set= (FOUND_SET*) my_malloc(sizeof(FOUND_SET)*max_length*count,
  430.                       MYF(MY_WME))))
  431.   {
  432.     free_sets(&sets);
  433.     DBUG_RETURN(0);
  434.   }
  435.   VOID(make_new_set(&sets));            /* Set starting set */
  436.   make_sets_invisible(&sets);            /* Hide previus sets */
  437.   used_sets=-1;
  438.   word_states=make_new_set(&sets);        /* Start of new word */
  439.   start_states=make_new_set(&sets);        /* This is first state */
  440.   if (!(follow=(FOLLOWS*) my_malloc((states+2)*sizeof(FOLLOWS),MYF(MY_WME))))
  441.   {
  442.     free_sets(&sets);
  443.     my_free((gptr) found_set,MYF(0));
  444.     DBUG_RETURN(0);
  445.   }
  446.  
  447.     /* Init follow_ptr[] */
  448.   for (i=0, states=1, follow_ptr=follow+1 ; i < count ; i++)
  449.   {
  450.     if (from[i][0] == '\\' && from[i][1] == '^')
  451.     {
  452.       set_bit(start_states,states+1);
  453.       if (!from[i][2])
  454.       {
  455.     start_states->table_offset=i;
  456.     start_states->found_offset=1;
  457.       }
  458.     }
  459.     else if (from[i][0] == '\\' && from[i][1] == '$')
  460.     {
  461.       set_bit(start_states,states);
  462.       set_bit(word_states,states);
  463.       if (!from[i][2] && start_states->table_offset == (uint) ~0)
  464.       {
  465.     start_states->table_offset=i;
  466.     start_states->found_offset=0;
  467.       }
  468.     }
  469.     else
  470.     {
  471.       set_bit(word_states,states);
  472.       if (from[i][0] == '\\' && (from[i][1] == 'b' && from[i][2]))
  473.     set_bit(start_states,states+1);
  474.       else
  475.     set_bit(start_states,states);
  476.     }
  477.     for (pos=from[i], len=0; *pos ; pos++)
  478.     {
  479.       if (*pos == '\\' && *(pos+1))
  480.       {
  481.     pos++;
  482.     switch (*pos) {
  483.     case 'b':
  484.       follow_ptr->chr = SPACE_CHAR;
  485.       break;
  486.     case '^':
  487.       follow_ptr->chr = START_OF_LINE;
  488.       break;
  489.     case '$':
  490.       follow_ptr->chr = END_OF_LINE;
  491.       break;
  492.     case 'r':
  493.       follow_ptr->chr = '\r';
  494.       break;
  495.     case 't':
  496.       follow_ptr->chr = '\t';
  497.       break;
  498.     case 'v':
  499.       follow_ptr->chr = '\v';
  500.       break;
  501.     default:
  502.       follow_ptr->chr = (uchar) *pos;
  503.       break;
  504.     }
  505.       }
  506.       else
  507.     follow_ptr->chr= (uchar) *pos;
  508.       follow_ptr->table_offset=i;
  509.       follow_ptr->len= ++len;
  510.       follow_ptr++;
  511.     }
  512.     follow_ptr->chr=0;
  513.     follow_ptr->table_offset=i;
  514.     follow_ptr->len=len;
  515.     follow_ptr++;
  516.     states+=(uint) len+1;
  517.   }
  518.  
  519.  
  520.   for (set_nr=0,pos=0 ; set_nr < sets.count ; set_nr++)
  521.   {
  522.     set=sets.set+set_nr;
  523.     default_state= 0;                /* Start from beginning */
  524.  
  525.     /* If end of found-string not found or start-set with current set */
  526.  
  527.     for (i= (uint) ~0; (i=get_next_bit(set,i)) ;)
  528.     {
  529.       if (!follow[i].chr)
  530.       {
  531.     if (! default_state)
  532.       default_state= find_found(found_set,set->table_offset,
  533.                     set->found_offset+1);
  534.       }
  535.     }
  536.     copy_bits(sets.set+used_sets,set);        /* Save set for changes */
  537.     if (!default_state)
  538.       or_bits(sets.set+used_sets,sets.set);    /* Can restart from start */
  539.  
  540.     /* Find all chars that follows current sets */
  541.     bzero((char*) used_chars,sizeof(used_chars));
  542.     for (i= (uint) ~0; (i=get_next_bit(sets.set+used_sets,i)) ;)
  543.     {
  544.       used_chars[follow[i].chr]=1;
  545.       if ((follow[i].chr == SPACE_CHAR && !follow[i+1].chr &&
  546.        follow[i].len > 1) || follow[i].chr == END_OF_LINE)
  547.     used_chars[0]=1;
  548.     }
  549.  
  550.     /* Mark word_chars used if \b is in state */
  551.     if (used_chars[SPACE_CHAR])
  552.       for (pos= word_end_chars ; *pos ; pos++)
  553.     used_chars[(int) (uchar) *pos] = 1;
  554.  
  555.     /* Handle other used characters */
  556.     for (chr= 0 ; chr < 256 ; chr++)
  557.     {
  558.       if (! used_chars[chr])
  559.     set->next[chr]= chr ? default_state : -1;
  560.       else
  561.       {
  562.     new_set=make_new_set(&sets);
  563.     set=sets.set+set_nr;            /* if realloc */
  564.     new_set->table_offset=set->table_offset;
  565.     new_set->found_len=set->found_len;
  566.     new_set->found_offset=set->found_offset+1;
  567.     found_end=0;
  568.  
  569.     for (i= (uint) ~0 ; (i=get_next_bit(sets.set+used_sets,i)) ; )
  570.     {
  571.       if (!follow[i].chr || follow[i].chr == chr ||
  572.           (follow[i].chr == SPACE_CHAR &&
  573.            (is_word_end[chr] ||
  574.         (!chr && follow[i].len > 1 && ! follow[i+1].chr))) ||
  575.           (follow[i].chr == END_OF_LINE && ! chr))
  576.       {
  577.         if ((! chr || (follow[i].chr && !follow[i+1].chr)) &&
  578.         follow[i].len > found_end)
  579.           found_end=follow[i].len;
  580.         if (chr && follow[i].chr)
  581.           set_bit(new_set,i+1);        /* To next set */
  582.         else
  583.           set_bit(new_set,i);
  584.       }
  585.     }
  586.     if (found_end)
  587.     {
  588.       new_set->found_len=0;            /* Set for testing if first */
  589.       bits_set=0;
  590.       for (i= (uint) ~0; (i=get_next_bit(new_set,i)) ;)
  591.       {
  592.         if ((follow[i].chr == SPACE_CHAR ||
  593.          follow[i].chr == END_OF_LINE) && ! chr)
  594.           bit_nr=i+1;
  595.         else
  596.           bit_nr=i;
  597.         if (follow[bit_nr-1].len < found_end ||
  598.         (new_set->found_len &&
  599.          (chr == 0 || !follow[bit_nr].chr)))
  600.           clear_bit(new_set,i);
  601.         else
  602.         {
  603.           if (chr == 0 || !follow[bit_nr].chr)
  604.           {                    /* best match  */
  605.         new_set->table_offset=follow[bit_nr].table_offset;
  606.         if (chr || (follow[i].chr == SPACE_CHAR ||
  607.                 follow[i].chr == END_OF_LINE))
  608.           new_set->found_offset=found_end;    /* New match */
  609.         new_set->found_len=found_end;
  610.           }
  611.           bits_set++;
  612.         }
  613.       }
  614.       if (bits_set == 1)
  615.       {
  616.         set->next[chr] = find_found(found_set,
  617.                     new_set->table_offset,
  618.                     new_set->found_offset);
  619.         free_last_set(&sets);
  620.       }
  621.       else
  622.         set->next[chr] = find_set(&sets,new_set);
  623.     }
  624.     else
  625.       set->next[chr] = find_set(&sets,new_set);
  626.       }
  627.     }
  628.   }
  629.  
  630.     /* Alloc replace structure for the replace-state-machine */
  631.  
  632.   if ((replace=(REPLACE*) my_malloc(sizeof(REPLACE)*(sets.count)+
  633.                     sizeof(REPLACE_STRING)*(found_sets+1)+
  634.                     sizeof(my_string)*count+result_len,
  635.                     MYF(MY_WME | MY_ZEROFILL))))
  636.   {
  637.     rep_str=(REPLACE_STRING*) (replace+sets.count);
  638.     to_array=(my_string*) (rep_str+found_sets+1);
  639.     to_pos=(my_string) (to_array+count);
  640.     for (i=0 ; i < count ; i++)
  641.     {
  642.       to_array[i]=to_pos;
  643.       to_pos=strmov(to_pos,to[i])+1;
  644.     }
  645.     rep_str[0].found=1;
  646.     rep_str[0].replace_string=0;
  647.     for (i=1 ; i <= found_sets ; i++)
  648.     {
  649.       pos=from[found_set[i-1].table_offset];
  650.       rep_str[i].found= !bcmp(pos,"\\^",3) ? 2 : 1;
  651.       rep_str[i].replace_string=to_array[found_set[i-1].table_offset];
  652.       rep_str[i].to_offset=found_set[i-1].found_offset-start_at_word(pos);
  653.       rep_str[i].from_offset=found_set[i-1].found_offset-replace_len(pos)+
  654.     end_of_word(pos);
  655.     }
  656.     for (i=0 ; i < sets.count ; i++)
  657.     {
  658.       for (j=0 ; j < 256 ; j++)
  659.     if (sets.set[i].next[j] >= 0)
  660.       replace[i].next[j]=replace+sets.set[i].next[j];
  661.     else
  662.       replace[i].next[j]=(REPLACE*) (rep_str+(-sets.set[i].next[j]-1));
  663.     }
  664.   }
  665.   my_free((gptr) follow,MYF(0));
  666.   free_sets(&sets);
  667.   my_free((gptr) found_set,MYF(0));
  668.   DBUG_PRINT("exit",("Replace table has %d states",sets.count));
  669.   DBUG_RETURN(replace);
  670. }
  671.  
  672.  
  673. static int init_sets(REP_SETS *sets,uint states)
  674. {
  675.   bzero((char*) sets,sizeof(*sets));
  676.   sets->size_of_bits=((states+7)/8);
  677.   if (!(sets->set_buffer=(REP_SET*) my_malloc(sizeof(REP_SET)*SET_MALLOC_HUNC,
  678.                           MYF(MY_WME))))
  679.     return 1;
  680.   if (!(sets->bit_buffer=(uint*) my_malloc(sizeof(uint)*sets->size_of_bits*
  681.                        SET_MALLOC_HUNC,MYF(MY_WME))))
  682.   {
  683.     my_free((gptr) sets->set,MYF(0));
  684.     return 1;
  685.   }
  686.   return 0;
  687. }
  688.  
  689.     /* Make help sets invisible for nicer codeing */
  690.  
  691. static void make_sets_invisible(REP_SETS *sets)
  692. {
  693.   sets->invisible=sets->count;
  694.   sets->set+=sets->count;
  695.   sets->count=0;
  696. }
  697.  
  698. static REP_SET *make_new_set(REP_SETS *sets)
  699. {
  700.   uint i,count,*bit_buffer;
  701.   REP_SET *set;
  702.   if (sets->extra)
  703.   {
  704.     sets->extra--;
  705.     set=sets->set+ sets->count++;
  706.     bzero((char*) set->bits,sizeof(uint)*sets->size_of_bits);
  707.     bzero((char*) &set->next[0],sizeof(set->next[0])*LAST_CHAR_CODE);
  708.     set->found_offset=0;
  709.     set->found_len=0;
  710.     set->table_offset= (uint) ~0;
  711.     set->size_of_bits=sets->size_of_bits;
  712.     return set;
  713.   }
  714.   count=sets->count+sets->invisible+SET_MALLOC_HUNC;
  715.   if (!(set=(REP_SET*) my_realloc((gptr) sets->set_buffer,
  716.                    sizeof(REP_SET)*count,
  717.                   MYF(MY_WME))))
  718.     return 0;
  719.   sets->set_buffer=set;
  720.   sets->set=set+sets->invisible;
  721.   if (!(bit_buffer=(uint*) my_realloc((gptr) sets->bit_buffer,
  722.                       (sizeof(uint)*sets->size_of_bits)*count,
  723.                       MYF(MY_WME))))
  724.     return 0;
  725.   sets->bit_buffer=bit_buffer;
  726.   for (i=0 ; i < count ; i++)
  727.   {
  728.     sets->set_buffer[i].bits=bit_buffer;
  729.     bit_buffer+=sets->size_of_bits;
  730.   }
  731.   sets->extra=SET_MALLOC_HUNC;
  732.   return make_new_set(sets);
  733. }
  734.  
  735. static void free_last_set(REP_SETS *sets)
  736. {
  737.   sets->count--;
  738.   sets->extra++;
  739.   return;
  740. }
  741.  
  742. static void free_sets(REP_SETS *sets)
  743. {
  744.   my_free((gptr)sets->set_buffer,MYF(0));
  745.   my_free((gptr)sets->bit_buffer,MYF(0));
  746.   return;
  747. }
  748.  
  749. static void set_bit(REP_SET *set, uint bit)
  750. {
  751.   set->bits[bit / WORD_BIT] |= 1 << (bit % WORD_BIT);
  752.   return;
  753. }
  754.  
  755. static void clear_bit(REP_SET *set, uint bit)
  756. {
  757.   set->bits[bit / WORD_BIT] &= ~ (1 << (bit % WORD_BIT));
  758.   return;
  759. }
  760.  
  761.  
  762. static void or_bits(REP_SET *to,REP_SET *from)
  763. {
  764.   reg1 uint i;
  765.   for (i=0 ; i < to->size_of_bits ; i++)
  766.     to->bits[i]|=from->bits[i];
  767.   return;
  768. }
  769.  
  770. static void copy_bits(REP_SET *to,REP_SET *from)
  771. {
  772.   memcpy((byte*) to->bits,(byte*) from->bits,
  773.      (size_t) (sizeof(uint) * to->size_of_bits));
  774. }
  775.  
  776. static int cmp_bits(REP_SET *set1,REP_SET *set2)
  777. {
  778.   return bcmp((byte*) set1->bits,(byte*) set2->bits,
  779.           sizeof(uint) * set1->size_of_bits);
  780. }
  781.  
  782.  
  783.     /* Get next set bit from set. */
  784.  
  785. static int get_next_bit(REP_SET *set,uint lastpos)
  786. {
  787.   uint pos,*start,*end,bits;
  788.  
  789.   start=set->bits+ ((lastpos+1) / WORD_BIT);
  790.   end=set->bits + set->size_of_bits;
  791.   bits=start[0] & ~((1 << ((lastpos+1) % WORD_BIT)) -1);
  792.  
  793.   while (! bits && ++start < end)
  794.     bits=start[0];
  795.   if (!bits)
  796.     return 0;
  797.   pos=(uint) (start-set->bits)*WORD_BIT;
  798.   while (! (bits & 1))
  799.   {
  800.     bits>>=1;
  801.     pos++;
  802.   }
  803.   return pos;
  804. }
  805.  
  806.     /* find if there is a same set in sets. If there is, use it and
  807.        free given set, else put in given set in sets and return it's
  808.        position */
  809.  
  810. static int find_set(REP_SETS *sets,REP_SET *find)
  811. {
  812.   uint i;
  813.   for (i=0 ; i < sets->count-1 ; i++)
  814.   {
  815.     if (!cmp_bits(sets->set+i,find))
  816.     {
  817.       free_last_set(sets);
  818.       return i;
  819.     }
  820.   }
  821.   return i;                /* return new postion */
  822. }
  823.  
  824.     /* find if there is a found_set with same table_offset & found_offset
  825.        If there is return offset to it, else add new offset and return pos.
  826.        Pos returned is -offset-2 in found_set_structure because it's is
  827.        saved in set->next and set->next[] >= 0 points to next set and
  828.        set->next[] == -1 is reserved for end without replaces.
  829.        */
  830.  
  831. static int find_found(FOUND_SET *found_set,uint table_offset, int found_offset)
  832. {
  833.   int i;
  834.   for (i=0 ; (uint) i < found_sets ; i++)
  835.     if (found_set[i].table_offset == table_offset &&
  836.     found_set[i].found_offset == found_offset)
  837.       return -i-2;
  838.   found_set[i].table_offset=table_offset;
  839.   found_set[i].found_offset=found_offset;
  840.   found_sets++;
  841.   return -i-2;                /* return new postion */
  842. }
  843.  
  844.     /* Return 1 if regexp starts with \b or ends with \b*/
  845.  
  846. static uint start_at_word(my_string pos)
  847. {
  848.   return (((!bcmp(pos,"\\b",2) && pos[2]) || !bcmp(pos,"\\^",2)) ? 1 : 0);
  849. }
  850.  
  851. static uint end_of_word(my_string pos)
  852. {
  853.   my_string end=strend(pos);
  854.   return ((end > pos+2 && !bcmp(end-2,"\\b",2)) ||
  855.       (end >= pos+2 && !bcmp(end-2,"\\$",2))) ?
  856.         1 : 0;
  857. }
  858.  
  859.  
  860. static uint replace_len(my_string str)
  861. {
  862.   uint len=0;
  863.   while (*str)
  864.   {
  865.     if (str[0] == '\\' && str[1])
  866.       str++;
  867.     str++;
  868.     len++;
  869.   }
  870.   return len;
  871. }
  872.  
  873.  
  874.     /* The actual loop */
  875.  
  876. uint replace_strings(REPLACE *rep, my_string *start,uint *max_length, my_string from)
  877. {
  878.   reg1 REPLACE *rep_pos;
  879.   reg2 REPLACE_STRING *rep_str;
  880.   my_string to,end,pos,new;
  881.  
  882.   end=(to= *start) + *max_length-1;
  883.   rep_pos=rep+1;
  884.   for(;;)
  885.   {
  886.     while (!rep_pos->found)
  887.     {
  888.       rep_pos= rep_pos->next[(uchar) *from];
  889.       if (to == end)
  890.       {
  891.     (*max_length)+=8192;
  892.     if (!(new=my_realloc(*start,*max_length,MYF(MY_WME))))
  893.       return (uint) -1;
  894.     to=new+(to - *start);
  895.     end=(*start=new)+ *max_length-1;
  896.       }
  897.       *to++= *from++;
  898.     }
  899.     if (!(rep_str = ((REPLACE_STRING*) rep_pos))->replace_string)
  900.       return (uint) (to - *start)-1;
  901.     updated=1;            /* Some my_string is replaced */
  902.     to-=rep_str->to_offset;
  903.     for (pos=rep_str->replace_string; *pos ; pos++)
  904.     {
  905.       if (to == end)
  906.       {
  907.     (*max_length)*=2;
  908.     if (!(new=my_realloc(*start,*max_length,MYF(MY_WME))))
  909.       return (uint) -1;
  910.     to=new+(to - *start);
  911.     end=(*start=new)+ *max_length-1;
  912.       }
  913.       *to++= *pos;
  914.     }
  915.     if (!*(from-=rep_str->from_offset) && rep_pos->found != 2)
  916.       return (uint) (to - *start);
  917.     rep_pos=rep;
  918.   }
  919. }
  920.  
  921. static char *buffer;        /* The buffer itself, grown as needed. */
  922. static int bufbytes;        /* Number of bytes in the buffer. */
  923. static int bufread,my_eof;        /* Number of bytes to get with each read(). */
  924. static uint bufalloc;
  925. static char *out_buff;
  926. static uint out_length;
  927.  
  928. static int initialize_buffer()
  929. {
  930.   bufread = 8192;
  931.   bufalloc = bufread + bufread / 2;
  932.   if (!(buffer = my_malloc(bufalloc+1,MYF(MY_WME))))
  933.     return 1;
  934.   bufbytes=my_eof=0;
  935.   out_length=bufread;
  936.   if (!(out_buff=my_malloc(out_length,MYF(MY_WME))))
  937.     return(1);
  938.   return 0;
  939. }
  940.  
  941. static void reset_buffer()
  942. {
  943.   bufbytes=my_eof=0;
  944. }
  945.  
  946. static void free_buffer()
  947. {
  948.   my_free(buffer,MYF(MY_WME));
  949.   my_free(out_buff,MYF(MY_WME));
  950. }
  951.  
  952.  
  953. /* Fill the buffer retaining the last n bytes at the beginning of the
  954.    newly filled buffer (for backward context).  Returns the number of new
  955.    bytes read from disk. */
  956.  
  957. static int fill_buffer_retaining(fd,n)
  958. File fd;
  959. int n;
  960. {
  961.   int i;
  962.  
  963.   /* See if we need to grow the buffer. */
  964.   if ((int) bufalloc - n <= bufread)
  965.   {
  966.     while ((int) bufalloc - n <= bufread)
  967.     {
  968.       bufalloc *= 2;
  969.       bufread *= 2;
  970.     }
  971.     buffer = my_realloc(buffer, bufalloc+1, MYF(MY_WME));
  972.     if (! buffer)
  973.       return(-1);
  974.   }
  975.  
  976.   /* Shift stuff down. */
  977.   bmove(buffer,buffer+bufbytes-n,(uint) n);
  978.   bufbytes = n;
  979.  
  980.   if (my_eof)
  981.     return 0;
  982.  
  983.   /* Read in new stuff. */
  984.   if ((i=(int) my_read(fd, buffer + bufbytes, (uint) bufread,MYF(MY_WME))) < 0)
  985.     return -1;
  986.  
  987.   /* Kludge to pretend every nonempty file ends with a newline. */
  988.   if (i == 0 && bufbytes > 0 && buffer[bufbytes - 1] != '\n')
  989.   {
  990.     my_eof = i = 1;
  991.     buffer[bufbytes] = '\n';
  992.   }
  993.  
  994.   bufbytes += i;
  995.   return i;
  996. }
  997.  
  998.     /* Return 0 if convert is ok */
  999.     /* Global variable update is set if something was changed */
  1000.  
  1001. static int convert_pipe(rep,in,out)
  1002. REPLACE *rep;
  1003. FILE *in,*out;
  1004. {
  1005.   int retain,error;
  1006.   uint length;
  1007.   char save_char,*end_of_line,*start_of_line;
  1008.   DBUG_ENTER("convert_pipe");
  1009.  
  1010.   updated=retain=0;
  1011.   reset_buffer();
  1012.  
  1013.   while ((error=fill_buffer_retaining(fileno(in),retain)) > 0)
  1014.   {
  1015.     end_of_line=buffer ;
  1016.     buffer[bufbytes]=0;            /* Sentinel  */
  1017.     for (;;)
  1018.     {
  1019.       start_of_line=end_of_line;
  1020.       while (end_of_line[0] != '\n' && end_of_line[0])
  1021.     end_of_line++;
  1022.       if (end_of_line == buffer+bufbytes)
  1023.       {
  1024.     retain= (int) (end_of_line - start_of_line);
  1025.     break;                /* No end of line, read more */
  1026.       }
  1027.       save_char=end_of_line[0];
  1028.       end_of_line[0]=0;
  1029.       end_of_line++;
  1030.       if ((length=replace_strings(rep,&out_buff,&out_length,start_of_line)) ==
  1031.       (uint) -1)
  1032.     return 1;
  1033.       if (!my_eof)
  1034.     out_buff[length++]=save_char;    /* Don't write added newline */
  1035.       if (my_fwrite(out,out_buff,length,MYF(MY_WME | MY_NABP)))
  1036.     DBUG_RETURN(1);
  1037.     }
  1038.   }
  1039.   DBUG_RETURN(error);
  1040. }
  1041.  
  1042.  
  1043. static int convert_file(rep,name)
  1044. REPLACE *rep;
  1045. my_string name;
  1046. {
  1047.   int error;
  1048.   FILE *in,*out;
  1049.   char dir_buff[FN_REFLEN],*tempname;
  1050.   DBUG_ENTER("convert_file");
  1051.  
  1052.   if (!(in=my_fopen(name,O_RDONLY,MYF(MY_WME))))
  1053.     DBUG_RETURN(1);
  1054.   dirname_part(dir_buff,name);
  1055.   tempname=my_tempnam(dir_buff,"PR",MYF(MY_WME));
  1056.   if (!(out=my_fopen(tempname,(int) (O_WRONLY | O_CREAT),
  1057.              MYF(MY_WME))))
  1058.   {
  1059.     (*free)(tempname);
  1060.     my_fclose(in,MYF(0));
  1061.     DBUG_RETURN(1);
  1062.   }
  1063.  
  1064.   error=convert_pipe(rep,in,out);
  1065.   my_fclose(in,MYF(0)); my_fclose(out,MYF(0));
  1066.  
  1067.   if (updated && ! error)
  1068.     my_redel(name,tempname,MYF(MY_WME | MY_LINK_WARNING));
  1069.   else
  1070.     my_delete(tempname,MYF(MY_WME));
  1071.   (*free)(tempname);
  1072.   if (!silent && ! error)
  1073.   {
  1074.     if (updated)
  1075.       printf("%s converted\n",name);
  1076.     else if (verbose)
  1077.       printf("%s left unchanged\n",name);
  1078.   }
  1079.   DBUG_RETURN(error);
  1080. }
  1081.