[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r25465 - gnunet/src/regex
From: |
gnunet |
Subject: |
[GNUnet-SVN] r25465 - gnunet/src/regex |
Date: |
Thu, 13 Dec 2012 20:31:14 +0100 |
Author: grothoff
Date: 2012-12-13 20:31:14 +0100 (Thu, 13 Dec 2012)
New Revision: 25465
Modified:
gnunet/src/regex/regex.c
gnunet/src/regex/regex_internal.h
Log:
reduce reallocing to improve performance
Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c 2012-12-13 19:15:14 UTC (rev 25464)
+++ gnunet/src/regex/regex.c 2012-12-13 19:31:14 UTC (rev 25465)
@@ -60,6 +60,22 @@
/**
+ * Append state to the given StateSet '
+ *
+ * @param set set to be modified
+ * @param state state to be appended
+ */
+static void
+state_set_append (struct GNUNET_REGEX_StateSet *set,
+ struct GNUNET_REGEX_State *state)
+{
+ if (set->off == set->size)
+ GNUNET_array_grow (set->states, set->size, set->size * 2 + 4);
+ set->states[set->off++] = state;
+}
+
+
+/**
* Compare two strings for equality. If either is NULL they are not equal.
*
* @param str1 first string for comparison.
@@ -231,12 +247,12 @@
if (NULL == sset1 || NULL == sset2)
return 1;
- result = sset1->len - sset2->len;
+ result = sset1->off - sset2->off;
if (result < 0)
return -1;
if (result > 0)
return 1;
- for (i = 0; i < sset1->len; i++)
+ for (i = 0; i < sset1->off; i++)
if (0 != (result = state_compare (&sset1->states[i], &sset2->states[i])))
break;
return result;
@@ -251,7 +267,8 @@
static void
state_set_clear (struct GNUNET_REGEX_StateSet *set)
{
- GNUNET_array_grow (set->states, set->len, 0);
+ GNUNET_array_grow (set->states, set->size, 0);
+ set->off = 0;
}
@@ -1250,16 +1267,16 @@
s->nfa_set = *nfa_states;
- if (nfa_states->len < 1)
+ if (nfa_states->off < 1)
return s;
/* Create a name based on 'nfa_states' */
- len = nfa_states->len * 14 + 4;
+ len = nfa_states->off * 14 + 4;
s->name = GNUNET_malloc (len);
strcat (s->name, "{");
pos = s->name + 1;
- for (i = 0; i < nfa_states->len; i++)
+ for (i = 0; i < nfa_states->off; i++)
{
cstate = nfa_states->states[i];
GNUNET_snprintf (pos, pos - s->name + len,
@@ -1749,6 +1766,7 @@
}
}
+
/**
* Compress paths in the given 'dfa'. Linear paths like 0->1->2->3 will be
* compressed to 0->3 by combining transitions.
@@ -1944,7 +1962,7 @@
/* Add start state to closure only for epsilon closure */
if (NULL == label)
- GNUNET_array_append (cls->states, cls->len, s);
+ state_set_append (cls, s);
GNUNET_CONTAINER_MDLL_insert (ST, cls_stack.head, cls_stack.tail, s);
cls_stack.len = 1;
@@ -1965,7 +1983,7 @@
continue;
if (0 == clsstate->contained)
{
- GNUNET_array_append (cls->states, cls->len, clsstate);
+ state_set_append (cls, clsstate);
GNUNET_CONTAINER_MDLL_insert_tail (ST, cls_stack.head, cls_stack.tail,
clsstate);
cls_stack.len++;
@@ -1974,12 +1992,12 @@
}
}
- for (i = 0; i < cls->len; i++)
+ for (i = 0; i < cls->off; i++)
cls->states[i]->contained = 0;
/* sort the states */
- if (cls->len > 1)
- qsort (cls->states, cls->len, sizeof (struct GNUNET_REGEX_State *),
+ if (cls->off > 1)
+ qsort (cls->states, cls->off, sizeof (struct GNUNET_REGEX_State *),
&state_compare);
}
@@ -2009,14 +2027,14 @@
if (NULL == states)
return;
- for (i = 0; i < states->len; i++)
+ for (i = 0; i < states->off; i++)
{
s = states->states[i];
nfa_closure_create (&sset, nfa, s, label);
- for (j = 0; j < sset.len; j++)
+ for (j = 0; j < sset.off; j++)
{
contains = 0;
- for (k = 0; k < ret->len; k++)
+ for (k = 0; k < ret->off; k++)
{
if (sset.states[j]->id == ret->states[k]->id)
{
@@ -2025,14 +2043,14 @@
}
}
if (!contains)
- GNUNET_array_append (ret->states, ret->len, sset.states[j]);
+ state_set_append (ret, sset.states[j]);
}
state_set_clear (&sset);
}
- if (ret->len > 1)
- qsort (ret->states, ret->len, sizeof (struct GNUNET_REGEX_State *),
- state_compare);
+ if (ret->off > 1)
+ qsort (ret->states, ret->off, sizeof (struct GNUNET_REGEX_State *),
+ &state_compare);
}
@@ -2289,7 +2307,8 @@
unsigned int count;
unsigned int altcount;
unsigned int atomcount;
- unsigned int pcount;
+ unsigned int poff;
+ unsigned int psize;
struct
{
int altcount;
@@ -2312,7 +2331,8 @@
error_msg = NULL;
altcount = 0;
atomcount = 0;
- pcount = 0;
+ poff = 0;
+ psize = 0;
for (count = 0; count < len && *regexp; count++, regexp++)
{
@@ -2324,9 +2344,11 @@
--atomcount;
nfa_add_concatenation (&ctx);
}
- GNUNET_array_grow (p, pcount, pcount + 1);
- p[pcount - 1].altcount = altcount;
- p[pcount - 1].atomcount = atomcount;
+ if (poff == psize)
+ GNUNET_array_grow (p, psize, psize * 2 + 4);
+ p[poff].altcount = altcount;
+ p[poff].atomcount = atomcount;
+ poff++;
altcount = 0;
atomcount = 0;
break;
@@ -2341,7 +2363,7 @@
altcount++;
break;
case ')':
- if (0 == pcount)
+ if (0 == poff)
{
error_msg = "Missing opening '('";
goto error;
@@ -2349,18 +2371,18 @@
if (0 == atomcount)
{
/* Ignore this: "()" */
- pcount--;
- altcount = p[pcount].altcount;
- atomcount = p[pcount].atomcount;
+ poff--;
+ altcount = p[poff].altcount;
+ atomcount = p[poff].atomcount;
break;
}
while (--atomcount > 0)
nfa_add_concatenation (&ctx);
for (; altcount > 0; altcount--)
nfa_add_alternation (&ctx);
- pcount--;
- altcount = p[pcount].altcount;
- atomcount = p[pcount].atomcount;
+ poff--;
+ altcount = p[poff].altcount;
+ atomcount = p[poff].atomcount;
atomcount++;
break;
case '*':
@@ -2399,7 +2421,7 @@
break;
}
}
- if (0 != pcount)
+ if (0 != poff)
{
error_msg = "Unbalanced parenthesis";
goto error;
@@ -2409,7 +2431,7 @@
for (; altcount > 0; altcount--)
nfa_add_alternation (&ctx);
- GNUNET_free_non_null (p);
+ GNUNET_array_grow (p, psize, 0);
nfa = ctx.stack_tail;
GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
@@ -2449,6 +2471,7 @@
static unsigned long long loopy;
+static unsigned long long doopy;
/**
* Create DFA states based on given 'nfa' and starting with 'dfa_state'.
@@ -2483,6 +2506,7 @@
/* FIXME: this O(n) loop can be done in O(1) with a hash map */
state_contains = NULL;
+ doopy++;
for (state_iter = dfa->states_head; NULL != state_iter;
state_iter = state_iter->next)
{
@@ -2559,7 +2583,7 @@
fprintf (stderr, "D");
construct_dfa_states (&ctx, nfa, dfa, dfa->start);
- // fprintf (stderr, "D-X: %llu\n", loopy);
+ fprintf (stderr, "D-X: %llu/%llu\n", loopy, doopy);
GNUNET_REGEX_automaton_destroy (nfa);
/* Minimize DFA */
@@ -2567,7 +2591,6 @@
dfa_minimize (&ctx, dfa);
/* Create proofs and hashes for all states */
- // fprintf (stderr, "P");
automaton_create_proofs (dfa);
/* Compress linear DFA paths */
@@ -2693,7 +2716,7 @@
state_set_clear (&new_sset);
}
- for (i = 0; i < sset.len; i++)
+ for (i = 0; i < sset.off; i++)
{
s = sset.states[i];
if ( (NULL != s) && (s->accepting) )
Modified: gnunet/src/regex/regex_internal.h
===================================================================
--- gnunet/src/regex/regex_internal.h 2012-12-13 19:15:14 UTC (rev 25464)
+++ gnunet/src/regex/regex_internal.h 2012-12-13 19:31:14 UTC (rev 25465)
@@ -98,9 +98,14 @@
struct GNUNET_REGEX_State **states;
/**
+ * Number of entries in *use* in the 'states' array.
+ */
+ unsigned int off;
+
+ /**
* Length of the 'states' array.
*/
- unsigned int len;
+ unsigned int size;
};
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r25465 - gnunet/src/regex,
gnunet <=