hi_util_kmap.c

来自「snort-2.1.0入侵检测」· C语言 代码 · 共 539 行

/*
*
*  kmap.c  -  a generic map library - maps key + data pairs
*  
*  Uses Lexical Keyword Trie 
*    The tree uses linked lists to build the finite automata
*
*  MapKeyFind(): Performs a setwise strcmp() equivalant.
*
*  Notes:
*
*  Keys may be ascii or binary, both may be of random sizes.
*  Each key may be a different size, or all one size.
*  Fast dictionary lookup, proportional to the length of the key,
*  and independent of the number of keys in the table.
*  May use more memory than a hash table, depends.
*  Memory is allocated as needed, so none is wasted.
*   
*  Copyright (C) 2002 Marc Norton
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "hi_util_kmap.h"
#include "hi_util_xmalloc.h"

//#define MEMASSERT(p) if(!p){printf("KMAP-No Memory: File: %s Line:%d!\n",__FILE__,__LINE__);exit(0);}

#define MEMASSERT(p) 
#define LOWERCASE tolower

/*
*
*/
static void * s_malloc( int n )
{
   void * p;

   p = xmalloc( n );

   MEMASSERT(p);

   return p;
}

/*
*
*/
static void s_free( void * p )
{
   if( p ) xfree( p );
}
/*
*
*/
KMAP * KMapNew( void (*userfree)(void*p) )
{
   KMAP * km = (KMAP*) s_malloc( sizeof(KMAP) );

   if( !km ) return 0;
   
   memset(km, 0, sizeof(KMAP));  

   km->userfree = userfree;

   return km;
}
/*
*
*/
void KMapSetNoCase( KMAP * km, int flag )
{
     km->nocase = flag;
}

/*
*   Free the list of key+data pair nodes - used by findfirst/next
*/
static int KMapFreeNodeList(KMAP * km )
{
   KEYNODE * k, *kold;

   for( k=km->keylist; k; )
   {
        if( k->key )
        {
            s_free( k->key );
        }
        if( km->userfree && k->userdata )
        {
            km->userfree( k->userdata ); 
        }
        kold = k;
        k = k->next;
        s_free(kold);
   }

   return 0;
}
/*
*     Recursively walk and free nodes
*/
static void KMapFreeNode( KMAP * km, KMAPNODE * r)
{
     if( r->sibling )
     {
         KMapFreeNode( km, r->sibling );
     }

     if( r->child )
     {
         KMapFreeNode( km, r->child );
     }

     s_free( r );
} 
/*
*  Free the KMAP and all of it's memory and nodes
*/
void KMapDelete( KMAP * km )
{
   KMAPNODE * r;
   int        i;

   /* Free the tree - on root node at a time */
   for(i=0;i<256;i++)
   {
      r = km->root[i];
      if( r )
      { 
          KMapFreeNode(km,r); 
      }
   }

   /* Free the node list */
   KMapFreeNodeList( km );

   s_free(km);
}

/*
*  Add key + data pair to the linked list of nodes
*/
static KEYNODE *  KMapAddKeyNode(KMAP * km,void * key, int n, void * userdata )
{
   KEYNODE * knode = (KEYNODE*) s_malloc( sizeof(KEYNODE) );

   if( !knode || n < 0 ) 
       return 0;
   
   memset(knode, 0, sizeof(KEYNODE) );  

   knode->key = (unsigned char*)s_malloc(n); // Alloc the key space
   if( !knode->key )
       return 0;

   memcpy(knode->key,key,n); // Copy the key
   knode->nkey     = n;
   knode->userdata = userdata;

   if( km->keylist ) // Insert at front of list 
   {
      knode->next = km->keylist;
      km->keylist = knode;
   }
   else
   {
      km->keylist = knode;
   }

   return knode;
}
/*
*  Create a character node
*/
static KMAPNODE * KMapCreateNode(KMAP * km)
{
   KMAPNODE * mn=(KMAPNODE*)s_malloc( sizeof(KMAPNODE) );

   if(!mn)
       return NULL;

   memset(mn,0,sizeof(KMAPNODE));

   km->nchars++;

   return mn;
}

/*
*    key : ptr to bytes of data used to identify this item
*          may be text string, or binary character sequence.
*    n   : > 0 number of bytes in the key
*          <=0 key is a null terminated  ascii string
*    userdata - ptr to data to associate with this key
*
*   returns:
*            -1 - no memory
*             1 - key already in table
*             0 - key added successfully
*/
int KMapAdd( KMAP *km, void * key, int n, void * userdata )
{
   int            i,ksize;
   int            type;
   unsigned char *P = (unsigned char *)key;
   KMAPNODE      *root;
   unsigned char  xkey[256];
   
   if( n <= 0 )
   {
       n = strlen( (char*) key );
       if( n > sizeof(xkey) )
           return -99;

       if( km->nocase )
       {
           for(i=0;i<n;i++)
               xkey[i] = LOWERCASE( P[i] );
           P = xkey;
       }
   }

   /* Save key size */
   ksize = n;

   //printf("adding key='%.*s'\n",n,P);
   
   /* Make sure we at least have a root character for the tree */
   if( !km->root[ *P ] )
   {
      root = KMapCreateNode(km);
      if( !root )
           return -1;
      km->root[ *P ] = root;
      root->nodechar = *P;

   }else{

      root = km->root[ *P ];
   }

   /* Walk exisitng Patterns */   
   while( n )
   {
     if( root->nodechar == *P )
     {
         //printf("matched char = %c, nleft = %d\n",*P,n-1);
         P++;
         n--;
         if( n && root->child )
         {
            root=root->child;   
         }
         else /* cannot continue */
         {
            type = 0; /* Expand the tree via the child */
            break; 
         }
     }
     else
     {
         if( root->sibling )
         {
            root=root->sibling;
         }
         else /* cannot continue */
         {
            type = 1; /* Expand the tree via the sibling */
            break; 
         }
     }
   }


   /* 
   * Add the next char of the Keyword, if any
   */
   if( n )
   {
     if( type == 0 )
     {
      /*
      *  Start with a new child to finish this Keyword 
      */
      //printf("added child branch nodechar = %c \n",*P);
      root->child= KMapCreateNode( km );
      if( !root->child )
           return -1;
      root=root->child;
      root->nodechar  = *P;
      P++;
      n--;
     }
     else
     { 
      /*
      *  Start a new sibling bracnch to finish this Keyword 
      */
      //printf("added sibling branch nodechar = %c \n",*P);
      root->sibling= KMapCreateNode( km );
      if( !root->sibling )
           return -1;
      root=root->sibling;
      root->nodechar  = *P;
      P++;
      n--;
     }
   }

   /*
   *    Finish the keyword as child nodes
   */
   while( n )
   {
      //printf("added child nodechar = %c \n",*P);
      root->child = KMapCreateNode(km);
      if( !root->child )
           return -1;
      root=root->child;
      root->nodechar  = *P;
      P++;
      n--;
   }

   /* 
   * Iteration support - Add this key/data to the linked list 
   * This allows us to do a findfirst/findnext search of 
   * all map nodes.
   */
   if( root->knode ) /* Already present */
        return 1;

   root->knode = KMapAddKeyNode( km, key, ksize, userdata );
   if( !root->knode )
        return -1;

   return 0;
}

/*
*  Exact Keyword Match - unique keys, with just one piece of 
*  'userdata' , for multiple entries, we could use a list
*  of 'userdata' nodes.
*/
void *  KMapFind( KMAP * ks, void * key, int n )
{
   unsigned char * T = (unsigned char *)key;
   KMAPNODE      * root;
   unsigned char   xkey[256];
   int             i;

   if( n <= 0 )
   {
       n = strlen( (char*)key );
       if( n > sizeof(xkey) )
           return 0;

       if( ks->nocase )
       {
         for(i=0;i<n;i++)
           xkey[i] = LOWERCASE( T[i] );

         T = xkey;
       }
   }
   //printf("finding key='%.*s'\n",n,T);

   root = ks->root[ *T ];

   /* Check if any keywords start with this character */
   root = ks->root[ *T ];
   if( !root ) return NULL;
        
   while( n )
   {
     if( root->nodechar == *T )
     {
         T++;
         n--;
         if( n && root->child )
         {
            root = root->child;   
         }
         else /* cannot continue -- match is over */
         {
            break; 
         }
     }
     else
     {
         if( root->sibling )
         {
            root = root->sibling;
         }
         else /* cannot continue */
         {
            break; 
         }
     }
   }

   if( !n )
   {
       return root->knode->userdata; /* success */
   }

   return NULL;
}
/*
*
*/
KEYNODE * KMapFindFirstKey( KMAP * km )
{
   km->keynext = km->keylist;

   if(!km->keynext)
   {
       return NULL;
   }

   return km->keynext;
}
/*
*
*/
void * KMapFindFirst( KMAP * km )
{
   km->keynext = km->keylist;

   if(!km->keynext)
   {
       return NULL;
   }

   return km->keynext->userdata;
}
/*
*
*/
KEYNODE * KMapFindNextKey( KMAP * km )
{
   if( !km->keynext )
       return 0;

   km->keynext = km->keynext->next; 

   if( !km->keynext )
       return 0;

   return km->keynext;
}
/*
*
*/
void * KMapFindNext( KMAP * km )
{
   if( !km->keynext )
       return 0;

   km->keynext = km->keynext->next; 

   if( !km->keynext )
       return 0;

   return km->keynext->userdata;
}

#ifdef KMAP_MAIN
/*
*
*/
int main( int argc, char ** argv )
{
    int    i,n=10;
    KMAP * km;
    char * p;
    char   str[80];

    printf("usage: kmap nkeys (default=10)\n\n");
    
    km = KMapNew( free );  /* use 'free' to free 'userdata' */

    KMapSetNoCase(km,1);  //need to add xlat....

    if( argc > 1 )
    {
        n = atoi(argv[1]);
    }

    for(i=1;i<=n;i++)
    {
       sprintf(str,"KeyWord%d",i);
       KMapAdd( km, str, 0 /* strlen(str) */, strupr(strdup(str)) );
       printf("Adding Key=%s\n",str);
    }
    printf("xmem: %u bytes, %d chars\n",xmalloc_bytes(),km->nchars);

    printf("\nKey Find test...\n");
    for(i=1;i<=n;i++)
    {
       sprintf(str,"KeyWord%d",i);
       p = (char*) KMapFind( km, str,  0 /*strlen(str) */ );
       if(p)printf("key=%s, data=%*s\n",str,strlen(str),p);
       else printf("'%s' NOT found.\n",str);
    }

    KMapSetNoCase(km,0);  // this should fail all key searches
    printf("\nKey Find test2...\n");
    for(i=1;i<=n;i++)
    {
       sprintf(str,"KeyWord%d",i);
       p = (char*) KMapFind( km, str,  0 /*strlen(str) */ );
       if(p)printf("key=%s, data=%*s\n",str,strlen(str),p);
       else printf("'%s' NOT found.\n",str);
    }

    printf("\nKey FindFirst/Next test...\n");
    for(p = (char*) KMapFindFirst(km); p; p=(char*)KMapFindNext(km) )
        printf("data=%s\n",p);

    printf("\nKey FindFirst/Next test done.\n");

    KMapDelete( km );

    printf("xmem: %u bytes\n",xmalloc_bytes());

    printf("normal pgm finish.\n");
     
    return 0;
}

#endif