From 4d6089c042e36b777f470621cfe84461da121eb6 Mon Sep 17 00:00:00 2001 From: Alasdair Kergon Date: Thu, 22 Apr 2010 20:35:24 +0000 Subject: [PATCH] Cache bitset locations to speed up _calc_states. (kabi) --- WHATS_NEW_DM | 1 + libdm/regex/matcher.c | 13 +++++++++++-- 2 files changed, 12 insertions(+), 2 deletions(-) diff --git a/WHATS_NEW_DM b/WHATS_NEW_DM index c96260ceb..4e2d0e978 100644 --- a/WHATS_NEW_DM +++ b/WHATS_NEW_DM @@ -1,5 +1,6 @@ Version 1.02.47 - ================================= + Cache bitset locations to speed up _calc_states. Add a regex optimisation pass for shared character prefixes. Add dm_bit_and and dm_bitset_equal to libdevmapper. Simplify dm_bitset_create. diff --git a/libdm/regex/matcher.c b/libdm/regex/matcher.c index d9c2d8ad5..fe3979d41 100644 --- a/libdm/regex/matcher.c +++ b/libdm/regex/matcher.c @@ -212,6 +212,8 @@ static int _calc_states(struct dm_regex *m, struct rx_node *rx) /* prime the queue */ h = t = _create_state_queue(m->scratch, dfa, rx->firstpos); while (h) { + int elems, j, idx[h->bits[0]]; + /* pop state off front of the queue */ dfa = h->s; dfa_bits = h->bits; @@ -219,10 +221,17 @@ static int _calc_states(struct dm_regex *m, struct rx_node *rx) /* 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++) { /* iterate through all the states in firstpos */ - for (i = dm_bit_get_first(dfa_bits); - i >= 0; i = dm_bit_get_next(dfa_bits, i)) { + for (j = 0; j < elems; j++) { + i = idx[j]; if (dm_bit(m->nodes[i]->charset, a)) { if (a == TARGET_TRANS) dfa->final = m->nodes[i]->final; -- 2.43.5