MultiSource/Benchmarks/Trimaran/netbench-url/search.c - third_party/llvm-test-suite - Git at Google

 /*
  * search.c - Searching routines for URL switching
  *
  * This file is a part of the NetBench
  *
  * This source file is distributed "as is" in the hope that it will be
  * useful. The suite comes with no warranty, and no author or
  * distributor accepts any responsibility for the consequences of its
  * use.
  *
  * Everyone is granted permission to copy, modify and redistribute
  * this tool set under the following conditions:
  *
  *    Permission is granted to anyone to make or distribute copies
  *    of this source code, either as received or modified, in any
  *    medium, provided that all copyright notices, permission and
  *    nonwarranty notices are preserved, and that the distributor
  *    grants the recipient permission for further redistribution as
  *    permitted by this document.
  *
  *    Permission is granted to distribute this file in compiled
  *    or executable form under the same conditions that apply for
  *    source code, provied that either:
  *
  *    A. it is accompanied by the corresponding machine-readable
  *       source code,
  *    B. it is accompanied by a written offer, with no time limit,
  *       to give anyone a machine-readable copy of the corresponding
  *       source code in return for reimbursement of the cost of
  *       distribution.  This written offer must permit verbatim
  *       duplication by anyone, or
  *    C. it is distributed by someone who received only the
  *       executable form, and is accompanied by a copy of the
  *       written offer of source code that they received concurrently.
  *
  * In other words, you are welcome to use and share this source file.
  * You are forbidden to forbid anyone else to use, share and improve
  * what you give them.
  */

 #include <stdlib.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include "utils.h"
 #include "search.h"
 #include "url.h"

 #define min(a, b) (a > b ? b : a)

 extern StrTreeNode *tree_head;

 int *
 calculate_bm_table (char *pattern, int pattern_length)
 {
   int i;
   int *returnval = (int *) malloc (sizeof(int) * CHAR_SIZE);

   if (returnval == NULL)
     fatal ("Not enough virtual memory \n");

   for (i = 0; i < CHAR_SIZE; ++i)
     returnval[i] = pattern_length;

   for (i = 0; i < pattern_length; ++i)
     returnval[(unsigned char)pattern[i]] = pattern_length - i - 1;

   return returnval;
 }


 /********************************************************************\
 * boyer_moore: Implements the Boyer-Moore al;gorithm to search the   *
 *              string x within string x. This is known to be one of  *
 *              the most efficient string search algorithms.          *
 *                                                                    *
 * Inputs:   Large and small pattern information                      *
 *           bmBc: the character table used for the algorithm,        *
 *           instead of generating it for every call, we generate the *
 *           table once in the creation and use it for every search.  *
 *                                                                    *
 * Returns:  The location of the match, -1 if no match                *
 \********************************************************************/
 int
 boyer_moore (char *y, int n, char *x, int m, int *bmBc)
 {
   int j, k, shift;

   shift = m - 1;
   j = 0;
   /* while (j < n) */
   /* Changed while-loop bound to prevent reading off the end of the array.
    * -KF 2/2007 */
   while (j + m - 1 < n)
     {
       k = bmBc[(unsigned char)y[j + m -1]];
       /* while ((k !=  0) && (j < n)) */
       /* Changed while-loop bound to prevent reading off the end of the array.
        * -KF 2/2007 */
       while ((k !=  0) && (j + k + m - 1 < n))
 	{
 	  j += k;
 	  k = bmBc[(unsigned char)y[j + m -1]];
 	}

       if (memcmp(x, y + j, m - 1) == 0 && (j < n))
 	return(j);
       j += shift;
     }
   return -1;
 }

 struct rtentry *
 find_destination (char *packet, int packet_size)
 {
   StrTreeNode *iterator = tree_head;

   while (iterator)
     {
 #ifdef DEBUG_2
       fprintf (stderr, "Comparing to %s \n", iterator->common_pattern);
 #endif

       /* If the packet contains the pattern at the header... */
       if ((boyer_moore (packet, packet_size, iterator->common_pattern, iterator->common_pattern_length, iterator->bm_table) != -1))
 	{
 	  /* We found a common substring in the header, so look into the list... */
 	  PatternNode *list = iterator->list;
 	  while (list)
 	    {
 	      int search_result;
 #ifdef DEBUG_2
 	      fprintf (stderr, "Inside comparing to %s \n", iterator->common_pattern);
 #endif
 	      if (list->search_depth == 0)
 		search_result = boyer_moore (packet, packet_size, list->pattern, list->pattern_length, list->bm_table);
 	      else
 		search_result = boyer_moore (packet, min(packet_size, list->search_depth), list->pattern, list->pattern_length, list->bm_table);

 	      if (search_result != -1)
 		{
 #ifdef DEBUG
 		  fprintf (stderr, "Found a packet \n");
 #endif
 		  /* An exact match */
 		  if (list->type == log)
 		    fprintf (list->logto, "Source: %x Destination %x \n", PACKET_SOURCE(packet), PACKET_DESTINATION(packet));
 		  return list->destination;
 		}
 	      list = list->below;
 	    }
 	}
       iterator = iterator->next;
     }

   /* No match, no rule can be find for the packet... */
   return NULL;
 }


 /********************************************************************\
 * Procedures to generate empty nodes.                                *
 \********************************************************************/
 PatternNode *
 NewPatternNode (int chainno, nodetype type, char *pattern, int pattern_length, int search_depth)
 {
   PatternNode *returnval;

   if ((returnval = (PatternNode *) malloc (sizeof (PatternNode))) == NULL)
     fatal ("Run out of virtual memory \n");

   returnval->chain_node_number = chainno;
   returnval->type = type;
   if ((returnval->pattern = (char *) malloc (pattern_length)) == NULL)
     fatal ("Not enough virtual memory \n");
   strncpy (returnval->pattern, pattern, pattern_length);
   returnval->pattern_length = pattern_length;
   returnval->search_depth = search_depth;
   returnval->bm_table = calculate_bm_table (pattern, pattern_length);

   return returnval;
 }

 StrTreeNode *
 NewStrTreeNode (int chainno, char *pattern, int pattern_length)
 {
   StrTreeNode *returnval;

   if ((returnval = (StrTreeNode *) malloc (sizeof (StrTreeNode))) == NULL)
     fatal ("Run out of virtual memory \n");

   returnval->chain_node_number = chainno;
   if ((returnval->common_pattern = (char *) malloc (pattern_length)) == NULL)
     fatal ("Not enough virtual memory \n");
   strncpy (returnval->common_pattern, pattern, pattern_length);
   returnval->common_pattern_length = pattern_length;
   returnval->bm_table = calculate_bm_table (returnval->common_pattern, pattern_length);

   return returnval;
 }


 /********************************************************************\
 * Find_lcs: A modified version of the boyer-moore algorithm to find  *
 *           the largest common substring                             *
 *                                                                    *
 * Inputs:   Large and small pattern information                      *
 *           lcssize: return value of the procedure                   *
 *                                                                    *
 * Returns:  The largest substring found                              *
 \********************************************************************/
 char *
 find_lcs (char *largepattern, int largepatternsize, char *smallpattern, int smallpatternsize, int *lcssize)
 {
   char *sub_pattern = NULL;
   char *exchanger;
   int sub_pat_size = 0;
   int j, k, shift, exchangersize;
   int *bmBc;

   /* Make sure the large is larger */
   if (smallpatternsize > largepatternsize)
     {
       exchanger = smallpattern;
       smallpattern = largepattern;
       largepattern = exchanger;
       exchangersize = smallpatternsize;
       smallpatternsize = largepatternsize;
       largepatternsize = exchangersize;
     }

   bmBc = calculate_bm_table (smallpattern, smallpatternsize);

   shift = 1;
   j = 0;
   k = bmBc[(unsigned char)largepattern[j + smallpatternsize -1]];
   while (j < largepatternsize)
     {
       j += k;
       k = bmBc[(unsigned char)largepattern[j + smallpatternsize -1]];
       /* Unlike original BM we can not shift the whole subpattern */
       if (k == smallpatternsize)
 	k = sub_pat_size + 1;
       else
 	{
 	  /* Match in the characters, check how big the substring is */
 	  int first_char = j + smallpatternsize - 1;
 	  int temp_sub_size = 0;

 	  /* First move back to find the start of the partial match */
 	  while ((k < smallpatternsize) && (smallpattern[smallpatternsize - k - 1] == largepattern[first_char]))
 	    {
 	      first_char--;
 	      k++;
 	    }
 	  k--;
 	  first_char++;

 	  /* Now move forward until there is a mismatch */
 	  while ((k >= 0) && (smallpattern[smallpatternsize - k - 1] == largepattern[first_char]))
 	    {
 	      temp_sub_size++;
 	      k--;
 	      first_char++;
 	    }

 	  if (temp_sub_size > sub_pat_size)
 	    {
 	      sub_pat_size = temp_sub_size;
 	      sub_pattern = &largepattern[first_char - temp_sub_size];

 	      /* If it is equal to the small pattern, no need to continue */
 	      if (sub_pat_size == smallpatternsize)
 		{
 		  *lcssize = sub_pat_size;
 		  return sub_pattern;
 		}
 	    }

 	  k = 1;
 	}
     }
   *lcssize = sub_pat_size;
   free(bmBc);
   return sub_pattern;
 }

 void
 insert_rule (char *pattern, int pattern_length, int depth)
 {
   StrTreeNode *head_iterator = tree_head;
   StrTreeNode *found_largestcommon = NULL;
   unsigned int largest_common = 0;
   char *sub_str;

   /* First traverse all the headers finding the longest common substring */
   while (head_iterator)
     {
       int temp_common;
       char *temp_str = find_lcs (head_iterator->common_pattern, head_iterator->common_pattern_length, pattern, pattern_length, &temp_common);

 #ifdef DEBUG_2
       fprintf (stdout, "Compared %s to %s and found %s with size %d \n", head_iterator->common_pattern, pattern, temp_str, temp_common);
 #endif

       if (temp_common > largest_common)
 	{
 	  largest_common = temp_common;
 	  found_largestcommon = head_iterator;
 	  sub_str = temp_str;
 	}
       head_iterator = head_iterator->next;
     }

   if (largest_common < MIN_COMMON_SIZE)
     {
       /* We have to create a new head */
       PatternNode *new_node;
       StrTreeNode *new_head;

       if (tree_head != NULL)
 	new_head = NewStrTreeNode (tree_head->chain_node_number + 1, pattern, pattern_length);
       else
 	new_head = NewStrTreeNode (0, pattern, pattern_length);

       new_node = NewPatternNode (0, route, pattern, pattern_length, depth);
       new_node->below = NULL;

       new_head->list = new_node;
       new_head->next = tree_head;
       tree_head = new_head;
     }
   else
     {
       /* Found a header matching the common value that is large enough */
       PatternNode *new_node;

       /* First change the head pattern (chunk it off) */
       strncpy (found_largestcommon->common_pattern, sub_str, largest_common);
       found_largestcommon->common_pattern_length = largest_common;

       /* Add the entry to the head list */
       new_node = NewPatternNode (found_largestcommon->list->chain_node_number + 1, route, pattern, pattern_length, depth);
       new_node->below = found_largestcommon->list;
       found_largestcommon->list = new_node;
     }
 }

 void
 db_init (char *file_name)
 {
   FILE *pattern_file;
   char line[BUF_SIZE];
   char *reader;
   int i;
   char *pattern;


   if ((pattern_file = fopen (file_name, "r")) == NULL)
     fatal ("Can not open the input file\n");

   /* Initialize the tree structure */
   while (fgets (line, BUF_SIZE, pattern_file) != NULL)
     {
       int value;
       int pattern_length, search_depth;

       reader = line + 1;
       switch (line[0])
 	{
 	case '1':
 	  sscanf (reader, "(%d)", &pattern_length);
 	  search_depth = 0;
 	  break;
 	case '2':
 	  sscanf (reader, "(%d:%d)", &pattern_length, &search_depth);
 	  break;
 	default:
 	  fatal ("unrecognized input line start: %c \n", line[0]);
 	}

       if ((pattern = (char *) malloc (pattern_length + 1)) == NULL)
 	fatal ("Not enough virtual memory \n");

       for (i = 0; i < pattern_length; i++)
 	{
 	  while (*reader != ',')
 	    reader++;
 	  reader++;
 	  sscanf (reader, " %d", &value);
 	  pattern[i] = (char)value;
 #ifdef DEBUG_2
 	  fprintf (stdout, "Read value: %d \n", value);
 #endif
 	}

       pattern[pattern_length] = '\0';

 #ifdef DEBUG_2
       fprintf (stdout, "Pattern: %s, length: %d depth: %d, tree before: %x\n", pattern, pattern_length, search_depth, tree_head);
 #endif

       insert_rule (pattern, pattern_length, search_depth);

 #ifdef DEBUG_2
       fprintf (stdout, "Tree after: %x\n", tree_head);
 #endif
     }
 }
	/*
	* search.c - Searching routines for URL switching
	*
	* This file is a part of the NetBench
	*
	* This source file is distributed "as is" in the hope that it will be
	* useful. The suite comes with no warranty, and no author or
	* distributor accepts any responsibility for the consequences of its
	* use.
	*
	* Everyone is granted permission to copy, modify and redistribute
	* this tool set under the following conditions:
	*
	* Permission is granted to anyone to make or distribute copies
	* of this source code, either as received or modified, in any
	* medium, provided that all copyright notices, permission and
	* nonwarranty notices are preserved, and that the distributor
	* grants the recipient permission for further redistribution as
	* permitted by this document.
	*
	* Permission is granted to distribute this file in compiled
	* or executable form under the same conditions that apply for
	* source code, provied that either:
	*
	* A. it is accompanied by the corresponding machine-readable
	* source code,
	* B. it is accompanied by a written offer, with no time limit,
	* to give anyone a machine-readable copy of the corresponding
	* source code in return for reimbursement of the cost of
	* distribution. This written offer must permit verbatim
	* duplication by anyone, or
	* C. it is distributed by someone who received only the
	* executable form, and is accompanied by a copy of the
	* written offer of source code that they received concurrently.
	*
	* In other words, you are welcome to use and share this source file.
	* You are forbidden to forbid anyone else to use, share and improve
	* what you give them.
	*/

	#include <stdlib.h>
	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	#include "utils.h"
	#include "search.h"
	#include "url.h"

	#define min(a, b) (a > b ? b : a)

	extern StrTreeNode *tree_head;

	int *
	calculate_bm_table (char *pattern, int pattern_length)
	{
	int i;
	int returnval = (int ) malloc (sizeof(int) * CHAR_SIZE);

	if (returnval == NULL)
	fatal ("Not enough virtual memory \n");

	for (i = 0; i < CHAR_SIZE; ++i)
	returnval[i] = pattern_length;

	for (i = 0; i < pattern_length; ++i)
	returnval[(unsigned char)pattern[i]] = pattern_length - i - 1;

	return returnval;
	}


	/********************************************************************\
	* boyer_moore: Implements the Boyer-Moore al;gorithm to search the *
	* string x within string x. This is known to be one of *
	* the most efficient string search algorithms. *
	* *
	* Inputs: Large and small pattern information *
	* bmBc: the character table used for the algorithm, *
	* instead of generating it for every call, we generate the *
	* table once in the creation and use it for every search. *
	* *
	* Returns: The location of the match, -1 if no match *
	\********************************************************************/
	int
	boyer_moore (char y, int n, char x, int m, int *bmBc)
	{
	int j, k, shift;

	shift = m - 1;
	j = 0;
	/* while (j < n) */
	/* Changed while-loop bound to prevent reading off the end of the array.
	* -KF 2/2007 */
	while (j + m - 1 < n)
	{
	k = bmBc[(unsigned char)y[j + m -1]];
	/* while ((k != 0) && (j < n)) */
	/* Changed while-loop bound to prevent reading off the end of the array.
	* -KF 2/2007 */
	while ((k != 0) && (j + k + m - 1 < n))
	{
	j += k;
	k = bmBc[(unsigned char)y[j + m -1]];
	}

	if (memcmp(x, y + j, m - 1) == 0 && (j < n))
	return(j);
	j += shift;
	}
	return -1;
	}

	struct rtentry *
	find_destination (char *packet, int packet_size)
	{
	StrTreeNode *iterator = tree_head;

	while (iterator)
	{
	#ifdef DEBUG_2
	fprintf (stderr, "Comparing to %s \n", iterator->common_pattern);
	#endif

	/* If the packet contains the pattern at the header... */
	if ((boyer_moore (packet, packet_size, iterator->common_pattern, iterator->common_pattern_length, iterator->bm_table) != -1))
	{
	/* We found a common substring in the header, so look into the list... */
	PatternNode *list = iterator->list;
	while (list)
	{
	int search_result;
	#ifdef DEBUG_2
	fprintf (stderr, "Inside comparing to %s \n", iterator->common_pattern);
	#endif
	if (list->search_depth == 0)
	search_result = boyer_moore (packet, packet_size, list->pattern, list->pattern_length, list->bm_table);
	else
	search_result = boyer_moore (packet, min(packet_size, list->search_depth), list->pattern, list->pattern_length, list->bm_table);

	if (search_result != -1)
	{
	#ifdef DEBUG
	fprintf (stderr, "Found a packet \n");
	#endif
	/* An exact match */
	if (list->type == log)
	fprintf (list->logto, "Source: %x Destination %x \n", PACKET_SOURCE(packet), PACKET_DESTINATION(packet));
	return list->destination;
	}
	list = list->below;
	}
	}
	iterator = iterator->next;
	}

	/* No match, no rule can be find for the packet... */
	return NULL;
	}


	/********************************************************************\
	* Procedures to generate empty nodes. *
	\********************************************************************/
	PatternNode *
	NewPatternNode (int chainno, nodetype type, char *pattern, int pattern_length, int search_depth)
	{
	PatternNode *returnval;

	if ((returnval = (PatternNode *) malloc (sizeof (PatternNode))) == NULL)
	fatal ("Run out of virtual memory \n");

	returnval->chain_node_number = chainno;
	returnval->type = type;
	if ((returnval->pattern = (char *) malloc (pattern_length)) == NULL)
	fatal ("Not enough virtual memory \n");
	strncpy (returnval->pattern, pattern, pattern_length);
	returnval->pattern_length = pattern_length;
	returnval->search_depth = search_depth;
	returnval->bm_table = calculate_bm_table (pattern, pattern_length);

	return returnval;
	}

	StrTreeNode *
	NewStrTreeNode (int chainno, char *pattern, int pattern_length)
	{
	StrTreeNode *returnval;

	if ((returnval = (StrTreeNode *) malloc (sizeof (StrTreeNode))) == NULL)
	fatal ("Run out of virtual memory \n");

	returnval->chain_node_number = chainno;
	if ((returnval->common_pattern = (char *) malloc (pattern_length)) == NULL)
	fatal ("Not enough virtual memory \n");
	strncpy (returnval->common_pattern, pattern, pattern_length);
	returnval->common_pattern_length = pattern_length;
	returnval->bm_table = calculate_bm_table (returnval->common_pattern, pattern_length);

	return returnval;
	}


	/********************************************************************\
	* Find_lcs: A modified version of the boyer-moore algorithm to find *
	* the largest common substring *
	* *
	* Inputs: Large and small pattern information *
	* lcssize: return value of the procedure *
	* *
	* Returns: The largest substring found *
	\********************************************************************/
	char *
	find_lcs (char largepattern, int largepatternsize, char smallpattern, int smallpatternsize, int *lcssize)
	{
	char *sub_pattern = NULL;
	char *exchanger;
	int sub_pat_size = 0;
	int j, k, shift, exchangersize;
	int *bmBc;

	/* Make sure the large is larger */
	if (smallpatternsize > largepatternsize)
	{
	exchanger = smallpattern;
	smallpattern = largepattern;
	largepattern = exchanger;
	exchangersize = smallpatternsize;
	smallpatternsize = largepatternsize;
	largepatternsize = exchangersize;
	}

	bmBc = calculate_bm_table (smallpattern, smallpatternsize);

	shift = 1;
	j = 0;
	k = bmBc[(unsigned char)largepattern[j + smallpatternsize -1]];
	while (j < largepatternsize)
	{
	j += k;
	k = bmBc[(unsigned char)largepattern[j + smallpatternsize -1]];
	/* Unlike original BM we can not shift the whole subpattern */
	if (k == smallpatternsize)
	k = sub_pat_size + 1;
	else
	{
	/* Match in the characters, check how big the substring is */
	int first_char = j + smallpatternsize - 1;
	int temp_sub_size = 0;

	/* First move back to find the start of the partial match */
	while ((k < smallpatternsize) && (smallpattern[smallpatternsize - k - 1] == largepattern[first_char]))
	{
	first_char--;
	k++;
	}
	k--;
	first_char++;

	/* Now move forward until there is a mismatch */
	while ((k >= 0) && (smallpattern[smallpatternsize - k - 1] == largepattern[first_char]))
	{
	temp_sub_size++;
	k--;
	first_char++;
	}

	if (temp_sub_size > sub_pat_size)
	{
	sub_pat_size = temp_sub_size;
	sub_pattern = &largepattern[first_char - temp_sub_size];

	/* If it is equal to the small pattern, no need to continue */
	if (sub_pat_size == smallpatternsize)
	{
	*lcssize = sub_pat_size;
	return sub_pattern;
	}
	}

	k = 1;
	}
	}
	*lcssize = sub_pat_size;
	free(bmBc);
	return sub_pattern;
	}

	void
	insert_rule (char *pattern, int pattern_length, int depth)
	{
	StrTreeNode *head_iterator = tree_head;
	StrTreeNode *found_largestcommon = NULL;
	unsigned int largest_common = 0;
	char *sub_str;

	/* First traverse all the headers finding the longest common substring */
	while (head_iterator)
	{
	int temp_common;
	char *temp_str = find_lcs (head_iterator->common_pattern, head_iterator->common_pattern_length, pattern, pattern_length, &temp_common);

	#ifdef DEBUG_2
	fprintf (stdout, "Compared %s to %s and found %s with size %d \n", head_iterator->common_pattern, pattern, temp_str, temp_common);
	#endif

	if (temp_common > largest_common)
	{
	largest_common = temp_common;
	found_largestcommon = head_iterator;
	sub_str = temp_str;
	}
	head_iterator = head_iterator->next;
	}

	if (largest_common < MIN_COMMON_SIZE)
	{
	/* We have to create a new head */
	PatternNode *new_node;
	StrTreeNode *new_head;

	if (tree_head != NULL)
	new_head = NewStrTreeNode (tree_head->chain_node_number + 1, pattern, pattern_length);
	else
	new_head = NewStrTreeNode (0, pattern, pattern_length);

	new_node = NewPatternNode (0, route, pattern, pattern_length, depth);
	new_node->below = NULL;

	new_head->list = new_node;
	new_head->next = tree_head;
	tree_head = new_head;
	}
	else
	{
	/* Found a header matching the common value that is large enough */
	PatternNode *new_node;

	/* First change the head pattern (chunk it off) */
	strncpy (found_largestcommon->common_pattern, sub_str, largest_common);
	found_largestcommon->common_pattern_length = largest_common;

	/* Add the entry to the head list */
	new_node = NewPatternNode (found_largestcommon->list->chain_node_number + 1, route, pattern, pattern_length, depth);
	new_node->below = found_largestcommon->list;
	found_largestcommon->list = new_node;
	}
	}

	void
	db_init (char *file_name)
	{
	FILE *pattern_file;
	char line[BUF_SIZE];
	char *reader;
	int i;
	char *pattern;


	if ((pattern_file = fopen (file_name, "r")) == NULL)
	fatal ("Can not open the input file\n");

	/* Initialize the tree structure */
	while (fgets (line, BUF_SIZE, pattern_file) != NULL)
	{
	int value;
	int pattern_length, search_depth;

	reader = line + 1;
	switch (line[0])
	{
	case '1':
	sscanf (reader, "(%d)", &pattern_length);
	search_depth = 0;
	break;
	case '2':
	sscanf (reader, "(%d:%d)", &pattern_length, &search_depth);
	break;
	default:
	fatal ("unrecognized input line start: %c \n", line[0]);
	}

	if ((pattern = (char *) malloc (pattern_length + 1)) == NULL)
	fatal ("Not enough virtual memory \n");

	for (i = 0; i < pattern_length; i++)
	{
	while (*reader != ',')
	reader++;
	reader++;
	sscanf (reader, " %d", &value);
	pattern[i] = (char)value;
	#ifdef DEBUG_2
	fprintf (stdout, "Read value: %d \n", value);
	#endif
	}

	pattern[pattern_length] = '\0';

	#ifdef DEBUG_2
	fprintf (stdout, "Pattern: %s, length: %d depth: %d, tree before: %x\n", pattern, pattern_length, search_depth, tree_head);
	#endif

	insert_rule (pattern, pattern_length, search_depth);

	#ifdef DEBUG_2
	fprintf (stdout, "Tree after: %x\n", tree_head);
	#endif
	}
	}