"Fossies" - the Fresh Open Source Software Archive

Member "dateutils-0.4.6/src/dexpr.c" (19 Mar 2019, 12483 Bytes) of package /linux/privat/dateutils-0.4.6.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "dexpr.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 0.4.4_vs_0.4.5.

    1 #if defined HAVE_CONFIG_H
    2 # include "config.h"
    3 #endif  /* HAVE_CONFIG_H */
    4 #include <stdlib.h>
    5 #include <string.h>
    6 #include <stdio.h>
    7 #include <stdbool.h>
    8 #include "strops.h"
    9 #include "dt-locale.h"
   10 #include "dexpr.h"
   11 #include "dexpr-parser.h"
   12 
   13 #if !defined STANDALONE
   14 # if defined __INTEL_COMPILER
   15 #  pragma warning (disable:2259)
   16 # endif /* __INTEL_COMPILER */
   17 # include "dexpr-parser.c"
   18 # if defined __INTEL_COMPILER
   19 #  pragma warning (default:2259)
   20 # endif /* __INTEL_COMPILER */
   21 
   22 # if defined __INTEL_COMPILER
   23 #  pragma warning (disable:2557)
   24 # endif /* __INTEL_COMPILER */
   25 # include "dexpr-scanner.c"
   26 # if defined __INTEL_COMPILER
   27 #  pragma warning (default:2557)
   28 # endif /* __INTEL_COMPILER */
   29 #endif  /* !STANDALONE */
   30 
   31 static void
   32 free_dexpr(dexpr_t root)
   33 {
   34 /* recursive free :( */
   35     switch (root->type) {
   36     case DEX_CONJ:
   37     case DEX_DISJ:
   38         if (root->left != NULL) {
   39             free_dexpr(root->left);
   40             free(root->left);
   41         }
   42         if (root->right != NULL) {
   43             free_dexpr(root->right);
   44             free(root->right);
   45         }
   46         break;
   47     case DEX_UNK:
   48     case DEX_VAL:
   49     default:
   50         break;
   51     }
   52     return;
   53 }
   54 
   55 static __attribute__((unused)) void
   56 __pr_val(struct dexkv_s *kv)
   57 {
   58     switch (kv->sp.spfl) {
   59     case DT_SPFL_N_DCNT_MON:
   60         fputs("%d ", stdout);
   61         break;
   62     case DT_SPFL_N_MON:
   63     case DT_SPFL_S_MON:
   64         fputs("%b ", stdout);
   65         break;
   66     case DT_SPFL_N_YEAR:
   67         fputs("%Y ", stdout);
   68         break;
   69     case DT_SPFL_N_DCNT_WEEK:
   70     case DT_SPFL_S_WDAY:
   71         fputs("%a ", stdout);
   72         break;
   73     case DT_SPFL_N_WCNT_MON:
   74         fputs("%c ", stdout);
   75         break;
   76     case DT_SPFL_N_DCNT_YEAR:
   77         fputs("%D ", stdout);
   78         break;
   79     case DT_SPFL_N_WCNT_YEAR:
   80         fputs("%C ", stdout);
   81         break;
   82     default:
   83         break;
   84     }
   85 
   86     switch (kv->op) {
   87     case OP_LT:
   88         fputs("< ", stdout);
   89         break;
   90     case OP_LE:
   91         fputs("<= ", stdout);
   92         break;
   93     case OP_GT:
   94         fputs("> ", stdout);
   95         break;
   96     case OP_GE:
   97         fputs(">= ", stdout);
   98         break;
   99     case OP_NE:
  100         fputs("!= ", stdout);
  101         break;
  102     case OP_EQ:
  103     default:
  104         fputs("== ", stdout);
  105         break;
  106     }
  107 
  108     switch (kv->sp.spfl) {
  109     case DT_SPFL_N_STD: {
  110         char buf[32];
  111         dt_strfdt(buf, sizeof(buf), NULL, kv->d);
  112         fputs(buf, stdout);
  113         break;
  114     }
  115     case DT_SPFL_N_DCNT_MON:
  116         fprintf(stdout, "%02d", kv->s);
  117         break;
  118     case DT_SPFL_N_MON:
  119     case DT_SPFL_S_MON:
  120         if (kv->s >= 0 && kv->s <= 12) {
  121             fputs(dut_abbr_mon[kv->s], stdout);
  122         }
  123         break;
  124     case DT_SPFL_N_YEAR:
  125         fprintf(stdout, "%04d", kv->s);
  126         break;
  127     case DT_SPFL_N_DCNT_WEEK:
  128     case DT_SPFL_S_WDAY:
  129         if (kv->s >= 0 && kv->s <= 7) {
  130             fputs(dut_abbr_wday[kv->s], stdout);
  131         }
  132         break;
  133     case DT_SPFL_N_WCNT_MON:
  134     case DT_SPFL_N_WCNT_YEAR:
  135         fprintf(stdout, "%02d", kv->s);
  136         break;
  137     case DT_SPFL_N_DCNT_YEAR:
  138         fprintf(stdout, "%03d", kv->s);
  139         break;
  140     default:
  141         break;
  142     }
  143     return;
  144 }
  145 
  146 static __attribute__((unused)) void
  147 __pr(dexpr_t root, size_t ind)
  148 {
  149     switch (root->type) {
  150     case DEX_VAL:
  151         for (size_t i = 0; i < ind; i++) {
  152             fputc(' ', stdout);
  153         }
  154         if (root->nega) {
  155             fputs("!(", stdout);
  156         }
  157         __pr_val(root->kv);
  158         if (root->nega) {
  159             fputs(")\n", stdout);
  160         } else {
  161             fputc('\n', stdout);
  162         }
  163         break;
  164 
  165     case DEX_CONJ:
  166         for (size_t i = 0; i < ind; i++) {
  167             fputc(' ', stdout);
  168         }
  169         if (!root->nega) {
  170             fputs("AND\n", stdout);
  171         } else {
  172             fputs("NAND\n", stdout);
  173         }
  174         __pr(root->left, ind + 2);
  175         __pr(root->right, ind + 2);
  176         break;
  177 
  178     case DEX_DISJ:
  179         for (size_t i = 0; i < ind; i++) {
  180             fputc(' ', stdout);
  181         }
  182         if (!root->nega) {
  183             fputs("OR\n", stdout);
  184         } else {
  185             fputs("NOR\n", stdout);
  186         }
  187         __pr(root->left, ind + 2);
  188         __pr(root->right, ind + 2);
  189         break;
  190 
  191     case DEX_UNK:
  192     default:
  193         for (size_t i = 0; i < ind; i++) {
  194             fputc(' ', stdout);
  195         }
  196         if (root->left != NULL) {
  197             fputs("ROOT\n", stderr);
  198             __pr(root->left, ind + 2);
  199             break;
  200         }
  201         break;
  202     }
  203     return;
  204 }
  205 
  206 static __attribute__((unused)) void
  207 __pr_infix(dexpr_t root)
  208 {
  209     if (root->type == DEX_VAL) {
  210         __pr_val(root->kv);
  211         return;
  212     }
  213 
  214     __pr_infix(root->left);
  215 
  216     switch (root->type) {
  217     case DEX_CONJ:
  218         fputs(" && ", stdout);
  219         break;
  220 
  221     case DEX_DISJ:
  222         fputs(" || ", stdout);
  223         break;
  224 
  225     case DEX_VAL:
  226     case DEX_UNK:
  227     default:
  228         /* shouldn't happen :O */
  229         fputs(" bollocks ", stdout);
  230         break;
  231         
  232     }
  233     __pr_infix(root->right);
  234 
  235     /* just ascend */
  236     return;
  237 }
  238 
  239 
  240 static dexpr_t
  241 make_dexpr(dex_type_t type)
  242 {
  243     dexpr_t res;
  244 
  245     if ((res = calloc(1, sizeof(*res))) != NULL) {
  246         res->type = type;
  247     }
  248     return res;
  249 }
  250 
  251 static dexpr_t
  252 dexpr_copy(const_dexpr_t src)
  253 {
  254     dexpr_t res;
  255 
  256     if ((res = calloc(1, sizeof(*res))) == NULL) {
  257         return NULL;
  258     }
  259     /* otherwise start by (shallow) copying things */
  260     memcpy(res, src, sizeof(*res));
  261 
  262     /* deep copy anyone? */
  263     switch (src->type) {
  264     case DEX_CONJ:
  265     case DEX_DISJ:
  266         res->left = dexpr_copy(src->left);
  267         res->right = dexpr_copy(src->right);
  268         break;
  269     case DEX_VAL:
  270     case DEX_UNK:
  271     default:
  272         break;
  273     }
  274     return res;
  275 }
  276 
  277 static dexpr_t
  278 dexpr_copy_j(dexpr_t src)
  279 {
  280 /* copy SRC, but only if it's a junction (disjunction or conjunction) */
  281     if (src->type == DEX_VAL) {
  282         return (dexpr_t)src;
  283     }
  284     return dexpr_copy(src);
  285 }
  286 
  287 static void
  288 __dnf(dexpr_t root)
  289 {
  290 /* recursive __dnf'er */
  291     switch (root->type) {
  292     case DEX_CONJ: {
  293         /* check if one of the children is a disjunction */
  294         dex_type_t rlt = root->left->type;
  295         dex_type_t rrt = root->right->type;
  296 
  297         if (rlt == DEX_DISJ && rrt == DEX_DISJ) {
  298             /* complexestest case
  299              * (a|b)&(c|d) -> (a&c)|(a&d)|(b&c)|(b&d) */
  300             dexpr_t a;
  301             dexpr_t b;
  302             dexpr_t c;
  303             dexpr_t d;
  304 
  305             /* get the new idea of b and c */
  306             a = root->left->left;
  307             b = root->left->right;
  308             c = root->right->left;
  309             d = root->right->right;
  310 
  311             /* now reuse what's possible */
  312             root->type = DEX_DISJ;
  313             root->left->type = DEX_CONJ;
  314 #if 0
  315             /* silly assignment, a comes from left->left */
  316             root->left->left = a;
  317 #endif  /* 0 */
  318             root->left->right = c;
  319 
  320             root->right->type = DEX_DISJ;
  321             root->right->left = make_dexpr(DEX_CONJ);
  322             root->right->left->left = dexpr_copy_j(a);
  323             root->right->left->right = d;
  324 
  325             root->right->right = make_dexpr(DEX_DISJ);
  326             root->right->right->left = make_dexpr(DEX_CONJ);
  327             root->right->right->left->left = b;
  328             root->right->right->left->right = dexpr_copy_j(c);
  329             /* right side, finalise the right branches with CONJ */
  330             root->right->right->right = make_dexpr(DEX_CONJ);
  331             root->right->right->right->left = dexpr_copy_j(b);
  332             root->right->right->right->right = dexpr_copy_j(d);
  333 
  334         } else if (rlt == DEX_DISJ || rrt == DEX_DISJ) {
  335             /* ok'ish case
  336              * a&(b|c) -> a&b|a&c
  337              * the other case gets normalised: (a|b)&c -> c&(a|b) */
  338             dexpr_t a;
  339             dexpr_t b;
  340             dexpr_t c;
  341 
  342             /* put the non-DISJ case left */
  343             if ((a = root->left)->type == DEX_DISJ) {
  344                 a = root->right;
  345                 root->right = root->left;
  346             }
  347             /* get the new idea of b and c */
  348             b = root->right->left;
  349             c = root->right->right;
  350 
  351             /* turn into disjoint */
  352             root->type = DEX_DISJ;
  353 
  354             /* inflate left branch */
  355             root->left = make_dexpr(DEX_CONJ);
  356             root->left->left = a;
  357             root->left->right = b;
  358 
  359             /* rearrange this node now, reuse the right disjoint */
  360             root->right->type = DEX_CONJ;
  361             root->right->left = a;
  362             root->right->right = c;
  363         }
  364         /* fallthrough! */
  365     }
  366     case DEX_DISJ:
  367         /* nothing to be done other than a quick descent */
  368         __dnf(root->left);
  369         __dnf(root->right);
  370 
  371         /* upon ascent fixup double OR's */
  372         if (root->left->type == DEX_DISJ &&
  373             root->right->type == DEX_DISJ) {
  374             /*      |             |
  375              *    /   \          / \
  376              *   |     |    ~>  a   |
  377              *  / \   / \          / \
  378              * a   b c   d        b   |
  379              *                       / \
  380              *                      c   d */
  381             dexpr_t i = root->left;
  382             dexpr_t j = root->right;
  383             dexpr_t a = i->left;
  384             dexpr_t b = i->right;
  385             dexpr_t c = j->left;
  386 
  387             root->left = a;
  388             root->right = i;
  389             i->left = b;
  390             i->right = j;
  391             j->left = c;
  392 
  393         } else if (root->left->type == DEX_DISJ) {
  394             /*     |           |
  395              *    / \         / \
  396              *   |   c   ~>  a   |
  397              *  / \             / \
  398              * a   b           b   c */
  399             dexpr_t i = root->left;
  400             dexpr_t c = root->right;
  401             dexpr_t a = i->left;
  402             dexpr_t b = i->right;
  403 
  404             root->left = a;
  405             root->right = i;
  406             i->left = b;
  407             i->right = c;
  408         }
  409         break;
  410 
  411     case DEX_VAL:
  412     case DEX_UNK:
  413     default:
  414         /* can't do anything to get the DNF going */
  415         break;
  416     }
  417     return;
  418 }
  419 
  420 static void
  421 __nega_kv(struct dexkv_s *kv)
  422 {
  423 /* assume the parent dexpr has the nega flag set, negate KV */
  424     kv->op = ~kv->op;
  425     return;
  426 }
  427 
  428 static void
  429 __denega(dexpr_t root)
  430 {
  431     dexpr_t left;
  432     dexpr_t right;
  433 
  434     if (root->nega) {
  435         /* negate */
  436         root->nega = 0;
  437 
  438         switch (root->type) {
  439         case DEX_CONJ:
  440             /* !(a&b) -> !a | !b */
  441             root->type = DEX_DISJ;
  442             break;
  443         case DEX_DISJ:
  444             /* !(a|b) -> !a & !b */
  445             root->type = DEX_DISJ;
  446             break;
  447         case DEX_VAL:
  448             __nega_kv(root->kv);
  449             /* fallthrough */
  450         case DEX_UNK:
  451         default:
  452             return;
  453         }
  454 
  455         if ((left = root->left) != NULL) {
  456             left->nega = ~left->nega;
  457         }
  458         if ((right = root->right) != NULL) {
  459             right->nega = ~right->nega;
  460         }
  461     } else {
  462         switch (root->type) {
  463         case DEX_CONJ:
  464         case DEX_DISJ:
  465             left = root->left;
  466             right = root->right;
  467             break;
  468         case DEX_VAL:
  469         case DEX_UNK:
  470         default:
  471             return;
  472         }
  473     }
  474     /* descend */
  475     if (left != NULL) {
  476         __denega(left);
  477     }
  478     if (right != NULL) {
  479         __denega(right);
  480     }
  481     return;
  482 }
  483 
  484 static void
  485 dexpr_simplify(dexpr_t root)
  486 {
  487     __denega(root);
  488     __dnf(root);
  489     return;
  490 }
  491 
  492 static int
  493 __cmp(struct dt_dt_s stream, struct dt_dt_s cell)
  494 {
  495 /* special promoting/demoting version of dt_dtcmp()
  496  * if CELL is d-only or t-only, demote STREAM */
  497     if (dt_sandwich_only_d_p(cell)) {
  498         return dt_dcmp(stream.d, cell.d);
  499     } else if (dt_sandwich_only_t_p(cell)) {
  500         return dt_tcmp(stream.t, cell.t);
  501     }
  502     return dt_dtcmp(stream, cell);
  503 }
  504 
  505 
  506 static bool
  507 dexkv_matches_p(const_dexkv_t dkv, struct dt_dt_s d)
  508 {
  509     signed int cmp;
  510     bool res;
  511 
  512     if (dkv->sp.spfl == DT_SPFL_N_STD) {
  513         if ((cmp = __cmp(d, dkv->d)) == -2) {
  514             return false;
  515         }
  516         switch (dkv->op) {
  517         case OP_UNK:
  518         case OP_EQ:
  519             res = cmp == 0;
  520             break;
  521         case OP_LT:
  522             res = cmp < 0;
  523             break;
  524         case OP_LE:
  525             res = cmp <= 0;
  526             break;
  527         case OP_GT:
  528             res = cmp > 0;
  529             break;
  530         case OP_GE:
  531             res = cmp >= 0;
  532             break;
  533         case OP_NE:
  534             res = cmp != 0;
  535             break;
  536         case OP_TRUE:
  537             res = true;
  538             break;
  539         default:
  540             res = false;
  541             break;
  542         }
  543         return res;
  544     }
  545     /* otherwise it's stuff that uses the S slot */
  546     switch (dkv->sp.spfl) {
  547     case DT_SPFL_N_YEAR:
  548         cmp = dt_get_year(d.d);
  549         break;
  550     case DT_SPFL_N_MON:
  551     case DT_SPFL_S_MON:
  552         cmp = dt_get_mon(d.d);
  553         break;
  554     case DT_SPFL_N_DCNT_MON:
  555         cmp = dt_get_mday(d.d);
  556         break;
  557     case DT_SPFL_N_DCNT_WEEK:
  558     case DT_SPFL_S_WDAY:
  559         cmp = dt_get_wday(d.d);
  560         break;
  561     case DT_SPFL_N_WCNT_MON:
  562         /* exotic function, needs extern'ing */
  563         cmp = dt_get_wcnt_mon(d.d);
  564         break;
  565     case DT_SPFL_N_DCNT_YEAR:
  566         cmp = dt_get_yday(d.d);
  567         break;
  568     case DT_SPFL_N_WCNT_YEAR:
  569         /* %C/%W week count */
  570         cmp = dt_get_wcnt_year(d.d, dkv->sp.wk_cnt);
  571         break;
  572     case DT_SPFL_N_STD:
  573     default:
  574         return false;
  575     }
  576     /* now do the actual comparison */
  577     switch (dkv->op) {
  578     case OP_EQ:
  579         res = dkv->s == cmp;
  580         break;
  581     case OP_LT:
  582         res = dkv->s < cmp;
  583         break;
  584     case OP_LE:
  585         res = dkv->s <= cmp;
  586         break;
  587     case OP_GT:
  588         res = dkv->s > cmp;
  589         break;
  590     case OP_GE:
  591         res = dkv->s >= cmp;
  592         break;
  593     case OP_NE:
  594         res = dkv->s != cmp;
  595         break;
  596     case OP_TRUE:
  597         res = true;
  598         break;
  599     default:
  600     case OP_UNK:
  601         res = false;
  602         break;
  603     }
  604     return res;
  605 }
  606 
  607 static bool
  608 __conj_matches_p(const_dexpr_t dex, struct dt_dt_s d)
  609 {
  610     const_dexpr_t a;
  611 
  612     for (a = dex; a->type == DEX_CONJ; a = a->right) {
  613         if (!dexkv_matches_p(a->left->kv, d)) {
  614             return false;
  615         }
  616     }
  617     /* rightmost cell might be a DEX_VAL */
  618     return dexkv_matches_p(a->kv, d);
  619 }
  620 
  621 static bool
  622 __disj_matches_p(const_dexpr_t dex, struct dt_dt_s d)
  623 {
  624     const_dexpr_t o;
  625 
  626     for (o = dex; o->type == DEX_DISJ; o = o->right) {
  627         if (__conj_matches_p(o->left, d)) {
  628             return true;
  629         }
  630     }
  631     /* rightmost cell may be a DEX_VAL */
  632     return __conj_matches_p(o, d);
  633 }
  634 
  635 static __attribute__((unused)) bool
  636 dexpr_matches_p(const_dexpr_t dex, struct dt_dt_s d)
  637 {
  638     return __disj_matches_p(dex, d);
  639 }
  640 
  641 
  642 #if defined STANDALONE
  643 const char *prog = "dexpr";
  644 
  645 int
  646 main(int argc, char *argv[])
  647 {
  648     dexpr_t root;
  649 
  650     for (int i = 1; i < argc; i++) {
  651         root = NULL;
  652         dexpr_parse(&root, argv[i], strlen(argv[i]));
  653         __pr(root, 0);
  654         fputc('\n', stdout);
  655         dexpr_simplify(root);
  656         __pr(root, 0);
  657         fputc('\n', stdout);
  658         /* also print an infix line */
  659         __pr_infix(root);
  660         fputc('\n', stdout);
  661         free_dexpr(root);
  662     }
  663     return 0;
  664 }
  665 #endif  /* STANDALONE */
  666 
  667 /* dexpr.c ends here */