src/regex/regex_test_lib.c

   1 /*
   2  *  This file is part of GNUnet
   3  *  (C) 2012 Christian Grothoff (and other contributing authors)
   4  *
   5  *  GNUnet is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published
   7  *  by the Free Software Foundation; either version 3, or (at your
   8  *  option) any later version.
   9  *
  10  *  GNUnet is distributed in the hope that it will be useful, but
  11  *  WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with GNUnet; see the file COPYING.  If not, write to the
  17  *  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  *  Boston, MA 02111-1307, USA.
  19  */
  20 /**
  21  * @file src/regex/regex_test_lib.c
  22  * @brief library to read regexes representing IP networks from a file.
  23  *        and simplyfinying the into one big regex, in order to run
  24  *        tests (regex performance, mesh profiler).
  25  * @author Bartlomiej Polot
  26  */
  27
  28 #include "platform.h"
  29 #include "gnunet_util_lib.h"
  30
  31
  32 /**
  33  * Struct to hold the tree formed by prefix-combining the regexes.
  34  */
  35 struct RegexCombineCtx {
  36
  37   /**
  38    * Next node with same prefix but different token.
  39    */
  40   struct RegexCombineCtx *next;
  41
  42   /**
  43    * Prev node with same prefix but different token.
  44    */
  45   struct RegexCombineCtx *prev;
  46
  47   /**
  48    * First child node with same prefix and token.
  49    */
  50   struct RegexCombineCtx *head;
  51
  52   /**
  53    * Last child node.
  54    */
  55   struct RegexCombineCtx *tail;
  56
  57   /**
  58    * Token.
  59    */
  60   char *s;
  61 };
  62
  63
  64 /**
  65  * Extract a string from all prefix-combined regexes.
  66  *
  67  * @param ctx Context with 0 or more regexes.
  68  *
  69  * @return Regex that matches any of the added regexes.
  70  */
  71 static char *
  72 regex_combine (struct RegexCombineCtx *ctx)
  73 {
  74   struct RegexCombineCtx *p;
  75   size_t len;
  76   char *regex;
  77   char *tmp;
  78   char *s;
  79
  80   if (NULL != ctx->s)
  81     GNUNET_asprintf (&regex, "%s(", ctx->s);
  82   else
  83     regex = GNUNET_strdup ("(");
  84   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "prefix: %s\n", regex);
  85
  86   for (p = ctx->head; NULL != p; p = p->next)
  87   {
  88     s = regex_combine (p);
  89     GNUNET_asprintf (&tmp, "%s%s|", regex, s);
  90     GNUNET_free_non_null (s);
  91     GNUNET_free_non_null (regex);
  92     regex = tmp;
  93   }
  94   len = strlen (regex);
  95   if (1 == len)
  96   {
  97     GNUNET_free (regex);
  98     return GNUNET_strdup ("");
  99   }
 100
 101   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "pre-partial: %s\n", regex);
 102   if ('|' == regex[len - 1])
 103     regex[len - 1] = ')';
 104   if ('(' == regex[len - 1])
 105     regex[len - 1] = '\0';
 106
 107   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "partial: %s\n", regex);
 108   return regex;
 109 }
 110
 111
 112 /**
 113  * Add a single regex to a context, combining with exisiting regex by-prefix.
 114  *
 115  * @param ctx Context with 0 or more regexes.
 116  * @param regex Regex to add.
 117  */
 118 static void
 119 regex_add (struct RegexCombineCtx *ctx, const char *regex)
 120 {
 121   struct RegexCombineCtx *p;
 122   const char *rest;
 123
 124   rest = &regex[1];
 125   for (p = ctx->head; NULL != p; p = p->next)
 126   {
 127     if (p->s[0] == regex[0])
 128     {
 129       if (1 == strlen(p->s))
 130       {
 131         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "common char %s\n", p->s);
 132         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "adding %s\n", rest);
 133         regex_add (p, rest);
 134       }
 135       else
 136       {
 137         struct RegexCombineCtx *new;
 138         new = GNUNET_malloc (sizeof (struct RegexCombineCtx));
 139         new->s = GNUNET_strdup (&p->s[1]);
 140         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " p has now %s\n", p->s);
 141         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " p will have %.1s\n", p->s);
 142         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " regex is %s\n", regex);
 143         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " new has now %s\n", new->s);
 144         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " rest is now %s\n", rest);
 145         p->s[1] = '\0'; /* dont realloc */
 146         GNUNET_CONTAINER_DLL_insert (p->head, p->tail, new);
 147         regex_add (p, rest);
 148       }
 149       return;
 150     }
 151   }
 152   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " no  match\n");
 153   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " new state %s\n", regex);
 154   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " under %s\n", ctx->s);
 155   p = GNUNET_malloc (sizeof (struct RegexCombineCtx));
 156   p->s = GNUNET_strdup (regex);
 157   GNUNET_CONTAINER_DLL_insert (ctx->head, ctx->tail, p);
 158 }
 159
 160
 161 /**
 162  * Free all resources used by the context node and all its children.
 163  *
 164  * @param ctx Context to free.
 165  */
 166 static void
 167 regex_ctx_destroy (struct RegexCombineCtx *ctx)
 168 {
 169   struct RegexCombineCtx *p;
 170   struct RegexCombineCtx *next;
 171
 172   for (p = ctx->head; NULL != p; p = next)
 173   {
 174     next = p->next;
 175     regex_ctx_destroy (p);
 176   }
 177   GNUNET_free_non_null (ctx->s); /* 's' on root node is null */
 178   GNUNET_free (ctx);
 179 }
 180
 181
 182 /**
 183  * Return a prefix-combine regex that matches the same strings as
 184  * any of the original regexes.
 185  *
 186  * WARNING: only useful for reading specific regexes for specific applications,
 187  *          namely the gnunet-regex-profiler / gnunet-regex-daemon.
 188  *          This function DOES NOT support arbitrary regex combining.
 189  */
 190 char *
 191 GNUNET_REGEX_combine (char * const regexes[])
 192 {
 193   unsigned int i;
 194   char *combined;
 195   const char *current;
 196   struct RegexCombineCtx *ctx;
 197
 198   ctx = GNUNET_malloc (sizeof (struct RegexCombineCtx));
 199   for (i = 0; regexes[i]; i++)
 200   {
 201     current = regexes[i];
 202     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Regex %u: %s\n", i, current);
 203     regex_add (ctx, current);
 204   }
 205   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\nCombining...\n");
 206
 207   combined = regex_combine (ctx);
 208
 209   regex_ctx_destroy (ctx);
 210
 211   return combined;
 212 }
 213
 214
 215 /**
 216  * Read a set of regexes from a file, one per line and return them in an array
 217  * suitable for GNUNET_REGEX_combine.
 218  * The array must be free'd using GNUNET_REGEX_free_from_file.
 219  *
 220  * @param filename Name of the file containing the regexes.
 221  *
 222  * @return A newly allocated, NULL terminated array of regexes.
 223  */
 224 char **
 225 GNUNET_REGEX_read_from_file (const char *filename)
 226 {
 227   struct GNUNET_DISK_FileHandle *f;
 228   unsigned int nr;
 229   unsigned int offset;
 230   off_t size;
 231   size_t len;
 232   char *buffer;
 233   char *regex;
 234   char **regexes;
 235
 236   f = GNUNET_DISK_file_open (filename,
 237                              GNUNET_DISK_OPEN_READ,
 238                              GNUNET_DISK_PERM_NONE);
 239   if (NULL == f)
 240   {
 241     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 242                 "Can't open file %s for reading\n", filename);
 243     return NULL;
 244   }
 245   if (GNUNET_OK != GNUNET_DISK_file_handle_size (f, &size))
 246   {
 247     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 248                 "Can't get size of file %s\n", filename);
 249     GNUNET_DISK_file_close (f);
 250     return NULL;
 251   }
 252   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 253               "using file %s, size %llu\n",
 254               filename, (unsigned long long) size);
 255
 256   buffer = GNUNET_malloc (size + 1);
 257   GNUNET_DISK_file_read (f, buffer, size);
 258   GNUNET_DISK_file_close (f);
 259   regexes = GNUNET_malloc (sizeof (char *));
 260   nr = 1;
 261   offset = 0;
 262   regex = NULL;
 263   do
 264   {
 265     if (NULL == regex)
 266       regex = GNUNET_malloc (size + 1);
 267     len = (size_t) sscanf (&buffer[offset], "%s", regex);
 268     if (0 == len)
 269       break;
 270     len = strlen (regex);
 271     offset += len + 1;
 272     if (len < 1)
 273       continue;
 274     if (len < 6 || strncmp (&regex[len - 6], "(0|1)*", 6) != 0)
 275     {
 276       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 277                   "%s (line %u) does not end in \"(0|1)*\"\n",
 278                   buffer, nr);
 279     }
 280     else
 281     {
 282       len -= 6;
 283       regex[len] = '\0';
 284     }
 285     regex = GNUNET_realloc (regex, len + 1);
 286     GNUNET_array_grow (regexes, nr, nr + 1);
 287     GNUNET_assert (NULL == regexes[nr - 2]);
 288     regexes[nr - 2] = regex;
 289     regexes[nr - 1] = NULL;
 290     regex = NULL;
 291   } while (offset < size);
 292   GNUNET_free_non_null (regex);
 293   GNUNET_free (buffer);
 294
 295   return regexes;
 296 }
 297
 298
 299 /**
 300  * Free all memory reserved for a set of regexes created by read_from_file.
 301  *
 302  * @param regexes NULL-terminated array of regexes.
 303  */
 304 void
 305 GNUNET_REGEX_free_from_file (char **regexes)
 306 {
 307   unsigned int i;
 308
 309   for (i = 0; regexes[i]; i++)
 310     GNUNET_free (regexes[i]);
 311   GNUNET_free (regexes);
 312 }
 313
 314 /* end of regex_test_lib.c */