public inbox for lvm2-cvs@sourceware.org help / color / mirror / Atom feed
From: thornber@sourceware.org To: lvm-devel@redhat.com, lvm2-cvs@sourceware.org Subject: LVM2 libdm/regex/matcher.c unit-tests/regex/ma ... Date: Wed, 21 Jul 2010 12:00:00 -0000 [thread overview] Message-ID: <20100721120054.20328.qmail@sourceware.org> (raw) CVSROOT: /cvs/lvm2 Module name: LVM2 Changes by: thornber@sourceware.org 2010-07-21 12:00:53 Modified files: libdm/regex : matcher.c unit-tests/regex: matcher_t.expected matcher_t.expected2 Log message: [REGEX] factor _calc_state() out of _calc_states() Patches: http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/matcher.c.diff?cvsroot=lvm2&r1=1.8&r2=1.9 http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/unit-tests/regex/matcher_t.expected.diff?cvsroot=lvm2&r1=1.2&r2=1.3 http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/unit-tests/regex/matcher_t.expected2.diff?cvsroot=lvm2&r1=1.1&r2=1.2 --- LVM2/libdm/regex/matcher.c 2010/07/21 11:58:49 1.8 +++ LVM2/libdm/regex/matcher.c 2010/07/21 12:00:53 1.9 @@ -38,6 +38,13 @@ int charsets_entered; struct rx_node **charsets; struct dm_pool *scratch, *mem; + + /* stuff for on the fly dfa calculation */ + dm_bitset_t charmap[256]; + dm_bitset_t dfa_copy; + struct ttree *tt; + dm_bitset_t bs; + struct state_queue *h, *t; }; static int _count_nodes(struct rx_node *rx) @@ -217,26 +224,60 @@ return r; } +static void _calc_state(struct dm_regex *m, struct state_queue *h, int a) +{ + int set_bits = 0, i; + struct dfa_state *dfa = h->s; + dm_bitset_t dfa_bits = h->bits; + dm_bit_and(m->dfa_copy, m->charmap[a], dfa_bits); + + /* iterate through all the states in firstpos */ + for (i = dm_bit_get_first(m->dfa_copy); i >= 0; i = dm_bit_get_next(m->dfa_copy, i)) { + if (a == TARGET_TRANS) + dfa->final = m->charsets[i]->final; + + dm_bit_union(m->bs, m->bs, m->charsets[i]->followpos); + set_bits = 1; + } + + if (set_bits) { /* FIXME: this is always true */ + struct state_queue *tmp; + struct dfa_state *ldfa = ttree_lookup(m->tt, m->bs + 1); + if (!ldfa) { + /* push */ + ldfa = _create_dfa_state(m->mem); + ttree_insert(m->tt, m->bs + 1, ldfa); + tmp = _create_state_queue(m->scratch, ldfa, m->bs); + if (!m->h) + m->h = m->t = tmp; + else { + m->t->next = tmp; + m->t = tmp; + } + } + + dfa->lookup[a] = ldfa; + dm_bit_clear_all(m->bs); + } +} + static int _calc_states(struct dm_regex *m, struct rx_node *rx) { unsigned iwidth = (m->num_charsets / DM_BITS_PER_INT) + 1; - struct ttree *tt = ttree_create(m->scratch, iwidth); - struct state_queue *h, *t, *tmp; - struct dfa_state *dfa, *ldfa; - int i, a, set_bits = 0, count = 0; - dm_bitset_t bs, dfa_bits; + struct dfa_state *dfa; + int i, a; - if (!tt) + m->tt = ttree_create(m->scratch, iwidth); + if (!m->tt) return_0; - if (!(bs = dm_bitset_create(m->scratch, m->num_charsets))) + if (!(m->bs = dm_bitset_create(m->scratch, m->num_charsets))) return_0; /* build some char maps */ - dm_bitset_t charmap[256]; for (a = 0; a < 256; a++) { - charmap[a] = dm_bitset_create(m->scratch, m->num_charsets); - if (!charmap[a]) + m->charmap[a] = dm_bitset_create(m->scratch, m->num_charsets); + if (!m->charmap[a]) return_0; } @@ -245,76 +286,31 @@ if (n->type == CHARSET) { for (a = dm_bit_get_first(n->charset); a >= 0; a = dm_bit_get_next(n->charset, a)) - dm_bit_set(charmap[a], n->charset_index); + dm_bit_set(m->charmap[a], n->charset_index); } } /* create first state */ dfa = _create_dfa_state(m->mem); m->start = dfa; - ttree_insert(tt, rx->firstpos + 1, dfa); + ttree_insert(m->tt, rx->firstpos + 1, dfa); /* prime the queue */ - h = t = _create_state_queue(m->scratch, dfa, rx->firstpos); - dm_bitset_t dfa_copy = dm_bitset_create(m->scratch, m->num_charsets); - while (h) { - int elems, idx[h->bits[0]]; + m->h = m->t = _create_state_queue(m->scratch, dfa, rx->firstpos); + m->dfa_copy = dm_bitset_create(m->scratch, m->num_charsets); + /* keep processing until there's nothing in the queue */ + struct state_queue *s; + while ((s = m->h)) { /* pop state off front of the queue */ - dfa = h->s; - dfa_bits = h->bits; - h = h->next; + m->h = m->h->next; /* iterate through all the inputs for this state */ - dm_bit_clear_all(bs); - - /* Cache list of locations of bits */ - elems = 0; - for (i = dm_bit_get_first(dfa_bits); - i >= 0; i = dm_bit_get_next(dfa_bits, i)) - idx[elems++] = i; - - for (a = 0; a < 256; a++) { - dm_bit_and(dfa_copy, charmap[a], dfa_bits); - - /* iterate through all the states in firstpos */ - for (i = dm_bit_get_first(dfa_copy); - i >= 0; i = dm_bit_get_next(dfa_copy, i)) { - if (a == TARGET_TRANS) - dfa->final = m->charsets[i]->final; - - dm_bit_union(bs, bs, - m->charsets[i]->followpos); - set_bits = 1; - } - - if (set_bits) { - ldfa = ttree_lookup(tt, bs + 1); - if (!ldfa) { - /* push */ - ldfa = _create_dfa_state(m->mem); - ttree_insert(tt, bs + 1, ldfa); - tmp = - _create_state_queue(m->scratch, - ldfa, bs); - if (!h) - h = t = tmp; - else { - t->next = tmp; - t = tmp; - } - - count++; - } - - dfa->lookup[a] = ldfa; - set_bits = 0; - dm_bit_clear_all(bs); - } - } + dm_bit_clear_all(m->bs); + for (a = 0; a < 256; a++) + _calc_state(m, s, a); } - log_debug("Matcher built with %d dfa states", count); return 1; } --- LVM2/unit-tests/regex/matcher_t.expected 2010/07/20 15:32:07 1.2 +++ LVM2/unit-tests/regex/matcher_t.expected 2010/07/21 12:00:53 1.3 @@ -1,4 +1,3 @@ -Matcher built with 23 dfa states fingerprint: 352b6c4f /dev/loop/0 : loop/[0-9]+ /dev/loop/1 : loop/[0-9]+ --- LVM2/unit-tests/regex/matcher_t.expected2 2010/07/21 11:52:46 1.1 +++ LVM2/unit-tests/regex/matcher_t.expected2 2010/07/21 12:00:53 1.2 @@ -1,2 +1 @@ -Matcher built with 447 dfa states fingerprint: eed8ceb8
reply other threads:[~2010-07-21 12:00 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
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=20100721120054.20328.qmail@sourceware.org \ --to=thornber@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).