diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-08-13 16:17:51 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-08-13 16:17:51 +0000 |
commit | 08a7d99253dc2bf1291ad9ab212b426a26fbb4a4 (patch) | |
tree | 7050019167a00ea8e14180e890920f1262a1d9de /src/regex | |
parent | 8e2f63c53202198ba8499393041c83bbd93ea6f7 (diff) | |
download | gnunet-08a7d99253dc2bf1291ad9ab212b426a26fbb4a4.tar.gz gnunet-08a7d99253dc2bf1291ad9ab212b426a26fbb4a4.zip |
using strings as labels
Diffstat (limited to 'src/regex')
-rw-r--r-- | src/regex/regex.c | 155 | ||||
-rw-r--r-- | src/regex/regex_graph.c | 13 | ||||
-rw-r--r-- | src/regex/regex_internal.h | 2 |
3 files changed, 93 insertions, 77 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index c8b8ad3fa..4fb524b1c 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -143,13 +143,13 @@ debug_print_transition (struct GNUNET_REGEX_Transition *t) | |||
143 | { | 143 | { |
144 | char *to_state; | 144 | char *to_state; |
145 | char *from_state; | 145 | char *from_state; |
146 | char label; | 146 | char *label; |
147 | 147 | ||
148 | if (NULL == t) | 148 | if (NULL == t) |
149 | return; | 149 | return; |
150 | 150 | ||
151 | if (0 == t->label) | 151 | if (0 == t->label) |
152 | label = '0'; | 152 | label = "0"; |
153 | else | 153 | else |
154 | label = t->label; | 154 | label = t->label; |
155 | 155 | ||
@@ -163,7 +163,7 @@ debug_print_transition (struct GNUNET_REGEX_Transition *t) | |||
163 | else | 163 | else |
164 | from_state = t->from_state->name; | 164 | from_state = t->from_state->name; |
165 | 165 | ||
166 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: From %s on %c to %s\n", | 166 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: From %s on %s to %s\n", |
167 | t->id, from_state, label, to_state); | 167 | t->id, from_state, label, to_state); |
168 | } | 168 | } |
169 | 169 | ||
@@ -179,6 +179,26 @@ debug_print_transitions (struct GNUNET_REGEX_State *s) | |||
179 | 179 | ||
180 | 180 | ||
181 | /** | 181 | /** |
182 | * Compare two strings for equality. If either is NULL they are not equal. | ||
183 | * | ||
184 | * @param str1 first string for comparison. | ||
185 | * @param str2 second string for comparison. | ||
186 | * | ||
187 | * @return 0 if the strings are the same or both NULL, 1 or -1 if not. | ||
188 | */ | ||
189 | static int | ||
190 | nullstrcmp (const char *str1, const char *str2) | ||
191 | { | ||
192 | if ((NULL == str1) != (NULL == str2)) | ||
193 | return -1; | ||
194 | if ((NULL == str1) && (NULL == str2)) | ||
195 | return 0; | ||
196 | |||
197 | return strcmp (str1, str2); | ||
198 | } | ||
199 | |||
200 | |||
201 | /** | ||
182 | * Adds a transition from one state to another on 'label'. Does not add | 202 | * Adds a transition from one state to another on 'label'. Does not add |
183 | * duplicate states. | 203 | * duplicate states. |
184 | * | 204 | * |
@@ -189,7 +209,7 @@ debug_print_transitions (struct GNUNET_REGEX_State *s) | |||
189 | */ | 209 | */ |
190 | static void | 210 | static void |
191 | state_add_transition (struct GNUNET_REGEX_Context *ctx, | 211 | state_add_transition (struct GNUNET_REGEX_Context *ctx, |
192 | struct GNUNET_REGEX_State *from_state, const char label, | 212 | struct GNUNET_REGEX_State *from_state, const char *label, |
193 | struct GNUNET_REGEX_State *to_state) | 213 | struct GNUNET_REGEX_State *to_state) |
194 | { | 214 | { |
195 | int is_dup; | 215 | int is_dup; |
@@ -206,7 +226,7 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx, | |||
206 | is_dup = GNUNET_NO; | 226 | is_dup = GNUNET_NO; |
207 | for (t = from_state->transitions_head; NULL != t; t = t->next) | 227 | for (t = from_state->transitions_head; NULL != t; t = t->next) |
208 | { | 228 | { |
209 | if (t->to_state == to_state && t->label == label && | 229 | if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) && |
210 | t->from_state == from_state) | 230 | t->from_state == from_state) |
211 | { | 231 | { |
212 | is_dup = GNUNET_YES; | 232 | is_dup = GNUNET_YES; |
@@ -220,13 +240,16 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx, | |||
220 | // sort transitions by label | 240 | // sort transitions by label |
221 | for (oth = from_state->transitions_head; NULL != oth; oth = oth->next) | 241 | for (oth = from_state->transitions_head; NULL != oth; oth = oth->next) |
222 | { | 242 | { |
223 | if (oth->label > label) | 243 | if (0 < nullstrcmp (oth->label, label)) |
224 | break; | 244 | break; |
225 | } | 245 | } |
226 | 246 | ||
227 | t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition)); | 247 | t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition)); |
228 | t->id = ctx->transition_id++; | 248 | t->id = ctx->transition_id++; |
229 | t->label = label; | 249 | if (NULL != label) |
250 | t->label = GNUNET_strdup (label); | ||
251 | else | ||
252 | t->label = NULL; | ||
230 | t->to_state = to_state; | 253 | t->to_state = to_state; |
231 | t->from_state = from_state; | 254 | t->from_state = from_state; |
232 | 255 | ||
@@ -256,6 +279,7 @@ state_remove_transition (struct GNUNET_REGEX_State *state, | |||
256 | state->transition_count--; | 279 | state->transition_count--; |
257 | GNUNET_CONTAINER_DLL_remove (state->transitions_head, state->transitions_tail, | 280 | GNUNET_CONTAINER_DLL_remove (state->transitions_head, state->transitions_tail, |
258 | transition); | 281 | transition); |
282 | GNUNET_free_non_null (transition->label); | ||
259 | GNUNET_free (transition); | 283 | GNUNET_free (transition); |
260 | } | 284 | } |
261 | 285 | ||
@@ -307,7 +331,7 @@ state_get_edges (struct GNUNET_REGEX_State *s, struct GNUNET_REGEX_Edge *edges) | |||
307 | { | 331 | { |
308 | if (NULL != t->to_state) | 332 | if (NULL != t->to_state) |
309 | { | 333 | { |
310 | edges[count].label = &t->label; | 334 | edges[count].label = t->label; |
311 | edges[count].destination = t->to_state->hash; | 335 | edges[count].destination = t->to_state->hash; |
312 | count++; | 336 | count++; |
313 | } | 337 | } |
@@ -408,6 +432,7 @@ automaton_destroy_state (struct GNUNET_REGEX_State *s) | |||
408 | { | 432 | { |
409 | next_t = t->next; | 433 | next_t = t->next; |
410 | GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t); | 434 | GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t); |
435 | GNUNET_free_non_null (t->label); | ||
411 | GNUNET_free (t); | 436 | GNUNET_free (t); |
412 | } | 437 | } |
413 | 438 | ||
@@ -500,7 +525,7 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
500 | is_dup = GNUNET_NO; | 525 | is_dup = GNUNET_NO; |
501 | for (t = t_check->from_state->transitions_head; NULL != t; t = t->next) | 526 | for (t = t_check->from_state->transitions_head; NULL != t; t = t->next) |
502 | { | 527 | { |
503 | if (t->to_state == s1 && t_check->label == t->label) | 528 | if (t->to_state == s1 && 0 == strcmp (t_check->label, t->label)) |
504 | is_dup = GNUNET_YES; | 529 | is_dup = GNUNET_YES; |
505 | } | 530 | } |
506 | if (GNUNET_NO == is_dup) | 531 | if (GNUNET_NO == is_dup) |
@@ -735,24 +760,6 @@ strkcmp (const char *str1, const char *str2, size_t k) | |||
735 | 760 | ||
736 | 761 | ||
737 | /** | 762 | /** |
738 | * Compare two strings for equality. If either is NULL (or if both are | ||
739 | * NULL), they are not equal. | ||
740 | * | ||
741 | * @param str1 first string for comparison. | ||
742 | * @param str2 second string for comparison. | ||
743 | * | ||
744 | * @return 0 if the strings are the same, 1 or -1 if not | ||
745 | */ | ||
746 | static int | ||
747 | nullstrcmp (const char *str1, const char *str2) | ||
748 | { | ||
749 | if ((NULL == str1) || (NULL == str2)) | ||
750 | return -1; | ||
751 | return strcmp (str1, str2); | ||
752 | } | ||
753 | |||
754 | |||
755 | /** | ||
756 | * Helper function used as 'action' in 'GNUNET_REGEX_automaton_traverse' function to create | 763 | * Helper function used as 'action' in 'GNUNET_REGEX_automaton_traverse' function to create |
757 | * the depth-first numbering of the states. | 764 | * the depth-first numbering of the states. |
758 | * | 765 | * |
@@ -1180,11 +1187,11 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1180 | { | 1187 | { |
1181 | j = t->to_state->proof_id; | 1188 | j = t->to_state->proof_id; |
1182 | if (NULL == R_last[i][j]) | 1189 | if (NULL == R_last[i][j]) |
1183 | GNUNET_asprintf (&R_last[i][j], "%c", t->label); | 1190 | GNUNET_asprintf (&R_last[i][j], "%s", t->label); |
1184 | else | 1191 | else |
1185 | { | 1192 | { |
1186 | temp = R_last[i][j]; | 1193 | temp = R_last[i][j]; |
1187 | GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label); | 1194 | GNUNET_asprintf (&R_last[i][j], "%s|%s", R_last[i][j], t->label); |
1188 | GNUNET_free (temp); | 1195 | GNUNET_free (temp); |
1189 | } | 1196 | } |
1190 | } | 1197 | } |
@@ -1342,7 +1349,7 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, | |||
1342 | // Add a transition for each distinct label to NULL state | 1349 | // Add a transition for each distinct label to NULL state |
1343 | for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next) | 1350 | for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next) |
1344 | { | 1351 | { |
1345 | if (0 != ctran->label) | 1352 | if (NULL != ctran->label) |
1346 | state_add_transition (ctx, s, ctran->label, NULL); | 1353 | state_add_transition (ctx, s, ctran->label, NULL); |
1347 | } | 1354 | } |
1348 | 1355 | ||
@@ -1367,7 +1374,7 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, | |||
1367 | * @return new state or NULL, if transition on label not possible | 1374 | * @return new state or NULL, if transition on label not possible |
1368 | */ | 1375 | */ |
1369 | static struct GNUNET_REGEX_State * | 1376 | static struct GNUNET_REGEX_State * |
1370 | dfa_move (struct GNUNET_REGEX_State *s, const char label) | 1377 | dfa_move (struct GNUNET_REGEX_State *s, const char *label) |
1371 | { | 1378 | { |
1372 | struct GNUNET_REGEX_Transition *t; | 1379 | struct GNUNET_REGEX_Transition *t; |
1373 | struct GNUNET_REGEX_State *new_s; | 1380 | struct GNUNET_REGEX_State *new_s; |
@@ -1379,7 +1386,9 @@ dfa_move (struct GNUNET_REGEX_State *s, const char label) | |||
1379 | 1386 | ||
1380 | for (t = s->transitions_head; NULL != t; t = t->next) | 1387 | for (t = s->transitions_head; NULL != t; t = t->next) |
1381 | { | 1388 | { |
1382 | if (label == t->label) | 1389 | // TODO: Use strstr to match substring and return number of char's that have |
1390 | // been consumed' | ||
1391 | if (0 == strcmp (label, t->label)) | ||
1383 | { | 1392 | { |
1384 | new_s = t->to_state; | 1393 | new_s = t->to_state; |
1385 | break; | 1394 | break; |
@@ -1517,13 +1526,13 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1517 | { | 1526 | { |
1518 | for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next) | 1527 | for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next) |
1519 | { | 1528 | { |
1520 | if (t1->label == t2->label) | 1529 | if (0 == strcmp (t1->label, t2->label)) |
1521 | { | 1530 | { |
1522 | num_equal_edges++; | 1531 | num_equal_edges++; |
1523 | if (0 != table[t1->to_state->marked][t2->to_state->marked] || | 1532 | if (0 != table[t1->to_state->marked][t2->to_state->marked] || |
1524 | 0 != table[t2->to_state->marked][t1->to_state->marked]) | 1533 | 0 != table[t2->to_state->marked][t1->to_state->marked]) |
1525 | { | 1534 | { |
1526 | table[s1->marked][s2->marked] = t1->label != 0 ? t1->label : 1; | 1535 | table[s1->marked][s2->marked] = 1; |
1527 | change = 1; | 1536 | change = 1; |
1528 | } | 1537 | } |
1529 | } | 1538 | } |
@@ -1686,13 +1695,13 @@ nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting) | |||
1686 | * @param nfa the NFA containing 's' | 1695 | * @param nfa the NFA containing 's' |
1687 | * @param s starting point state | 1696 | * @param s starting point state |
1688 | * @param label transitioning label on which to base the closure on, | 1697 | * @param label transitioning label on which to base the closure on, |
1689 | * pass 0 for epsilon transition | 1698 | * pass NULL for epsilon transition |
1690 | * | 1699 | * |
1691 | * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0) | 1700 | * @return sorted nfa closure on 'label' (epsilon closure if 'label' is NULL) |
1692 | */ | 1701 | */ |
1693 | static struct GNUNET_REGEX_StateSet * | 1702 | static struct GNUNET_REGEX_StateSet * |
1694 | nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | 1703 | nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, |
1695 | struct GNUNET_REGEX_State *s, const char label) | 1704 | struct GNUNET_REGEX_State *s, const char *label) |
1696 | { | 1705 | { |
1697 | struct GNUNET_REGEX_StateSet *cls; | 1706 | struct GNUNET_REGEX_StateSet *cls; |
1698 | struct GNUNET_REGEX_StateSet *cls_check; | 1707 | struct GNUNET_REGEX_StateSet *cls_check; |
@@ -1710,7 +1719,7 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1710 | clsstate->contained = 0; | 1719 | clsstate->contained = 0; |
1711 | 1720 | ||
1712 | // Add start state to closure only for epsilon closure | 1721 | // Add start state to closure only for epsilon closure |
1713 | if (0 == label) | 1722 | if (NULL == label) |
1714 | GNUNET_array_append (cls->states, cls->len, s); | 1723 | GNUNET_array_append (cls->states, cls->len, s); |
1715 | 1724 | ||
1716 | GNUNET_array_append (cls_check->states, cls_check->len, s); | 1725 | GNUNET_array_append (cls_check->states, cls_check->len, s); |
@@ -1722,7 +1731,7 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1722 | for (ctran = currentstate->transitions_head; NULL != ctran; | 1731 | for (ctran = currentstate->transitions_head; NULL != ctran; |
1723 | ctran = ctran->next) | 1732 | ctran = ctran->next) |
1724 | { | 1733 | { |
1725 | if (NULL != ctran->to_state && label == ctran->label) | 1734 | if (NULL != ctran->to_state && 0 == nullstrcmp (label, ctran->label)) |
1726 | { | 1735 | { |
1727 | clsstate = ctran->to_state; | 1736 | clsstate = ctran->to_state; |
1728 | 1737 | ||
@@ -1753,13 +1762,13 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1753 | * @param nfa the NFA containing 's' | 1762 | * @param nfa the NFA containing 's' |
1754 | * @param states list of states on which to base the closure on | 1763 | * @param states list of states on which to base the closure on |
1755 | * @param label transitioning label for which to base the closure on, | 1764 | * @param label transitioning label for which to base the closure on, |
1756 | * pass 0 for epsilon transition | 1765 | * pass NULL for epsilon transition |
1757 | * | 1766 | * |
1758 | * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0) | 1767 | * @return sorted nfa closure on 'label' (epsilon closure if 'label' is NULL) |
1759 | */ | 1768 | */ |
1760 | static struct GNUNET_REGEX_StateSet * | 1769 | static struct GNUNET_REGEX_StateSet * |
1761 | nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa, | 1770 | nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa, |
1762 | struct GNUNET_REGEX_StateSet *states, const char label) | 1771 | struct GNUNET_REGEX_StateSet *states, const char *label) |
1763 | { | 1772 | { |
1764 | struct GNUNET_REGEX_State *s; | 1773 | struct GNUNET_REGEX_State *s; |
1765 | struct GNUNET_REGEX_StateSet *sset; | 1774 | struct GNUNET_REGEX_StateSet *sset; |
@@ -1823,7 +1832,7 @@ nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx) | |||
1823 | GNUNET_assert (NULL != a); | 1832 | GNUNET_assert (NULL != a); |
1824 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); | 1833 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); |
1825 | 1834 | ||
1826 | state_add_transition (ctx, a->end, 0, b->start); | 1835 | state_add_transition (ctx, a->end, NULL, b->start); |
1827 | a->end->accepting = 0; | 1836 | a->end->accepting = 0; |
1828 | b->end->accepting = 1; | 1837 | b->end->accepting = 1; |
1829 | 1838 | ||
@@ -1866,10 +1875,10 @@ nfa_add_star_op (struct GNUNET_REGEX_Context *ctx) | |||
1866 | start = nfa_state_create (ctx, 0); | 1875 | start = nfa_state_create (ctx, 0); |
1867 | end = nfa_state_create (ctx, 1); | 1876 | end = nfa_state_create (ctx, 1); |
1868 | 1877 | ||
1869 | state_add_transition (ctx, start, 0, a->start); | 1878 | state_add_transition (ctx, start, NULL, a->start); |
1870 | state_add_transition (ctx, start, 0, end); | 1879 | state_add_transition (ctx, start, NULL, end); |
1871 | state_add_transition (ctx, a->end, 0, a->start); | 1880 | state_add_transition (ctx, a->end, NULL, a->start); |
1872 | state_add_transition (ctx, a->end, 0, end); | 1881 | state_add_transition (ctx, a->end, NULL, end); |
1873 | 1882 | ||
1874 | a->end->accepting = 0; | 1883 | a->end->accepting = 0; |
1875 | end->accepting = 1; | 1884 | end->accepting = 1; |
@@ -1895,7 +1904,7 @@ nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx) | |||
1895 | a = ctx->stack_tail; | 1904 | a = ctx->stack_tail; |
1896 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); | 1905 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); |
1897 | 1906 | ||
1898 | state_add_transition (ctx, a->end, 0, a->start); | 1907 | state_add_transition (ctx, a->end, NULL, a->start); |
1899 | 1908 | ||
1900 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a); | 1909 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a); |
1901 | } | 1910 | } |
@@ -1928,9 +1937,9 @@ nfa_add_question_op (struct GNUNET_REGEX_Context *ctx) | |||
1928 | start = nfa_state_create (ctx, 0); | 1937 | start = nfa_state_create (ctx, 0); |
1929 | end = nfa_state_create (ctx, 1); | 1938 | end = nfa_state_create (ctx, 1); |
1930 | 1939 | ||
1931 | state_add_transition (ctx, start, 0, a->start); | 1940 | state_add_transition (ctx, start, NULL, a->start); |
1932 | state_add_transition (ctx, start, 0, end); | 1941 | state_add_transition (ctx, start, NULL, end); |
1933 | state_add_transition (ctx, a->end, 0, end); | 1942 | state_add_transition (ctx, a->end, NULL, end); |
1934 | 1943 | ||
1935 | a->end->accepting = 0; | 1944 | a->end->accepting = 0; |
1936 | 1945 | ||
@@ -1966,11 +1975,11 @@ nfa_add_alternation (struct GNUNET_REGEX_Context *ctx) | |||
1966 | 1975 | ||
1967 | start = nfa_state_create (ctx, 0); | 1976 | start = nfa_state_create (ctx, 0); |
1968 | end = nfa_state_create (ctx, 1); | 1977 | end = nfa_state_create (ctx, 1); |
1969 | state_add_transition (ctx, start, 0, a->start); | 1978 | state_add_transition (ctx, start, NULL, a->start); |
1970 | state_add_transition (ctx, start, 0, b->start); | 1979 | state_add_transition (ctx, start, NULL, b->start); |
1971 | 1980 | ||
1972 | state_add_transition (ctx, a->end, 0, end); | 1981 | state_add_transition (ctx, a->end, NULL, end); |
1973 | state_add_transition (ctx, b->end, 0, end); | 1982 | state_add_transition (ctx, b->end, NULL, end); |
1974 | 1983 | ||
1975 | a->end->accepting = 0; | 1984 | a->end->accepting = 0; |
1976 | b->end->accepting = 0; | 1985 | b->end->accepting = 0; |
@@ -1990,10 +1999,10 @@ nfa_add_alternation (struct GNUNET_REGEX_Context *ctx) | |||
1990 | * Adds a new nfa fragment to the stack | 1999 | * Adds a new nfa fragment to the stack |
1991 | * | 2000 | * |
1992 | * @param ctx context | 2001 | * @param ctx context |
1993 | * @param lit label for nfa transition | 2002 | * @param label label for nfa transition |
1994 | */ | 2003 | */ |
1995 | static void | 2004 | static void |
1996 | nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char lit) | 2005 | nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char *label) |
1997 | { | 2006 | { |
1998 | struct GNUNET_REGEX_Automaton *n; | 2007 | struct GNUNET_REGEX_Automaton *n; |
1999 | struct GNUNET_REGEX_State *start; | 2008 | struct GNUNET_REGEX_State *start; |
@@ -2003,7 +2012,7 @@ nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char lit) | |||
2003 | 2012 | ||
2004 | start = nfa_state_create (ctx, 0); | 2013 | start = nfa_state_create (ctx, 0); |
2005 | end = nfa_state_create (ctx, 1); | 2014 | end = nfa_state_create (ctx, 1); |
2006 | state_add_transition (ctx, start, lit, end); | 2015 | state_add_transition (ctx, start, label, end); |
2007 | n = nfa_fragment_create (start, end); | 2016 | n = nfa_fragment_create (start, end); |
2008 | GNUNET_assert (NULL != n); | 2017 | GNUNET_assert (NULL != n); |
2009 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n); | 2018 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n); |
@@ -2044,6 +2053,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
2044 | struct GNUNET_REGEX_Context ctx; | 2053 | struct GNUNET_REGEX_Context ctx; |
2045 | struct GNUNET_REGEX_Automaton *nfa; | 2054 | struct GNUNET_REGEX_Automaton *nfa; |
2046 | const char *regexp; | 2055 | const char *regexp; |
2056 | char curlabel[2]; | ||
2047 | char *error_msg; | 2057 | char *error_msg; |
2048 | unsigned int count; | 2058 | unsigned int count; |
2049 | unsigned int altcount; | 2059 | unsigned int altcount; |
@@ -2058,6 +2068,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
2058 | GNUNET_REGEX_context_init (&ctx); | 2068 | GNUNET_REGEX_context_init (&ctx); |
2059 | 2069 | ||
2060 | regexp = regex; | 2070 | regexp = regex; |
2071 | curlabel[1] = '\0'; | ||
2061 | p = NULL; | 2072 | p = NULL; |
2062 | error_msg = NULL; | 2073 | error_msg = NULL; |
2063 | altcount = 0; | 2074 | altcount = 0; |
@@ -2147,7 +2158,8 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
2147 | --atomcount; | 2158 | --atomcount; |
2148 | nfa_add_concatenation (&ctx); | 2159 | nfa_add_concatenation (&ctx); |
2149 | } | 2160 | } |
2150 | nfa_add_label (&ctx, *regexp); | 2161 | curlabel[0] = *regexp; |
2162 | nfa_add_label (&ctx, curlabel); | ||
2151 | atomcount++; | 2163 | atomcount++; |
2152 | break; | 2164 | break; |
2153 | } | 2165 | } |
@@ -2221,7 +2233,7 @@ construct_dfa_states (struct GNUNET_REGEX_Context *ctx, | |||
2221 | 2233 | ||
2222 | for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next) | 2234 | for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next) |
2223 | { | 2235 | { |
2224 | if (0 == ctran->label || NULL != ctran->to_state) | 2236 | if (NULL == ctran->label || NULL != ctran->to_state) |
2225 | continue; | 2237 | continue; |
2226 | 2238 | ||
2227 | tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->label); | 2239 | tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->label); |
@@ -2343,6 +2355,7 @@ static int | |||
2343 | evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | 2355 | evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) |
2344 | { | 2356 | { |
2345 | const char *strp; | 2357 | const char *strp; |
2358 | char str[2]; | ||
2346 | struct GNUNET_REGEX_State *s; | 2359 | struct GNUNET_REGEX_State *s; |
2347 | 2360 | ||
2348 | if (DFA != a->type) | 2361 | if (DFA != a->type) |
@@ -2358,9 +2371,11 @@ evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
2358 | if ((NULL == string || 0 == strlen (string)) && s->accepting) | 2371 | if ((NULL == string || 0 == strlen (string)) && s->accepting) |
2359 | return 0; | 2372 | return 0; |
2360 | 2373 | ||
2374 | str[1] = '\0'; | ||
2361 | for (strp = string; NULL != strp && *strp; strp++) | 2375 | for (strp = string; NULL != strp && *strp; strp++) |
2362 | { | 2376 | { |
2363 | s = dfa_move (s, *strp); | 2377 | str[0] = *strp; |
2378 | s = dfa_move (s, str); | ||
2364 | if (NULL == s) | 2379 | if (NULL == s) |
2365 | break; | 2380 | break; |
2366 | } | 2381 | } |
@@ -2384,6 +2399,7 @@ static int | |||
2384 | evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) | 2399 | evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) |
2385 | { | 2400 | { |
2386 | const char *strp; | 2401 | const char *strp; |
2402 | char str[2]; | ||
2387 | struct GNUNET_REGEX_State *s; | 2403 | struct GNUNET_REGEX_State *s; |
2388 | struct GNUNET_REGEX_StateSet *sset; | 2404 | struct GNUNET_REGEX_StateSet *sset; |
2389 | struct GNUNET_REGEX_StateSet *new_sset; | 2405 | struct GNUNET_REGEX_StateSet *new_sset; |
@@ -2404,9 +2420,11 @@ evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
2404 | result = 1; | 2420 | result = 1; |
2405 | sset = nfa_closure_create (a, a->start, 0); | 2421 | sset = nfa_closure_create (a, a->start, 0); |
2406 | 2422 | ||
2423 | str[1] = '\0'; | ||
2407 | for (strp = string; NULL != strp && *strp; strp++) | 2424 | for (strp = string; NULL != strp && *strp; strp++) |
2408 | { | 2425 | { |
2409 | new_sset = nfa_closure_set_create (a, sset, *strp); | 2426 | str[0] = *strp; |
2427 | new_sset = nfa_closure_set_create (a, sset, str); | ||
2410 | state_set_clear (sset); | 2428 | state_set_clear (sset); |
2411 | sset = nfa_closure_set_create (a, new_sset, 0); | 2429 | sset = nfa_closure_set_create (a, new_sset, 0); |
2412 | state_set_clear (new_sset); | 2430 | state_set_clear (new_sset); |
@@ -2549,7 +2567,6 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | |||
2549 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) | 2567 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) |
2550 | { | 2568 | { |
2551 | unsigned int i; | 2569 | unsigned int i; |
2552 | char label[state->transition_count][2]; | ||
2553 | char *temp; | 2570 | char *temp; |
2554 | struct GNUNET_REGEX_Transition *t; | 2571 | struct GNUNET_REGEX_Transition *t; |
2555 | unsigned int num_edges = state->transition_count; | 2572 | unsigned int num_edges = state->transition_count; |
@@ -2560,9 +2577,7 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | |||
2560 | { | 2577 | { |
2561 | for (i = 0, t = state->transitions_head; NULL != t; t = t->next, i++) | 2578 | for (i = 0, t = state->transitions_head; NULL != t; t = t->next, i++) |
2562 | { | 2579 | { |
2563 | label[i][0] = t->label; | 2580 | edges[i].label = t->label; |
2564 | label[i][1] = '\0'; | ||
2565 | edges[i].label = label[i]; | ||
2566 | edges[i].destination = t->to_state->hash; | 2581 | edges[i].destination = t->to_state->hash; |
2567 | } | 2582 | } |
2568 | 2583 | ||
@@ -2577,9 +2592,9 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | |||
2577 | for (t = state->transitions_head; NULL != t; t = t->next) | 2592 | for (t = state->transitions_head; NULL != t; t = t->next) |
2578 | { | 2593 | { |
2579 | if (NULL != consumed_string) | 2594 | if (NULL != consumed_string) |
2580 | GNUNET_asprintf (&temp, "%s%c", consumed_string, t->label); | 2595 | GNUNET_asprintf (&temp, "%s%s", consumed_string, t->label); |
2581 | else | 2596 | else |
2582 | GNUNET_asprintf (&temp, "%c", t->label); | 2597 | GNUNET_asprintf (&temp, "%s", t->label); |
2583 | 2598 | ||
2584 | iterate_initial_edge (min_len, max_len, cur_len, temp, t->to_state, | 2599 | iterate_initial_edge (min_len, max_len, cur_len, temp, t->to_state, |
2585 | iterator, iterator_cls); | 2600 | iterator, iterator_cls); |
@@ -2626,12 +2641,12 @@ iterate_initial_edges (struct GNUNET_REGEX_Automaton *a, | |||
2626 | if (NULL != consumed_string) | 2641 | if (NULL != consumed_string) |
2627 | { | 2642 | { |
2628 | temp = consumed_string; | 2643 | temp = consumed_string; |
2629 | GNUNET_asprintf (&consumed_string, "%s%c", consumed_string, | 2644 | GNUNET_asprintf (&consumed_string, "%s%s", consumed_string, |
2630 | s->transitions_head->label); | 2645 | s->transitions_head->label); |
2631 | GNUNET_free (temp); | 2646 | GNUNET_free (temp); |
2632 | } | 2647 | } |
2633 | else | 2648 | else |
2634 | GNUNET_asprintf (&consumed_string, "%c", s->transitions_head->label); | 2649 | GNUNET_asprintf (&consumed_string, "%s", s->transitions_head->label); |
2635 | 2650 | ||
2636 | s = s->transitions_head->to_state; | 2651 | s = s->transitions_head->to_state; |
2637 | cur_len++; | 2652 | cur_len++; |
diff --git a/src/regex/regex_graph.c b/src/regex/regex_graph.c index 9dfdb15a4..06546e8f7 100644 --- a/src/regex/regex_graph.c +++ b/src/regex/regex_graph.c | |||
@@ -188,7 +188,8 @@ GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count, | |||
188 | } | 188 | } |
189 | else if (GNUNET_YES == ctx->coloring) | 189 | else if (GNUNET_YES == ctx->coloring) |
190 | { | 190 | { |
191 | GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name, | 191 | GNUNET_asprintf (&s_acc, |
192 | "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name, | ||
192 | s->scc_id); | 193 | s->scc_id); |
193 | } | 194 | } |
194 | else | 195 | else |
@@ -224,7 +225,7 @@ GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count, | |||
224 | else | 225 | else |
225 | GNUNET_asprintf (&to_name, "%i", ctran->to_state->proof_id); | 226 | GNUNET_asprintf (&to_name, "%i", ctran->to_state->proof_id); |
226 | 227 | ||
227 | if (ctran->label == 0) | 228 | if (NULL == ctran->label) |
228 | { | 229 | { |
229 | if (GNUNET_YES == ctx->coloring) | 230 | if (GNUNET_YES == ctx->coloring) |
230 | { | 231 | { |
@@ -234,8 +235,8 @@ GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count, | |||
234 | } | 235 | } |
235 | else | 236 | else |
236 | { | 237 | { |
237 | GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", | 238 | GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name, |
238 | name, to_name, s->scc_id); | 239 | to_name, s->scc_id); |
239 | } | 240 | } |
240 | } | 241 | } |
241 | else | 242 | else |
@@ -243,12 +244,12 @@ GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count, | |||
243 | if (GNUNET_YES == ctx->coloring) | 244 | if (GNUNET_YES == ctx->coloring) |
244 | { | 245 | { |
245 | GNUNET_asprintf (&s_tran, | 246 | GNUNET_asprintf (&s_tran, |
246 | "\"%s\" -> \"%s\" [label = \"%c\", color=\"0.%i 0.8 0.95\"];\n", | 247 | "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n", |
247 | name, to_name, ctran->label, s->scc_id); | 248 | name, to_name, ctran->label, s->scc_id); |
248 | } | 249 | } |
249 | else | 250 | else |
250 | { | 251 | { |
251 | GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n", name, | 252 | GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name, |
252 | to_name, ctran->label, s->scc_id); | 253 | to_name, ctran->label, s->scc_id); |
253 | } | 254 | } |
254 | } | 255 | } |
diff --git a/src/regex/regex_internal.h b/src/regex/regex_internal.h index d1e829633..007870832 100644 --- a/src/regex/regex_internal.h +++ b/src/regex/regex_internal.h | |||
@@ -66,7 +66,7 @@ struct GNUNET_REGEX_Transition | |||
66 | /** | 66 | /** |
67 | * Label for this transition. This is basically the edge label for the graph. | 67 | * Label for this transition. This is basically the edge label for the graph. |
68 | */ | 68 | */ |
69 | char label; | 69 | char *label; |
70 | 70 | ||
71 | /** | 71 | /** |
72 | * State to which this transition leads. | 72 | * State to which this transition leads. |