[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 9/9] dfa: automatically resize position_sets
From: |
Paolo Bonzini |
Subject: |
[PATCH 9/9] dfa: automatically resize position_sets |
Date: |
Tue, 3 Jan 2012 09:38:22 +0100 |
* src/dfa.c (insert, copy, merge): Resize arrays here.
(dfaanalyze): Do not track number of allocated elements here.
(dfastate): Allocate mbps with only one element.
---
src/dfa.c | 26 ++++++++++++--------------
1 files changed, 12 insertions(+), 14 deletions(-)
diff --git a/src/dfa.c b/src/dfa.c
index 491f447..0db93cd 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -1828,6 +1828,7 @@ dfaparse (char const *s, size_t len, struct dfa *d)
static void
copy (position_set const *src, position_set *dst)
{
+ REALLOC_IF_NECESSARY(dst->elems, dst->alloc, src->nelem);
memcpy(dst->elems, src->elems, sizeof(dst->elems[0]) * src->nelem);
dst->nelem = src->nelem;
}
@@ -1849,6 +1850,7 @@ insert (position p, position_set *s)
{
int count = s->nelem;
int lo = 0, hi = count;
+ int i;
while (lo < hi)
{
int mid = ((unsigned) lo + (unsigned) hi) >> 1;
@@ -1859,15 +1861,16 @@ insert (position p, position_set *s)
}
if (lo < count && p.index == s->elems[lo].index)
- s->elems[lo].constraint |= p.constraint;
- else
{
- int i;
- for (i = count; i > lo; i--)
- s->elems[i] = s->elems[i - 1];
- s->elems[lo] = p;
- ++s->nelem;
+ s->elems[lo].constraint |= p.constraint;
+ return;
}
+
+ REALLOC_IF_NECESSARY(s->elems, s->alloc, count + 1);
+ for (i = count; i > lo; i--)
+ s->elems[i] = s->elems[i - 1];
+ s->elems[lo] = p;
+ ++s->nelem;
}
/* Merge two sets of positions into a third. The result is exactly as if
@@ -1877,6 +1880,7 @@ merge (position_set const *s1, position_set const *s2,
position_set *m)
{
int i = 0, j = 0;
+ REALLOC_IF_NECESSARY(m->elems, m->alloc, s1->nelem + s2->nelem);
m->nelem = 0;
while (i < s1->nelem && j < s2->nelem)
if (s1->elems[i].index > s2->elems[j].index)
@@ -2162,8 +2166,6 @@ dfaanalyze (struct dfa *d, int searchflag)
for (j = 0; j < nlastpos[-1]; ++j)
{
merge(&tmp, &d->follows[pos[j].index], &merged);
- REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems,
- d->follows[pos[j].index].alloc, merged.nelem);
copy(&merged, &d->follows[pos[j].index]);
}
@@ -2182,8 +2184,6 @@ dfaanalyze (struct dfa *d, int searchflag)
for (j = 0; j < nlastpos[-2]; ++j)
{
merge(&tmp, &d->follows[pos[j].index], &merged);
- REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems,
- d->follows[pos[j].index].alloc, merged.nelem);
copy(&merged, &d->follows[pos[j].index]);
}
@@ -2291,8 +2291,6 @@ dfaanalyze (struct dfa *d, int searchflag)
#endif
copy(&d->follows[i], &merged);
epsclosure(&merged, d);
- REALLOC_IF_NECESSARY(d->follows[i].elems, d->follows[i].alloc,
- merged.nelem);
copy(&merged, &d->follows[i]);
}
@@ -2410,7 +2408,7 @@ dfastate (int s, struct dfa *d, int trans[])
must put it to d->states[s].mbps, which contains the positions
which can match with a single character not a byte. */
if (d->states[s].mbps.nelem == 0)
- alloc_posset(&d->states[s].mbps, d->states[s].elems.nelem);
+ alloc_posset(&d->states[s].mbps, 1);
insert(pos, &(d->states[s].mbps));
continue;
}
--
1.7.7.1
- Re: [PATCH 4/9] dfa: use a separate data type for grps, (continued)