struct GNUNET_REGEX_State *from_state, const char *label,
struct GNUNET_REGEX_State *to_state)
{
- int is_dup;
struct GNUNET_REGEX_Transition *t;
struct GNUNET_REGEX_Transition *oth;
}
// Do not add duplicate state transitions
- is_dup = GNUNET_NO;
for (t = from_state->transitions_head; NULL != t; t = t->next)
{
if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) &&
t->from_state == from_state)
- {
- is_dup = GNUNET_YES;
- break;
- }
+ return;
}
- if (GNUNET_YES == is_dup)
- return;
-
// sort transitions by label
for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
{
if (transition->from_state != state)
return;
+ GNUNET_free_non_null (transition->label);
+
state->transition_count--;
GNUNET_CONTAINER_DLL_remove (state->transitions_head, state->transitions_tail,
transition);
- GNUNET_free_non_null (transition->label);
GNUNET_free (transition);
}
static void
state_set_clear (struct GNUNET_REGEX_StateSet *set)
{
- if (NULL != set)
- {
- GNUNET_free_non_null (set->states);
- GNUNET_free (set);
- }
+ if (NULL == set)
+ return;
+
+ if (set->len > 0)
+ GNUNET_array_grow (set->states, set->len, 0);
+ GNUNET_free (set);
}
GNUNET_free_non_null (s->name);
GNUNET_free_non_null (s->proof);
+ state_set_clear (s->nfa_set);
for (t = s->transitions_head; NULL != t; t = next_t)
{
next_t = t->next;
- GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t);
- GNUNET_free_non_null (t->label);
- GNUNET_free (t);
+ state_remove_transition (s, t);
}
- state_set_clear (s->nfa_set);
-
GNUNET_free (s);
}
automaton_remove_state (struct GNUNET_REGEX_Automaton *a,
struct GNUNET_REGEX_State *s)
{
- struct GNUNET_REGEX_State *ss;
struct GNUNET_REGEX_State *s_check;
struct GNUNET_REGEX_Transition *t_check;
+ struct GNUNET_REGEX_Transition *t_check_next;
if (NULL == a || NULL == s)
return;
- // remove state
- ss = s;
- GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
- a->state_count--;
-
// remove all transitions leading to this state
for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
{
for (t_check = s_check->transitions_head; NULL != t_check;
- t_check = t_check->next)
+ t_check = t_check_next)
{
- if (t_check->to_state == ss)
- {
- GNUNET_CONTAINER_DLL_remove (s_check->transitions_head,
- s_check->transitions_tail, t_check);
- s_check->transition_count--;
- }
+ t_check_next = t_check->next;
+ if (t_check->to_state == s)
+ state_remove_transition (s_check, t_check);
}
}
- automaton_destroy_state (ss);
+ // remove state
+ GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
+ a->state_count--;
+
+ automaton_destroy_state (s);
}
t->from_state = start;
GNUNET_CONTAINER_DLL_insert (*transitions_head, *transitions_tail, t);
- GNUNET_free_non_null (label);
-
if (GNUNET_NO == cur->marked)
{
dfa_compress_paths_helper (cur, cur, NULL, transitions_head,
dfa_compress_paths_helper (start, t->to_state, new_label,
transitions_head, transitions_tail);
}
+ GNUNET_free (new_label);
}
}
GNUNET_free_non_null (a->regex);
GNUNET_free_non_null (a->canonical_regex);
- for (s = a->states_head; NULL != s;)
+ for (s = a->states_head; NULL != s; s = next_state)
{
next_state = s->next;
+ GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
automaton_destroy_state (s);
- s = next_state;
}
GNUNET_free (a);
*
* @param min_len minimum length of the path in the graph.
* @param max_len maximum length of the path in the graph.
- * @param cur_len current length of the path already traversed.
* @param consumed_string string consumed by traversing the graph till this state.
* @param state current state of the automaton.
* @param iterator iterator function called for each edge.
*/
static void
iterate_initial_edge (const unsigned int min_len, const unsigned int max_len,
- unsigned int cur_len, char *consumed_string,
- struct GNUNET_REGEX_State *state,
+ char *consumed_string, struct GNUNET_REGEX_State *state,
GNUNET_REGEX_KeyIterator iterator, void *iterator_cls)
{
unsigned int i;
struct GNUNET_REGEX_Transition *t;
unsigned int num_edges = state->transition_count;
struct GNUNET_REGEX_Edge edges[num_edges];
+ struct GNUNET_REGEX_Edge edge[1];
struct GNUNET_HashCode hash;
+ struct GNUNET_HashCode hash_new;
+
+ unsigned int cur_len;
+
+ if (NULL != consumed_string)
+ cur_len = strlen (consumed_string);
+ else
+ cur_len = 0;
- if (cur_len > min_len && NULL != consumed_string && cur_len <= max_len)
+ if (cur_len >= min_len && cur_len > 0 && NULL != consumed_string)
{
- for (i = 0, t = state->transitions_head; NULL != t; t = t->next, i++)
+ if (cur_len <= max_len)
{
- edges[i].label = t->label;
- edges[i].destination = t->to_state->hash;
- }
+ for (i = 0, t = state->transitions_head; NULL != t && i < num_edges;
+ t = t->next, i++)
+ {
+ edges[i].label = t->label;
+ edges[i].destination = t->to_state->hash;
+ }
+
+ GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash);
+ iterator (iterator_cls, &hash, consumed_string, state->accepting,
+ num_edges, edges);
- GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash);
- iterator (iterator_cls, &hash, consumed_string, state->accepting, num_edges,
- edges);
+ // Special case for regex consisting of just a string that is shorter than
+ // max_len
+ if (GNUNET_YES == state->accepting && cur_len > 1 &&
+ state->transition_count < 1 && cur_len < max_len)
+ {
+ edge[0].label = &consumed_string[cur_len - 1];
+ edge[0].destination = state->hash;
+ temp = GNUNET_strdup (consumed_string);
+ temp[cur_len - 1] = '\0';
+ GNUNET_CRYPTO_hash (temp, cur_len - 1, &hash_new);
+ iterator (iterator_cls, &hash_new, temp, GNUNET_NO, 1, edge);
+ GNUNET_free (temp);
+ }
+ }
+ else if (max_len < cur_len)
+ {
+ edge[0].label = &consumed_string[max_len];
+ edge[0].destination = state->hash;
+ temp = GNUNET_strdup (consumed_string);
+ temp[max_len] = '\0';
+ GNUNET_CRYPTO_hash (temp, max_len, &hash);
+ iterator (iterator_cls, &hash, temp, GNUNET_NO, 1, edge);
+ GNUNET_free (temp);
+ }
}
if (cur_len < max_len)
{
- cur_len++;
for (t = state->transitions_head; NULL != t; t = t->next)
{
if (NULL != consumed_string)
else
GNUNET_asprintf (&temp, "%s", t->label);
- iterate_initial_edge (min_len, max_len, cur_len, temp, t->to_state,
- iterator, iterator_cls);
+ iterate_initial_edge (min_len, max_len, temp, t->to_state, iterator,
+ iterator_cls);
GNUNET_free (temp);
}
}
}
-/**
- * Iterate over all initial edges that aren't actually part of the automaton.
- * This is needed to find the initial states returned by
- * GNUNET_REGEX_get_first_key. Iteration will start at the first state that has
- * more than one outgoing edge, i.e. the state that branches the graph.
- * For example consider the following graph:
- * a -> b -> c -> d -> ...
- * \-> e -> ...
- *
- * This function will not iterate over the edges leading to "c", because these
- * will be covered by the iterate_edges function.
- *
- * @param a the automaton for which the initial states should be computed.
- * @param initial_len length of the initial state string.
- * @param iterator iterator function called for each edge.
- * @param iterator_cls closure for the iterator function.
- */
-void
-iterate_initial_edges (struct GNUNET_REGEX_Automaton *a,
- const unsigned int initial_len,
- GNUNET_REGEX_KeyIterator iterator, void *iterator_cls)
-{
- char *consumed_string;
- char *temp;
- struct GNUNET_REGEX_State *s;
- unsigned int cur_len;
-
- if (1 > initial_len)
- return;
-
- consumed_string = NULL;
- s = a->start;
- cur_len = 0;
-
- if (1 == s->transition_count)
- {
- do
- {
- if (NULL != consumed_string)
- {
- temp = consumed_string;
- GNUNET_asprintf (&consumed_string, "%s%s", consumed_string,
- s->transitions_head->label);
- GNUNET_free (temp);
- }
- else
- GNUNET_asprintf (&consumed_string, "%s", s->transitions_head->label);
-
- s = s->transitions_head->to_state;
- cur_len += strlen (s->transitions_head->label);
- }
- while (cur_len < initial_len && 1 == s->transition_count);
- }
-
- iterate_initial_edge (cur_len, initial_len, cur_len, consumed_string, s,
- iterator, iterator_cls);
-
- GNUNET_free_non_null (consumed_string);
-}
-
-
/**
* Iterate over all edges helper function starting from state 's', calling
- * iterator function for each edge.
+ * iterator function for each edge if the automaton.
*
* @param s state.
* @param iterator iterator function called for each edge.
for (s = a->states_head; NULL != s; s = s->next)
s->marked = GNUNET_NO;
- iterate_initial_edges (a, INITIAL_BITS, iterator, iterator_cls);
+ iterate_initial_edge (0, INITIAL_BITS, NULL, a->start, iterator,
+ iterator_cls);
iterate_edge (a->start, iterator, iterator_cls);
}
+
+
+/**
+ * Create a string with binary IP notation for the given 'addr' in 'str'.
+ *
+ * @param af address family of the given 'addr'.
+ * @param addr address that should be converted to a string.
+ * struct in_addr * for IPv4 and struct in6_addr * for IPv6.
+ * @param str string that will contain binary notation of 'addr'. Expected
+ * to be at least 33 bytes long for IPv4 and 129 bytes long for IPv6.
+ */
+static void
+iptobinstr (const int af, const void *addr, char *str)
+{
+ unsigned int i;
+
+ switch (af)
+ {
+ case AF_INET:
+ {
+ uint32_t b = htonl (((struct in_addr *) addr)->s_addr);
+
+ str[32] = '\0';
+ str += 31;
+ for (i = 31; i >= 0; i--)
+ {
+ *str-- = (b & 1) + '0';
+ b >>= 1;
+ }
+ break;
+ }
+ case AF_INET6:
+ {
+ struct in6_addr b = *(struct in6_addr *) addr;
+
+ str[128] = '\0';
+ str += 127;
+ for (i = 127; i >= 0; i--)
+ {
+ *str-- = (b.s6_addr[i / 8] & 1) + '0';
+ b.s6_addr[i / 8] >>= 1;
+ }
+ break;
+ }
+ }
+}
+
+
+/**
+ * Get the ipv4 network prefix from the given 'netmask'.
+ *
+ * @param netmask netmask for which to get the prefix len.
+ *
+ * @return length of ipv4 prefix for 'netmask'.
+ */
+static unsigned int
+ipv4netmasktoprefixlen (const char *netmask)
+{
+ struct in_addr a;
+ unsigned int len;
+ uint32_t t;
+
+ if (1 != inet_pton (AF_INET, netmask, &a))
+ return 0;
+
+ for (len = 32, t = htonl (~a.s_addr); t & 1; t >>= 1, len--) ;
+
+ return len;
+}
+
+
+/**
+ * Create a regex in 'rxstr' from the given 'ip' and 'netmask'.
+ *
+ * @param ip IPv4 representation.
+ * @param netmask netmask for the ip.
+ * @param rxstr generated regex, must be at least GNUNET_REGEX_IPV4_REGEXLEN
+ * bytes long.
+ */
+void
+GNUNET_REGEX_ipv4toregex (const struct in_addr *ip, const char *netmask,
+ char *rxstr)
+{
+ unsigned int pfxlen;
+
+ pfxlen = ipv4netmasktoprefixlen (netmask);
+ iptobinstr (AF_INET, ip, rxstr);
+ rxstr[pfxlen] = '\0';
+ strcat (rxstr, "(0|1)*");
+}
+
+
+/**
+ * Create a regex in 'rxstr' from the given 'ipv6' and 'prefixlen'.
+ *
+ * @param ipv6 IPv6 representation.
+ * @param prefixlen length of the ipv6 prefix.
+ * @param rxstr generated regex, must be at least GNUNET_REGEX_IPV6_REGEXLEN
+ * bytes long.
+ */
+void
+GNUNET_REGEX_ipv6toregex (const struct in6_addr *ipv6,
+ const unsigned int prefixlen, char *rxstr)
+{
+ iptobinstr (AF_INET6, ipv6, rxstr);
+ rxstr[prefixlen] = '\0';
+ strcat (rxstr, "(0|1)*");
+}
projects / oweals / gnunet.git / blobdiff