path: root/src/regex/regex.c

/*
     This file is part of GNUnet
     (C) 2012 Christian Grothoff (and other contributing authors)

     GNUnet is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published
     by the Free Software Foundation; either version 3, or (at your
     option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with GNUnet; see the file COPYING.  If not, write to the
     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
     Boston, MA 02111-1307, USA.
*/
/**
 * @file src/regex/regex.c
 * @brief library to create automatons from regular expressions
 * @author Maximilian Szengel
 */
#include "platform.h"
#include "gnunet_container_lib.h"
#include "gnunet_regex_lib.h"
#include "regex.h"

/**
 * Context that contains an id counter for states and transitions
 * as well as a DLL of automatons used as a stack for NFA construction.
 */
struct GNUNET_REGEX_Context
{
  unsigned int state_id;
  unsigned int transition_id;

  /**
   * DLL of GNUNET_REGEX_Automaton's used as a stack
   */
  struct GNUNET_REGEX_Automaton *stack_head;
  struct GNUNET_REGEX_Automaton *stack_tail;
};

enum GNUNET_REGEX_automaton_type
{
  NFA,
  DFA
};

/**
 * Automaton representation
 */
struct GNUNET_REGEX_Automaton
{
  struct GNUNET_REGEX_Automaton *prev;
  struct GNUNET_REGEX_Automaton *next;

  struct State *start;
  struct State *end;

  unsigned int state_count;
  struct State *states_head;
  struct State *states_tail;

  enum GNUNET_REGEX_automaton_type type;
};

/**
 * A state. Can be used in DFA and NFA automatons.
 */
struct State
{
  struct State *prev;
  struct State *next;

  unsigned int id;
  int accepting;
  int marked;
  char *name;

  unsigned int transition_count;
  struct Transition *transitions_head;
  struct Transition *transitions_tail;

  struct StateSet *nfa_set;
};

/**
 * Transition between two states. Each state can have 0-n transitions.
 * If literal is 0, this is considered to be an epsilon transition.
 */
struct Transition
{
  struct Transition *prev;
  struct Transition *next;

  unsigned int id;
  char literal;
  struct State *state;
};

/**
 * Set of states
 */
struct StateSet
{
  /**
   * Array of states
   */
  struct State **states;
  unsigned int len;
};

/**
 * Initialize a new context
 *
 * @param ctx context
 */
static void
G