[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r21782 - gnunet/src/regex
From: |
gnunet |
Subject: |
[GNUnet-SVN] r21782 - gnunet/src/regex |
Date: |
Wed, 6 Jun 2012 15:05:24 +0200 |
Author: szengel
Date: 2012-06-06 15:05:24 +0200 (Wed, 06 Jun 2012)
New Revision: 21782
Modified:
gnunet/src/regex/regex.c
Log:
even better proofs
Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c 2012-06-06 13:01:03 UTC (rev 21781)
+++ gnunet/src/regex/regex.c 2012-06-06 13:05:24 UTC (rev 21782)
@@ -817,7 +817,10 @@
char *R_last[a->state_count][a->state_count];
char *R_cur[a->state_count][a->state_count];
char *temp;
- int length;
+ char *R_cur_l;
+ char *R_cur_r;
+ int length_l;
+ int length_r;
k = 0;
n = a->state_count;
@@ -850,18 +853,24 @@
}
}
- if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j]))
- {
- temp = R_last[i][j];
- GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]);
- GNUNET_free (temp);
- }
if (i == j)
{
if (NULL == R_last[i][j])
GNUNET_asprintf (&R_last[i][j], "");
+ else if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j]))
+ {
+ temp = R_last[i][j];
+ GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]);
+ GNUNET_free (temp);
+ }
}
+ else if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j]))
+ {
+ temp = R_last[i][j];
+ GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]);
+ GNUNET_free (temp);
+ }
}
}
@@ -882,41 +891,60 @@
else
{
// R(k)ij = R(k-1)ij + R(k-1)ik (R(k-1)kk)* R(k-1)kj
- length =
- snprintf (NULL, 0, "(%s|%s(%s)*%s)", R_last[i][j], R_last[i][k],
- R_last[k][k], R_last[k][j]) + 1;
- char *left = GNUNET_malloc (length);
- char *right = GNUNET_malloc (length);
+ length_l = (NULL == R_last[i][j]) ? 1 : strlen (R_last[i][j]) + 1;
+ length_r =
+ snprintf (NULL, 0, "%s(%s)*%s", R_last[i][k], R_last[k][k],
+ R_last[k][j]) + 1;
+ R_cur_l = GNUNET_malloc (length_l);
+ R_cur_r = GNUNET_malloc (length_r);
if (NULL != R_last[i][j])
- strcat (left, R_last[i][j]);
+ strcat (R_cur_l, R_last[i][j]);
if (NULL != R_last[i][k])
- strcat (right, R_last[i][k]);
+ strcat (R_cur_r, R_last[i][k]);
if (NULL != R_last[k][k] && 0 != strcmp (R_last[k][k], ""))
{
- strcat (right, "(");
- strcat (right, R_last[k][k]);
- strcat (right, ")*");
+ strcat (R_cur_r, "(");
+ strcat (R_cur_r, R_last[k][k]);
+ strcat (R_cur_r, ")*");
}
if (NULL != R_last[k][j])
- strcat (right, R_last[k][j]);
+ strcat (R_cur_r, R_last[k][j]);
- if (0 == strcmp (left, right) || 0 == strcmp (left, "") ||
- 0 == strcmp (right, ""))
+ // | is idempotent: a | a = a for all a in A
+ if (0 == strcmp (R_cur_l, R_cur_r) || 0 == strcmp (R_cur_l, "") ||
+ 0 == strcmp (R_cur_r, ""))
{
- if (0 == strcmp (left, ""))
- GNUNET_asprintf (&R_cur[i][j], "%s", right);
+ if (0 == strcmp (R_cur_l, ""))
+ GNUNET_asprintf (&R_cur[i][j], "%s", R_cur_r);
else
- GNUNET_asprintf (&R_cur[i][j], "%s", left);
+ GNUNET_asprintf (&R_cur[i][j], "%s", R_cur_l);
}
+ // a | a a* a = a+
+ else if (R_last[i][j] == R_last[i][k] && R_last[i][k] == R_last[k][k]
+ && R_last[k][k] == R_last[k][j])
+ {
+ GNUNET_asprintf (&R_cur[i][j], "%s+", R_last[i][j]);
+ }
+ // a | a b* b => a | a b | a b b | ... => a b*
+ else if (R_last[i][j] == R_last[i][k] && R_last[k][k] ==
R_last[k][j])
+ {
+ GNUNET_asprintf (&R_cur[i][j], "%s%s*", R_last[i][k],
R_last[k][k]);
+ }
+ // a | b b* a => a | b a | b b a | ... => b* a
+ else if (R_last[i][j] == R_last[k][j] && R_last[i][k] ==
R_last[k][k])
+ {
+ GNUNET_asprintf (&R_cur[i][j], "%s*%s", R_last[k][k],
R_last[k][j]);
+ }
else
- GNUNET_asprintf (&R_cur[i][j], "(%s|%s)", left, right);
+ GNUNET_asprintf (&R_cur[i][j], "(%s|%s)", R_cur_l, R_cur_r);
- GNUNET_free_non_null (left);
- GNUNET_free_non_null (right);
+ GNUNET_free_non_null (R_cur_l);
+ GNUNET_free_non_null (R_cur_r);
+
}
}
}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r21782 - gnunet/src/regex,
gnunet <=