regex_test_lib.c File Reference

#include "platform.h"
#include "gnunet_util_lib.h"
#include "regex_test_lib.h"

Include dependency graph for regex_test_lib.c:

Go to the source code of this file.

Data Structures
struct	RegexCombineCtx
	Struct to hold the tree formed by prefix-combining the regexes. More...

Functions
static int	c2i (char c, int size)
	Char 2 int. More...
static void	debugctx (struct RegexCombineCtx *ctx, int level)
	Printf the combined regex ctx. More...
static void	regex_add (struct RegexCombineCtx *ctx, const char *regex)
	Add a single regex to a context, combining with existing regex by-prefix. More...
static struct RegexCombineCtx *	new_regex_ctx (unsigned int alphabet_size)
	Create and initialize a new RegexCombineCtx. More...
static void	move_children (struct RegexCombineCtx *dst, const struct RegexCombineCtx *src)
static char *	regex_combine (struct RegexCombineCtx *ctx)
	Extract a string from all prefix-combined regexes. More...
static unsigned int	get_prefix_length (const char *s1, const char *s2)
	Get the number of matching characters on the prefix of both strings. More...
static struct RegexCombineCtx *	get_longest_prefix (struct RegexCombineCtx *ctx, const char *regex)
	Return the child context with the longest prefix match with the regex. More...
static void	regex_add_multiple (struct RegexCombineCtx *ctx, const char *regex, struct RegexCombineCtx **children)
static void	regex_split (struct RegexCombineCtx *ctx, unsigned int len, unsigned int prefix_l)
	Add a single regex to a context, splitting the existing state. More...
static void	regex_ctx_destroy (struct RegexCombineCtx *ctx)
	Free all resources used by the context node and all its children. More...
char *	REGEX_TEST_combine (char *const regexes[], unsigned int alphabet_size)
	Combine an array of regexes into a single prefix-shared regex. More...
char **	REGEX_TEST_read_from_file (const char *filename)
	Read a set of regexes from a file, one per line and return them in an array suitable for REGEX_TEST_combine. More...
void	REGEX_TEST_free_from_file (char **regexes)
	Free all memory reserved for a set of regexes created by read_from_file. More...

Function Documentation

c2i()

static int c2i ( char  c, int  size  )

static

Char 2 int.

Convert a character into its int value depending on the base used

Parameters

c	Char
size	base (2, 8 or 16(hex))

Returns

Int in range [0, (base-1)]

Definition at line 65 of file regex_test_lib.c.

{
  switch (size)
  {
  case 2:
  case 8:
    return c - '0';
    break;
 
  case 16:
    if ((c >= '0') && (c <= '9') )
      return c - '0';
    else if ((c >= 'A') && (c <= 'F') )
      return c - 'A' + 10;
    else if ((c >= 'a') && (c <= 'f') )
      return c - 'a' + 10;
    else
    {
      GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                  "Cannot convert char %c in base %u\n",
                  c, size);
      GNUNET_assert (0);
    }
    break;
 
  default:
    GNUNET_assert (0);
  }
}

References GNUNET_assert, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, and size.

Referenced by debugctx(), regex_add(), regex_add_multiple(), and regex_split().

Here is the caller graph for this function:

debugctx()

static void debugctx ( struct RegexCombineCtx *  ctx, int  level  )

static

Printf the combined regex ctx.

Parameters

ctx	The ctx to printf
level	Indentation level to start with

Definition at line 120 of file regex_test_lib.c.

{
#if DEBUG_REGEX
  if (NULL != ctx->s)
  {
    space (level - 1);
    fprintf (stderr, "%u:'%s'\n", c2i (ctx->s[0], ctx->size), ctx->s);
  }
  else
    fprintf (stderr, "ROOT (base %u)\n", ctx->size);
  for (unsigned int i = 0; i < ctx->size; i++)
  {
    if (NULL != ctx->children[i])
    {
      space (level);
      debugctx (ctx->children[i], level + 1);
    }
  }
  fflush (stderr);
#endif
}

References c2i(), ctx, and debugctx().

Referenced by debugctx(), and REGEX_TEST_combine().

Here is the call graph for this function:

Here is the caller graph for this function:

regex_add()

static void regex_add ( struct RegexCombineCtx *  ctx, const char *  regex  )

static

Add a single regex to a context, combining with existing regex by-prefix.

Parameters

ctx	Context with 0 or more regexes.
regex	Regex to add.

Definition at line 444 of file regex_test_lib.c.

{
  struct RegexCombineCtx *p;
  struct RegexCombineCtx *newctx;
  long unsigned int l;
  unsigned int prefix_l;
  const char *rest_r;
  const char *rest_s;
  size_t len;
  int idx;
 
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "regex_add '%s' into '%s'\n",
              regex, ctx->s);
  l = strlen (regex);
  if (0UL == l)
    return;
 
  /* If the regex is in the form of (a|b|c), add every character separately */
  if ('(' == regex[0])
  {
    regex_add_multiple (ctx, regex, NULL);
    return;
  }
 
  p = get_longest_prefix (ctx, regex);
  if (NULL != p)
  {
    /* There is some prefix match, reduce regex and try again */
    prefix_l = get_prefix_length (p->s, regex);
    rest_s = &p->s[prefix_l];
    rest_r = &regex[prefix_l];
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "chosen '%s' [%u]\n", p->s, prefix_l);
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "prefix r '%.*s'\n", prefix_l, p->s);
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "rest r '%s'\n", rest_r);
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "rest s '%s'\n", rest_s);
    len = strlen (p->s);
    if (prefix_l < len)
    {
      regex_split (p, len, prefix_l);
    }
    regex_add (p, rest_r);
    return;
  }
 
  /* There is no prefix match, add new */
  idx = c2i (regex[0], ctx->size);
  if ((NULL == ctx->children[idx]) && (NULL != ctx->s))
  {
    /* this was the end before, add empty string */
    newctx = new_regex_ctx (ctx->size);
    newctx->s = GNUNET_strdup ("");
    ctx->children[idx] = newctx;
  }
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " no match\n");
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " new state %s\n", regex);
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " under %s\n", ctx->s);
  newctx = new_regex_ctx (ctx->size);
  newctx->s = GNUNET_strdup (regex);
  ctx->children[idx] = newctx;
}

References c2i(), ctx, get_longest_prefix(), get_prefix_length(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_strdup, new_regex_ctx(), p, regex_add(), regex_add_multiple(), regex_split(), and RegexCombineCtx::s.

Referenced by regex_add(), and REGEX_TEST_combine().

Here is the call graph for this function:

Here is the caller graph for this function:

new_regex_ctx()

static struct RegexCombineCtx * new_regex_ctx ( unsigned int  alphabet_size )

static

Create and initialize a new RegexCombineCtx.

Parameters

alphabet_size

Size of the alphabet (and the Trie array)

Definition at line 160 of file regex_test_lib.c.

{
  struct RegexCombineCtx *ctx;
  size_t array_size;
 
  array_size = sizeof(struct RegexCombineCtx *) * alphabet_size;
  ctx = GNUNET_new (struct RegexCombineCtx);
  ctx->children = GNUNET_malloc (array_size);
  ctx->size = alphabet_size;
 
  return ctx;
}

References ctx, GNUNET_malloc, and GNUNET_new.

Referenced by regex_add(), regex_add_multiple(), regex_split(), and REGEX_TEST_combine().

Here is the caller graph for this function:

move_children()

static void move_children ( struct RegexCombineCtx *  dst, const struct RegexCombineCtx *  src  )

static

Definition at line 175 of file regex_test_lib.c.

{
  size_t array_size;
 
  array_size = sizeof(struct RegexCombineCtx *) * src->size;
  GNUNET_memcpy (dst->children,
                 src->children,
                 array_size);
  for (unsigned int i = 0; i < src->size; i++)
  {
    src->children[i] = NULL;
  }
}

References RegexCombineCtx::children, GNUNET_memcpy, and RegexCombineCtx::size.

Referenced by regex_split().

Here is the caller graph for this function:

regex_combine()

static char * regex_combine ( struct RegexCombineCtx *  ctx )

static

Extract a string from all prefix-combined regexes.

Parameters

ctx	Context with 0 or more regexes.

Returns

Regex that matches any of the added regexes.

Definition at line 199 of file regex_test_lib.c.

{
  struct RegexCombineCtx *p;
  unsigned int i;
  size_t len;
  char *regex;
  char *tmp;
  char *s;
  int opt;
 
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "new combine %s\n", ctx->s);
  regex = GNUNET_strdup ("");
  opt = GNUNET_NO;
  for (i = 0; i < ctx->size; i++)
  {
    p = ctx->children[i];
    if (NULL == p)
      continue;
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                "adding '%s' to innner %s\n",
                p->s, ctx->s);
    s = regex_combine (p);
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  total '%s'\n", s);
    if (strlen (s) == 0)
    {
      opt = GNUNET_YES;
    }
    else
    {
      GNUNET_asprintf (&tmp, "%s%s|", regex, s);
      GNUNET_free (regex);
      regex = tmp;
    }
    GNUNET_free (s);
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  so far '%s' for inner %s\n", regex,
                ctx->s);
  }
 
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "opt: %d, innner: '%s'\n", opt, regex);
  len = strlen (regex);
  if (0 == len)
  {
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "empty, returning ''\n");
    GNUNET_free (regex);
    return NULL == ctx->s ? NULL : GNUNET_strdup (ctx->s);
  }
 
  if ('|' == regex[len - 1])
    regex[len - 1] = '\0';
 
  if (NULL != ctx->s)
  {
    if (opt)
      GNUNET_asprintf (&s, "%s(%s)?", ctx->s, regex);
    else
      GNUNET_asprintf (&s, "%s(%s)", ctx->s, regex);
    GNUNET_free (regex);
    regex = s;
  }
 
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "partial: %s\n", regex);
  return regex;
}

References ctx, GNUNET_asprintf(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_log, GNUNET_NO, GNUNET_strdup, GNUNET_YES, p, regex_combine(), and RegexCombineCtx::s.

Referenced by regex_combine(), and REGEX_TEST_combine().

Here is the call graph for this function:

Here is the caller graph for this function:

get_prefix_length()

static unsigned int get_prefix_length ( const char *  s1, const char *  s2  )

static

Get the number of matching characters on the prefix of both strings.

Parameters

s1	String 1.
s2	String 2.

Returns

Number of characters of matching prefix.

Definition at line 273 of file regex_test_lib.c.

{
  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;
}

Referenced by get_longest_prefix(), and regex_add().

Here is the caller graph for this function:

get_longest_prefix()

static struct RegexCombineCtx * get_longest_prefix ( struct RegexCombineCtx *  ctx, const char *  regex  )

static

Return the child context with the longest prefix match with the regex.

Usually only one child will match, search all just in case.

Parameters

ctx	Context whose children to search.
regex	String to match.

Returns

Child with the longest prefix, NULL if no child matches.

Definition at line 303 of file regex_test_lib.c.

{
  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;
}

References ctx, get_prefix_length(), GNUNET_break, and p.

Referenced by regex_add().

Here is the call graph for this function:

Here is the caller graph for this function:

regex_add_multiple()

static void regex_add_multiple ( struct RegexCombineCtx *  ctx, const char *  regex, struct RegexCombineCtx **  children  )

static

Definition at line 333 of file regex_test_lib.c.

{
  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;
    }
  }
}

References c2i(), RegexCombineCtx::children, ctx, GNUNET_assert, GNUNET_memcpy, GNUNET_strdup, new_regex_ctx(), and RegexCombineCtx::s.

Referenced by regex_add(), and regex_split().

Here is the call graph for this function:

Here is the caller graph for this function:

regex_split()

static void regex_split ( struct RegexCombineCtx *  ctx, unsigned int  len, unsigned int  prefix_l  )

static

Add a single regex to a context, splitting the existing 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.

Parameters

ctx	Context to split.
len	Length of ctx->s
prefix_l	Length of common prefix of the new regex and ctx->s

Definition at line 395 of file regex_test_lib.c.

{
  struct RegexCombineCtx *newctx;
  unsigned int idx;
  char *suffix;
 
  suffix = GNUNET_malloc (len - prefix_l + 1);
  /*
   * We can use GNUNET_strlcpy because ctx->s is null-terminated
   */
  GNUNET_strlcpy (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;
}

References c2i(), ctx, GNUNET_free, GNUNET_malloc, GNUNET_strlcpy(), move_children(), new_regex_ctx(), regex_add_multiple(), and RegexCombineCtx::s.

Referenced by regex_add().

Here is the call graph for this function:

Here is the caller graph for this function:

regex_ctx_destroy()

static void regex_ctx_destroy ( struct RegexCombineCtx *  ctx )

static

Free all resources used by the context node and all its children.

Parameters

ctx	Context to free.

Definition at line 513 of file regex_test_lib.c.

{
  unsigned int i;
 
  if (NULL == ctx)
    return;
 
  for (i = 0; i < ctx->size; i++)
  {
    regex_ctx_destroy (ctx->children[i]);
  }
  GNUNET_free (ctx->s);  /* 's' on root node is null */
  GNUNET_free (ctx->children);
  GNUNET_free (ctx);
}

References ctx, GNUNET_free, and regex_ctx_destroy().

Referenced by regex_ctx_destroy(), and REGEX_TEST_combine().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_TEST_combine()

char * REGEX_TEST_combine	(	char *const	regexes[],
		unsigned int	alphabet_size
	)

Combine an array of regexes into a single prefix-shared regex.

Returns a prefix-combine regex that matches the same strings as any of the original regexes.

WARNING: only useful for reading specific regexes for specific applications, namely the gnunet-regex-profiler / gnunet-regex-daemon. This function DOES NOT support arbitrary regex combining.

Parameters

regexes	A NULL-terminated array of regexes.
alphabet_size	Size of the alphabet the regex uses.

Returns

A string with a single regex that matches any of the original regexes

Definition at line 545 of file regex_test_lib.c.

{
  unsigned int i;
  char *combined;
  const char *current;
  struct RegexCombineCtx *ctx;
 
  ctx = new_regex_ctx (alphabet_size);
  for (i = 0; regexes[i]; i++)
  {
    current = regexes[i];
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Regex %u: %s\n", i, current);
    regex_add (ctx, current);
    debugctx (ctx, 0);
  }
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\nCombining...\n");
  debugctx (ctx, 0);
 
  combined = regex_combine (ctx);
 
  regex_ctx_destroy (ctx);
 
  return combined;
}

References ctx, debugctx(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, new_regex_ctx(), regex_add(), regex_combine(), and regex_ctx_destroy().

Referenced by main(), and run().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_TEST_read_from_file()

char ** REGEX_TEST_read_from_file

(

const char *

filename

)

Read a set of regexes from a file, one per line and return them in an array suitable for REGEX_TEST_combine.

The array must be free'd using REGEX_TEST_free_from_file.

Parameters

filename

Name of the file containing the regexes.

Returns

A newly allocated, NULL terminated array of regexes.

Definition at line 581 of file regex_test_lib.c.

{
  struct GNUNET_DISK_FileHandle *f;
  unsigned int nr;
  unsigned int offset;
  off_t size;
  size_t len;
  char *buffer;
  char *regex;
  char **regexes;
 
  f = GNUNET_DISK_file_open (filename,
                             GNUNET_DISK_OPEN_READ,
                             GNUNET_DISK_PERM_NONE);
  if (NULL == f)
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                "Can't open file %s for reading\n", filename);
    return NULL;
  }
  if (GNUNET_OK != GNUNET_DISK_file_handle_size (f, &size))
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                "Can't get size of file %s\n", filename);
    GNUNET_DISK_file_close (f);
    return NULL;
  }
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "using file %s, size %llu\n",
              filename, (unsigned long long) size);
 
  buffer = GNUNET_malloc (size + 1);
  GNUNET_DISK_file_read (f, buffer, size);
  GNUNET_DISK_file_close (f);
  regexes = GNUNET_malloc (sizeof(char *));
  nr = 1;
  offset = 0;
  regex = NULL;
  do
  {
    if (NULL == regex)
      regex = GNUNET_malloc (size + 1);
    len = (size_t) sscanf (&buffer[offset], "%s", regex);
    if (0 == len)
      break;
    len = strlen (regex);
    offset += len + 1;
    if (len < 1)
      continue;
    regex[len] = '\0';
    regex = GNUNET_realloc (regex, len + 1);
    GNUNET_array_grow (regexes, nr, nr + 1);
    GNUNET_assert (NULL == regexes[nr - 2]);
    regexes[nr - 2] = regex;
    regexes[nr - 1] = NULL;
    regex = NULL;
  }
  while (offset < size);
  GNUNET_free (regex);
  GNUNET_free (buffer);
 
  return regexes;
}

References filename, GNUNET_array_grow, GNUNET_assert, GNUNET_DISK_file_close(), GNUNET_DISK_file_handle_size(), GNUNET_DISK_file_open(), GNUNET_DISK_file_read(), GNUNET_DISK_OPEN_READ, GNUNET_DISK_PERM_NONE, GNUNET_ERROR_TYPE_DEBUG, GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_log, GNUNET_malloc, GNUNET_OK, GNUNET_realloc, and size.

Referenced by main(), and run().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_TEST_free_from_file()

void REGEX_TEST_free_from_file

(

char **

regexes

)

Free all memory reserved for a set of regexes created by read_from_file.

Parameters

regexes

NULL-terminated array of regexes.

Definition at line 652 of file regex_test_lib.c.

{
  unsigned int i;
 
  for (i = 0; regexes[i]; i++)
    GNUNET_free (regexes[i]);
  GNUNET_free (regexes);
}

References GNUNET_free.

Referenced by main(), and run().

Here is the caller graph for this function: