text: /*
   * node.c: implementation of automata node
   * This file is part of multifast.
   *
   Copyright 2010-2012 Kamiar Kanani <kamiar.kanani@gmail.com>
  
   multifast is free software: you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.
  
   multifast 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 Lesser General Public License for more details.
  
   You should have received a copy of the GNU Lesser General Public License
   along with multifast.  If not, see <http://www.gnu.org/licenses/>.
  */
  
  #ifndef __KERNEL__
  #include <stdio.h>
  #include <string.h>
  #include <stdlib.h>
  #endif
  
  #include "node.h"
  #include "sort.h"
  
  /* reallocation step for AC_NODE_t.matched_patterns */
  #define REALLOC_CHUNK_MATCHSTR 8
  
  /* reallocation step for AC_NODE_t.outgoing array */
  #define REALLOC_CHUNK_OUTGOING 8
  /* TODO: For different depth of node, number of outgoing edges differs
     considerably, It is efficient to use different chunk size for 
     different depths */
  
  /* Private function prototype */
  void node_init         (AC_NODE_t * thiz);
  int  node_edge_compare (const void * l, const void * r);
  int  node_has_matchstr (AC_NODE_t * thiz, AC_PATTERN_t * newstr);
  
  
  /******************************************************************************
   * FUNCTION: node_create
   * Create the node
   ******************************************************************************/
  AC_NODE_t * node_create(void)
  {
    AC_NODE_t * thiz =  (AC_NODE_t *) malloc (sizeof(AC_NODE_t));
    node_init(thiz);
    node_assign_id(thiz);
    return thiz;
  }
  
  /******************************************************************************
   * FUNCTION: node_init
   * Initialize node
   ******************************************************************************/
  void node_init(AC_NODE_t * thiz)
  {
    memset(thiz, 0, sizeof(AC_NODE_t));
  
    thiz->outgoing_max = REALLOC_CHUNK_OUTGOING;
    thiz->outgoing = (struct edge *) malloc
      (thiz->outgoing_max*sizeof(struct edge));
  
    thiz->matched_patterns_max = REALLOC_CHUNK_MATCHSTR;
    thiz->matched_patterns = (AC_PATTERN_t *) malloc
      (thiz->matched_patterns_max*sizeof(AC_PATTERN_t));
  }
  
  /******************************************************************************
   * FUNCTION: node_release
   * Release node
   ******************************************************************************/
  void node_release(AC_NODE_t * thiz)
  {
    free(thiz->matched_patterns);
    free(thiz->outgoing);
    free(thiz);
  }
  
  /******************************************************************************
   * FUNCTION: node_find_next
   * Find out the next node for a given Alpha to move. this function is used in
   * the pre-processing stage in which edge array is not sorted. so it uses
   * linear search.
   ******************************************************************************/
  AC_NODE_t * node_find_next(AC_NODE_t * thiz, AC_ALPHABET_t alpha)
  {
    int i;
  
    for (i=0; i < thiz->outgoing_degree; i++)
      {
        if(thiz->outgoing[i].alpha == alpha)
  	return (thiz->outgoing[i].next);
      }
    return NULL;
  }
  
  /******************************************************************************
   * FUNCTION: node_findbs_next
   * Find out the next node for a given Alpha. this function is used after the
   * pre-processing stage in which we sort edges. so it uses Binary Search.
   ******************************************************************************/
  AC_NODE_t * node_findbs_next (AC_NODE_t * thiz, AC_ALPHABET_t alpha)
  {
    int min, max, mid;
    AC_ALPHABET_t amid;
  
    min = 0;
    max = thiz->outgoing_degree - 1;
  
    while (min <= max)
      {
        mid = (min+max) >> 1;
        amid = thiz->outgoing[mid].alpha;
        if (alpha > amid)
  	min = mid + 1;
        else if (alpha < amid)
  	max = mid - 1;
        else
  	return (thiz->outgoing[mid].next);
      }
    return NULL;
  }
  
  /******************************************************************************
   * FUNCTION: node_has_matchstr
   * Determine if a final node contains a pattern in its accepted pattern list
   * or not. return values: 1 = it has, 0 = it hasn't
   ******************************************************************************/
  int node_has_matchstr (AC_NODE_t * thiz, AC_PATTERN_t * newstr)
  {
    int i, j;
    AC_PATTERN_t * str;
  
    for (i=0; i < thiz->matched_patterns_num; i++)
      {
        str = &thiz->matched_patterns[i];
  
        if (str->length != newstr->length)
  	continue;
  
        for (j=0; j<(int)str->length; j++)
  	if(str->astring[j] != newstr->astring[j])
  	  continue;
  
        if (j == str->length)
  	return 1;
      }
    return 0;
  }
  
  /******************************************************************************
   * FUNCTION: node_create_next
   * Create the next node for the given alpha.
   ******************************************************************************/
  AC_NODE_t * node_create_next (AC_NODE_t * thiz, AC_ALPHABET_t alpha)
  {
    AC_NODE_t * next;
    next = node_find_next (thiz, alpha);
    if (next)
      /* The edge already exists */
      return NULL;
    /* Otherwise register new edge */
    next = node_create ();
    node_register_outgoing(thiz, next, alpha);
  
    return next;
  }
  
  /******************************************************************************
   * FUNCTION: node_register_matchstr
   * Adds the pattern to the list of accepted pattern.
   ******************************************************************************/
  void node_register_matchstr (AC_NODE_t * thiz, AC_PATTERN_t * str)
  {
    /* Check if the new pattern already exists in the node list */
    if (node_has_matchstr(thiz, str))
      return;
  
    /* Manage memory */
    if (thiz->matched_patterns_num >= thiz->matched_patterns_max)
      {
        thiz->matched_patterns = (AC_PATTERN_t *) realloc 
  	(thiz->matched_patterns, 
  	 (REALLOC_CHUNK_MATCHSTR+thiz->matched_patterns_max)*sizeof(AC_PATTERN_t));
  
        thiz->matched_patterns_max += REALLOC_CHUNK_MATCHSTR;
      }
  
    thiz->matched_patterns[thiz->matched_patterns_num].astring = str->astring;
    thiz->matched_patterns[thiz->matched_patterns_num].length = str->length;
    thiz->matched_patterns[thiz->matched_patterns_num].rep = str->rep;
    thiz->matched_patterns_num++;
  }
  
  /******************************************************************************
   * FUNCTION: node_register_outgoing
   * Establish an edge between two nodes
   ******************************************************************************/
  void node_register_outgoing
  (AC_NODE_t * thiz, AC_NODE_t * next, AC_ALPHABET_t alpha)
  {
    if(thiz->outgoing_degree >= thiz->outgoing_max)
      {
        thiz->outgoing = (struct edge *) realloc 
  	(thiz->outgoing,
  	 (REALLOC_CHUNK_OUTGOING+thiz->outgoing_max)*sizeof(struct edge));
        thiz->outgoing_max += REALLOC_CHUNK_OUTGOING;
      }
  
    thiz->outgoing[thiz->outgoing_degree].alpha = alpha;
    thiz->outgoing[thiz->outgoing_degree++].next = next;
  }
  
  /******************************************************************************
   * FUNCTION: node_assign_id
   * assign a unique ID to the node (used for debugging purpose).
   ******************************************************************************/
  void node_assign_id (AC_NODE_t * thiz)
  {
    static int unique_id = 1;
    thiz->id = unique_id ++;
  }
  
  /******************************************************************************
   * FUNCTION: node_edge_compare
   * Comparison function for qsort. see man qsort.
   ******************************************************************************/
  int node_edge_compare (const void * l, const void * r)
  {
    /* According to man page:
     * The comparison function must return an integer less than, equal to, or
     * greater than zero if the first argument is considered to be
     * respectively less than, equal to, or greater than the second. if  two
     * members compare as equal, their order in the sorted array is undefined.
     *
     * NOTE: Because edge alphabets are unique in every node we ignore
     * equivalence case.
     **/
    if ( ((struct edge *)l)->alpha >= ((struct edge *)r)->alpha )
      return 1;
    else
      return -1;
  }
  
  /******************************************************************************
   * FUNCTION: node_sort_edges
   * sorts edges alphabets.
   ******************************************************************************/
  void node_sort_edges (AC_NODE_t * thiz)
  {
    sort ((void *)thiz->outgoing, thiz->outgoing_degree, sizeof(struct edge), node_edge_compare, NULL);
  }
  