home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / program / 619 / strsed / strsed.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-05  |  37.0 KB  |  1,360 lines
  1. #ifndef lint
  2. static char *rcsid = "$Header: h:/tmp/tmp/strsed\\RCS\\strsed.c,v 1.17 1990/03/08 20:44:32 terry Exp $";
  3. #endif lint
  4.  
  5. /*
  6.  * Strsed.c
  7.  *
  8.  *     ed(1)/tr(1)-like search, replace, transliterate. See the
  9.  *     manpage for details.
  10.  *
  11.  * Usage:
  12.  *
  13.  *        strsed(string, pattern, 0);
  14.  *        char *string;
  15.  *        char *pattern;
  16.  * or
  17.  *        strsed(string, pattern, range);
  18.  *        char *string;
  19.  *        char *pattern;
  20.  *        int  range[2];
  21.  *
  22.  *
  23.  * Terry Jones    
  24.  * terry@distel.pcs.com
  25.  * ...!{pyramid,unido}!pcsbst!distel!terry
  26.  *
  27.  * PCS Computer Systeme GmbH
  28.  * Pfaelzer-Wald-Str 36
  29.  * 8000 Muenchen 90
  30.  * West Germany       49-89-68004288
  31.  *
  32.  * January 8th, 1990.
  33.  *
  34.  */
  35.  
  36. /*
  37.  * $Log: strsed.c,v $
  38.  * Revision 1.17  90/03/08  20:44:32  terry
  39.  * Final cleanup.
  40.  * 
  41.  * Revision 1.16  90/03/07  15:46:35  terry
  42.  * Changed backslash_eliminate to only malloc on 
  43.  * REPLACEMENT type. Added ".*" optimisation so that
  44.  * the regex functions are never called.
  45.  * 
  46.  * Revision 1.15  90/03/06  22:27:49  terry
  47.  * Removed varargs stuff since the 3rd argument is now 
  48.  * compulsory. Cleaned up. A few comments even.
  49.  * 
  50.  * Revision 1.14  90/03/06  21:50:28  terry
  51.  * Touched up memory stuff. Added mem_find(). Changed
  52.  * buf_sz and buf_inc to be a reasonable refelection
  53.  * of the length of the input.
  54.  * 
  55.  * Revision 1.13  90/03/06  20:22:48  terry
  56.  * Major rearrangements. Added mem(), mem_init(), mem_save(),
  57.  * mem_free() to handle memory in a vastly improved fashion.
  58.  * Calls to malloc are minimised as far as possible.
  59.  * 
  60.  * Revision 1.12  90/03/06  13:23:33  terry
  61.  * Made map static.
  62.  * 
  63.  * Revision 1.11  90/01/10  15:51:12  terry
  64.  * checked in with -k by terry at 90.01.18.20.03.08.
  65.  * 
  66.  * Revision 1.11  90/01/10  15:51:12  terry
  67.  * *** empty log message ***
  68.  * 
  69.  * Revision 1.10  90/01/10  12:48:40  terry
  70.  * Fixed handling of perverted character ranges in nextch().
  71.  * a-f-c now means a-c.
  72.  * 
  73.  * Revision 1.9  90/01/10  12:03:48  terry
  74.  * Pounded on space allocation, added more_space,
  75.  * remove free() in build_map, tested tiny buffer sizes etc.
  76.  * 
  77.  * Revision 1.8  90/01/09  18:15:12  terry
  78.  * added backslash elimination to str.
  79.  * altered backslash_elimantion to take one of three types
  80.  * REGEX, NORMAL or REPLACEMENT depending on the
  81.  * elimination desired. Changed interpretation of \ 
  82.  * followed by a single digit to be that character if the
  83.  * type of elimination is NORMAL. i.e. \4 = ^D.
  84.  * 
  85.  * Revision 1.7  90/01/09  17:05:05  terry
  86.  * Frozen version for release to comp.sources.unix
  87.  * 
  88.  * Revision 1.6  90/01/09  16:47:54  terry
  89.  * Altered pure searching return values to be -1
  90.  * 
  91.  * Revision 1.5  90/01/09  14:54:34  terry
  92.  * *** empty log message ***
  93.  * 
  94.  * Revision 1.4  90/01/09  14:51:04  terry
  95.  * removed #include <stdio> silliness.
  96.  * 
  97.  * Revision 1.2  90/01/09  10:48:22  terry
  98.  * Fixed handling of } and - metacharacters inside
  99.  * transliteration request strings in backslash_eliminate().
  100.  * 
  101.  * Revision 1.1  90/01/08  17:41:35  terry
  102.  * Initial revision
  103.  * 
  104.  *
  105.  */
  106.  
  107. #include <ctype.h>
  108. #include <string.h>
  109. #ifdef __GNUC__
  110. #include <stdlib.h>
  111. #else
  112. #include <malloc.h>
  113. #endif
  114. #include "regex.h"
  115.  
  116. #define BYTEWIDTH     8
  117. #define REGEX         0
  118. #define REPLACEMENT   1
  119. #define NORMAL        2
  120.  
  121. /*
  122.  * And this is supposed to make freeing easier. It's a little hard to
  123.  * keep track of what can and cannot be freed in what follows, so I
  124.  * ignore it and every time a malloc is done for one of the things
  125.  * below (and these are the only ones possible) we free if need be and
  126.  * then alloc some more if it can't be avoided. No-one (who is going 
  127.  * to free) needs to call malloc then. And no-one need call free. 
  128.  * Wonderful in theory...
  129.  */
  130.  
  131. #define MEM_STR       0
  132. #define MEM_PAT       1
  133. #define MEM_FROM      2
  134. #define MEM_TO        3
  135. #define MEM_NEWSTR    4
  136. #define MEM_MAP       5
  137. #define MEM_MAP_SAVE  6
  138.  
  139. #define MEM_SLOTS     7
  140.  
  141. /*
  142.  * This calls mem_free(), which free()s all the allocated storage EXCEPT
  143.  * for the piece whose address is 'n'. If something goes wrong below
  144.  * we call RETURN(0) and if we want to return some address we call RETURN
  145.  * with the address to be returned.
  146.  */
  147.  
  148. #define RETURN(n)     \
  149.     mem_free(n);      \
  150.     return (char *)n;
  151.  
  152. static struct {
  153.     char *s;
  154.     int size;
  155.     int used;
  156. } mem_slots[MEM_SLOTS];
  157.  
  158.  
  159. #define more_space(need)                                                   \
  160.     if (need && space != -1){                                              \
  161.         if (space - (need) < 0){                                           \
  162.             buf_sz += buf_inc + (need) - space;                            \
  163.             if (!(new_str = (char *)realloc(new_str, (unsigned)buf_sz))){  \
  164.                 RETURN(0);                                                 \
  165.             }                                                              \
  166.         mem_slots[MEM_NEWSTR].s = new_str;                             \
  167.         mem_slots[MEM_NEWSTR].size = buf_sz;                           \
  168.             space = buf_inc;                                               \
  169.         }                                                                  \
  170.         else{                                                              \
  171.             space -= need;                                                 \
  172.         }                                                                  \
  173.     }
  174.  
  175.  
  176. char *
  177. strsed(string, pattern, range)
  178. register char *string;
  179. register char *pattern;
  180. int *range;
  181. {
  182.     extern char *re_compile_pattern();
  183.     extern int re_search();
  184.  
  185.     static char *backslash_eliminate();
  186.     static char *mem();
  187.     static void mem_init();
  188.     static void mem_free();
  189.     
  190.     char *from;
  191.     char *new_str;
  192.     char *pat;
  193.     char *str;
  194.     char *tmp;
  195.     char *to;
  196.     static char map[1 << BYTEWIDTH];
  197.     int buf_sz;
  198.     int buf_inc;
  199.     int global = 0;
  200.     int match;
  201.     int new_pos = 0;
  202.     int search_only = 0;
  203.     int seenbs = 0;
  204.     int space;
  205.     int match_all = 0;
  206.     register int str_len;
  207.     static int first_time = 1;
  208.     static struct re_pattern_buffer re_comp_buf;
  209.     struct re_registers regs;
  210.  
  211.     if (!string || !pattern){
  212.         RETURN(0);
  213.     }
  214.     
  215.     /*
  216.      * If this is the first time we've been called, clear the memory slots.
  217.      */
  218.     if (first_time){
  219.     mem_init();
  220.     }
  221.  
  222.     /*
  223.      * Take our own copies of the string and pattern since we promised
  224.      * in the man page not to hurt the originals.
  225.      */
  226.     str = mem(MEM_STR, strlen(string) + 1);
  227.     str[0] = '\0';
  228.     strcat(str, string);
  229.     pat = mem(MEM_PAT, strlen(pattern) + 1);
  230.     pat[0] = '\0';
  231.     strcat(pat, pattern);
  232.  
  233.     /*
  234.      * If escape sequences are not already removed elsewhere, remove
  235.      * them from the string. If you don't know what you're doing here
  236.      * or are in any doubt, don't define ESCAPED_STRING.
  237.      */
  238. #ifndef ESCAPED_STRING
  239.     if (!(str = backslash_eliminate(str, NORMAL, MEM_STR))){
  240.         RETURN(0);
  241.     }
  242. #endif
  243.  
  244.     str_len = strlen(str);
  245.     
  246.     /*
  247.      * Set up the size of our buffer (in which we build the
  248.      * newstring, and the size by which we increment it when
  249.      * (and if) the need arises. There shouldn't be too much
  250.      * growth in the average case. Of course some people will
  251.      * go and do things like 
  252.      *
  253.      * strsed(string, "s/.*$/\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0")
  254.      *
  255.      * and they will be somewhat penalised. Oh well.
  256.      *
  257.      */
  258.  
  259.     buf_sz = str_len < 8 ? 16 : str_len << 1;
  260.     buf_inc = buf_sz;
  261.  
  262.     /*
  263.      * Get the action. 
  264.      * s = substitue and g = global.
  265.      * anything else is invalid.
  266.      *
  267.      */
  268.     while (*pat && *pat != '/'){
  269.         switch (*pat){
  270.             case 'g':{
  271.                 global = 1;
  272.                 break;
  273.             }
  274.             case 's':{
  275.                 break;
  276.             }
  277.             default:{
  278.                 RETURN(0);
  279.             }
  280.         }
  281.         pat++;
  282.     }
  283.  
  284.     if (!*pat){
  285.         RETURN(0);
  286.     }
  287.  
  288.     pat++;
  289.  
  290.     /*
  291.      * Now split 'pat' into its two components. These are delimited (or
  292.      * should be) by (unquoted) '/'. The first we point to with 'from' 
  293.      * and the second with 'to'. 
  294.      *
  295.      * Someone should write a function to make this sort of thing trivial...
  296.      *
  297.      */
  298.     
  299.     from = to = pat;
  300.  
  301.     while (*to){
  302.         if (seenbs){
  303.             seenbs = 0;
  304.         }
  305.         else{
  306.             if (*to == '\\'){
  307.                 seenbs = 1;
  308.             }
  309.             else if (*to == '/'){
  310.                 break;
  311.             }
  312.         }
  313.         to++;
  314.     }
  315.  
  316.     if (!*to){
  317.         RETURN(0);
  318.     }
  319.  
  320.     *to++ = '\0';
  321.  
  322.     if (*to){
  323.         tmp = to + strlen(to) - 1;
  324.  
  325.         /*
  326.          * Back up to the last non-whitespace char in 'to'
  327.          *
  328.          */
  329.  
  330.         while (*tmp == ' ' || *tmp == '\t'){
  331.             tmp--;
  332.         }
  333.  
  334.         /*
  335.          * Make sure that, if there was a character,
  336.          * that it was a / and wasn't preceded by \.
  337.          *
  338.         */
  339.  
  340.         if (*tmp && !(*tmp = '/' && *(tmp - 1) != '\\')){
  341.             RETURN(0);
  342.         }
  343.  
  344.         *tmp = '\0';
  345.     }
  346.     else{
  347.         /*
  348.      * Search only.
  349.          * It doesn't make sense to say
  350.          *
  351.          * strsed(string, "g/abc/", range)
  352.          *
  353.          * because we are only searching and returning the 
  354.          * matched indexes. So turn off global (in case it's on)
  355.      * so that we will return just the first instance.
  356.      *
  357.      * If no range has been given either, then there's no
  358.      * point in going on.
  359.          *
  360.          */
  361.     
  362.     if (!range){
  363.         RETURN(0);
  364.     }
  365.     
  366.         global = 0;
  367.         search_only = 1;
  368.     }
  369.  
  370.     /*
  371.      * Eliminate backslashes and character ranges etc.
  372.      *
  373.      */
  374.  
  375.     if (!(from = backslash_eliminate(from, REGEX, MEM_FROM)) || 
  376.         !(to = backslash_eliminate(to, REPLACEMENT, MEM_TO))){
  377.         RETURN(0);
  378.     }
  379.     
  380.     /*
  381.      * If the first char of 'to' is '\0' then we are deleting or 
  382.      * searching only. We don't have to worry about space since 
  383.      * the transformed string will be less than or equal in length
  384.      * to the original. We just overwrite.
  385.      * We set space = -1 so that later on we can avoid worrying
  386.      * about overflow etc.
  387.      *
  388.      * Otherwise, we are doing a substitution. Here we have to
  389.      * worry about space because the replacement may be larger
  390.      * than the original. malloc some room and if we overflow it 
  391.      * later we will realloc. slows things down if the new string
  392.      * turns out to be too much bigger. oh well.
  393.      *
  394.      */
  395.     
  396.     if (*to){
  397.         if (!(new_str = mem(MEM_NEWSTR, buf_sz + 1))){
  398.             RETURN(0);
  399.         }
  400.         space = buf_sz;
  401.     }
  402.     else{
  403.         new_str = str;
  404.         space = -1;
  405.     }
  406.  
  407.     /*
  408.      * Do things to get ready for the regex functions.
  409.      * Don't do anything though if the regex in 'from' is ".*"
  410.      * We handle that below. (Just a special case optimisation).
  411.      *
  412.      */
  413.  
  414.     if (from[0] == '.' && from[1] == '*' && from[2] == '\0'){
  415.     register int i; 
  416.     match_all = 1;
  417.     /*
  418.      * For safety's sake, clear out the register values.
  419.      * There might be a register reference in the replacement. 
  420.      * There will be nothing in the register (since the search
  421.      * pattern was ".*"). Since we aren't calling the regex 
  422.      * stuff we can't rely on it to set these to -1.
  423.      */
  424.     for (i = 0; i < RE_NREGS; i++){
  425.         regs.start[i] = -1;
  426.     }
  427.     }
  428.     else{
  429.     if (first_time){
  430.         if (!(re_comp_buf.buffer = (char *)malloc((unsigned)200))){
  431.         RETURN(0);
  432.         }
  433.         
  434.         re_comp_buf.allocated = 200;
  435.         
  436.         if (!(re_comp_buf.fastmap = (char *)malloc((unsigned)1 << BYTEWIDTH))){
  437.         RETURN(0);
  438.         }
  439.         
  440.         first_time = 0;
  441.     }
  442.     
  443.     re_comp_buf.translate = 0;
  444.     re_comp_buf.used = 0;
  445.  
  446.     /*
  447.      * Compile the r.e. 
  448.      *
  449.      */
  450.     if (re_compile_pattern(from, strlen(from), &re_comp_buf)){
  451.         RETURN(0);
  452.     }
  453.     }
  454.     
  455.  
  456.     /*
  457.      * Now get on with the matching/replacing etc.
  458.      *
  459.      */
  460.  
  461.     do {
  462.     if (match_all){
  463.         /* Fake a match instead of calling re_search(). */
  464.         match = 1;
  465.         regs.start[0] = 0;
  466.         regs.end[0] = str_len;
  467.     }
  468.     else{
  469.         match = re_search(&re_comp_buf, str, str_len, 0, str_len, ®s);
  470.     }
  471.  
  472.         if (search_only){
  473.             /*
  474.              * Show what happened and return.
  475.              *
  476.              */
  477.         
  478.         range[0] = match == -1 ? -1 : regs.start[0];
  479.         range[1] = match == -1 ? -1 : regs.end[0];
  480.             RETURN(str);
  481.         }
  482.  
  483.         if (match != -1){
  484.  
  485.             /*
  486.              * Copy that portion that was not matched. It will
  487.              * be unchanged in the output string.
  488.              *
  489.              */
  490.             more_space(regs.start[0]);
  491.             strncpy(new_str + new_pos, str, regs.start[0]);
  492.             new_pos += regs.start[0];
  493.  
  494.             /*
  495.              * Put in the replacement text (if any).
  496.              * We substitute the contents of 'to', watching for register
  497.              * references.
  498.              */
  499.  
  500.             tmp = to;
  501.             while (*tmp){
  502.                 if (*tmp == '\\' && isdigit(*(tmp + 1))){
  503.  
  504.                     /* A register reference. */
  505.  
  506.                     register int reg = *(tmp + 1) - '0';
  507.                     int translit = 0;
  508.                     int need = regs.end[reg] - regs.start[reg];
  509.  
  510.                     /*
  511.                      * Check for a transliteration request.
  512.                      *
  513.                      */
  514.             if (*(tmp + 2) == '{'){
  515.             /* A transliteration table. Build the map. */
  516.             static char *build_map();
  517.             if (!(tmp = build_map(tmp + 2, map))){
  518.                 RETURN(0);
  519.             }
  520.             translit = 1;
  521.             }
  522.             else{
  523.             tmp += 2;
  524.             translit = 0;
  525.             }
  526.  
  527.             more_space(need);
  528.             
  529.             /*
  530.              * Copy in the register contents (if it matched), transliterating if need be.
  531.              *
  532.              */
  533.                     if (regs.start[reg] != -1){
  534.             register int i;
  535.                         for (i = regs.start[reg]; i < regs.end[reg]; i++){
  536.                             new_str[new_pos++] = translit ? map[str[i]] : str[i];
  537.                         }
  538.                     }
  539.                 }
  540.                 else{
  541.                     /* A plain character, put it in. */
  542.                     more_space(1);
  543.                     new_str[new_pos++] = *tmp++;
  544.                 }
  545.             }
  546.  
  547.             /*
  548.              * Move forward over the matched text.
  549.              *
  550.              */
  551.             str += regs.end[0];
  552.             str_len -= regs.end[0];
  553.         }
  554.     } while (global && match != -1 && *str);
  555.  
  556.     /*
  557.      * Copy the final portion of the string. This is the section that
  558.      * was not matched (and hence which remains unchanged) by the last
  559.      * match. Then we head off home.
  560.      *
  561.      */
  562.     more_space(str_len);
  563.     (void) strcpy(new_str + new_pos, str);
  564.     RETURN(new_str);
  565. }
  566.  
  567. #define DIGIT(x) (isdigit(x) ? (x) - '0' : islower(x) ? (x) + 10 - 'a' : (x) + 10 - 'A')
  568.  
  569. static char *
  570. backslash_eliminate(str, type, who)
  571. char *str;
  572. int type;
  573. int who;
  574. {
  575.     /*
  576.      * Remove backslashes from the strings. Turn \040 etc. into a single
  577.      * character (we allow eight bit values). Currently NUL is not
  578.      * allowed.
  579.      *
  580.      * Turn "\n" and "\t" into '\n' and '\t' characters. Etc.
  581.      *
  582.      * The string may grow slightly here. Under normal circumstances
  583.      * it will stay the same length or get shorter. It is only in the 
  584.      * case where we have to turn {a-z}{A-Z} into \0{a-z}{A-Z} that
  585.      * we add two chars. This only happens when we are doing a REPLACEMENT.
  586.      * So we can't overwrite str, and we have to 
  587.      * malloc. Sad, but the only ways I could find around it (at this
  588.      * late stage) were really gross. I allowed an extra 
  589.      * 100 bytes which should cover most idiotic behaviour.
  590.      * I count the extra space and exit nicely if they do do something
  591.      * extremely silly.
  592.      *
  593.      * 'i' is an index into new_str.
  594.      *
  595.      * 'type' tells us how to interpret escaped characters.
  596.      *
  597.      * type = REGEX 
  598.      *        if the pattern is a regular expression. If it is then
  599.      *        we leave escaped things alone (except for \n and \t and 
  600.      *        friends).
  601.      *
  602.      * type = REPLACEMENT
  603.      *        if this is a replacement pattern. In this case we change
  604.      *        \( and \) to ( and ), but leave \1 etc alone as they are
  605.      *        register references. - becomes a metacharacter between
  606.      *        { and }.
  607.      *
  608.      * type = NORMAL
  609.      *        We do \n and \t elimination, as well as \040 etc, plus
  610.      *        all other characters that we find quoted we unquote.
  611.      *        type = NORMAL when we do a backslash elimination on the
  612.      *        string argument to strsed.
  613.      *
  614.      * who tells us where to tell mem where to stick the new string.
  615.      *
  616.      * \{m,n\} syntax (see ed(1)) is not supported.
  617.      *
  618.      */
  619.  
  620.     static char *mem();
  621.     char *new_str;
  622.     int extra = 100;
  623.     int seenlb = 0;
  624.     register int i = 0;
  625.     register int seenbs = 0;
  626.     int first_half = 0;
  627.  
  628.     if (type == REPLACEMENT){
  629.     if (!(new_str = mem(who, strlen(str) + 1 + extra))){
  630.         return 0;
  631.     }
  632.     }
  633.     else{
  634.     new_str = str;
  635.     }
  636.  
  637.     while (*str){
  638.         if (seenbs){
  639.             seenbs = 0;
  640.             switch (*str){
  641.                 case '\\':{
  642.                     new_str[i++] = '\\';
  643.                     str++;
  644.                     break;
  645.                 }
  646.  
  647.                 case '-':{
  648.                     if (seenlb){
  649.                         /* Keep it quoted. */
  650.                         new_str[i++] = '\\';
  651.                     }
  652.                     new_str[i++] = '-';
  653.                     str++;
  654.                     break;
  655.                 }
  656.  
  657.                 case '}':{
  658.                     if (seenlb){
  659.                         /* Keep it quoted. */
  660.                         new_str[i++] = '\\';
  661.                     }
  662.                     new_str[i++] = '}';
  663.                     str++;
  664.                     break;
  665.                 }
  666.  
  667.                 case 'n':{
  668.                     new_str[i++] = '\n';
  669.                     str++;
  670.                     break;
  671.                 }
  672.  
  673.                 case 't':{
  674.                     new_str[i++] = '\t';
  675.                     str++;
  676.                     break;
  677.                 }
  678.  
  679.                 case 's':{
  680.                     new_str[i++] = ' ';
  681.                     str++;
  682.                     break;
  683.                 }
  684.  
  685.                 case 'r':{
  686.                     new_str[i++] = '\r';
  687.                     str++;
  688.                     break;
  689.                 }
  690.  
  691.                 case 'f':{
  692.                     new_str[i++] = '\f';
  693.                     str++;
  694.                     break;
  695.                 }
  696.  
  697.                 case 'b':{
  698.                     new_str[i++] = '\b';
  699.                     str++;
  700.                     break;
  701.                 }
  702.  
  703.                 case 'v':{
  704.                     new_str[i++] = '\13';
  705.                     str++;
  706.                     break;
  707.                 }
  708.  
  709.                 case 'z':{
  710.                     str++;
  711.                     break;
  712.                 }
  713.  
  714.                 case '0': case '1': case '2': case '3': case '4':
  715.                 case '5': case '6': case '7': case '8': case '9':{
  716.  
  717.                     char val;
  718.  
  719.                     /*
  720.                      * Three digit octal constant.
  721.                      *
  722.                      */
  723.                     if (*str >= '0' && *str <= '3' && 
  724.                         *(str + 1) >= '0' && *(str + 1) <= '7' &&
  725.                         *(str + 2) >= '0' && *(str + 2) <= '7'){
  726.  
  727.                         val = (DIGIT(*str) << 6) + 
  728.                               (DIGIT(*(str + 1)) << 3) + 
  729.                                DIGIT(*(str + 2));
  730.  
  731.                         if (!val){
  732.                             /*
  733.                              * NUL is not allowed.
  734.                              */
  735.                             return 0;
  736.                         }
  737.  
  738.                         new_str[i++] = val;
  739.                         str += 3;
  740.                         break;
  741.                     }
  742.  
  743.                     /*
  744.                      * One or two digit hex constant.
  745.                      * If two are there they will both be taken.
  746.                      * Use \z to split them up if this is not wanted.
  747.                      *
  748.                      */
  749.                     if (*str == '0' && (*(str + 1) == 'x' || *(str + 1) == 'X') && isxdigit(*(str + 2))){
  750.                         val = DIGIT(*(str + 2));
  751.                         if (isxdigit(*(str + 3))){
  752.                             val = (val << 4) + DIGIT(*(str + 3));
  753.                             str += 4;
  754.                         }
  755.                         else{
  756.                             str += 3;
  757.                         }
  758.  
  759.                         if (!val){
  760.                             return 0;
  761.                         }
  762.  
  763.                         new_str[i++] = val;
  764.                         break;
  765.                     }
  766.  
  767.                     /*
  768.                      * Two or three decimal digits.
  769.                      * (One decimal digit is taken as either a register reference
  770.                      * or as a decimal digit if NORMAL is true below.)
  771.                      *
  772.                      */
  773.                     if (isdigit(*(str + 1))){
  774.                         val = DIGIT(*str) * 10 + DIGIT(*(str + 1));
  775.                         if (isdigit(*(str + 2))){
  776.                             val = 10 * val + DIGIT(*(str + 2));
  777.                             str += 3;
  778.                         }
  779.                         else{
  780.                             str += 2;
  781.                         }
  782.  
  783.                         if (!val){
  784.                             return 0;
  785.                         }
  786.  
  787.                         new_str[i++] = val;
  788.                         break;
  789.                     }
  790.  
  791.                     /*
  792.                      * A register reference or else a single decimal digit if this
  793.                      * is a normal string..
  794.                      *
  795.                      * Emit \4 (etc) if we are not NORMAL (unless the digit is a 0 
  796.                      * and we are processing an r.e. This is because \0 makes no 
  797.                      * sense in an r.e., only in a replacement. If we do have \0 
  798.                      * and it is an r.e. we return.)
  799.                      *
  800.                      */
  801.                     if (*str == '0' && type == REGEX){
  802.                         return 0;
  803.                     }
  804.  
  805.                     if (type == NORMAL){
  806.                         if (!(val = DIGIT(*str))){
  807.                             return 0;
  808.                         }
  809.                         new_str[i++] = val;
  810.                         str++;
  811.                     }
  812.                     else{
  813.                         new_str[i++] = '\\';
  814.                         new_str[i++] = *str++;
  815.                     }
  816.                     break;
  817.                 }
  818.  
  819.                 default:{
  820.                     if (type == REGEX){
  821.                         new_str[i++] = '\\';
  822.                     }
  823.                     new_str[i++] = *str++;
  824.                     break;
  825.                 }
  826.             }
  827.         }
  828.         else{
  829.             if (*str == '\\'){
  830.                 seenbs = 1;
  831.                 str++;
  832.             }
  833.             else if (type == REPLACEMENT && *str == '}'){
  834.                 if (*(str + 1) == '{' && first_half){
  835.                     new_str[i++] = *str++;
  836.                     new_str[i++] = *str++;
  837.             first_half = 0;
  838.                 }
  839.                 else{
  840.                     seenlb = 0;
  841.                     new_str[i++] = *str++;
  842.                 }
  843.             }
  844.             else if (type == REPLACEMENT && !seenlb && *str == '{'){
  845.                 /*
  846.                  * Within { and }, \- should be left as such. So we can differentiate
  847.                  * between s/fred/\-/ and s/fred/{\-a-z}{+A-Z}
  848.                  *
  849.                  * We stick in a "\0" here in the case that \X has not just been
  850.                  * seen. (X = 0..9) Which is to say, {a-z}{A-Z} defaults to 
  851.                  * \0{a-z}{A-Z}
  852.                  *
  853.                  */
  854.  
  855.                 seenlb = 1;
  856.         first_half = 1;
  857.  
  858.                 if (i < 2 || new_str[i - 2] != '\\' || !(new_str[i - 1] >= '0' && new_str[i - 1] <= '9')){
  859.                     if ((extra -= 2) < 0){
  860.                         /* ran out of extra room. */
  861.                         return 0;
  862.                     }
  863.                     new_str[i++] = '\\';
  864.                     new_str[i++] = '0';
  865.                 }
  866.                 new_str[i++] = *str++;
  867.             }
  868.             else{
  869.                 /* 
  870.                  * A normal char.
  871.                  *
  872.                  */
  873.                 new_str[i++] = *str++;
  874.             }
  875.         }
  876.     }
  877.  
  878.     if (seenbs){
  879.         /*
  880.          * The final character was a '\'. Ignore it.
  881.          *
  882.          */
  883.     }
  884.  
  885.     new_str[i] = '\0';
  886.     return new_str;
  887. }
  888.  
  889. static char *
  890. build_map(s, map)
  891. char *s;
  892. char *map;
  893. {
  894.     /*
  895.      * Produce a mapping table for the given transliteration.
  896.      * We are passed something that looks like "{a-z}{A-Z}"
  897.      * Look out for \ chars, these are used to quote } and -.
  898.      *
  899.      * Return a pointer to the char after the closing }.
  900.      * We cannot clobber s.
  901.      *
  902.      * The building of maps is somewhat optimised.
  903.      * If the string is the same as the last one we were 
  904.      * called with then we don't do anything. It would be better
  905.      * to remember all the transliterations we have seen, in
  906.      * order (because in a global substitution we will
  907.      * apply them in the same order repeatedly) and then we
  908.      * could do the minimum amount of building. This is a 
  909.      * compromise because it is a fairly safe bet that there will 
  910.      * not be more than one transliteration done.
  911.      *
  912.      */
  913.  
  914.     char *in;
  915.     char *out;
  916.     char *str;
  917.     char *tmp;
  918.     char c;
  919.     static char *mem();
  920.     static char nextch();
  921.     int i = 0;
  922.     int range_count = 0;
  923.     int seenbs = 0;
  924.     static char *last = 0;
  925.     static int last_len;
  926.  
  927.     if (!s){
  928.         return 0;
  929.     }
  930.  
  931.     if (last && !strncmp(s, last, last_len)){
  932.         /* Re-use the map. */
  933.         return s + last_len;
  934.     }
  935.     else{
  936.     /*
  937.      * Make a copy of s in both 'last' and 'str'
  938.      */
  939.     int len = strlen(s) + 1;
  940.         if (!(str = mem(MEM_MAP, len)) || !(last = mem(MEM_MAP_SAVE, len))){
  941.             return 0;
  942.         }
  943.     str[0] = last[0] = '\0';
  944.     strcat(str, s);
  945.     strcat(last, s);
  946.     }
  947.  
  948.     tmp = str + 1;
  949.     in = str;
  950.  
  951.     while (*tmp){
  952.         if (seenbs){
  953.             if (*tmp == '-'){
  954.                 /* 
  955.                  * Keep the \ before a - since this is the range
  956.                  * separating metacharacter. We don't keep } quoted,
  957.                  * we just put it in. Then it is passed as a normal
  958.                  * char (no longer a metachar) to nextch().
  959.                  *
  960.                  */
  961.                 str[i++] = '\\';
  962.             }
  963.             str[i++] = *tmp++;
  964.             seenbs = 0;
  965.         }
  966.         else{
  967.             if (*tmp == '\\'){
  968.                 seenbs = 1;
  969.                 tmp++;
  970.             }
  971.             else if (*tmp == '}'){
  972.                 if (!range_count){
  973.                     /* seen first range. */
  974.                     range_count = 1;
  975.                     str[i++] = '\0';
  976.                     tmp++;
  977.                     while (*tmp == ' ' || *tmp == '\t'){
  978.                         tmp++;
  979.                     }
  980.                     if (*tmp != '{'){
  981.                         return 0;
  982.                     }
  983.                     out = str + i;
  984.                     tmp++;
  985.                 }
  986.                 else{
  987.                     /* seen both ranges. */
  988.                     str[i++] = '\0';
  989.                     tmp++;
  990.                     range_count = 2; 
  991.                     break;
  992.                 }
  993.             }
  994.             else{
  995.                 /* A plain defenceless character. */
  996.                 str[i++] = *tmp++;
  997.             }
  998.         }
  999.     }
  1000.  
  1001.     if (range_count != 2){
  1002.         return 0;
  1003.     }
  1004.  
  1005.     last_len = tmp - str;
  1006.  
  1007.     /*
  1008.      * Now 'out' and 'in' both point to character ranges.
  1009.      * These will look something like "A-Z" but may be 
  1010.      * more complicated and have {} and - in them elsewhere.
  1011.      *
  1012.      */
  1013.     
  1014.     for (i = 0; i < 1 << BYTEWIDTH; i++){
  1015.         map[i] = i;
  1016.     }
  1017.  
  1018.     /*
  1019.      * Ready the range expanding function.
  1020.      *
  1021.      */
  1022.     (void) nextch(in, 0);
  1023.     (void) nextch(out, 1);
  1024.  
  1025.     /*
  1026.      * For each char in 'in', assign it a value in
  1027.      * 'map' corresponding to the next char in 'out'.
  1028.      *
  1029.      */
  1030.  
  1031.     while ((c = nextch(0, 0))){
  1032.         map[c] = nextch(0, 1);
  1033.     }
  1034.  
  1035.     return tmp;
  1036. }
  1037.  
  1038. static char
  1039. nextch(str, who)
  1040. char *str;
  1041. int who;
  1042. {
  1043.     /*
  1044.      * Given a range like {a-z0237-9}
  1045.      * return successive characters from the range on
  1046.      * successive calls. The first call (when str != 0)
  1047.      * sets things up.
  1048.      *
  1049.      * We must handle strange things like
  1050.      * {a-b-c-z}            = {a-z}
  1051.      * and {z-l-a}          = {z-a}
  1052.      * and {f-f-f-f-h}      = {f-h}
  1053.      * and {a-z-f-h-y-d-b}  = {a-b}
  1054.      *
  1055.      * and so on.
  1056.      *
  1057.      * This function will remember two strings and will return
  1058.      * the next charcter in the range specified by 'who'. This
  1059.      * makes the building of the transliteration table above
  1060.      * a trivial loop.
  1061.      *
  1062.      * I can't be bothered to comment this as much as it
  1063.      * deserves right now... 8-)
  1064.      *
  1065.      */
  1066.  
  1067.     static char *what[2] = {0, 0};
  1068.     static char last[2] = {0, 0};
  1069.     static int increment[2];
  1070.     static int pos[2];
  1071.  
  1072.     if (who < 0 || who > 1){
  1073.         return 0;
  1074.     }
  1075.  
  1076.     if (str){
  1077.         /* Set up for this string. */
  1078.         what[who] = str;
  1079.         pos[who] = 0;
  1080.         return 1;
  1081.     }
  1082.     else if (!what[who]){
  1083.         return 0;
  1084.     }
  1085.  
  1086.     if (!pos[who] && what[who][0] == '-'){
  1087.         return 0;
  1088.     }
  1089.  
  1090.     switch (what[who][pos[who]]){
  1091.         
  1092.         case '-':{
  1093.             /* we're in mid-range. */
  1094.             last[who] += increment[who];
  1095.             if (what[who][pos[who] + 1] == last[who]){
  1096.                 pos[who] += 2;
  1097.             }
  1098.             return last[who];
  1099.         }
  1100.  
  1101.         case '\0':{
  1102.             /* 
  1103.              * We've finished. Keep on returning the
  1104.              * last thing you saw if who = 1.
  1105.              */
  1106.             if (who){
  1107.                 return last[1];
  1108.             }
  1109.             return 0;
  1110.         }
  1111.  
  1112.         /* FALLTHROUGH */
  1113.         case '\\':{
  1114.             pos[who]++;
  1115.         }
  1116.  
  1117.         default:{
  1118.             last[who] = what[who][pos[who]++];
  1119.             /*
  1120.              * If we have reached a '-' then this is the start of a
  1121.              * range. Keep on moving forward until we see a sensible 
  1122.              * end of range character. Then set up increment so that
  1123.              * we do the right thing next time round. We leave pos
  1124.              * pointing at the '-' sign.
  1125.              *
  1126.              */
  1127.  
  1128.             while (what[who][pos[who]] == '-'){
  1129.                 int inc = 1;
  1130.                 if (what[who][pos[who] + inc] == '\\'){
  1131.                     inc++;
  1132.                 }
  1133.                 if (!what[who][pos[who] + inc]){
  1134.                     return 0;
  1135.                 }
  1136.                 if (what[who][pos[who] + inc + 1] == '-'){
  1137.                     pos[who] += inc + 1;
  1138.                     continue;
  1139.                 }
  1140.                 increment[who] = what[who][pos[who] + inc] - last[who];
  1141.                 if (!increment[who]){
  1142.                     pos[who] += 2;
  1143.                     continue;
  1144.                 }
  1145.                 if (increment[who] > 0){
  1146.                     increment[who] = 1;
  1147.                     break;
  1148.                 }
  1149.                 else if (increment[who] < 0){
  1150.                     increment[who] = -1;
  1151.                     break;
  1152.                 }
  1153.             }
  1154.             return last[who];
  1155.         }
  1156.     }
  1157. }
  1158.  
  1159. static char *
  1160. mem(who, size)
  1161. int who;
  1162. int size;
  1163. {
  1164.     /*
  1165.      * Get 'size' bytes of memeory one way or another.
  1166.      *
  1167.      * The 'mem_slots' array holds currently allocated hunks.
  1168.      * If we can use one that's already in use then do so, otherwise
  1169.      * try and find a hunk not in use somewhere else in the table.
  1170.      * As a last resort call malloc. All a bit specialised and
  1171.      * not too clear. Seems to works fine though.
  1172.      */
  1173.     
  1174.     static void mem_save();
  1175.  
  1176.     if (who < 0 || who >= MEM_SLOTS){
  1177.     return 0;
  1178.     }
  1179.     
  1180.     if (mem_slots[who].used){
  1181.     /*
  1182.      * There is already something here. Either move/free it or
  1183.      * return it if it is already big enough to hold this request.
  1184.      */
  1185.     if (mem_slots[who].size >= size){
  1186.         /* It is already big enough. */
  1187.         return mem_slots[who].s;
  1188.     }
  1189.     else{
  1190.         mem_save(who);
  1191.     }
  1192.     }
  1193.     else{
  1194.     /*
  1195.      * The slot was not in use. Check to see if there is space
  1196.      * allocated here already that we can use. If there is and
  1197.      * we can, use it, if there is and it's not big enough try to
  1198.      * save it. if there isn't then try to find it in another free slot,
  1199.      * otherwise don't worry, the malloc below will get us some.
  1200.      */
  1201.     if (mem_slots[who].s && mem_slots[who].size >= size){
  1202.         /* We'll take it. */
  1203.         mem_slots[who].used = 1;
  1204.         return mem_slots[who].s;
  1205.     }
  1206.     
  1207.     if (mem_slots[who].s){
  1208.         mem_save(who);
  1209.     }
  1210.     else{
  1211.         static int mem_find();
  1212.         int x = mem_find(size);
  1213.         if (x != -1){
  1214.         mem_slots[who].s = mem_slots[x].s;
  1215.         mem_slots[who].size = mem_slots[x].size;
  1216.         mem_slots[who].used = 1;
  1217.         mem_slots[x].s = (char *)0;
  1218.         return mem_slots[who].s;
  1219.         }
  1220.     }
  1221.     }
  1222.     
  1223.     /*
  1224.      * Have to use malloc 8-(
  1225.      */
  1226.  
  1227.     if (!(mem_slots[who].s = (char *) malloc((unsigned)size))){
  1228.     return 0;
  1229.     }
  1230.     mem_slots[who].size = size;
  1231.     mem_slots[who].used = 1;
  1232.     
  1233.     return mem_slots[who].s;
  1234. }
  1235.  
  1236. static int
  1237. mem_find(size)
  1238. int size;
  1239. {
  1240.     /*
  1241.      * See if we can find an unused but allocated slot with 'size' 
  1242.      * (or more) space available. Return the index, or -1 if not.
  1243.      */
  1244.      
  1245.     register int i;
  1246.     
  1247.     for (i = 0; i < MEM_SLOTS; i++){
  1248.     if (!mem_slots[i].used && mem_slots[i].s && mem_slots[i].size >= size){
  1249.         return i;
  1250.     }
  1251.     }
  1252.     return -1;
  1253. }
  1254.  
  1255. static void
  1256. mem_save(x)
  1257. int x;
  1258. {
  1259.     /*
  1260.      * There is some memory in mem_slots[x] and we try to save it rather
  1261.      * than free it. In order we try to
  1262.      *
  1263.      * 1) put it in an unused slot that has no allocation.
  1264.      * 2) put it in an unused slot that has an allocation smaller than x's
  1265.      * 3) free it since there are no free slots and all the full ones are bigger.
  1266.      *
  1267.      */
  1268.  
  1269.     register int i;
  1270.     register int saved = 0;
  1271.     
  1272.     /*
  1273.      * First we try to find somewhere unused and with no present allocation.
  1274.      */
  1275.     for (i = 0; i < MEM_SLOTS; i++){
  1276.     if (!mem_slots[i].used && !mem_slots[i].s){
  1277.         saved = 1;
  1278.         mem_slots[i].s = mem_slots[x].s;
  1279.         mem_slots[i].size = mem_slots[x].size;
  1280.         mem_slots[i].used = 0;
  1281.         break;
  1282.     }
  1283.     }
  1284.     
  1285.     /*
  1286.      * No luck yet. Try for a place that is not being used but which has
  1287.      * space allocated, and which is smaller than us (and all other such spots). 
  1288.      * Pick on the smallest, yeah.
  1289.      */
  1290.     if (!saved){
  1291.     register int small = -1;
  1292.     register int small_val = 1000000;
  1293.     for (i = 0; i < MEM_SLOTS; i++){
  1294.         if (!mem_slots[i].used && mem_slots[i].size < mem_slots[x].size && mem_slots[i].size < small_val){
  1295.         small_val = mem_slots[i].size;
  1296.         small = i;
  1297.         }
  1298.     }
  1299.     
  1300.     if (small != -1){
  1301.         saved = 1;
  1302.         /* We got one, now clobber it... */
  1303.         free(mem_slots[small].s);
  1304.         /* and move on in. */
  1305.         mem_slots[small].s = mem_slots[x].s;
  1306.         mem_slots[small].size = mem_slots[x].size;
  1307.         mem_slots[small].used = 0;
  1308.     }
  1309.     }
  1310.     
  1311.     if (!saved){
  1312.     /* Have to toss it away. */
  1313.     free(mem_slots[x].s);
  1314.     }
  1315. }
  1316.  
  1317. static void
  1318. mem_init()
  1319. {
  1320.     /*
  1321.      * Clear all the memory slots.
  1322.      */
  1323.  
  1324.     register int i;
  1325.     
  1326.     for (i = 0; i < MEM_SLOTS; i++){
  1327.     mem_slots[i].s = (char *)0;
  1328.     mem_slots[i].used = 0;
  1329.     }
  1330. }
  1331.  
  1332. static void
  1333. mem_free(except)
  1334. char *except;
  1335. {
  1336.     /*
  1337.      * "Clear out" all the memory slots. Actually we do no freeing since
  1338.      * we may well be called again. We just mark the slots as unused. Next
  1339.      * time round they might be useful - the addresses and sizes are still there.
  1340.      *
  1341.      * For the slot (if any) whose address is 'except', we actually set the
  1342.      * address to 0. This is done because we are called ONLY from the macro
  1343.      * RETURN() in strsed() and we intend to return the value in 'except'.
  1344.      * Once this is done, strsed should (in theory) have no knowledge at all
  1345.      * of the address it passed back last time. That way we won't clobber it
  1346.      * and cause all sorts of nasty problems.
  1347.      */
  1348.  
  1349.     register int i;
  1350.     
  1351.     for (i = 0; i < MEM_SLOTS; i++){
  1352.     mem_slots[i].used = 0;
  1353.     if (mem_slots[i].s == except){
  1354.         mem_slots[i].s = (char *)0;
  1355.         mem_slots[i].size = 0;
  1356.     }
  1357.     } 
  1358. }
  1359.  
  1360.