home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 387b.lha / dice_v2.02 / lib / extra / wildcard.c < prev   
Encoding:
C/C++ Source or Header  |  1990-05-30  |  6.9 KB  |  352 lines
  1.  
  2. /*
  3.  *  WILDCARD.C        AmigaDos wildcard comparator
  4.  *
  5.  *            WARNING:  Uses *Lots* of stack
  6.  *
  7.  *  (c)Copyright 1990, Matthew Dillon, All Rights Reserved
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <errno.h>
  13.  
  14. #define CompWild    _CompWild
  15. #define ParseWild   _ParseWild
  16. #define FreeWild    _FreeWild
  17.  
  18. /*
  19.  *  Example:    #(a|b|c)xx  consts of:
  20.  *
  21.  *    masternode(#), wn_Next = xx
  22.  *               wn_Sub  = (a|b|c)
  23.  *
  24.  *    (a|b|c) wn_Next ->  a, wn_Next = NULL, wn_Sib = b
  25.  *                b, wn_Next = NULL, wn_Sib = c
  26.  *                c, wn_Next = NULL, wn_Sib = NULL
  27.  *
  28.  *  Etc...
  29.  *
  30.  *  The most complexity occurs when dealing with '#' ... this could
  31.  *  probably be made more efficient.  Basically, we run through all
  32.  *  possible repeats from N to none at all.  For example, if the pattern
  33.  *  is #?x  then we try ????x ???x ??x ?x, and x.  The number of repeats
  34.  *  we try is currently STUPIDLY set to the length of the name remaining
  35.  *  since that is the worst case.
  36.  *
  37.  *  Note that this algorithm correctly handles extremely complex patterns
  38.  *  like:   #(a|b#?|c).o
  39.  */
  40.  
  41. typedef struct WildNode {
  42.     struct WildNode *wn_Next;    /*  next wild node (append to current) */
  43.     struct WildNode *wn_Sib;    /*  sibling wild node (a|b|c|d)        */
  44.     struct WildNode *wn_Sub;    /*  sub wildnode #(a|b|c)              */
  45.     struct WildNode *wn_Cont;    /*  used at Compare time           */
  46.     const char *wn_Pat;     /*  patterns not containing | or #     */
  47.     short wn_PatLen;        /*  length of pattern        */
  48.     short wn_Type;        /*  '|', '#', or 0          */
  49.     short wn_Repeat;        /*  # of repeats (for '#')  */
  50. } WildNode;
  51.  
  52. WildNode *ParseSubWild();
  53.  
  54. /*
  55.  *  Parse the structure & run
  56.  */
  57.  
  58. static char *BotStack;
  59.  
  60. WildNode *
  61. _ParseWild(pat, patlen)
  62. const char *pat;
  63. short patlen;
  64. {
  65.     short i;
  66.     WildNode *wn = NULL;
  67.     WildNode **wnext = &wn;
  68.  
  69.     if (patlen == 0)
  70.     return(NULL);
  71.  
  72.     while (i = extinpat(pat, patlen)) {
  73.     *wnext = ParseSubWild(pat, i);
  74.  
  75.     wnext = &(*wnext)->wn_Sib;
  76.  
  77.     pat += i;
  78.     patlen -= i;
  79.     if (patlen && *pat == '|') {
  80.         ++pat;
  81.         --patlen;
  82.     }
  83.     }
  84.     return(wn);
  85. }
  86.  
  87. static WildNode *
  88. ParseSubWild(pat, patlen)
  89. const char *pat;
  90. short patlen;
  91. {
  92.     WildNode *wn;
  93.  
  94.     short i;
  95.  
  96.     if (patlen == 0)
  97.     return(NULL);
  98.  
  99.     wn = calloc(sizeof(WildNode), 1);
  100.  
  101.     for (i = 0; i < patlen; ++i) {
  102.     if (pat[i] == '#' || pat[i] == '(')
  103.         break;
  104.     if (pat[i] == '\'')
  105.         ++i;
  106.     }
  107.  
  108.     if (i) {
  109.     wn->wn_Pat = pat;
  110.     wn->wn_PatLen = i;
  111.     wn->wn_Next = ParseSubWild(pat + i, patlen - i);
  112.     } else if (*pat == '#') {
  113.     ++pat;
  114.     --patlen;
  115.     i = extonepat(pat, patlen);
  116.     wn->wn_Sub  = ParseWild(pat, i);
  117.     wn->wn_Type = '#';
  118.     wn->wn_Next = ParseSubWild(pat + i, patlen - i);
  119.     } else if (*pat == '(') {
  120.     i = extonepat(pat, patlen);
  121.     wn->wn_Sub = ParseWild(pat + 1, i - 2);
  122.     wn->wn_Type = 0;
  123.     wn->wn_Next = ParseSubWild(pat + i, patlen - i);
  124.     }
  125.     return(wn);
  126. }
  127.  
  128. void
  129. FreeWild(wn)
  130. WildNode *wn;
  131. {
  132.     if (wn) {
  133.     if (wn->wn_Sib)
  134.         FreeWild(wn->wn_Sib);
  135.     if (wn->wn_Next)
  136.         FreeWild(wn->wn_Next);
  137.     if (wn->wn_Sub)
  138.         FreeWild(wn->wn_Sub);
  139.     free(wn);
  140.     }
  141. }
  142.  
  143. void
  144. _SetWildStack(n)
  145. long n;
  146. {
  147.     BotStack = (char *)&n - n;
  148. }
  149.  
  150. /*
  151.  *  CompWild().     Pretty straight forward except for '#'.
  152.  *
  153.  *  The 'cont' field is a linked string of nodes that specify patterns
  154.  *  that must be successfully compared after the current pattern, 'wn',
  155.  *  compares successfully.  When we are dealing with repeats of a
  156.  *  pattern, such as #(a|b).o, then the 'cont' field is used to specify
  157.  *  that (a|b) should be repeated wn_Repeat times.
  158.  *
  159.  *  A further complication occurs with: #(a|b#?).o, where we have a
  160.  *  nested repeat loop.  In this case as 'cont' is scanned ONLY the
  161.  *  top repeat loop is decremented by the 'cont' code.  The inner loop
  162.  *  will be decremented by the '#' code.  Thus, when we skip to the
  163.  *  next 'cont' we must skip any nodes with non-zero wn_Repeat
  164.  *
  165.  *  I am not entirely certain that I've done it properly, the code is
  166.  *  complex.
  167.  */
  168.  
  169. CompWild(name, wn, cont)
  170. const char *name;
  171. WildNode *wn;
  172. WildNode *cont;
  173. {
  174.     {
  175.     char x;
  176.  
  177.     if (&x < BotStack) {
  178.         errno = ESTACK;
  179.         return(-1);
  180.     }
  181.     }
  182. top:
  183.     if (wn == NULL) {
  184.     if (cont) {
  185.         if (cont->wn_Repeat) {
  186.         if (--cont->wn_Repeat) {
  187.             wn = cont->wn_Sub;
  188.             cont = cont;
  189.         } else {
  190.             wn = cont->wn_Sub;
  191.             cont = cont->wn_Cont;
  192.             while (cont && cont->wn_Repeat)
  193.             cont = cont->wn_Cont;
  194.         }
  195.         goto top;
  196.         } else {
  197.         wn = cont;
  198.         cont = cont->wn_Cont;
  199.         while (cont && cont->wn_Repeat)
  200.             cont = cont->wn_Cont;
  201.         goto top;
  202.         /*return(CompWild(name, cont, cont->wn_Cont));*/
  203.         }
  204.     }
  205.     if (*name)
  206.         return(-1);
  207.     return(0);
  208.     }
  209.     /*printf("foo %08lx (%d)%.*s\n", wn, wn->wn_PatLen, wn->wn_PatLen, wn->wn_Pat);*/
  210.     if (wn->wn_PatLen) {
  211.     const char *pat = wn->wn_Pat;
  212.     const char *oname = name;
  213.     short patlen;
  214.  
  215.     for (patlen = wn->wn_PatLen; patlen > 0; --patlen, ++pat) {
  216.         switch(*pat) {
  217.         case '%':
  218.         break;
  219.         case '?':
  220.         if (*name == 0)
  221.             patlen = 0;     /*    fail    */
  222.         ++name;
  223.         break;
  224.         case '\'':
  225.         ++pat;
  226.         --patlen;
  227.         /* fall through */
  228.         default:
  229.         if (*name != *pat)
  230.             patlen = 0;     /*    fail    */
  231.         ++name;
  232.         break;
  233.         }
  234.     }
  235.     if (patlen < 0 || CompWild(name, wn->wn_Next, cont) < 0) {
  236.         if (wn->wn_Sib)
  237.         return(CompWild(oname, wn->wn_Sib, cont));
  238.         return(-1);
  239.     }
  240.     return(0);
  241.     }
  242.     {
  243.     WildNode *next = wn->wn_Next;
  244.  
  245.     if (next) {
  246.         next->wn_Cont = cont;
  247.         cont = next;
  248.     }
  249.     if (wn->wn_Type == '#') {
  250.         short i = strlen(name);
  251.  
  252.         while (i > 0) {
  253.         wn->wn_Cont = cont;
  254.         wn->wn_Repeat = i;
  255.         if (CompWild(name, NULL, wn) >= 0) {
  256.             wn->wn_Repeat = 0;
  257.             return(0);
  258.         }
  259.         --i;
  260.         }
  261.         wn->wn_Repeat = 0;
  262.         if (CompWild(name, NULL, cont) < 0) {
  263.         if (wn->wn_Sib) {
  264.             wn = wn->wn_Sib;
  265.             goto top;
  266.         }
  267.         return(-1);
  268.         }
  269.         return(0);
  270.     } else {
  271.         if (CompWild(name, wn->wn_Sub, cont) < 0) {
  272.         if (wn->wn_Sib == NULL)
  273.             return(-1);
  274.         wn = wn->wn_Sib;
  275.         goto top;
  276.         /*return(CompWild(name, wn->wn_Sib, cont));*/
  277.         }
  278.         return(0);
  279.     }
  280.     }
  281. }
  282.  
  283.  
  284. static int
  285. extonepat(pat, patlen)
  286. const char *pat;
  287. int patlen;
  288. {
  289.     if (patlen <= 0) {
  290.     printf("PATLEN BAD %d\n", patlen);
  291.     return(0);
  292.     }
  293.     switch(*pat) {
  294.     case '?':
  295.     case '%':
  296.     return(1);
  297.     case '#':
  298.     return(1 + extonepat(pat + 1, patlen - 1);
  299.     case '|':
  300.     puts("extone, unexpected '|'");
  301.     return(0);
  302.     case '(':
  303.     {
  304.         short pcnt = 0;
  305.         short i = 0;
  306.  
  307.         while (patlen) {
  308.         ++i;
  309.         if (*pat == '(')
  310.             ++pcnt;
  311.         if (*pat == ')' && --pcnt == 0)
  312.             return(i);
  313.         ++pat;
  314.         --patlen;
  315.         }
  316.     }
  317.     puts("unexpected EOF looking for ')'");
  318.     return(0);
  319.     case '\'':
  320.     if (patlen < 2) {
  321.         puts("extone, unexpected EOF at '");
  322.         return(0);
  323.     }
  324.     return(2);
  325.     default:
  326.     return(1);
  327.     }
  328.     /* not reached */
  329. }
  330.  
  331.  
  332. static int
  333. extinpat(pat, patlen)
  334. const char *pat;
  335. int patlen;
  336. {
  337.     int i;
  338.     short paren = 0;
  339.  
  340.     for (i = 0; i < patlen; ++i) {
  341.     if (pat[i] == '(')
  342.         ++paren;
  343.     if (pat[i] == ')' && --paren < 0)
  344.         return(i);
  345.     if (pat[i] == '|' && paren == 0)
  346.         return(i);
  347.     }
  348.     return(i);
  349. }
  350.  
  351.  
  352.