home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / comm / ums / SUMSTools.lha / UMS / Tools / SUMSTools / Source / filter.c < prev    next >
C/C++ Source or Header  |  1995-08-03  |  9KB  |  436 lines
  1. /*
  2. ** General Purpose Expression Filter Code.
  3. **
  4. ** You need a BitHook and a FilterSpec to customize this.
  5. **
  6. ** Your data needs to have the ability to flag certain entries
  7. ** with certain bits and select some of them with mask and match
  8. ** values, just as UMS. This is absolutely necessary for a fast
  9. ** and efficient filter handling!
  10. **
  11. ** This code is prepared to have complexity values for expressions.
  12. ** Complex expressions (that might take a long time to evaluate)
  13. ** would be calculated after less complex expressions already
  14. ** clipped away a considerable amount of data.
  15. **
  16. ** sumstools don't make use of these complexity values for now,
  17. ** all complexity values are set to 0.
  18. */
  19.  
  20. /*  30-Jan-94 [kmel] Corrected misfeature with filter token, "AND"
  21. **                   and "OR" were also recognized in expressions.
  22. */
  23.  
  24. #include <exec/memory.h>
  25.  
  26. #include "sumstl.h"
  27.  
  28. #include <stdio.h>
  29. #include <ctype.h>
  30.  
  31. #include "filter.h"
  32.  
  33. #define between(a,x,b) ((UBYTE)(x)>=(UBYTE)(a) && (UBYTE)(x)<=(UBYTE)(b))
  34.  
  35.  
  36. struct Expression
  37. {
  38.     struct Expression *left;
  39.     struct Expression *right;
  40.  
  41.     struct Hook *hook;
  42.     ULONG uid;
  43.     APTR udata;
  44.  
  45.     UBYTE relation;
  46.     UBYTE complexity;
  47.  
  48.     char data[1];
  49. };
  50.  
  51. #define REL_NONE      0
  52. #define REL_FIRST     1
  53. #define REL_LOWEQ     1
  54. #define REL_HIGHEQ    2
  55. #define REL_LOWER     3
  56. #define REL_HIGHER    4
  57. #define REL_NOTEQUAL  5
  58. #define REL_EQUAL     6
  59. #define REL_LAST      6
  60.  
  61. #define CON_FIRST     7
  62. #define CON_OR        7
  63. #define CON_AND       8
  64. #define CON_LAST      8
  65.  
  66. #define OPEN_BRACE    9
  67. #define CLOSE_BRACE   10
  68.  
  69. struct FilterTokenize
  70. {
  71.     char *name;
  72.     char token;
  73. };
  74.  
  75. static struct FilterTokenize Tokens[] =
  76. {
  77.     { "OR" , CON_OR       },
  78.     { "|"  , CON_OR       },
  79.     { "AND", CON_AND      },
  80.     { "&"  , CON_AND      },
  81.     { "<=" , REL_LOWEQ    },
  82.     { ">=" , REL_HIGHEQ   },
  83.     { "<"  , REL_LOWER    },
  84.     { ">"  , REL_HIGHER   },
  85.     { "!=" , REL_NOTEQUAL },
  86.     { "<>" , REL_NOTEQUAL },
  87.     { "="  , REL_EQUAL    },
  88.     { "("  , OPEN_BRACE   },
  89.     { ")"  , CLOSE_BRACE  },
  90.     { NULL , 0            }
  91. };
  92.  
  93.  
  94. static char *FilterTokenize(char *spec,struct FilterTokenize *tokens)
  95. {
  96.     struct FilterTokenize *x;
  97.     char *str = spec;
  98.     BOOL anf = FALSE, space = FALSE, con;
  99.     int len;
  100.  
  101.     while (*str)
  102.     {
  103. //        printf("spec: %s    space: %d\n", spec, space);
  104.  
  105.         if (*str=='"')
  106.         {
  107.             anf = !anf;
  108.             memmove(str,str+1,strlen(str));
  109.         }
  110.         else if (!anf)
  111.         {
  112.             if (*str==' ')
  113.             {
  114.                 memmove(str,str+1,strlen(str));
  115.                 space = TRUE;
  116.             }
  117.             else
  118.             {
  119.                 for (x=tokens; x->name; x++)
  120.                 {
  121.                     if (!strnicmp(str, x->name, len = strlen(x->name)))
  122.                     {
  123. //                        printf("Token: %s   space: %d\n", x->name, space);
  124.  
  125.                         if ((con = between(CON_FIRST, x->token, CON_LAST)) && (*(str+len) != ' '))
  126.                             space = FALSE;
  127.  
  128.                         if (!con || space)
  129.                         {
  130. //                            printf("Token inserted: %s\n", x->name);
  131.  
  132.                             *str = x->token;
  133.  
  134.                             if (len>1)
  135.                                 memmove(str+1, str+len,strlen(str+len)+1);
  136.  
  137.                             break;
  138.                         }
  139.                     }
  140.                 }
  141.  
  142.                 if (!x->name)
  143.                     str++;
  144.  
  145.                 space = FALSE;
  146.             }
  147.  
  148.         }
  149.         else
  150.             str++;
  151.     }
  152.  
  153.     return(spec);
  154. }
  155.  
  156.  
  157. static struct FilterSpec *FindFilterSpec(struct FilterSpec *spec,char *name,int len)
  158. {
  159.     struct FilterSpec *fs;
  160.  
  161.     for (fs=spec;fs->keyword;fs++)
  162.         if (!(strnicmp(fs->keyword,name,len)))
  163.             return(fs);
  164.  
  165.     return(NULL);
  166. }
  167.  
  168.  
  169. #define FCERROR ((char *)-1)
  170.  
  171. static char *findconj(char *str,int len)
  172. {
  173.     int blevel = 0;
  174.  
  175.     while (len--)
  176.     {
  177.         if (!blevel && between(CON_FIRST,*str,CON_LAST))
  178.         {
  179.             return(str);
  180.         }
  181.         else if (*str==OPEN_BRACE)
  182.         {
  183.             blevel++;
  184.         }
  185.         else if (*str==CLOSE_BRACE)
  186.         {
  187.             if (!blevel) return(FCERROR);
  188.             blevel--;
  189.         }
  190.         str++;
  191.     }
  192.  
  193.     return(blevel ? FCERROR : NULL);
  194. }
  195.  
  196.  
  197. static VOID deleteexp(struct Expression *exp)
  198. {
  199.     if (exp)
  200.     {
  201.         deleteexp(exp->left);
  202.         deleteexp(exp->right);
  203.         FreeVec(exp);
  204.     }
  205. }
  206.  
  207.  
  208. static APTR createexp(LONG *err,struct Hook *hook,struct FilterSpec *spec,char *str,int len)
  209. {
  210.     char *c;
  211.     struct Expression *exp;
  212.  
  213.     if (len==-1) len=strlen(str);
  214.  
  215.     if (len<1)
  216.     {
  217.         *err = FIL_ERROR_EMPTYEXPRESSION;
  218.         return(NULL);
  219.     }
  220.  
  221.     if ((c=findconj(str,len)) == FCERROR)
  222.     {
  223.         *err = FIL_ERROR_UNMATCHEDBRACES;
  224.         return(NULL);
  225.     }
  226.  
  227.     if (c)
  228.     {
  229.         if (exp=AllocVec(sizeof(struct Expression),MEMF_CLEAR))
  230.         {
  231.             if (exp->left = createexp(err,hook,spec,str,c-str))
  232.             {
  233.                 if (exp->right = createexp(err,hook,spec,c+1,len-(c-str)-1))
  234.                 {
  235.                     exp->hook = hook;
  236.                     exp->relation = *c;
  237.                     return(exp);
  238.                 }
  239.             }
  240.             deleteexp(exp);
  241.         }
  242.         else
  243.             *err = FIL_ERROR_OUTOFMEMORY;
  244.  
  245.         return(NULL);
  246.     }
  247.     else if (str[0]==OPEN_BRACE)
  248.     {
  249.         if (str[len-1]!=CLOSE_BRACE)
  250.         {
  251.             *err = FIL_ERROR_UNMATCHEDBRACES;
  252.             return(NULL);
  253.         }
  254.         return(createexp(err,hook,spec,str+1,len-2));
  255.     }
  256.     else if (len>=3)
  257.     {
  258.         int l;
  259.         struct FilterSpec *fs;
  260.  
  261.         c = str;
  262.  
  263.         while (*c && !between(REL_FIRST,*c,REL_LAST))
  264.             c++;
  265.  
  266.         if (!*c)
  267.         {
  268.             *err = FIL_ERROR_MISC;
  269.             return(NULL);
  270.         }
  271.  
  272.         if ((l = c - str)<1)
  273.         {
  274.             *err = FIL_ERROR_MISC;
  275.             return(NULL);
  276.         }
  277.  
  278.         if (!(fs = FindFilterSpec(spec,str,l)))
  279.         {
  280.             *err = FIL_ERROR_UNKNOWNKEYWORD;
  281.             return(NULL);
  282.         }
  283.  
  284.         str += l+1;
  285.         len -= l+1;
  286.  
  287.         if (len<0)
  288.         {
  289.             *err = FIL_ERROR_MISC;
  290.             return(NULL);
  291.         }
  292.  
  293.         if (!(exp=AllocVec(sizeof(struct Expression)+len,MEMF_CLEAR)))
  294.         {
  295.             *err = FIL_ERROR_OUTOFMEMORY;
  296.             return(NULL);
  297.         }
  298.  
  299.         exp->hook       = hook;
  300.         exp->uid        = fs->id;
  301.         exp->udata      = fs->data;
  302.         exp->relation   = *c;
  303.         exp->complexity = 0;
  304.         if (len>0) strncpy(exp->data,str,len);
  305.  
  306.         return(exp);
  307.     }
  308.  
  309.     *err = FIL_ERROR_MISC;
  310.     return(NULL);
  311. }
  312.  
  313.  
  314. static LONG filterexp(struct Expression *exp,APTR data,ULONG mask,ULONG match,ULONG setbit)
  315. {
  316.     int err;
  317.     ULONG help = setbit<<1;
  318.  
  319.     /*printf("fexp: mask %08lx match %08lx set %08lx\n",mask,match,setbit);*/
  320.  
  321.     if (help & (FIL_LASTBIT>>2)) return(FIL_ERROR_TOODEEP);
  322.  
  323.     mask |= setbit;
  324.  
  325.     switch (exp->relation)
  326.     {
  327.         case CON_AND:
  328.         {
  329.             ULONG help2 = help<<1;
  330.  
  331.             if (exp->left->complexity <= exp->right->complexity)
  332.             {
  333.                 if (err=filterexp(exp->left ,data,mask,match,help)) return(err);
  334.                 if (err=filterexp(exp->right,data,mask|help,match|help,help2)) return(err);
  335.             }
  336.             else
  337.             {
  338.                 if (err=filterexp(exp->right,data,mask,match,help)) return(err);
  339.                 if (err=filterexp(exp->left ,data,mask|help,match|help,help2)) return(err);
  340.             }
  341.             if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask|help|help2,match|help|help2,setbit,help2,FIL_ACTION_BITS,NULL)) return(err);
  342.             if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask|help,match|help,0,help,FIL_ACTION_BITS,NULL)) return(err);
  343.         }
  344.         break;
  345.  
  346.         case CON_OR:
  347.         {
  348.             if (exp->left->complexity <= exp->right->complexity)
  349.             {
  350.                 if (err=filterexp(exp->left ,data,mask,match,setbit)) return(err);
  351.                 if (err=filterexp(exp->right,data,mask,match,setbit)) return(err);
  352.             }
  353.             else
  354.             {
  355.                 if (err=filterexp(exp->right,data,mask,match,setbit)) return(err);
  356.                 if (err=filterexp(exp->left ,data,mask,match,setbit)) return(err);
  357.             }
  358.         }
  359.         break;
  360.  
  361.         default:
  362.         {
  363.             switch (exp->relation)
  364.             {
  365.                 case REL_EQUAL:
  366.                 {
  367.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask,match,setbit,0,FIL_ACTION_EQUAL,exp->data)) return(err);
  368.                 }
  369.                 break;
  370.  
  371.                 case REL_NOTEQUAL:
  372.                 {
  373.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask,match,help,0,FIL_ACTION_EQUAL,exp->data)) return(err);
  374.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask|help,match,setbit,0,FIL_ACTION_BITS,NULL)) return(err);
  375.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask|help,match|help,0,help,FIL_ACTION_BITS,NULL)) return(err);
  376.                 }
  377.                 break;
  378.  
  379.                 case REL_LOWEQ:
  380.                 {
  381.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask,match,setbit,0,FIL_ACTION_EQUAL,exp->data)) return(err);
  382.                 }
  383.                 case REL_LOWER:
  384.                 {
  385.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask,match,setbit,0,FIL_ACTION_LOWER,exp->data)) return(err);
  386.                 }
  387.                 break;
  388.  
  389.                 case REL_HIGHER:
  390.                 {
  391.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask,match,help,0,FIL_ACTION_EQUAL,exp->data)) return(err);
  392.                 }
  393.                 case REL_HIGHEQ:
  394.                 {
  395.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask,match,help,0,FIL_ACTION_LOWER,exp->data)) return(err);
  396.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask|help,match,setbit,0,FIL_ACTION_BITS,NULL)) return(err);
  397.                      if (err=CallHook(exp->hook,data,exp->uid,exp->udata,mask|help,match|help,0,help,FIL_ACTION_BITS,NULL)) return(err);
  398.                 }
  399.                 break;
  400.  
  401.             }
  402.         }
  403.         break;
  404.     }
  405.  
  406.     return(FIL_ERROR_OK);
  407. }
  408.  
  409.  
  410.  
  411. /*
  412. ** That's the master function. You call only this one from outside.
  413. */
  414.  
  415. LONG FilterExpression(struct Hook *hook,struct FilterSpec *spec,char *str,APTR data,ULONG mask,ULONG match,ULONG setbit)
  416. {
  417.     LONG err;
  418.     struct Expression *exp;
  419.     char *dup;
  420.  
  421.     if (dup=AllocVec(strlen(str)+1,MEMF_ANY))
  422.     {
  423.         strcpy(dup,str);
  424.  
  425.         if (exp=createexp(&err,hook,spec,FilterTokenize(dup,Tokens),strlen(dup)))
  426.         {
  427.             err=filterexp(exp,data,mask,match,setbit);
  428.             deleteexp(exp);
  429.         }
  430.  
  431.         FreeVec(dup);
  432.     }
  433.  
  434.     return(err);
  435. }
  436.