summaryrefslogtreecommitdiff
path: root/libdm/regex
diff options
context:
space:
mode:
Diffstat (limited to 'libdm/regex')
-rw-r--r--libdm/regex/matcher.c183
-rw-r--r--libdm/regex/ttree.c1
2 files changed, 113 insertions, 71 deletions
diff --git a/libdm/regex/matcher.c b/libdm/regex/matcher.c
index 9590865..aa58d98 100644
--- a/libdm/regex/matcher.c
+++ b/libdm/regex/matcher.c
@@ -1,6 +1,6 @@
/*
* Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
- * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
+ * Copyright (C) 2004-2012 Red Hat, Inc. All rights reserved.
*
* This file is part of the device-mapper userspace tools.
*
@@ -98,21 +98,27 @@ static void _fill_table(struct dm_regex *m, struct rx_node *rx)
m->charsets[m->charsets_entered++] = rx;
}
-static void _create_bitsets(struct dm_regex *m)
+static int _create_bitsets(struct dm_regex *m)
{
- int i;
+ unsigned i;
+ struct rx_node *n;
for (i = 0; i < m->num_nodes; i++) {
- struct rx_node *n = m->nodes[i];
- n->firstpos = dm_bitset_create(m->scratch, m->num_charsets);
- n->lastpos = dm_bitset_create(m->scratch, m->num_charsets);
- n->followpos = dm_bitset_create(m->scratch, m->num_charsets);
+ n = m->nodes[i];
+ if (!(n->firstpos = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
+ if (!(n->lastpos = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
+ if (!(n->followpos = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
}
+
+ return 1;
}
static void _calc_functions(struct dm_regex *m)
{
- int i, j, final = 1;
+ unsigned i, j, final = 1;
struct rx_node *rx, *c1, *c2;
for (i = 0; i < m->num_nodes; i++) {
@@ -206,14 +212,17 @@ static struct dfa_state *_create_state_queue(struct dm_pool *mem,
struct dfa_state *dfa,
dm_bitset_t bits)
{
- dfa->bits = dm_bitset_create(mem, bits[0]); /* first element is the size */
+ if (!(dfa->bits = dm_bitset_create(mem, bits[0]))) /* first element is the size */
+ return_NULL;
+
dm_bit_copy(dfa->bits, bits);
dfa->next = 0;
- dfa->final = -1;
+ dfa->final = -1;
+
return dfa;
}
-static void _calc_state(struct dm_regex *m, struct dfa_state *dfa, int a)
+static int _calc_state(struct dm_regex *m, struct dfa_state *dfa, int a)
{
int set_bits = 0, i;
dm_bitset_t dfa_bits = dfa->bits;
@@ -233,9 +242,12 @@ static void _calc_state(struct dm_regex *m, struct dfa_state *dfa, int a)
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 (!(ldfa = _create_dfa_state(m->mem)))
+ return_0;
+
+ ttree_insert(m->tt, m->bs + 1, ldfa);
+ if (!(tmp = _create_state_queue(m->scratch, ldfa, m->bs)))
+ return_0;
if (!m->h)
m->h = m->t = tmp;
else {
@@ -247,31 +259,32 @@ static void _calc_state(struct dm_regex *m, struct dfa_state *dfa, int a)
dfa->lookup[a] = ldfa;
dm_bit_clear_all(m->bs);
}
+
+ return 1;
}
static int _calc_states(struct dm_regex *m, struct rx_node *rx)
{
unsigned iwidth = (m->num_charsets / DM_BITS_PER_INT) + 1;
struct dfa_state *dfa;
- int i, a;
+ struct rx_node *n;
+ unsigned i;
+ int a;
- m->tt = ttree_create(m->scratch, iwidth);
- if (!m->tt)
+ if (!(m->tt = ttree_create(m->scratch, iwidth)))
return_0;
if (!(m->bs = dm_bitset_create(m->scratch, m->num_charsets)))
return_0;
/* build some char maps */
- for (a = 0; a < 256; a++) {
- m->charmap[a] = dm_bitset_create(m->scratch, m->num_charsets);
- if (!m->charmap[a])
- return_0;
- }
+ for (a = 0; a < 256; a++)
+ if (!(m->charmap[a] = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
for (i = 0; i < m->num_nodes; i++) {
- struct rx_node *n = m->nodes[i];
- if (n->type == CHARSET) {
+ n = m->nodes[i];
+ 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(m->charmap[a], n->charset_index);
@@ -279,13 +292,19 @@ static int _calc_states(struct dm_regex *m, struct rx_node *rx)
}
/* create first state */
- dfa = _create_dfa_state(m->mem);
+ if (!(dfa = _create_dfa_state(m->mem)))
+ return_0;
+
m->start = dfa;
ttree_insert(m->tt, rx->firstpos + 1, dfa);
/* prime the queue */
- m->h = m->t = _create_state_queue(m->scratch, dfa, rx->firstpos);
- m->dfa_copy = dm_bitset_create(m->scratch, m->num_charsets);
+ if (!(m->h = m->t = _create_state_queue(m->scratch, dfa, rx->firstpos)))
+ return_0;
+
+ if (!(m->dfa_copy = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
+
return 1;
}
@@ -293,7 +312,7 @@ static int _calc_states(struct dm_regex *m, struct rx_node *rx)
* Forces all the dfa states to be calculated up front, ie. what
* _calc_states() used to do before we switched to calculating on demand.
*/
-static void _force_states(struct dm_regex *m)
+static int _force_states(struct dm_regex *m)
{
int a;
@@ -306,15 +325,18 @@ static void _force_states(struct dm_regex *m)
/* iterate through all the inputs for this state */
dm_bit_clear_all(m->bs);
for (a = 0; a < 256; a++)
- _calc_state(m, s, a);
+ if (!_calc_state(m, s, a))
+ return_0;
}
+
+ return 1;
}
struct dm_regex *dm_regex_create(struct dm_pool *mem, const char * const *patterns,
unsigned num_patterns)
{
char *all, *ptr;
- int i;
+ unsigned i;
size_t len = 0;
struct rx_node *rx;
struct dm_regex *m;
@@ -347,24 +369,29 @@ struct dm_regex *dm_regex_create(struct dm_pool *mem, const char * const *patter
m->mem = mem;
m->scratch = scratch;
m->num_nodes = _count_nodes(rx);
- m->num_charsets = _count_charsets(rx);
- _enumerate_charsets(rx);
- m->nodes = dm_pool_alloc(scratch, sizeof(*m->nodes) * m->num_nodes);
- if (!m->nodes)
+ m->num_charsets = _count_charsets(rx);
+ _enumerate_charsets(rx);
+ if (!(m->nodes = dm_pool_alloc(scratch, sizeof(*m->nodes) * m->num_nodes)))
goto_bad;
- m->charsets = dm_pool_alloc(scratch, sizeof(*m->charsets) * m->num_charsets);
- if (!m->charsets)
- goto_bad;
+ if (!(m->charsets = dm_pool_alloc(scratch, sizeof(*m->charsets) * m->num_charsets)))
+ goto_bad;
_fill_table(m, rx);
- _create_bitsets(m);
+
+ if (!_create_bitsets(m))
+ goto_bad;
+
_calc_functions(m);
- _calc_states(m, rx);
+
+ if (!_calc_states(m, rx))
+ goto_bad;
+
return m;
bad:
dm_pool_free(mem, m);
+
return NULL;
}
@@ -373,14 +400,17 @@ static struct dfa_state *_step_matcher(struct dm_regex *m, int c, struct dfa_sta
struct dfa_state *ns;
if (!(ns = cs->lookup[(unsigned char) c])) {
- _calc_state(m, cs, (unsigned char) c);
+ if (!_calc_state(m, cs, (unsigned char) c))
+ return_NULL;
+
if (!(ns = cs->lookup[(unsigned char) c]))
return NULL;
}
// yuck, we have to special case the target trans
- if (ns->final == -1)
- _calc_state(m, ns, TARGET_TRANS);
+ if ((ns->final == -1) &&
+ !_calc_state(m, ns, TARGET_TRANS))
+ return_NULL;
if (ns->final && (ns->final > *r))
*r = ns->final;
@@ -433,14 +463,14 @@ struct printer {
unsigned next_index;
};
-static uint32_t randomise_(uint32_t n)
+static uint32_t _randomise(uint32_t n)
{
/* 2^32 - 5 */
uint32_t const prime = (~0) - 4;
return n * prime;
}
-static int seen_(struct node_list *n, struct dfa_state *node, uint32_t *i)
+static int _seen(struct node_list *n, struct dfa_state *node, uint32_t *i)
{
while (n) {
if (n->node == node) {
@@ -456,32 +486,36 @@ static int seen_(struct node_list *n, struct dfa_state *node, uint32_t *i)
/*
* Push node if it's not been seen before, returning a unique index.
*/
-static uint32_t push_node_(struct printer *p, struct dfa_state *node)
+static uint32_t _push_node(struct printer *p, struct dfa_state *node)
{
uint32_t i;
- if (seen_(p->pending, node, &i) ||
- seen_(p->processed, node, &i))
+ struct node_list *n;
+
+ if (_seen(p->pending, node, &i) ||
+ _seen(p->processed, node, &i))
return i;
- else {
- struct node_list *n = dm_pool_alloc(p->mem, sizeof(*n));
- assert(n);
- n->node_id = p->next_index++;
- n->node = node;
- n->next = p->pending;
- p->pending = n;
- return n->node_id;
- }
+
+ if (!(n = dm_pool_alloc(p->mem, sizeof(*n))))
+ return_0;
+
+ n->node_id = ++p->next_index; /* start from 1, keep 0 as error code */
+ n->node = node;
+ n->next = p->pending;
+ p->pending = n;
+
+ return n->node_id;
}
/*
* Pop the front node, and fill out it's previously assigned index.
*/
-static struct dfa_state *pop_node_(struct printer *p)
+static struct dfa_state *_pop_node(struct printer *p)
{
struct dfa_state *node = NULL;
+ struct node_list *n;
- if (p->pending) {
- struct node_list *n = p->pending;
+ if (p->pending) {
+ n = p->pending;
p->pending = n->next;
n->next = p->processed;
p->processed = n;
@@ -492,22 +526,22 @@ static struct dfa_state *pop_node_(struct printer *p)
return node;
}
-static uint32_t combine_(uint32_t n1, uint32_t n2)
+static uint32_t _combine(uint32_t n1, uint32_t n2)
{
- return ((n1 << 8) | (n1 >> 24)) ^ randomise_(n2);
+ return ((n1 << 8) | (n1 >> 24)) ^ _randomise(n2);
}
-static uint32_t fingerprint_(struct printer *p)
+static uint32_t _fingerprint(struct printer *p)
{
int c;
uint32_t result = 0;
struct dfa_state *node;
- while ((node = pop_node_(p))) {
- result = combine_(result, node->final < 0 ? 0 : node->final);
+ while ((node = _pop_node(p))) {
+ result = _combine(result, (node->final < 0) ? 0 : node->final);
for (c = 0; c < 256; c++)
- result = combine_(result,
- push_node_(p, node->lookup[c]));
+ result = _combine(result,
+ _push_node(p, node->lookup[c]));
}
return result;
@@ -515,20 +549,27 @@ static uint32_t fingerprint_(struct printer *p)
uint32_t dm_regex_fingerprint(struct dm_regex *regex)
{
- uint32_t result;
struct printer p;
+ uint32_t result = 0;
struct dm_pool *mem = dm_pool_create("regex fingerprint", 1024);
- _force_states(regex);
+ if (!mem)
+ return_0;
+
+ if (!_force_states(regex))
+ goto_out;
- assert(mem);
p.mem = mem;
p.pending = NULL;
p.processed = NULL;
p.next_index = 0;
- push_node_(&p, regex->start);
- result = fingerprint_(&p);
+ if (!_push_node(&p, regex->start))
+ goto_out;
+
+ result = _fingerprint(&p);
+out:
dm_pool_destroy(mem);
+
return result;
}
diff --git a/libdm/regex/ttree.c b/libdm/regex/ttree.c
index ec97c98..00b371e 100644
--- a/libdm/regex/ttree.c
+++ b/libdm/regex/ttree.c
@@ -28,6 +28,7 @@ struct ttree {
struct node *root;
};
+__attribute__((nonnull(1)))
static struct node **_lookup_single(struct node **c, unsigned int k)
{
while (*c) {
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-26 05:26:34 +0000