diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-11-13 17:02:07 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-11-13 17:02:07 +0000 |
commit | 6bb3af348c931d7a01bf2b063ad9e2e294cc7af9 (patch) | |
tree | 01156e2a7d495a33fd3eea30413b0b1c65096cfc /src/regex | |
parent | a1ab1459c85a5a647f36aba790c36d89c9faa268 (diff) | |
download | gnunet-6bb3af348c931d7a01bf2b063ad9e2e294cc7af9.tar.gz gnunet-6bb3af348c931d7a01bf2b063ad9e2e294cc7af9.zip |
optimizations
Diffstat (limited to 'src/regex')
-rw-r--r-- | src/regex/regex.c | 174 | ||||
-rw-r--r-- | src/regex/regex_internal.h | 14 |
2 files changed, 124 insertions, 64 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 3281ff469..96d8747b7 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -28,6 +28,11 @@ | |||
28 | #include "gnunet_regex_lib.h" | 28 | #include "gnunet_regex_lib.h" |
29 | #include "regex_internal.h" | 29 | #include "regex_internal.h" |
30 | 30 | ||
31 | /** | ||
32 | * Set this to GNUNET_YES to enable state naming. Used to debug NFA->DFA | ||
33 | * creation. | ||
34 | */ | ||
35 | #define REGEX_DEBUG_DFA GNUNET_NO | ||
31 | 36 | ||
32 | /** | 37 | /** |
33 | * Set of states. | 38 | * Set of states. |
@@ -45,6 +50,27 @@ struct GNUNET_REGEX_StateSet | |||
45 | unsigned int len; | 50 | unsigned int len; |
46 | }; | 51 | }; |
47 | 52 | ||
53 | /** | ||
54 | * Set of states using MDLL API. | ||
55 | */ | ||
56 | struct GNUNET_REGEX_StateSet_MDLL | ||
57 | { | ||
58 | /** | ||
59 | * MDLL of states. | ||
60 | */ | ||
61 | struct GNUNET_REGEX_State *head; | ||
62 | |||
63 | /** | ||
64 | * MDLL of states. | ||
65 | */ | ||
66 | struct GNUNET_REGEX_State *tail; | ||
67 | |||
68 | /** | ||
69 | * Length of the MDLL. | ||
70 | */ | ||
71 | unsigned int len; | ||
72 | }; | ||
73 | |||
48 | 74 | ||
49 | /** | 75 | /** |
50 | * Compare two strings for equality. If either is NULL they are not equal. | 76 | * Compare two strings for equality. If either is NULL they are not equal. |
@@ -361,7 +387,6 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
361 | struct GNUNET_REGEX_Transition *t_check; | 387 | struct GNUNET_REGEX_Transition *t_check; |
362 | struct GNUNET_REGEX_Transition *t; | 388 | struct GNUNET_REGEX_Transition *t; |
363 | struct GNUNET_REGEX_Transition *t_next; | 389 | struct GNUNET_REGEX_Transition *t_next; |
364 | char *new_name; | ||
365 | int is_dup; | 390 | int is_dup; |
366 | 391 | ||
367 | GNUNET_assert (NULL != ctx && NULL != a && NULL != s1 && NULL != s2); | 392 | GNUNET_assert (NULL != ctx && NULL != a && NULL != s1 && NULL != s2); |
@@ -369,8 +394,8 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
369 | if (s1 == s2) | 394 | if (s1 == s2) |
370 | return; | 395 | return; |
371 | 396 | ||
372 | // 1. Make all transitions pointing to s2 point to s1, unless this transition | 397 | /* 1. Make all transitions pointing to s2 point to s1, unless this transition |
373 | // does not already exists, if it already exists remove transition. | 398 | does not already exists, if it already exists remove transition. */ |
374 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) | 399 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) |
375 | { | 400 | { |
376 | for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next) | 401 | for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next) |
@@ -393,19 +418,22 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
393 | } | 418 | } |
394 | } | 419 | } |
395 | 420 | ||
396 | // 2. Add all transitions from s2 to sX to s1 | 421 | /* 2. Add all transitions from s2 to sX to s1 */ |
397 | for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next) | 422 | for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next) |
398 | { | 423 | { |
399 | if (t_check->to_state != s1) | 424 | if (t_check->to_state != s1) |
400 | state_add_transition (ctx, s1, t_check->label, t_check->to_state); | 425 | state_add_transition (ctx, s1, t_check->label, t_check->to_state); |
401 | } | 426 | } |
402 | 427 | ||
403 | // 3. Rename s1 to {s1,s2} | 428 | /* 3. Rename s1 to {s1,s2} */ |
429 | #if REGEX_DEBUG_DFA | ||
430 | char *new_name; | ||
404 | new_name = s1->name; | 431 | new_name = s1->name; |
405 | GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name); | 432 | GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name); |
406 | GNUNET_free (new_name); | 433 | GNUNET_free (new_name); |
434 | #endif | ||
407 | 435 | ||
408 | // remove state | 436 | /* remove state */ |
409 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s2); | 437 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s2); |
410 | a->state_count--; | 438 | a->state_count--; |
411 | automaton_destroy_state (s2); | 439 | automaton_destroy_state (s2); |
@@ -624,7 +652,7 @@ has_epsilon (const char *str) | |||
624 | * epsilon could be found, NULL if 'str' was NULL | 652 | * epsilon could be found, NULL if 'str' was NULL |
625 | */ | 653 | */ |
626 | static char * | 654 | static char * |
627 | remove_epsilon (const char *str) | 655 | remove_epsilon (char *str) |
628 | { | 656 | { |
629 | size_t len; | 657 | size_t len; |
630 | 658 | ||
@@ -1069,8 +1097,8 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1069 | 1097 | ||
1070 | unsigned int n = a->state_count; | 1098 | unsigned int n = a->state_count; |
1071 | struct GNUNET_REGEX_State *states[n]; | 1099 | struct GNUNET_REGEX_State *states[n]; |
1072 | char *R_last[n][n]; | 1100 | char **R_last; |
1073 | char *R_cur[n][n]; | 1101 | char **R_cur; |
1074 | char *temp; | 1102 | char *temp; |
1075 | struct GNUNET_REGEX_Transition *t; | 1103 | struct GNUNET_REGEX_Transition *t; |
1076 | char *complete_regex; | 1104 | char *complete_regex; |
@@ -1078,6 +1106,9 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1078 | unsigned int j; | 1106 | unsigned int j; |
1079 | unsigned int k; | 1107 | unsigned int k; |
1080 | 1108 | ||
1109 | R_last = GNUNET_malloc_large (sizeof (char *) * n * n); | ||
1110 | R_cur = GNUNET_malloc_large (sizeof (char *) * n * n); | ||
1111 | |||
1081 | /* create depth-first numbering of the states, initializes 'state' */ | 1112 | /* create depth-first numbering of the states, initializes 'state' */ |
1082 | GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &number_states, | 1113 | GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &number_states, |
1083 | states); | 1114 | states); |
@@ -1090,36 +1121,36 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1090 | { | 1121 | { |
1091 | for (j = 0; j < n; j++) | 1122 | for (j = 0; j < n; j++) |
1092 | { | 1123 | { |
1093 | R_cur[i][j] = NULL; | 1124 | R_cur[i * n + j] = NULL; |
1094 | R_last[i][j] = NULL; | 1125 | R_last[i * n + j] = NULL; |
1095 | } | 1126 | } |
1096 | for (t = states[i]->transitions_head; NULL != t; t = t->next) | 1127 | for (t = states[i]->transitions_head; NULL != t; t = t->next) |
1097 | { | 1128 | { |
1098 | j = t->to_state->dfs_id; | 1129 | j = t->to_state->dfs_id; |
1099 | if (NULL == R_last[i][j]) | 1130 | if (NULL == R_last[i * n + j]) |
1100 | GNUNET_asprintf (&R_last[i][j], "%s", t->label); | 1131 | GNUNET_asprintf (&R_last[i * n + j], "%s", t->label); |
1101 | else | 1132 | else |
1102 | { | 1133 | { |
1103 | temp = R_last[i][j]; | 1134 | temp = R_last[i * n + j]; |
1104 | GNUNET_asprintf (&R_last[i][j], "%s|%s", R_last[i][j], t->label); | 1135 | GNUNET_asprintf (&R_last[i * n + j], "%s|%s", R_last[i * n + j], t->label); |
1105 | GNUNET_free (temp); | 1136 | GNUNET_free (temp); |
1106 | } | 1137 | } |
1107 | } | 1138 | } |
1108 | if (NULL == R_last[i][i]) | 1139 | if (NULL == R_last[i*n+i]) |
1109 | GNUNET_asprintf (&R_last[i][i], ""); | 1140 | GNUNET_asprintf (&R_last[i*n+i], ""); |
1110 | else | 1141 | else |
1111 | { | 1142 | { |
1112 | temp = R_last[i][i]; | 1143 | temp = R_last[i*n+i]; |
1113 | GNUNET_asprintf (&R_last[i][i], "(|%s)", R_last[i][i]); | 1144 | GNUNET_asprintf (&R_last[i*n+i], "(|%s)", R_last[i*n+i]); |
1114 | GNUNET_free (temp); | 1145 | GNUNET_free (temp); |
1115 | } | 1146 | } |
1116 | } | 1147 | } |
1117 | for (i = 0; i < n; i++) | 1148 | for (i = 0; i < n; i++) |
1118 | for (j = 0; j < n; j++) | 1149 | for (j = 0; j < n; j++) |
1119 | if (needs_parentheses (R_last[i][j])) | 1150 | if (needs_parentheses (R_last[i * n + j])) |
1120 | { | 1151 | { |
1121 | temp = R_last[i][j]; | 1152 | temp = R_last[i * n + j]; |
1122 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); | 1153 | GNUNET_asprintf (&R_last[i * n + j], "(%s)", R_last[i * n + j]); |
1123 | GNUNET_free (temp); | 1154 | GNUNET_free (temp); |
1124 | } | 1155 | } |
1125 | 1156 | ||
@@ -1136,9 +1167,9 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1136 | // R_last == R^{(k-1)}, R_cur == R^{(k)} | 1167 | // R_last == R^{(k-1)}, R_cur == R^{(k)} |
1137 | 1168 | ||
1138 | // Create R_cur[i][j] and simplify the expression | 1169 | // Create R_cur[i][j] and simplify the expression |
1139 | automaton_create_proofs_simplify (R_last[i][j], R_last[i][k], | 1170 | automaton_create_proofs_simplify (R_last[i * n + j], R_last[i*n+k], |
1140 | R_last[k][k], R_last[k][j], | 1171 | R_last[k*n+k], R_last[k*n+j], |
1141 | &R_cur[i][j]); | 1172 | &R_cur[i * n + j]); |
1142 | } | 1173 | } |
1143 | } | 1174 | } |
1144 | 1175 | ||
@@ -1147,9 +1178,9 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1147 | { | 1178 | { |
1148 | for (j = 0; j < n; j++) | 1179 | for (j = 0; j < n; j++) |
1149 | { | 1180 | { |
1150 | GNUNET_free_non_null (R_last[i][j]); | 1181 | GNUNET_free_non_null (R_last[i * n + j]); |
1151 | R_last[i][j] = R_cur[i][j]; | 1182 | R_last[i * n + j] = R_cur[i * n + j]; |
1152 | R_cur[i][j] = NULL; | 1183 | R_cur[i * n + j] = NULL; |
1153 | } | 1184 | } |
1154 | } | 1185 | } |
1155 | } | 1186 | } |
@@ -1157,9 +1188,9 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1157 | // assign proofs and hashes | 1188 | // assign proofs and hashes |
1158 | for (i = 0; i < n; i++) | 1189 | for (i = 0; i < n; i++) |
1159 | { | 1190 | { |
1160 | if (NULL != R_last[a->start->dfs_id][i]) | 1191 | if (NULL != R_last[a->start->dfs_id*n+i]) |
1161 | { | 1192 | { |
1162 | states[i]->proof = GNUNET_strdup (R_last[a->start->dfs_id][i]); | 1193 | states[i]->proof = GNUNET_strdup (R_last[a->start->dfs_id*n+i]); |
1163 | GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof), | 1194 | GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof), |
1164 | &states[i]->hash); | 1195 | &states[i]->hash); |
1165 | } | 1196 | } |
@@ -1172,16 +1203,16 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1172 | { | 1203 | { |
1173 | if (states[i]->accepting) | 1204 | if (states[i]->accepting) |
1174 | { | 1205 | { |
1175 | if (NULL == complete_regex && 0 < strlen (R_last[a->start->dfs_id][i])) | 1206 | if (NULL == complete_regex && 0 < strlen (R_last[a->start->dfs_id*n+i])) |
1176 | { | 1207 | { |
1177 | GNUNET_asprintf (&complete_regex, "%s", R_last[a->start->dfs_id][i]); | 1208 | GNUNET_asprintf (&complete_regex, "%s", R_last[a->start->dfs_id*n+i]); |
1178 | } | 1209 | } |
1179 | else if (NULL != R_last[a->start->dfs_id][i] && | 1210 | else if (NULL != R_last[a->start->dfs_id*n+i] && |
1180 | 0 < strlen (R_last[a->start->dfs_id][i])) | 1211 | 0 < strlen (R_last[a->start->dfs_id*n+i])) |
1181 | { | 1212 | { |
1182 | temp = complete_regex; | 1213 | temp = complete_regex; |
1183 | GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex, | 1214 | GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex, |
1184 | R_last[a->start->dfs_id][i]); | 1215 | R_last[a->start->dfs_id*n+i]); |
1185 | GNUNET_free (temp); | 1216 | GNUNET_free (temp); |
1186 | } | 1217 | } |
1187 | } | 1218 | } |
@@ -1192,8 +1223,10 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1192 | for (i = 0; i < n; i++) | 1223 | for (i = 0; i < n; i++) |
1193 | { | 1224 | { |
1194 | for (j = 0; j < n; j++) | 1225 | for (j = 0; j < n; j++) |
1195 | GNUNET_free_non_null (R_last[i][j]); | 1226 | GNUNET_free_non_null (R_last[i * n + j]); |
1196 | } | 1227 | } |
1228 | GNUNET_free (R_cur); | ||
1229 | GNUNET_free (R_last); | ||
1197 | } | 1230 | } |
1198 | 1231 | ||
1199 | 1232 | ||
@@ -1417,7 +1450,7 @@ static void | |||
1417 | dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | 1450 | dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, |
1418 | struct GNUNET_REGEX_Automaton *a) | 1451 | struct GNUNET_REGEX_Automaton *a) |
1419 | { | 1452 | { |
1420 | int table[a->state_count][a->state_count]; | 1453 | int *table; |
1421 | struct GNUNET_REGEX_State *s1; | 1454 | struct GNUNET_REGEX_State *s1; |
1422 | struct GNUNET_REGEX_State *s2; | 1455 | struct GNUNET_REGEX_State *s2; |
1423 | struct GNUNET_REGEX_Transition *t1; | 1456 | struct GNUNET_REGEX_Transition *t1; |
@@ -1427,29 +1460,40 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1427 | int change; | 1460 | int change; |
1428 | unsigned int num_equal_edges; | 1461 | unsigned int num_equal_edges; |
1429 | unsigned int i; | 1462 | unsigned int i; |
1463 | unsigned int state_cnt; | ||
1464 | |||
1465 | if (NULL == a || 0 == a->state_count) | ||
1466 | { | ||
1467 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
1468 | "Could not merge nondistinguishable states, automaton was NULL.\n"); | ||
1469 | return; | ||
1470 | } | ||
1430 | 1471 | ||
1431 | for (i = 0, s1 = a->states_head; i < a->state_count && NULL != s1; | 1472 | state_cnt = a->state_count; |
1473 | table = (int *)GNUNET_malloc_large (sizeof (int) * state_cnt * a->state_count); | ||
1474 | |||
1475 | for (i = 0, s1 = a->states_head; i < state_cnt && NULL != s1; | ||
1432 | i++, s1 = s1->next) | 1476 | i++, s1 = s1->next) |
1433 | { | 1477 | { |
1434 | s1->marked = i; | 1478 | s1->marked = i; |
1435 | } | 1479 | } |
1436 | 1480 | ||
1437 | // Mark all pairs of accepting/!accepting states | 1481 | /* Mark all pairs of accepting/!accepting states */ |
1438 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) | 1482 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) |
1439 | { | 1483 | { |
1440 | for (s2 = a->states_head; NULL != s2; s2 = s2->next) | 1484 | for (s2 = a->states_head; NULL != s2; s2 = s2->next) |
1441 | { | 1485 | { |
1442 | table[s1->marked][s2->marked] = 0; | 1486 | table[((s1->marked * state_cnt) + s2->marked)] = 0; |
1443 | 1487 | ||
1444 | if ((s1->accepting && !s2->accepting) || | 1488 | if ((s1->accepting && !s2->accepting) || |
1445 | (!s1->accepting && s2->accepting)) | 1489 | (!s1->accepting && s2->accepting)) |
1446 | { | 1490 | { |
1447 | table[s1->marked][s2->marked] = 1; | 1491 | table[((s1->marked * state_cnt) + s2->marked)] = 1; |
1448 | } | 1492 | } |
1449 | } | 1493 | } |
1450 | } | 1494 | } |
1451 | 1495 | ||
1452 | // Find all equal states | 1496 | /* Find all equal states */ |
1453 | change = 1; | 1497 | change = 1; |
1454 | while (0 != change) | 1498 | while (0 != change) |
1455 | { | 1499 | { |
@@ -1458,7 +1502,7 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1458 | { | 1502 | { |
1459 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next) | 1503 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next) |
1460 | { | 1504 | { |
1461 | if (0 != table[s1->marked][s2->marked]) | 1505 | if (0 != table[((s1->marked * state_cnt) + s2->marked)]) |
1462 | continue; | 1506 | continue; |
1463 | 1507 | ||
1464 | num_equal_edges = 0; | 1508 | num_equal_edges = 0; |
@@ -1469,10 +1513,10 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1469 | if (0 == strcmp (t1->label, t2->label)) | 1513 | if (0 == strcmp (t1->label, t2->label)) |
1470 | { | 1514 | { |
1471 | num_equal_edges++; | 1515 | num_equal_edges++; |
1472 | if (0 != table[t1->to_state->marked][t2->to_state->marked] || | 1516 | if (0 != table[((t1->to_state->marked * state_cnt) + t2->to_state->marked)] || |
1473 | 0 != table[t2->to_state->marked][t1->to_state->marked]) | 1517 | 0 != table[((t2->to_state->marked * state_cnt) + t1->to_state->marked)]) |
1474 | { | 1518 | { |
1475 | table[s1->marked][s2->marked] = 1; | 1519 | table[((s1->marked * state_cnt) + s2->marked)] = 1; |
1476 | change = 1; | 1520 | change = 1; |
1477 | } | 1521 | } |
1478 | } | 1522 | } |
@@ -1481,24 +1525,26 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1481 | if (num_equal_edges != s1->transition_count || | 1525 | if (num_equal_edges != s1->transition_count || |
1482 | num_equal_edges != s2->transition_count) | 1526 | num_equal_edges != s2->transition_count) |
1483 | { | 1527 | { |
1484 | // Make sure ALL edges of possible equal states are the same | 1528 | /* Make sure ALL edges of possible equal states are the same */ |
1485 | table[s1->marked][s2->marked] = -2; | 1529 | table[((s1->marked * state_cnt) + s2->marked)] = -2; |
1486 | } | 1530 | } |
1487 | } | 1531 | } |
1488 | } | 1532 | } |
1489 | } | 1533 | } |
1490 | 1534 | ||
1491 | // Merge states that are equal | 1535 | /* Merge states that are equal */ |
1492 | for (s1 = a->states_head; NULL != s1; s1 = s1_next) | 1536 | for (s1 = a->states_head; NULL != s1; s1 = s1_next) |
1493 | { | 1537 | { |
1494 | s1_next = s1->next; | 1538 | s1_next = s1->next; |
1495 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next) | 1539 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next) |
1496 | { | 1540 | { |
1497 | s2_next = s2->next; | 1541 | s2_next = s2->next; |
1498 | if (table[s1->marked][s2->marked] == 0) | 1542 | if (0 == table[((s1->marked * state_cnt) + s2->marked)]) |
1499 | automaton_merge_states (ctx, a, s1, s2); | 1543 | automaton_merge_states (ctx, a, s1, s2); |
1500 | } | 1544 | } |
1501 | } | 1545 | } |
1546 | |||
1547 | GNUNET_free (table); | ||
1502 | } | 1548 | } |
1503 | 1549 | ||
1504 | 1550 | ||
@@ -1907,8 +1953,9 @@ static struct GNUNET_REGEX_StateSet * | |||
1907 | nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | 1953 | nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, |
1908 | struct GNUNET_REGEX_State *s, const char *label) | 1954 | struct GNUNET_REGEX_State *s, const char *label) |
1909 | { | 1955 | { |
1956 | unsigned int i; | ||
1910 | struct GNUNET_REGEX_StateSet *cls; | 1957 | struct GNUNET_REGEX_StateSet *cls; |
1911 | struct GNUNET_REGEX_StateSet *cls_check; | 1958 | struct GNUNET_REGEX_StateSet_MDLL cls_check; |
1912 | struct GNUNET_REGEX_State *clsstate; | 1959 | struct GNUNET_REGEX_State *clsstate; |
1913 | struct GNUNET_REGEX_State *currentstate; | 1960 | struct GNUNET_REGEX_State *currentstate; |
1914 | struct GNUNET_REGEX_Transition *ctran; | 1961 | struct GNUNET_REGEX_Transition *ctran; |
@@ -1917,20 +1964,21 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1917 | return NULL; | 1964 | return NULL; |
1918 | 1965 | ||
1919 | cls = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet)); | 1966 | cls = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet)); |
1920 | cls_check = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet)); | 1967 | cls_check.head = NULL; |
1921 | 1968 | cls_check.tail = NULL; | |
1922 | for (clsstate = nfa->states_head; NULL != clsstate; clsstate = clsstate->next) | ||
1923 | clsstate->contained = 0; | ||
1924 | 1969 | ||
1925 | // Add start state to closure only for epsilon closure | 1970 | // Add start state to closure only for epsilon closure |
1926 | if (NULL == label) | 1971 | if (NULL == label) |
1927 | GNUNET_array_append (cls->states, cls->len, s); | 1972 | GNUNET_array_append (cls->states, cls->len, s); |
1928 | 1973 | ||
1929 | GNUNET_array_append (cls_check->states, cls_check->len, s); | 1974 | GNUNET_CONTAINER_MDLL_insert (SS, cls_check.head, cls_check.tail, s); |
1930 | while (cls_check->len > 0) | 1975 | cls_check.len = 1; |
1976 | |||
1977 | while (cls_check.len > 0) | ||
1931 | { | 1978 | { |
1932 | currentstate = cls_check->states[cls_check->len - 1]; | 1979 | currentstate = cls_check.tail; |
1933 | GNUNET_array_grow (cls_check->states, cls_check->len, cls_check->len - 1); | 1980 | GNUNET_CONTAINER_MDLL_remove (SS, cls_check.head, cls_check.tail, currentstate); |
1981 | cls_check.len--; | ||
1934 | 1982 | ||
1935 | for (ctran = currentstate->transitions_head; NULL != ctran; | 1983 | for (ctran = currentstate->transitions_head; NULL != ctran; |
1936 | ctran = ctran->next) | 1984 | ctran = ctran->next) |
@@ -1942,14 +1990,16 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1942 | if (NULL != clsstate && 0 == clsstate->contained) | 1990 | if (NULL != clsstate && 0 == clsstate->contained) |
1943 | { | 1991 | { |
1944 | GNUNET_array_append (cls->states, cls->len, clsstate); | 1992 | GNUNET_array_append (cls->states, cls->len, clsstate); |
1945 | GNUNET_array_append (cls_check->states, cls_check->len, clsstate); | 1993 | GNUNET_CONTAINER_MDLL_insert_tail (SS, cls_check.head, cls_check.tail, clsstate); |
1994 | cls_check.len++; | ||
1946 | clsstate->contained = 1; | 1995 | clsstate->contained = 1; |
1947 | } | 1996 | } |
1948 | } | 1997 | } |
1949 | } | 1998 | } |
1950 | } | 1999 | } |
1951 | GNUNET_assert (0 == cls_check->len); | 2000 | |
1952 | GNUNET_free (cls_check); | 2001 | for (i = 0; i < cls->len; i++) |
2002 | cls->states[i]->contained = 0; | ||
1953 | 2003 | ||
1954 | // sort the states | 2004 | // sort the states |
1955 | if (cls->len > 1) | 2005 | if (cls->len > 1) |
diff --git a/src/regex/regex_internal.h b/src/regex/regex_internal.h index 21c498145..479de7024 100644 --- a/src/regex/regex_internal.h +++ b/src/regex/regex_internal.h | |||
@@ -86,16 +86,26 @@ struct GNUNET_REGEX_Transition | |||
86 | struct GNUNET_REGEX_State | 86 | struct GNUNET_REGEX_State |
87 | { | 87 | { |
88 | /** | 88 | /** |
89 | * This is a linked list. | 89 | * This is a linked list to keep states in an automaton. |
90 | */ | 90 | */ |
91 | struct GNUNET_REGEX_State *prev; | 91 | struct GNUNET_REGEX_State *prev; |
92 | 92 | ||
93 | /** | 93 | /** |
94 | * This is a linked list. | 94 | * This is a linked list to keep states in an automaton. |
95 | */ | 95 | */ |
96 | struct GNUNET_REGEX_State *next; | 96 | struct GNUNET_REGEX_State *next; |
97 | 97 | ||
98 | /** | 98 | /** |
99 | * This is a multi DLL for StateSet_p. | ||
100 | */ | ||
101 | struct GNUNET_REGEX_State *prev_SS; | ||
102 | |||
103 | /** | ||
104 | * This is a multi DLL for StateSet_p. | ||
105 | */ | ||
106 | struct GNUNET_REGEX_State *next_SS; | ||
107 | |||
108 | /** | ||
99 | * Unique state id. | 109 | * Unique state id. |
100 | */ | 110 | */ |
101 | unsigned int id; | 111 | unsigned int id; |