+/**
+ * Get the number of matching characters on the prefix of both strings.
+ *
+ * @param s1 String 1.
+ * @param s2 String 2.
+ *
+ * @return Number of characters of matching prefix.
+ */
+static unsigned int
+get_prefix_length (const char *s1, const char *s2)
+{
+ unsigned int l1;
+ unsigned int l2;
+ unsigned int limit;
+ unsigned int i;
+
+ l1 = strlen (s1);
+ l2 = strlen (s2);
+ limit = l1 > l2 ? l2 : l1;
+
+ for (i = 0; i < limit; i++)
+ {
+ if (s1[i] != s2[i])
+ return i;
+ }
+ return limit;
+}
+
+
+/**
+ * Return the child context with the longest prefix match with the regex.
+ * Usually only one child will match, search all just in case.
+ *
+ * @param ctx Context whose children to search.
+ * @param regex String to match.
+ *
+ * @return Child with the longest prefix, NULL if no child matches.
+ */
+static struct RegexCombineCtx *
+get_longest_prefix (struct RegexCombineCtx *ctx, const char *regex)
+{
+ struct RegexCombineCtx *p;
+ struct RegexCombineCtx *best;
+ unsigned int i;
+ unsigned int l;
+ unsigned int best_l;
+
+ best_l = 0;
+ best = NULL;
+
+ for (i = 0; i < ctx->size; i++)
+ {
+ p = ctx->children[i];
+ if (NULL == p)
+ continue;
+
+ l = get_prefix_length (p->s, regex);
+ if (l > best_l)
+ {
+ GNUNET_break (0 == best_l);
+ best = p;
+ best_l = l;
+ }
+ }
+ return best;
+}
+
+static void
+regex_add_multiple (struct RegexCombineCtx *ctx,
+ const char *regex,
+ struct RegexCombineCtx **children)
+{
+ char tmp[2];
+ long unsigned int i;
+ size_t l;
+ struct RegexCombineCtx *newctx;
+ unsigned int count;
+
+ if ('(' != regex[0])
+ {
+ GNUNET_assert (0);
+ }
+
+ /* Does the regex cover *all* possible children? Then don't add any,
+ * as it will be covered by the post-regex "(a-z)*"
+ */
+ l = strlen (regex);
+ count = 0;
+ for (i = 1UL; i < l; i++)
+ {
+ if (regex[i] != '|' && regex[i] != ')')
+ {
+ count++;
+ }
+ }
+ if (count == ctx->size)
+ {
+ return;
+ }
+
+ /* Add every component as a child node */
+ tmp[1] = '\0';
+ for (i = 1UL; i < l; i++)
+ {
+ if (regex[i] != '|' && regex[i] != ')')
+ {
+ tmp[0] = regex[i];
+ newctx = new_regex_ctx(ctx->size);
+ newctx->s = GNUNET_strdup (tmp);
+ if (children != NULL)
+ GNUNET_memcpy (newctx->children,
+ children,
+ sizeof (*children) * ctx->size);
+ ctx->children[c2i(tmp[0], ctx->size)] = newctx;
+ }
+ }
+}
+
+/**
+ * Add a single regex to a context, splitting the exisiting state.
+ *
+ * We only had a partial match, split existing state, truncate the current node
+ * so it only contains the prefix, add suffix(es) as children.
+ *
+ * @param ctx Context to split.
+ * @param len Lenght of ctx->s
+ * @param prefix_l Lenght of common prefix of the new regex and @a ctx->s
+ */
+static void
+regex_split (struct RegexCombineCtx *ctx,
+ unsigned int len,
+ unsigned int prefix_l)
+{
+ struct RegexCombineCtx *newctx;
+ unsigned int idx;
+ char *suffix;
+
+ suffix = GNUNET_malloc (len - prefix_l + 1);
+ strncpy (suffix, &ctx->s[prefix_l], len - prefix_l + 1);
+
+ /* Suffix saved, truncate current node so it only contains the prefix,
+ * copy any children nodes to put as grandchildren and initialize new empty
+ * children array.
+ */
+ ctx->s[prefix_l] = '\0';
+
+ /* If the suffix is an OR expression, add multiple children */
+ if ('(' == suffix[0])
+ {
+ struct RegexCombineCtx **tmp;
+
+ tmp = ctx->children;
+ ctx->children = GNUNET_malloc (sizeof(*tmp) * ctx->size);
+ regex_add_multiple (ctx, suffix, tmp);
+ GNUNET_free (suffix);
+ GNUNET_free (tmp);
+ return;
+ }
+
+ /* The suffix is a normal string, add as one node */
+ newctx = new_regex_ctx (ctx->size);
+ newctx->s = suffix;
+ move_children (newctx, ctx);
+ idx = c2i(suffix[0], ctx->size);
+ ctx->children[idx] = newctx;
+}
+
+