home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 333_02 / regex1.c < prev    next >
C/C++ Source or Header  |  1989-04-22  |  19KB  |  719 lines
  1. /* Extended regular expression matching and search.
  2.    Copyright (C) 1985 Free Software Foundation, Inc.
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include "awk.h"
  9.  
  10. /* To test, compile with -Dtest.  This Dtestable feature turns this into   */
  11. /* a self-contained program which reads a pattern, describes how it       */
  12. /* compiles, then reads a string and searches for it.               */
  13.  
  14.  
  15. STATIC VOID     NEAR PASCAL    init_syntax_once(void);
  16. STATIC VOID     NEAR PASCAL    store_jump(char *from, char opcode, char *to);
  17. STATIC VOID     NEAR PASCAL    insert_jump(char op, char *from,
  18.                         char *to, char *current_end);
  19.  
  20.  
  21.  
  22. /* JF this var has taken on whole new meanings as time goes by.  Various   */
  23. /* bits in this int tell how certain pieces of syntax should work       */
  24.  
  25. static int         obscure_syntax = 0;
  26.  
  27.  
  28. /*  Define the syntax stuff, so we can do the \<...\> things.  */
  29.  
  30.  
  31. STATIC VOID NEAR PASCAL init_syntax_once(void)
  32. {
  33.     register int       c;
  34.     static   BOOL      done = FALSE;
  35.  
  36.     if (!done)
  37.     {
  38.     memset(re_syntax_table, 0, sizeof(re_syntax_table));
  39.     for (c = 'a'; c <= 'z'; c++)
  40.         re_syntax_table[c] = Sword;
  41.     for (c = 'A'; c <= 'Z'; c++)
  42.         re_syntax_table[c] = Sword;
  43.     for (c = '0'; c <= '9'; c++)
  44.         re_syntax_table[c] = Sword;
  45.     done = TRUE;
  46.     }
  47.     return;
  48. }
  49.  
  50.  
  51.  
  52. /* compile_pattern takes a regular-expression descriptor string in the        */
  53. /* user's format and converts it into a buffer full of byte commands for    */
  54. /* matching.                                    */
  55. /*                                        */
  56. /*  pattern   is the address of the pattern string                */
  57. /*  size      is the length of it.                        */
  58. /*  bufp      is a  struct re_pattern_buffer *    which points to the info    */
  59. /*          on where to store the byte commands.                */
  60. /*          This structure contains a  char *  which points to the        */
  61. /*          actual space, which should have been obtained with malloc.    */
  62. /*          compile_pattern may use  realloc    to grow the buffer space.   */
  63. /*                                        */
  64. /* The number of bytes of commands can be found out by looking in the        */
  65. /* struct re_pattern_buffer that bufp pointed to, after compile_pattern     */
  66. /* returns.                                    */
  67.  
  68. #define PATPUSH(ch)        (*b++ = (char) (ch))
  69.  
  70. #define PATFETCH(c) \
  71.  {if (p == pend) goto end_of_pattern; \
  72.   c = * (unsigned char *) p++; }
  73.  
  74. #define PATFETCH_RAW(c) \
  75.  {if (p == pend) goto end_of_pattern; \
  76.   c = * (unsigned char *) p++; }
  77.  
  78. #define PATUNFETCH           p--
  79.  
  80. #define EXTEND_BUFFER \
  81.   { char *old_buffer = bufp->buffer; \
  82.     if (bufp->allocated == (1<<16)) goto too_big; \
  83.     bufp->allocated *= 2; \
  84.     if (bufp->allocated > (1<<16)) bufp->allocated = (1<<16); \
  85.     if (!(bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated))) \
  86.       goto memory_exhausted; \
  87.     c = bufp->buffer - old_buffer; \
  88.     b += c; \
  89.     if (fixup_jump) fixup_jump += c; \
  90.     if (laststart) laststart += c; \
  91.     begalt += c; \
  92.     if (pending_exact) pending_exact += c; \
  93.   }
  94.  
  95.  
  96. /* JF this function is used to compile UN*X style regexps.  In particular,  */
  97. /* ( ) and | don't have to be \ed to have a special meaning                 */
  98.  
  99. int PASCAL re_set_syntax(int syntax)
  100. {
  101.     auto     int    ret;
  102.  
  103.     ret        = obscure_syntax;
  104.     obscure_syntax = syntax;
  105.     return(ret);
  106. }
  107.  
  108.  
  109. char * PASCAL re_compile_pattern(char *pattern, int size, REPAT_BUFFER *bufp)
  110. {
  111.     register char         *b    = bufp->buffer;
  112.     register char         *p    = pattern;
  113.     auto     char         *pend = pattern + size;
  114.     register unsigned          c, c1;
  115.     auto     char         *p1;
  116.  
  117.     /* address of the count-byte of the most recently inserted "exactn"  */
  118.     /* command. This makes it possible to tell whether a new exact-match */
  119.     /* character can be added to that command or requires a new "exactn" */
  120.     /* command.                              */
  121.     auto     char         *pending_exact = 0;
  122.  
  123.     /* address of the place where a forward-jump should go to the end of the */
  124.     /* containing expression. Each alternative of an "or", except the last,  */
  125.     /* ends with a forward-jump of this sort.                     */
  126.     auto     char         *fixup_jump = 0;
  127.  
  128.     /* address of start of the most recently finished expression. This tells */
  129.     /* postfix * where to find the start of its operand.             */
  130.     auto     char        *laststart = 0;
  131.  
  132.     /* In processing a repeat, TRUE means zero matches is allowed */
  133.     auto     BOOL         zero_times_ok;
  134.  
  135.     /* In processing a repeat, TRUE means many matches is allowed */
  136.     auto     BOOL         many_times_ok;
  137.  
  138.     /* address of beginning of regexp, or inside of last \( */
  139.     auto     char        *begalt = b;
  140.  
  141.     /* Stack of information saved by \( and restored by \). Four stack        */
  142.     /* elements are pushed by each \(: First, the value of b. Second, the   */
  143.     /* value of fixup_jump. Third, the value of regnum. Fourth, the value of*/
  144.     /* begalt.                                    */
  145.     auto     int         stackb[40];
  146.     auto     int        *stackp = stackb;
  147.     auto     int        *stacke = stackb + 40;
  148.     auto     int        *stackt;
  149.  
  150.     /* Counts \('s as they are encountered.  Remembered for the matching \), */
  151.     /* where it becomes the "register number" to put in the stop_memory      */
  152.     /* command                                     */
  153.     auto     int         regnum = 1;
  154.  
  155.     bufp->fastmap_accurate = 0;
  156.     init_syntax_once();
  157.  
  158.     if (bufp->allocated == 0)
  159.     {
  160.     bufp->allocated = 28;
  161.     if (bufp->buffer)
  162.         /* EXTEND_BUFFER loses when bufp->allocated is 0 */
  163.         bufp->buffer = (char *) realloc(bufp->buffer, 28);
  164.     else
  165.         /* Caller did not allocate a buffer.  Do it for him */
  166.         bufp->buffer = (char *) malloc(28);
  167.     if (!bufp->buffer)
  168.         goto memory_exhausted;
  169.     begalt = b = bufp->buffer;
  170.     }
  171.  
  172.     while (p != pend)
  173.     {
  174.     if (b - bufp->buffer > bufp->allocated - 10)
  175.         EXTEND_BUFFER;       /* Note that EXTEND_BUFFER clobbers c */
  176.  
  177.     PATFETCH(c);
  178.  
  179.     switch (c)
  180.     {
  181.         case '$':
  182.         /* $ means succeed if at end of line, but only in special  */
  183.         /* contexts. If randomly in the middle of a pattern, it is */
  184.         /* a normal character.                       */
  185.         if (p == pend || (*p == '\\' && (p[1] == ')' || p[1] == '|')))
  186.         {
  187.             PATPUSH(RECODE_ENDLINE);
  188.             break;
  189.         }
  190.         goto normal_char;
  191.         case '^':
  192.         /* ^ means succeed if at beg of line, but only if no       */
  193.         /* preceding pattern.                       */
  194.         if (laststart)
  195.             goto normal_char;
  196.         PATPUSH(RECODE_BEGLINE);
  197.         break;
  198.         case '*':
  199.         case '+':
  200.         case '?':
  201.         /* If there is no previous pattern, char not special.      */
  202.         if (!laststart)
  203.             goto normal_char;
  204.         /* If there is a sequence of repetition chars, collapse it
  205.          * down to equivalent to just one.  */
  206.         zero_times_ok = FALSE;
  207.         many_times_ok = FALSE;
  208.         while (TRUE)
  209.         {
  210.             zero_times_ok |= (c != '+');
  211.             many_times_ok |= (c != '?');
  212.             if (p == pend)
  213.             break;
  214.             PATFETCH(c);
  215.             if (!(c == '*' || c == '+' || c == '?'))
  216.             {
  217.             PATUNFETCH;
  218.             break;
  219.             }
  220.         }
  221.  
  222.         /* Now we know whether 0 matches is allowed, and whether 2 or
  223.          * more matches is allowed.  */
  224.         if (many_times_ok)
  225.         {
  226.             /* If more than one repetition is allowed, put in a
  227.              * backward jump at the end.  */
  228.             store_jump(b, RECODE_MAYBE_FINALIZE_JUMP, laststart - 3);
  229.             b += 3;
  230.         }
  231.         insert_jump(RECODE_ON_FAILURE_JUMP, laststart, b + 3, b);
  232.         pending_exact = 0;
  233.         b += 3;
  234.         if (!zero_times_ok)
  235.         {
  236.             /* At least one repetition required: insert before the
  237.              * loop a skip over the initial on-failure-jump
  238.              * instruction */
  239.             insert_jump(RECODE_DUMMY_FAILURE_JUMP, laststart,
  240.                 laststart + 6, b);
  241.             b += 3;
  242.         }
  243.         break;
  244.  
  245.         case '.':
  246.         laststart = b;
  247.         PATPUSH(RECODE_ANYCHAR);
  248.         break;
  249.  
  250.         case '[':
  251.         if (b - bufp->buffer
  252.             > bufp->allocated - 3 - (1 << BYTEWIDTH) / BYTEWIDTH)
  253.             /* Note that EXTEND_BUFFER clobbers c */
  254.             EXTEND_BUFFER;
  255.  
  256.         laststart = b;
  257.         if (*p == '^')
  258.         {
  259.             PATPUSH(RECODE_CHARSET_NOT);
  260.             ++p;
  261.         }
  262.         else
  263.             PATPUSH(RECODE_CHARSET);
  264.         p1 = p;
  265.  
  266.         PATPUSH((1 << BYTEWIDTH) / BYTEWIDTH);
  267.         /* Clear the whole map */
  268.         bzero(b, (1 << BYTEWIDTH) / BYTEWIDTH);
  269.         /* Read in characters and ranges, setting map bits */
  270.         while (TRUE)
  271.         {
  272.             PATFETCH(c);
  273.             if (c == ']' && p != p1 + 1)
  274.             break;
  275.             if (*p == '-')
  276.             {
  277.             PATFETCH(c1);
  278.             PATFETCH(c1);
  279.             while (c <= c1)
  280.                 b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH), c++;
  281.             }
  282.             else
  283.             {
  284.             b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH);
  285.             }
  286.         }
  287.         /* Discard any bitmap bytes that are all 0 at the end of the
  288.          * map. Decrement the map-length byte too. */
  289.         while (b[-1] > 0 && b[b[-1] - 1] == 0)
  290.             b[-1]--;
  291.         b += b[-1];
  292.         break;
  293.  
  294.         case '(':
  295.         if (!(obscure_syntax & RE_NO_BK_PARENS))
  296.             goto normal_char;
  297.         if (stackp == stacke)
  298.             goto nesting_too_deep;
  299.         if (regnum < RE_NREGS)
  300.         {
  301.             PATPUSH(RECODE_START_MEMORY);
  302.             PATPUSH(regnum);
  303.         }
  304.         *stackp++ = b - bufp->buffer;
  305.         *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0;
  306.         *stackp++ = regnum++;
  307.         *stackp++ = begalt - bufp->buffer;
  308.         fixup_jump = 0;
  309.         laststart = 0;
  310.         begalt = b;
  311.         break;
  312.  
  313.         case ')':
  314.         if (!(obscure_syntax & RE_NO_BK_PARENS))
  315.             goto normal_char;
  316.         if (stackp == stackb)
  317.             goto unmatched_close;
  318.         begalt = bufp->buffer + (*--stackp);
  319.         if (fixup_jump)
  320.             store_jump(fixup_jump, RECODE_JUMP, b);
  321.         if (stackp[-1] < RE_NREGS)
  322.         {
  323.             PATPUSH(RECODE_STOP_MEMORY);
  324.             PATPUSH(stackp[-1]);
  325.         }
  326.         stackp -= 2;
  327.         fixup_jump = 0;
  328.         if (*stackp)
  329.             fixup_jump = bufp->buffer + *stackp - 1;
  330.         laststart = bufp->buffer + (*--stackp);
  331.         break;
  332.  
  333.         case '|':
  334.         if (!(obscure_syntax & RE_NO_BK_VBAR))
  335.             goto normal_char;
  336.         insert_jump(RECODE_ON_FAILURE_JUMP, begalt, b + 6, b);
  337.         pending_exact = 0;
  338.         b += 3;
  339.         if (fixup_jump)
  340.             store_jump(fixup_jump, RECODE_JUMP, b);
  341.         fixup_jump = b;
  342.         b += 3;
  343.         laststart = 0;
  344.         begalt = b;
  345.         break;
  346.  
  347.         case '\\':
  348.         if (p == pend)
  349.             goto invalid_pattern;
  350.         PATFETCH_RAW(c);
  351.         switch (c)
  352.         {
  353.             case '(':
  354.             if (obscure_syntax & RE_NO_BK_PARENS)
  355.                 goto normal_backsl;
  356.             if (stackp == stacke)
  357.                 goto nesting_too_deep;
  358.             if (regnum < RE_NREGS)
  359.             {
  360.                 PATPUSH(RECODE_START_MEMORY);
  361.                 PATPUSH(regnum);
  362.             }
  363.             *stackp++ = b - bufp->buffer;
  364.             *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1
  365.                            : 0;
  366.             *stackp++ = regnum++;
  367.             *stackp++ = begalt - bufp->buffer;
  368.             fixup_jump = 0;
  369.             laststart = 0;
  370.             begalt = b;
  371.             break;
  372.  
  373.             case ')':
  374.             if (obscure_syntax & RE_NO_BK_PARENS)
  375.                 goto normal_backsl;
  376.             if (stackp == stackb)
  377.                 goto unmatched_close;
  378.             begalt = bufp->buffer + (*--stackp);
  379.             if (fixup_jump)
  380.                 store_jump(fixup_jump, RECODE_JUMP, b);
  381.             if (stackp[-1] < RE_NREGS)
  382.             {
  383.                 PATPUSH(RECODE_STOP_MEMORY);
  384.                 PATPUSH(stackp[-1]);
  385.             }
  386.             stackp -= 2;
  387.             fixup_jump = 0;
  388.             if (*stackp)
  389.                 fixup_jump = bufp->buffer + *stackp - 1;
  390.             laststart = bufp->buffer + (*--stackp);
  391.             break;
  392.  
  393.             case '|':
  394.             if (obscure_syntax & RE_NO_BK_VBAR)
  395.                 goto normal_backsl;
  396.             insert_jump(RECODE_ON_FAILURE_JUMP, begalt, b + 6, b);
  397.             pending_exact = 0;
  398.             b += 3;
  399.             if (fixup_jump)
  400.                 store_jump(fixup_jump, RECODE_JUMP, b);
  401.             fixup_jump = b;
  402.             b += 3;
  403.             laststart = 0;
  404.             begalt = b;
  405.             break;
  406.  
  407.             case 'w':
  408.             laststart = b;
  409.             PATPUSH(RECODE_WORDCHAR);
  410.             break;
  411.  
  412.             case 'W':
  413.             laststart = b;
  414.             PATPUSH(RECODE_NOTWORDCHAR);
  415.             break;
  416.  
  417.             case '<':
  418.             PATPUSH(RECODE_WORDBEG);
  419.             break;
  420.  
  421.             case '>':
  422.             PATPUSH(RECODE_WORDEND);
  423.             break;
  424.  
  425.             case 'b':
  426.             PATPUSH(RECODE_WORDBOUND);
  427.             break;
  428.  
  429.             case 'B':
  430.             PATPUSH(RECODE_NOTWORDBOUND);
  431.             break;
  432.  
  433.             case '`':
  434.             PATPUSH(RECODE_BEGBUF);
  435.             break;
  436.  
  437.             case '\'':
  438.             PATPUSH(RECODE_ENDBUF);
  439.             break;
  440.  
  441.             case '1':
  442.             case '2':
  443.             case '3':
  444.             case '4':
  445.             case '5':
  446.             case '6':
  447.             case '7':
  448.             case '8':
  449.             case '9':
  450.             c1 = c - '0';
  451.             if (c1 >= regnum)
  452.                 goto normal_char;
  453.             for (stackt = stackp - 2; stackt > stackb; stackt -= 4)
  454.                 if (*stackt == c1)
  455.                 goto normal_char;
  456.             laststart = b;
  457.             PATPUSH(RECODE_DUPLICATE);
  458.             PATPUSH(c1);
  459.             break;
  460.             default:
  461. normal_backsl:
  462.             goto normal_char;
  463.         }
  464.         break;
  465.  
  466.         default:
  467. normal_char:
  468.         if (!pending_exact || pending_exact + *pending_exact + 1 != b
  469.             || *pending_exact == 0177 || *p == '*' || *p == '^'
  470.             || *p == '+' || *p == '?')
  471.         {
  472.             laststart = b;
  473.             PATPUSH(RECODE_EXACTN);
  474.             pending_exact = b;
  475.             PATPUSH(0);
  476.         }
  477.         PATPUSH(c);
  478.         (*pending_exact)++;
  479.     }
  480.     }
  481.  
  482.     if (fixup_jump)
  483.     store_jump(fixup_jump, RECODE_JUMP, b);
  484.  
  485.     if (stackp != stackb)
  486.     goto unmatched_open;
  487.  
  488.     bufp->used = b - bufp->buffer;
  489.     return(NULL);
  490.  
  491. invalid_pattern:
  492.     return("Invalid regular expression");
  493.  
  494. unmatched_open:
  495.     return("Unmatched \\(");
  496.  
  497. unmatched_close:
  498.     return("Unmatched \\)");
  499.  
  500. end_of_pattern:
  501.     return("Premature end of regular expression");
  502.  
  503. nesting_too_deep:
  504.     return("Nesting too deep");
  505.  
  506. too_big:
  507.     return("Regular expression too big");
  508.  
  509. memory_exhausted:
  510.     return("Memory exhausted");
  511. }
  512.  
  513.  
  514. /* Store where `from' points a jump operation to jump to where `to' points. */
  515. /* `opcode' is the opcode to store.                                         */
  516.  
  517. STATIC VOID NEAR PASCAL store_jump(char *from, char opcode, char *to)
  518. {
  519.     from[0] = opcode;
  520.     from[1] = (to - (from + 3)) & 0377;
  521.     from[2] = (to - (from + 3)) >> 8;
  522.     return;
  523. }
  524.  
  525.  
  526. /* Open up space at char FROM, and insert there a jump to TO.  CURRENT_END  */
  527. /* gives te end of the storage no in use, so we know how much data to copy  */
  528. /* up.    OP is the opcode of the jump to insert.  If you call this function, */
  529. /* you must zero out pending_exact.                        */
  530.  
  531. STATIC VOID NEAR PASCAL insert_jump(char op, char *from,
  532.                     char *to, char *current_end)
  533. {
  534.     register char     *pto    = current_end + 3;
  535.     register char     *pfrom = current_end;
  536.  
  537.     while (pfrom != from)
  538.     *--pto = *--pfrom;
  539.     store_jump(from, op, to);
  540.     return;
  541. }
  542.  
  543.  
  544. /* Given a pattern, compute a fastmap from it.    The fastmap records which   */
  545. /* of the (1 << BYTEWIDTH) possible characters can start a string that        */
  546. /* matches the pattern.  This fastmap is used by re_search to skip quickly  */
  547. /* over totally implausible text.                        */
  548. /*                                        */
  549. /* The caller must supply the address of a (1 << BYTEWIDTH)-byte data area  */
  550. /* as bufp->fastmap.  The other components of bufp describe the pattern to  */
  551. /* be used.                                    */
  552.  
  553. VOID PASCAL re_compile_fastmap(REPAT_BUFFER *bufp)
  554. {
  555.     register int        c;
  556.     auto     unsigned char     *pattern = (unsigned char *) bufp->buffer;
  557.     auto     int        size    = bufp->used;
  558.     register char           *fastmap = bufp->fastmap;
  559.     register unsigned char     *p    = pattern;
  560.     register unsigned char     *pend    = pattern + size;
  561.     register int        j;
  562.     auto     unsigned char     *stackb[NFAILURES];
  563.     auto     unsigned char    **stackp    = stackb;
  564.  
  565.     memset(fastmap, 0, (1 << BYTEWIDTH));
  566.     bufp->fastmap_accurate = TRUE;
  567.     bufp->can_be_null       = 0;
  568.  
  569.     while (p)
  570.     {
  571.     if (p == pend)
  572.     {
  573.         bufp->can_be_null = 1;
  574.         break;
  575.     }
  576.     c = *p++;
  577.     switch (c)
  578.     {
  579.         case RECODE_EXACTN:
  580.         fastmap[p[1]] = 1;
  581.         break;
  582.         case RECODE_BEGLINE:
  583.         case RECODE_BEFORE_DOT:
  584.         case RECODE_AT_DOT:
  585.         case RECODE_AFTER_DOT:
  586.         case RECODE_BEGBUF:
  587.         case RECODE_ENDBUF:
  588.         case RECODE_WORDBOUND:
  589.         case RECODE_NOTWORDBOUND:
  590.         case RECODE_WORDBEG:
  591.         case RECODE_WORDEND:
  592.         continue;
  593.         case RECODE_ENDLINE:
  594.         fastmap['\n'] = 1;
  595.         if (bufp->can_be_null != 1)
  596.             bufp->can_be_null = 2;
  597.         break;
  598.         case RECODE_FINALIZE_JUMP:
  599.         case RECODE_MAYBE_FINALIZE_JUMP:
  600.         case RECODE_JUMP:
  601.         bufp->can_be_null = 1;         /* intentional fall thru */
  602.         case RECODE_DUMMY_FAILURE_JUMP:
  603.         j = *p++ & 0377;
  604.         j += SIGN_EXTEND_CHAR(*(char *) p) << 8;
  605.         p += j + 1;    /* The 1 compensates for missing ++ above */
  606.         if (j > 0)
  607.             continue;
  608.         /* Jump backward reached implies we just went through the
  609.          * body of a loop and matched nothing. Opcode jumped to
  610.          * should be an on_failure_jump. Just treat it like an
  611.          * ordinary jump. For a * loop, it has pushed its failure
  612.          * point already; if so, discard that as redundant.  */
  613.         if (*p != RECODE_ON_FAILURE_JUMP)
  614.             continue;
  615.         p++;
  616.         j = *p++ & 0377;
  617.         j += SIGN_EXTEND_CHAR(*(char *) p) << 8;
  618.         p += j + 1;    /* The 1 compensates for missing ++ above */
  619.         if (stackp != stackb && *stackp == p)
  620.             stackp--;
  621.         continue;
  622.         case RECODE_ON_FAILURE_JUMP:
  623.         j = *p++ & 0377;
  624.         j += SIGN_EXTEND_CHAR(*(char *) p) << 8;
  625.         p++;
  626.         *++stackp = p + j;
  627.         continue;
  628.         case RECODE_START_MEMORY:
  629.         case RECODE_STOP_MEMORY:
  630.         p++;
  631.         continue;
  632.         case RECODE_DUPLICATE:
  633.         bufp->can_be_null = 1;
  634.         fastmap['\n'] = 1;
  635.         case RECODE_ANYCHAR:
  636.         for (j = 0; j < (1 << BYTEWIDTH); j++)
  637.             if (j != '\n')
  638.             fastmap[j] = 1;
  639.         if (bufp->can_be_null)
  640.             return;
  641.         /* Don't return; check the alternative paths so we can set
  642.          * can_be_null if appropriate.  */
  643.         break;
  644.         case RECODE_WORDCHAR:
  645.         for (j = 0; j < (1 << BYTEWIDTH); j++)
  646.             if (SYNTAX(j) == Sword)
  647.             fastmap[j] = 1;
  648.         break;
  649.         case RECODE_NOTWORDCHAR:
  650.         for (j = 0; j < (1 << BYTEWIDTH); j++)
  651.             if (SYNTAX(j) != Sword)
  652.             fastmap[j] = 1;
  653.         break;
  654.         case RECODE_CHARSET:
  655.         for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
  656.             if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
  657.             {
  658.             fastmap[j] = 1;
  659.             }
  660.         break;
  661.         case RECODE_CHARSET_NOT:
  662.         /* Chars beyond end of map must be allowed */
  663.         for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
  664.             fastmap[j] = 1;
  665.  
  666.         for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
  667.             if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
  668.             {
  669.             fastmap[j] = 1;
  670.             }
  671.         break;
  672.     }
  673.  
  674.     /* Get here means we have successfully found the possible starting
  675.      * characters of one path of the pattern.  We need not follow this
  676.      * path any farther. Instead, look at the next alternative remembered
  677.      * in the stack. */
  678.     if (stackp != stackb)
  679.         p = *stackp--;
  680.     else
  681.         break;
  682.     }
  683.     return;
  684. }
  685.  
  686.  
  687. /* Entry points compatible with bsd4.2 regex library */
  688.  
  689.  
  690. static REPAT_BUFFER          re_comp_buf;
  691.  
  692. char * PASCAL re_comp(char *s)
  693. {
  694.     if (!s)
  695.     {
  696.     if (!re_comp_buf.buffer)
  697.         return "No previous regular expression";
  698.     return(NULL);
  699.     }
  700.  
  701.     if (!re_comp_buf.buffer)
  702.     {
  703.     if (!(re_comp_buf.buffer = (char *) malloc(200)))
  704.         return("Memory exhausted");
  705.     re_comp_buf.allocated = 200;
  706.     if (!(re_comp_buf.fastmap = (char *) malloc(1 << BYTEWIDTH)))
  707.         return("Memory exhausted");
  708.     }
  709.     return(re_compile_pattern(s, strlen(s), &re_comp_buf));
  710. }
  711.  
  712.  
  713. int PASCAL re_exec(char *s)
  714. {
  715.     auto     int       len = strlen(s);
  716.  
  717.     return(0 <= re_search(&re_comp_buf, s, len, 0, len, 0));
  718. }
  719.