home *** CD-ROM | disk | FTP | other *** search
/ ftp.barnyard.co.uk / 2015.02.ftp.barnyard.co.uk.tar / ftp.barnyard.co.uk / cpm / walnut-creek-CDROM / CPM / BDSC / BDSC-3 / PAT.CQ / PAT.C
Text File  |  2000-06-30  |  11KB  |  428 lines
  1. /*        Pattern Search Utility
  2.  *
  3.  *    This utility will search for regular expressions in text streams.
  4.  * First a function is called to "compile" the search pattern into a form
  5.  * easier to search with.  Then a function is called with the text to be
  6.  * searched; it returns a pointer to the first line within the text which
  7.  * matches the pattern (or 0 if none did).  This second function can be
  8.  * called repeatedly, with successive pointers to find all lines which
  9.  * match the pattern.  The second function also returns a pointer to the
  10.  * memory location just past the matched string, making repeated searches
  11.  * easier.
  12.  *    For example:
  13.  *
  14.  *        comppat("*one*",'\n',FALSE);
  15.  *        sptr = srchpat(textbuf,bufsz,endptr);
  16.  *
  17.  *    will set sptr to the first line in textbuf containing the string
  18.  * "one" anywhere in it, and endptr to the point just past the matched
  19.  * line; or else it will return zero if there was no matching line.
  20.  *    Although the line must match the pattern exactly, searching for
  21.  * a pattern anywhere in the line can be done by prefixing and postfixing
  22.  * the pattern with "*".  Also, comppat() can be told (via the third
  23.  * parameter) to ignore case when comparing letters.
  24.  *
  25.  *    Characters in the regular expressions have the following meanings:
  26.  *
  27.  *        <char> - unless one of the ones below, match exactly <char>.
  28.  *        ? - match any single character.
  29.  *        * - match zero or more of any character.
  30.  *        [<char_set>] - match any of the characters in the set.
  31.  *        [-<char_set>] - match any of the characters not in the set.
  32.  *            <char_set> ::= <char>        match <char>
  33.  *                       <char1>-<char2>    match any char in the
  34.  *                            range <char1>-<char2>
  35.  *    "\" can be used to quote characters (i.e., prevent them from being
  36.  * interpretted specially).
  37.  *
  38.  *
  39.  *    Initial coding 8/18/82 by Harry R. Chesley.
  40.  *
  41.  *
  42.  *    Copyright 1982 by Harry R. Chesley.
  43.  *    Unlimited permission granted for non-profit use only.
  44.  */
  45.  
  46. #include "pat.h"
  47.  
  48. /*    comppat(pat,eolchar,anycase)
  49.  *
  50.  *    Function: Compile the regular expression pattern given in pat
  51.  * into a series of pattern elements; append an element which matches
  52.  * the eolchar.  If anycase is TRUE, ignore case on letters.
  53.  *
  54.  *    Algorithm: Parse pat for regular expression special characters,
  55.  * constructing a compiled version in cpat.  The following transformations
  56.  * are made to get from the original pattern to the compiled series of
  57.  * elements:
  58.  *        <char> - if anycase FALSE, pel_type = MONEC, pel_c = <char>;
  59.  *             if anycase TRUE, pel_type = MSET, set = [<char>,
  60.  *                other case of <char>].
  61.  *        ? - pel_type = MONEA.
  62.  *        * - pel_type = MMANY.
  63.  *        [...] - pel_type = MSET, set = indicated characters.
  64.  *        [-...] - pel_type = MSET, set = all but indicated characters.
  65.  *
  66.  *    Also, eolchar is not allowed in any but the last element.
  67.  *
  68.  *    Comments: This routine compiles into the global cpat, and also
  69.  * sets cptop and eolch.  Therefore, it is not reentrant, and it is not
  70.  * possible to be using more than one pattern at a time.
  71.  */
  72.  
  73. comppat(pat,eolchar,anycase)
  74.  
  75. char *pat;
  76. char eolchar;
  77. int anycase;
  78.  
  79. {
  80.     int negflg;    /* Used in [...] processing to remember leading -. */
  81.     char c1, c2, ct; /* Used in [...] for <char>-<char> processing. */
  82.  
  83.     eolch = eolchar;    /* Remember end-of-line char. */
  84.     cptop = cpat;        /* Start with nothing. */
  85.  
  86.     /* Go thru pattern 'til end of string. */
  87.     while (*pat != 0) {
  88.  
  89.         /* Never allow the EOL character in the search pattern. */
  90.         if (*pat == eolch) {
  91.             pat++;
  92.             continue;
  93.         };
  94.  
  95.         /* Look for special characters. */
  96.         switch (*pat++) {
  97.  
  98.             /* Zero or more of anything. */
  99.             case '*':
  100.                 cptop->pel_type = MMANY; /* Zero or more. */
  101.                 break;
  102.  
  103.             /* One of anything. */
  104.             case '?':
  105.                 cptop->pel_type = MONEA; /* One of anything.*/
  106.                 break;
  107.  
  108.             /* Character sets. */
  109.             case '[':
  110.                 cptop->pel_type = MSET; /* Any in set. */
  111.                 clrall(cptop);    /* Start with nothing. */
  112.                 /* Check for "any but". */
  113.                 if (*pat == '-') {
  114.                     pat++;
  115.                     negflg = TRUE;
  116.                 } else negflg = FALSE;
  117.                 /* Figure the set. */
  118.                 while ((*pat != ']') && (*pat != 0)) {
  119.                     if (*pat == '\\')
  120.                         if (*(++pat) == 0) break;
  121.                     /* Check for <char>-<char>. */
  122.                     if (*(pat+1) == '-') {
  123.                         if (*(pat+2) != 0) {
  124.                             if ((c1 = *pat) >
  125.                                 (c2 = *(pat+2))) {
  126.                                 ct = c1;
  127.                                 c1 = c2;
  128.                                 c2 = ct;
  129.                             };
  130.                             do if (anycase)
  131.                                  setnoc(cptop,c1);
  132.                             else
  133.                                  setmem(cptop,c1);
  134.                             while (c1++ < c2);
  135.                             pat += 2;
  136.                         } else pat++;
  137.                     } else {
  138.                         if (anycase)
  139.                             setnoc(cptop,*pat);
  140.                         else setmem(cptop,*pat);
  141.                     };
  142.                     pat++;
  143.                 };
  144.                 if (negflg) negset(cptop);
  145.                 if (*pat == ']') pat++;
  146.                 /* Never match the EOL char. */
  147.                 clrmem(cptop,eolch);
  148.                 break;
  149.  
  150.             /* Quote. */
  151.             case '\\':
  152.                 if (*pat != 0) pat++;
  153.                 /* Fall thru to match single processing. */
  154.  
  155.             /* Anything else: match only it. */
  156.             default:
  157.                 if (anycase) {
  158.                     cptop->pel_type = MSET;
  159.                     clrall(cptop);
  160.                     setnoc(cptop,*(pat-1));
  161.                 } else {
  162.                     cptop->pel_type = MONEC;
  163.                     cptop->pel_c = *(pat-1);
  164.                 };
  165.                 break;
  166.         };
  167.  
  168.         cptop++;    /* Next element. */
  169.     };
  170.  
  171.     /* Last of all, match EOL. */
  172.     cptop->pel_type = MONEC;
  173.     cptop->pel_c = eolchar;
  174.  
  175. #ifdef DEBUG
  176.     /* Print out the pattern we just compiled. */
  177.     prtpat();
  178. #endif
  179. }
  180.  
  181. /*    srchpat(strng,sz,eosptr)
  182.  *
  183.  *    Function: Using the previously compiled pattern, search the string
  184.  * strng (of size sz) for a line exactly matching the pattern.  Return a
  185.  * pointer to that line, or 0.  On a non-zero return, return in eosptr a
  186.  * pointer to the next character after the matched string.
  187.  *
  188.  *    Algorithm: Repeatedly call match() on each successive line until a
  189.  * line matching the pattern is found, or we run out of data.
  190.  *
  191.  *    Comments: See comments on comppat().
  192.  *    The eosptr return value is passed from match by side-effect.
  193.  */
  194.  
  195. char *srchpat(strng,sz,eosptr)
  196.  
  197. register char *strng;
  198. register unsigned sz;
  199. char **eosptr;
  200.  
  201. {
  202.     /* While we've still got something to search thru. */
  203.     while (sz != 0) {
  204.         /* If this one matches, return it. */
  205.         if (match(strng,sz,cpat)) {
  206.             *eosptr = nextstr;
  207.             return(strng);
  208.         };
  209.         /* Otherwise, find the next line, and try it. */
  210.         while (*strng != eolch) {
  211.             strng++; sz--;
  212.             if (sz == 0) return(0);
  213.         };
  214.         strng++; sz--;    /* Skip EOL. */
  215.     };
  216.     return(0);
  217. }
  218.  
  219. /*    match(sptr,sz,cpptr)
  220.  *
  221.  *    Function: Return TRUE if the string sptr (of size sz) exactly
  222.  * matches the compiled search pattern cpptr.  If returning TRUE, also
  223.  * return the next character past the match in nextstr.
  224.  *
  225.  *    Algorithm: Match only the first element (shortest string first),
  226.  * recursively calling ourself to match the remainder of the string.
  227.  *
  228.  *    Comments: This function is used by srchpat() only.  The user should
  229.  * never call it directly.
  230.  *    nextstr is a side-effect return, which is not generally a nice idea.
  231.  * However, match() is the most crucial routine in this package with regard
  232.  * to execution-time efficiency, and passing another parameter thru the whole
  233.  * recursive search would severly slow things down.
  234.  *    The recursive depth of this routine is bounded by the maximum size
  235.  * of the search pattern.  I.e., with a max pattern size of 100, this routine
  236.  * will never call itself more than 100 times (or is it 101 times?).
  237.  */
  238.  
  239. match(sptr,sz,cpptr)
  240.  
  241. register char *sptr;
  242. register unsigned sz;
  243. register struct pel *cpptr;
  244.  
  245. {
  246.     struct pel *cpp1;    /* cpptr + 1. */
  247.  
  248.     /* If there's nothing left of the string, we can't match it. */
  249.     if (sz == 0) return(FALSE);
  250.  
  251.     /* Calculate next cpptr for later use. */
  252.     cpp1 = cpptr+1;
  253.  
  254.     /* Switch on type of element. */
  255.     switch (cpptr->pel_type) {
  256.  
  257.         /* Match one exactly. */
  258.         case MONEC:
  259.             if (*sptr != cpptr->pel_c) return(FALSE);
  260.             break;
  261.  
  262.         /* Match any one. */
  263.         case MONEA:
  264.             if (*sptr == eolch) return(FALSE);
  265.             break;
  266.  
  267.         /* Match any in set. */
  268.         case MSET:
  269.             if (! inset(cpptr,*sptr)) return(FALSE);
  270.             break;
  271.  
  272.         /* Match zero or more. */
  273.         case MMANY:
  274.             /* Try matching 0, 1, 2, ... */
  275.             do {
  276.                 if (match(sptr,sz,cpp1)) return(TRUE);
  277.                 if (*sptr++ == eolch) break;
  278.             } while (--sz);
  279.             return(FALSE);
  280.  
  281.         /* We'd better not get here! */
  282.         default:
  283. #ifdef DEBUG
  284.             printf("Illegal pel_type in match().\n");
  285. #endif
  286.             exit(1);
  287.     };
  288.  
  289.     /* It matched so see if we're at the end or the rest matches. */
  290.     if (cpptr == cptop) {
  291.         nextstr = sptr+1;    /* Return next char past line. */
  292.         return(TRUE);
  293.     };
  294.  
  295.     /* See if the rest matches. */
  296.     if (match(sptr+1,sz-1,cpp1)) return(TRUE);
  297.  
  298.     /* No match. */
  299.     return(FALSE);
  300. }
  301.  
  302. /*    setall(sptr), clrall(sptr), negset(sptr), setmem(sptr,mem),
  303.  *    setnoc(sptr,mem)
  304.  *
  305.  *    Function: Set operations: set all bits, clear all, complement all,
  306.  * clear one member bit, set one member bit, and set one member bit and it's
  307.  * other case equivalent if a letter.
  308.  *
  309.  *    Algorithm: Obvious.
  310.  *
  311.  *    Comments: One other set operation (inset) is define as a macro
  312.  * for speed.
  313.  */
  314.  
  315. setall(sptr)
  316.  
  317. struct pel *sptr;
  318.  
  319. {
  320.     int i;
  321.     int *iptr;
  322.  
  323.     for (i = SETMAX, iptr = sptr->pel_set; i-- > 0; *iptr++ = 0xFFFF);
  324. }
  325.  
  326. clrall(sptr)
  327.  
  328. struct pel *sptr;
  329.  
  330. {
  331.     int i;
  332.     int *iptr;
  333.  
  334.     for (i = SETMAX, iptr = sptr->pel_set; i-- > 0; *iptr++ = 0);
  335. }
  336.  
  337. negset(sptr)
  338.  
  339. struct pel *sptr;
  340.  
  341. {
  342.     int i;
  343.     int *iptr;
  344.  
  345.     for (i = SETMAX, iptr = sptr->pel_set; i-- > 0;
  346.         *iptr = ~*iptr, iptr++);
  347. }
  348.  
  349. clrmem(sptr,mem)
  350.  
  351. struct pel *sptr;
  352. char mem;
  353.  
  354. {
  355.     sptr->pel_set[(mem>>4)&7] &= ~(1<<(mem&15));
  356. }
  357.  
  358. setmem(sptr,mem)
  359.  
  360. struct pel *sptr;
  361. char mem;
  362.  
  363. {
  364.     sptr->pel_set[(mem>>4)&7] |= (1<<(mem&15));
  365. }
  366.  
  367. setnoc(sptr,mem)
  368.  
  369. struct pel *sptr;
  370. char mem;
  371.  
  372. {
  373.     if ((mem >= 'a') && (mem <= 'z')) setmem(sptr,mem+('A'-'a'));
  374.     else if ((mem >= 'A') && (mem <= 'Z')) setmem(sptr,mem+('a'-'A'));
  375.     setmem(sptr,mem);
  376. }
  377.  
  378. /*    prtpat()
  379.  *
  380.  *    Function: Print the current pattern is a readable form.
  381.  *
  382.  *    Algorithm: Obvious to the casual observer.
  383.  *
  384.  *    Comments: This is for debugging purposes only, and is only compiled
  385.  * or called if DEBUG is defined.
  386.  */
  387.  
  388. #ifdef DEBUG
  389.  
  390. prtpat()
  391.  
  392. {
  393.     struct pel *cpptr;
  394.     char c;
  395.  
  396.     for (cpptr = cpat; cpptr <= cptop; cpptr++) {
  397.         printf("** Prtpat: ");
  398.         switch (cpptr->pel_type) {
  399.             case MMANY:
  400.                 printf("*");
  401.                 break;
  402.             case MONEA:
  403.                 printf("?");
  404.                 break;
  405.             case MONEC:
  406.                 if (cpptr->pel_c < ' ')
  407.                     printf("\\%3.3o",cpptr->pel_c);
  408.                 else printf("%c",cpptr->pel_c);
  409.                 break;
  410.             case MSET:
  411.                 printf("[");
  412.                 for (c = 0; c <= 128; c++ )
  413.                     if (inset(cpptr,c))
  414.                         if (c < ' ')
  415.                             printf(" \\%3.3o",c);
  416.                         else printf(" %c",c);
  417.                 printf("]");
  418.                 break;
  419.             default:
  420.                 printf("Illegal pel_type in prtpat!\n");
  421.                 break;
  422.         };
  423.         printf("\n");
  424.     };
  425. }
  426.  
  427. #endif
  428.