From: thornber@sourceware.org <thornber@sourceware.org>
To: lvm-devel@redhat.com
Subject: LVM2 libdm/regex/matcher.c unit-tests/regex/ma ...
Date: 21 Jul 2010 12:00:54 -0000 [thread overview]
Message-ID: <20100721120054.20328.qmail@sourceware.org> (raw)
CVSROOT: /cvs/lvm2
Module name: LVM2
Changes by: thornber at 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 \
/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: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.