home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_disks / 400-499 / ff473.lzh / CNewsSrc / cnews_src.lzh / libcnews / ngmatch.c < prev    next >
C/C++ Source or Header  |  1990-12-25  |  7KB  |  247 lines
  1. /*
  2.  * ngmatch - newsgroup name matching
  3.  *
  4.  * ngmatch returns true iff the newsgroup(s) in ngs match
  5.  * the pattern(s) in ngpat, where
  6.  *
  7.  *     ngpats: { ngpat { "," ngpat }* }?
  8.  *    ngpat: "!"? word { "." word }*
  9.  *    word: { alphanum }+ | "all"
  10.  *
  11.  * Only one group need match for success.
  12.  * Failure to match any pattern with a group is a mismatch of that group only.
  13.  * Failure to match any group against any pattern is a total failure.
  14.  *
  15.  * For each group, note the depth of each match against the patterns,
  16.  * negated or not.  Ignore mismatches.  The deepest match wins at the
  17.  * end:  a deeper negated match is a failure, a deeper plain match is a
  18.  * success; a tie is a failure, but see the description of wildcards.
  19.  *
  20.  * "all" in a pattern is a wildcard that matches exactly one word;
  21.  * it does not cross "." (NGDELIM) delimiters.  A non-wildcard match is
  22.  * considered to have matched slightly deeper than a wildcard match in the
  23.  * same position.  This ensures that !alt.sex.all,alt.sex.bondage matches
  24.  * alt.sex.bondage.
  25.  */
  26.  
  27. #include <stdio.h>
  28. #include <string.h>
  29. #ifdef unix
  30. # include <sys/types.h>
  31. #endif /* unix */
  32. #include "news.h"
  33.  
  34. #define truth(bool) ((bool)? "yes": "no")
  35.  
  36. #ifndef STATIC
  37. #define STATIC /* static */
  38. #endif
  39.  
  40. #define ALL "all"            /* word wildcard */
  41.  
  42. /* private */
  43. static boolean debug = NO;
  44.  
  45. /* forwards */
  46. FORWARD boolean mpatsmatch();
  47. FORWARD int onepatmatch();
  48.  
  49. void
  50. matchdebug(state)
  51. boolean state;
  52. {
  53.     debug = state;
  54. }
  55.  
  56. boolean
  57. ngmatch(ngpat, ngs)
  58. char *ngpat, *ngs;
  59. {
  60.     register char *ngp;            /* point at current group */
  61.     register char *ngcomma;
  62.     register char *rngpat = ngpat;
  63.  
  64.     if (debug)
  65.         (void) fprintf(stderr, "ngmatch(`%s', `%s')\n", rngpat, ngs);
  66.     for (ngp = ngs; ngp != NULL; ngp = ngcomma) {
  67.         register boolean match;
  68.  
  69.         STRCHR(ngp, NGSEP, ngcomma);
  70.         if (ngcomma != NULL)
  71.             *ngcomma = '\0';    /* will be restored below */
  72.         match = mpatsmatch(rngpat, ngp); /* try 1 group, n-patterns */
  73.         if (ngcomma != NULL)
  74.             *ngcomma++ = NGSEP;    /* point after the comma */
  75.         if (match)
  76.             return YES;
  77.     }
  78.     return NO;            /* no pattern matched any group */
  79. }
  80.  
  81. /*
  82.  * Match one group against multiple patterns, as above.
  83.  * The key is to keep track of how deeply plain and negated patterns matched.
  84.  */
  85. STATIC boolean
  86. mpatsmatch(ngpat, grp)
  87. char *ngpat, *grp;
  88. {
  89.     register char *patp;        /* point at current pattern */
  90.     register char *patcomma;
  91.     register int depth;
  92.     register int faildeepest = 0, hitdeepest = 0;    /* in case no match */
  93.     register boolean negation;
  94.     register char *rgrp = grp;        /* optimisation */
  95.  
  96.     if (debug)
  97.         (void) fprintf(stderr, "mpatsmatch(`%s', `%s')\n", ngpat, grp);
  98.     for (patp = ngpat; patp != NULL; patp = patcomma) {
  99.         negation = NO;
  100.         STRCHR(patp, NGSEP, patcomma);
  101.         if (patcomma != NULL)
  102.             *patcomma = '\0';    /* will be restored below */
  103.         if (*patp == NGNEG) {
  104.             ++patp;
  105.             negation = YES;
  106.         }
  107.         depth = onepatmatch(patp, rgrp);    /* try 1 pattern, 1 group */
  108.         if (patcomma != NULL)
  109.             *patcomma++ = NGSEP;    /* point after the comma */
  110.         if (depth == 0)            /* mis-match */
  111.             ;            /* ignore it */
  112.         else if (negation) {
  113.             /* record depth of deepest negated matched word */
  114.             if (depth > faildeepest)
  115.                 faildeepest = depth;
  116.         } else {
  117.             /* record depth of deepest plain matched word */
  118.             if (depth > hitdeepest)
  119.                 hitdeepest = depth;
  120.         }
  121.     }
  122.     if (debug)
  123.         (void) fprintf(stderr, "mpatsmatch(`%s', `%s') returns %s\n",
  124.             ngpat, grp, truth(hitdeepest > faildeepest));
  125.     return hitdeepest > faildeepest;
  126. }
  127.  
  128. /*
  129.  * Match a pattern against a group by looking at each word of pattern in turn.
  130.  *
  131.  * On a match, return the depth (roughly, ordinal number * k) of the rightmost
  132.  * word that matches.  If group runs out first, the match fails; if pattern
  133.  * runs out first, it succeeds.  On a failure, return zero.
  134.  */
  135. STATIC int
  136. onepatmatch(patp, grp)
  137. char *patp, *grp;
  138. {
  139.     register char *rpatwd;        /* used by word match (inner loop) */
  140.     register char *patdot, *grdot;    /* point at dots after words */
  141.     register char *patwd, *grwd;    /* point at current words */
  142.     register int depth = 0;
  143.  
  144.     for (patwd = patp, grwd = grp; patwd != NULL && grwd != NULL;
  145.         patwd = patdot, grwd = grdot) {
  146.         register boolean match = NO;
  147.         register int incr = 20;
  148.  
  149.         /*
  150.          * optimisation: first bytes *must* match, unless first
  151.          * pattern byte is start of ALL.
  152.          */
  153.         if (*patwd != *grwd && *patwd != ALL[0]) {
  154.             depth = 0;        /* words differed - mismatch */
  155.             break;
  156.         }
  157.  
  158.             /* null-terminate words */
  159.             STRCHR(patwd, NGDELIM, patdot);
  160.         if (patdot != NULL)
  161.             *patdot = '\0';        /* will be restored below */
  162.             STRCHR(grwd, NGDELIM, grdot);
  163.         if (grdot != NULL)
  164.             *grdot = '\0';        /* will be restored below */
  165.  
  166.         /*
  167.          * Match one word of pattern with one word of group.
  168.          * A pattern word of "all" matches any group word,
  169.          * but isn't worth as much.
  170.          */
  171. #ifdef FAST_STRCMP
  172.         match = STREQ(patwd, grwd);
  173.         if (!match && STREQ(patwd, ALL)) {
  174.             match = YES;
  175.             --incr;
  176.         }
  177. #else
  178.         for (rpatwd = patwd; *rpatwd == *grwd++; )
  179.             if (*rpatwd++ == '\0') {
  180.                 match = YES;        /* literal match */
  181.                 break;
  182.             }
  183.         if (!match) {
  184.             /* ugly special case match for "all" */
  185.             rpatwd = patwd;
  186.             if (*rpatwd++ == 'a' && *rpatwd++ == 'l' &&
  187.                 *rpatwd++ == 'l' && *rpatwd   == '\0') {
  188.                 match = YES;
  189.                 --incr;
  190.             }
  191.         }
  192. #endif                /* FAST_STRCMP */
  193.  
  194.         if (patdot != NULL)
  195.             *patdot++ = NGDELIM;    /* point after the dot */
  196.         if (grdot != NULL)
  197.             *grdot++ = NGDELIM;
  198.         if (!match) {
  199.             depth = 0;        /* words differed - mismatch */
  200.             break;
  201.         }
  202.         depth += incr;
  203.     }
  204.     /* if group name ran out before pattern, then match fails */
  205.     if (grwd == NULL && patwd != NULL)
  206.         depth = 0;
  207.     if (debug)
  208.         (void) fprintf(stderr, "onepatmatch(`%s', `%s') returns %d\n",
  209.             patp, grp, depth);
  210.     return depth;
  211. }
  212.  
  213. #ifdef CROSS_POSTINGS_RESTRICTED
  214. /*
  215.  * ngtopsame(ngs) - true iff ngs are all in the same top-level distribution
  216.  */
  217. boolean
  218. ngtopsame(ngs)
  219. register char *ngs;
  220. {
  221.     register char *nextng;
  222.  
  223.     STRCHR(ngs, NGSEP, nextng);
  224.     if (nextng == NULL)        /* no groups left */
  225.         return YES;
  226.     ++nextng;            /* skip NGSEP */
  227.     return firstsame(ngs, nextng) && ngtopsame(nextng);
  228. }
  229.  
  230. /*
  231.  * firstsame(ng1, ng2) - true iff first characters (up to the first
  232.  * NGDELIM or NGSEP) are the same in each string.  Neither string
  233.  * is guaranteed to be null-terminated (a small lie; one *is*).
  234.  */
  235. STATIC boolean
  236. firstsame(ng1, ng2)
  237. register char *ng1, *ng2;
  238. {
  239.     register int ng1brk;
  240.     static char delimstr[] = { NGSEP, NGDELIM, '\0' };
  241.     extern int strcspn();
  242.  
  243.     ng1brk = strcspn(ng1, delimstr);
  244.     return ng1brk == strcspn(ng2, delimstr) && STREQN(ng1, ng2, ng1brk);
  245. }
  246. #endif                /* CROSS_POSTINGS_RESTRICTED */
  247.