public inbox for lvm2-cvs@sourceware.org help / color / mirror / Atom feed
From: agk@sourceware.org To: lvm-devel@redhat.com, lvm2-cvs@sourceware.org Subject: LVM2/libdm/regex parse_rx.c Date: Thu, 22 Apr 2010 13:18:00 -0000 [thread overview] Message-ID: <20100422131829.14207.qmail@sourceware.org> (raw) CVSROOT: /cvs/lvm2 Module name: LVM2 Changes by: agk@sourceware.org 2010-04-22 13:18:27 Modified files: libdm/regex : parse_rx.c Log message: fix leftmost rotation Patches: http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.5&r2=1.6 --- LVM2/libdm/regex/parse_rx.c 2010/04/22 03:24:24 1.5 +++ LVM2/libdm/regex/parse_rx.c 2010/04/22 13:18:27 1.6 @@ -16,6 +16,8 @@ #include "dmlib.h" #include "parse_rx.h" +#include <ctype.h> + struct parse_sp { /* scratch pad for the parsing process */ struct dm_pool *mem; int type; /* token type, 0 indicates a charset */ @@ -413,24 +415,36 @@ return 0; } -static struct rx_node *_exchange_nodes(struct dm_pool *mem, struct rx_node *r, struct rx_node *left_cat, struct rx_node *right_cat, unsigned leftmost) +/* If top node is OR, rotate from ((ab)|((ac)|d)) to (((ab)|(ac))|d) */ +static int _rotate_ors(struct rx_node *r) +{ + struct rx_node *old_r_right; + + if (r->type == OR && r->right->type == OR) { + old_r_right = r->right; + r->right = old_r_right->right; + old_r_right->right = old_r_right->left; + old_r_right->left = r->left; + r->left = old_r_right; + return 1; + } + + return 0; +} + +static struct rx_node *_exchange_nodes(struct dm_pool *mem, struct rx_node *r, + struct rx_node *left_cat, struct rx_node *right_cat, + unsigned leftmost) { - struct rx_node *new_r, *new_cat; + struct rx_node *new_r; - /* FIXME Clean up leftmost */ if (leftmost) { - new_r = r->right; - new_cat = _node(mem, CAT, left_cat->left, r); - if (!new_cat) + new_r = _node(mem, CAT, left_cat->left, r); + if (!new_r) return_NULL; - new_r->left = new_cat; memcpy(left_cat, left_cat->right, sizeof(*left_cat)); - r->right = right_cat->right; - - /* FIXME Avoid this */ - if (new_r->right == right_cat->right) - new_r = new_r->left; + memcpy(right_cat, right_cat->right, sizeof(*right_cat)); } else { new_r = _node(mem, CAT, r, right_cat->right); if (!new_r) @@ -447,6 +461,8 @@ struct rx_node *r, int *changed) { + struct rx_node *left, *right; + /* * walk the tree, optimising every 'or' node. */ @@ -475,18 +491,17 @@ if (!(r->right = _pass(mem, r->right, changed))) return_NULL; - { - struct rx_node *left, *right; - - if (_find_leftmost_common(r, &left, &right, 1)) { + if (_find_leftmost_common(r, &left, &right, 1)) { + /* + * If rotate_ors changes the tree, left and right are stale, + * so just set 'changed' to repeat the search. + */ + if (!_rotate_ors(r)) r = _exchange_nodes(mem, r, left, right, 1); - - *changed = 1; - } else if (_find_leftmost_common(r, &left, &right, 0)) { - r = _exchange_nodes(mem, r, left, right, 0); - - *changed = 1; - } + *changed = 1; + } else if (_find_leftmost_common(r, &left, &right, 0)) { + r = _exchange_nodes(mem, r, left, right, 0); + *changed = 1; } break;
next reply other threads:[~2010-04-22 13:18 UTC|newest] Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top 2010-04-22 13:18 agk [this message] -- strict thread matches above, loose matches on Subject: below -- 2010-11-02 20:10 agk 2010-08-09 10:29 thornber 2010-04-22 20:15 agk 2010-04-22 14:33 agk 2010-04-22 13:42 agk 2010-04-22 3:24 agk 2010-04-20 22:31 agk
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20100422131829.14207.qmail@sourceware.org \ --to=agk@sourceware.org \ --cc=lvm-devel@redhat.com \ --cc=lvm2-cvs@sourceware.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).