sfghash.c

Linux snort-2.4.4源代码

/*
*
*  sfghash.c
*
*  Generic hash table library.
*
*  This hash table maps unique keys to void data pointers.
*
*  Features:
*    1) Keys may be ascii strings of variable size, or
*       fixed length (per table) binary byte sequences.  This
*       allows use as a Mapping for String+Data pairs, or a 
*       generic hashing.
*    2) User can allocate keys, or pass copies and we can 
*       allocate space and save keys.
*    3) User can pass a free function to free up user data
*       when the table is deleted.
*    4) Table rows sizes can be automatically adjusted to
*       the nearest prime number size.
*
*  6/10/03 - man - Upgraded the hash function to a Hardened hash function,
*      it has no predictable cycles, and each hash table gets a different
*      randomized hashing function. So even with the source code, you cannot predict 
*      anything with this function.  If an  attacker can can setup a feedback
*      loop he might gain some knowledge of how to muck with us, buit even in that case
*      his odds are astronomically skinny.  This is actually the same problem as solved
*      early on with hashing functions where degenerate data with close keys could
*      produce very long bucket chains.
*
*  Copyright (C) 2001 Marc A Norton
*  Copyright (C) 2003 Sourcefire,Inc.
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "sfghash.h"

/*
*  uncomment this include to use xmalloc functions
*/

/*
*  Private Malloc
*/
static 
void * s_malloc( int n )
{
     return malloc( n );
}

/*
*  Private Free
*/
static 
void s_free( void * p )
{
   if( p )free( p );
}

/*
*  A classic hash routine using prime numbers
*
*  Constants for the Prime No. based hash routines
*/


/*
*   Primiitive Prime number test, not very fast nor efficient, but should be ok for
*   hash table sizes of typical size.
*/
static 
int isPrime(int num )
{
   int i;
   for(i=2;i<num;i++)
   {
      if( (num % i) == 0 ) break;//oops not prime, should have a remainder
   }
   if( i == num ) return 1;
   return 0;
}
/*
*  Iterate number till we find a prime.
*/
static
int calcNextPrime(int num )
{
	while( !isPrime( num ) ) num++;
	return num;
}

/*
*
*    Create a new hash table
*
*    nrows    : number of rows in hash table, primes are best.
*               > 0  => we calc the nearest prime .ge. nrows internally
*               < 0  => we use the magnitude as nrows.
*    keysize  : > 0 => bytes in each key, keys are binary bytes,
*               all keys are the same size.
*               ==0 => keys are strings and are null terminated, 
*               allowing random key lengths. 
*    userkeys : > 0 => indicates user owns the key data
*               and we should not allocate or free space for it,
*               nor should we attempt to free the user key. We just
*               save the pointer to the key. 
*               ==0 => we should copy the keys and manage them internally
*    userfree : routine to free users data, null if we should not 
*               free user data in sfghash_delete(). The routine
*               should be of the form 'void userfree(void * userdata)',
*               'free' works for simple allocations.
*/
SFGHASH * sfghash_new( int nrows, int keysize, int userkeys, void (*userfree)(void*p) )
{
   int    i;
   SFGHASH * h;

   if( nrows > 0 ) /* make sure we have a prime number */
   {
      nrows = calcNextPrime( nrows );
   }
   else   /* use the magnitude or nrows as is */
   { 
      nrows = -nrows;
   }


   h = (SFGHASH*)s_malloc( sizeof(SFGHASH) );
   if( !h ) return 0;

   memset( h, 0, sizeof(SFGHASH) );

   h->sfhashfcn = sfhashfcn_new( nrows );
   if( !h->sfhashfcn ) return 0;

   h->table = (SFGHASH_NODE**) s_malloc( sizeof(SFGHASH_NODE*) * nrows );
   if( !h->table ) return 0;

   for( i=0; i<nrows; i++ )
   {
      h->table[i] = 0;
   }

   h->userkey = userkeys;

   h->keysize = keysize;

   h->nrows = nrows;

   h->count = 0;

   h->userfree = userfree;

   h->crow = 0; // findfirst/next current row

   h->cnode = 0; // findfirst/next current node ptr

   return h;
}

/*
*  Set Splay mode : Splays nodes to front of list on each access
*/
void sfghash_splaymode( SFGHASH * t, int n )
{
   t->splay = n;
}


SFDICT * sfdict_new( int nitems )
{
   return sfghash_new( nitems, 0, GH_COPYKEYS, NULL );
}

void sfdict_delete( SFDICT * h )
{
    sfghash_delete( h );
}

/*
*  Delete the hash Table 
*
*  free key's, free node's, and free the users data.
*/
void sfghash_delete( SFGHASH * h )
{
  int            i;
  SFGHASH_NODE * node, * onode;

  if( !h ) return;
 
  sfhashfcn_free( h->sfhashfcn );

  if( h->table )
  {  
    for(i=0;i<h->nrows;i++)
    {
      for( node=h->table[i]; node;  )
      {
        onode = node;
        node  = node->next;

        if( !h->userkey && onode->key ) 
            s_free( onode->key );

        if( h->userfree && onode->data )
            h->userfree( onode->data ); /* free users data, with users function */

        s_free( onode );
      }
    }
    s_free( h->table );
    h->table = 0;
  }

  s_free( h );
}

/*
*  Get the # of Nodes in HASH the table
*/
int sfghash_count( SFGHASH * t )
{
  return t->count;
}

int sfdict_count( SFDICT * t )
{
  return t->count;
}


/*
*  Add a key + data pair
*  ---------------------
*
*  key + data should both be non-zero, although data can be zero
*
*  t    - hash table
*  key  - users key data (should be unique in this table)
*         may be ascii strings or fixed size binary keys
*  data - users data pointer
*
*  returns  SF_HASH_NOMEM: malloc error
*           SF_HASH_INTABLE : key already in table (t->cnode points to the node)
*           SF_OK: added a node for this key + data pair
*
*  Notes:
*  If the key node already exists, then t->cnode points to it on return,
*  this allows you to do something with the node - like add the data to a 
*  linked list of data items held by the node, or track a counter, or whatever.
*
*/
int sfghash_add( SFGHASH * t, void * key, void * data )
{
    unsigned    hashkey;
	int         klen;
    int         index;
    SFGHASH_NODE  *hnode;

    /*
    *   Get proper Key Size
    */  
    if( t->keysize > 0  )
    {
        klen = t->keysize;
    }
    else
    {
	/* need the nul byte for strcmp() in sfghash_find() */
        klen = strlen( (char*)key ) + 1;
    }
    
    hashkey = t->sfhashfcn->hash_fcn(  t->sfhashfcn, (unsigned char*) key, klen );
    
    index = hashkey % t->nrows;

    /*
    *  Uniqueness: 
    *  Check 1st to see if the key is already in the table
    *  Just bail if it is.
    */
    for( hnode=t->table[index]; hnode; hnode=hnode->next )
    {
       if( t->keysize > 0 )
       {
          if( !t->sfhashfcn->keycmp_fcn(hnode->key,key,klen) )
          {
              t->cnode = hnode; /* save pointer to the node */
              return SFGHASH_INTABLE; /* found it */
          }
       }
       else
       {
         if( !strcmp((const char *)hnode->key,(const char*)key) )
         {
             t->cnode = hnode; /* save pointer to the node */
             return SFGHASH_INTABLE; /* found it */
         }
       }
    }

    /* 
    *  Create new node 
    */
    hnode = (SFGHASH_NODE*)s_malloc(sizeof(SFGHASH_NODE));
    if( !hnode )
         return SFGHASH_NOMEM;
    
    /* Add the Key */
    if( t->userkey )
    {
      /* Use the Users key */
      hnode->key = key;
    }
    else
    {
      /* Create new key */
      hnode->key = s_malloc( klen );
      if( !hnode->key )
           return SFGHASH_NOMEM;

      /* Copy key  */
      memcpy(hnode->key,key,klen);
    }
    
    /* Add The Node */
    if( t->table[index] ) /* add the node to the existing list */
    {
        hnode->prev = 0;  // insert node as head node
        hnode->next=t->table[index];
        hnode->data=data;
        t->table[index]->prev = hnode;
        t->table[index] = hnode;
    }
    else /* 1st node in this list */
    {
        hnode->prev=0;
        hnode->next=0;
        hnode->data=data;
        t->table[index] = hnode;
    }

    t->count++;

    return SFGHASH_OK;
}

/*
*
*/
int sfdict_add( SFGHASH * t, char * key, void * data )
{
   return sfghash_add( t, key, data );
}
/*
*  move a node to the front of the list
*/
static void movetofront( SFGHASH *t , int index, SFGHASH_NODE * n )
{
    if( t->table[index] != n ) // if not at fron of list already...
    {
      /* Unlink the node */
      if( n->prev ) n->prev->next = n->next;
      if( n->next ) n->next->prev = n->prev;
      
      /* Link at front of list */
      n->prev=0;
      n->next=t->table[index];
      t->table[index]->prev=n;
    }
}

/*
*  Find a Node based on the key, return users data.
*/
static SFGHASH_NODE * sfghash_find_node( SFGHASH * t, void * key)
{
    unsigned    hashkey;
    int         index, klen;
    SFGHASH_NODE  *hnode;

    if( t->keysize  )
    {
	klen = t->keysize;
    }
    else
    {
	klen = strlen( (char*) key ) + 1;
    }

    hashkey = t->sfhashfcn->hash_fcn(  t->sfhashfcn, (unsigned char*) key, klen );
    
    index = hashkey % t->nrows;
   
    for( hnode=t->table[index]; hnode; hnode=hnode->next )
    {
        if( t->keysize == 0 )
        {
           if( !strcmp((char*)hnode->key,(char*)key) )
           {
               if( t->splay  > 0 )
                   movetofront(t,index,hnode);

               return hnode;
           }
        }
        else
        {
           if( !t->sfhashfcn->keycmp_fcn(hnode->key,key,t->keysize) )
           {
               if( t->splay  > 0 )
                   movetofront(t,index,hnode);

               return hnode;
           }
        }
    }

   return NULL;
}

/*
*  Find a Node based on the key, return users data.
*/
void * sfghash_find( SFGHASH * t, void * key)
{