sfxhash.c

著名的入侵检测系统snort的最新版本的源码

        t->fhead    = hnode;
        t->ftail    = hnode;
    }
}
static
SFXHASH_NODE * sfxhash_get_free_node( SFXHASH *t )
{
    SFXHASH_NODE * node = t->fhead;

    /* Remove A Node from the Free Node List - remove the head node */
    if( t->fhead  ) 
    {
        t->fhead = t->fhead->gnext;
        if( t->fhead ) 
            t->fhead->gprev = 0;

        if( t->ftail  == node ) /* no more nodes - clear the tail */
            t->ftail  =  0;
    }

    return node;
}

static
void sfxhash_glink_node( SFXHASH *t, SFXHASH_NODE * hnode )
{
    /* Add The Node */
    if( t->ghead ) /* add the node to head of the the existing list */
    {
        hnode->gprev    = 0;  
        hnode->gnext    = t->ghead;
        t->ghead->gprev = hnode;
        t->ghead        = hnode;
        /* tail is not affected */
    }
    else /* 1st node in this list */
    {
        hnode->gprev = 0;
        hnode->gnext = 0;
        t->ghead    = hnode;
        t->gtail    = hnode;
    }
}

static
void sfxhash_gunlink_node( SFXHASH *t, SFXHASH_NODE * hnode )
{
    /* Remove the Head Node */
    if( t->ghead == hnode ) /* add the node to head of the the existing list */
    {
        t->ghead = t->ghead->gnext;
        if( t->ghead ) 
            t->ghead->gprev = 0;
    }

    if( hnode->gprev ) hnode->gprev->gnext = hnode->gnext;
    if( hnode->gnext ) hnode->gnext->gprev = hnode->gprev;

    if( t->gtail  == hnode )
        t->gtail  =  hnode->gprev;             
}

void sfxhash_gmovetofront( SFXHASH *t, SFXHASH_NODE * hnode )
{
    if( hnode != t->ghead )
    {
        sfxhash_gunlink_node( t, hnode );
        sfxhash_glink_node( t, hnode );
    }
}

/*
 *
 */
static
void sfxhash_link_node( SFXHASH * t, SFXHASH_NODE * hnode )
{
    /* Add The Node to the Hash Table Row List */
    if( t->table[hnode->rindex] ) /* add the node to the existing list */
    {
        hnode->prev = 0;  // insert node as head node
        hnode->next=t->table[hnode->rindex];
        t->table[hnode->rindex]->prev = hnode;
        t->table[hnode->rindex] = hnode;
    }
    else /* 1st node in this list */
    {
        hnode->prev=0;
        hnode->next=0;
        t->table[hnode->rindex] = hnode;
    }
}

static
void sfxhash_unlink_node( SFXHASH * t, SFXHASH_NODE * hnode )
{
    if( hnode->prev )  // definitely not the 1st node in the list
    {
        hnode->prev->next = hnode->next;
        if( hnode->next ) 
            hnode->next->prev = hnode->prev;
    }
    else if( t->table[hnode->rindex] )  // must be the 1st node in the list
    {
        t->table[hnode->rindex] = t->table[hnode->rindex]->next;
        if( t->table[hnode->rindex] )
            t->table[hnode->rindex]->prev = 0;
    }
}

/*
 *  move a node to the front of the row list at row = 'index'
 */
static void movetofront( SFXHASH *t, SFXHASH_NODE * n )
{
    /* Modify Hash Node Row List */
    if( t->table[n->rindex] != n ) // if not at front of list already...
    {
        /* Unlink the node */
        sfxhash_unlink_node( t, n );
     
        /* Link at front of list */
        sfxhash_link_node( t, n );
    }

    /* Move node in the global hash node list to the front */
    sfxhash_gmovetofront( t, n );
}

/*
 * Allocat a new hash node, uses Auto Node Recovery if needed and enabled.
 * 
 * The oldest node is the one with the longest time since it was last touched, 
 * and does not have any direct indication of how long the node has been around.
 * We don't monitor the actual time since last being touched, instead we use a
 * splayed global list of node pointers. As nodes are accessed they are splayed
 * to the front of the list. The oldest node is just the tail node.
 *
 */
static 
SFXHASH_NODE * sfxhash_newnode( SFXHASH * t )
{
    SFXHASH_NODE * hnode;

    /* Recycle Old Nodes - if any */
    hnode = sfxhash_get_free_node( t );

    /* Allocate memory for a node */
    if( ! hnode )
    {
        if ((t->max_nodes == 0) || (t->count < t->max_nodes))
        {
            hnode = (SFXHASH_NODE*)s_alloc( t, sizeof(SFXHASH_NODE) +
                                         t->keysize + t->datasize );
        }
    }
        
    /*  If we still haven't found hnode, we're at our memory limit.
     *
     *  Uses Automatic Node Recovery, to recycle the oldest node-based on access
     *  (Unlink and reuse the tail node)
     */ 
    if( !hnode && t->anr_flag && t->gtail )
    {
        /* Find the oldes node the users willing to let go. */
        for(hnode = t->gtail; hnode; hnode = hnode->gprev )
        {
            if( t->anrfree ) /* User has provided a permission+release callback function */
            {
                t->anr_tries++;/* Count # ANR requests */
                
                /* Ask the user for permission to release this node, but let them say no! */
                if( t->anrfree( hnode->key, hnode->data ) )
                {
                    /* NO, don't recycle this node, user's not ready to let it go. */                            
                    continue;
                }
                
                /* YES, user said we can recycle this node */
            }

            sfxhash_gunlink_node( t, hnode ); /* unlink from the global list */
            sfxhash_unlink_node( t, hnode ); /* unlink from the row list */
            t->count--;
            t->anr_count++; /* count # of ANR operations */
            break;
        }
    }

    /* either we are returning a node or we're all full and the user
     * won't let us allocate anymore and we return NULL */
    return hnode;
}

/*
 *
 *  Find a Node based on the key, return the node and the index.
 *  The index is valid even if the return value is NULL, in which
 *  case the index is the corect row in which the node should be 
 *  created.
 *
 */

#define hashsize(n) ((u_int32_t)1<<(n))
#define hashmask(n) (hashsize(n)-1)

static 
SFXHASH_NODE * sfxhash_find_node_row( SFXHASH * t, void * key, int * rindex )
{
    unsigned       hashkey;
    int            index;
    SFXHASH_NODE  *hnode;

    hashkey = t->sfhashfcn->hash_fcn( t->sfhashfcn,
                                      (unsigned char*)key,
                                      t->keysize );
    
/*     printf("hashkey: %u t->keysize: %d\n", hashkey, t->keysize); */
/*     flowkey_fprint(stdout, key);  */
/*     printf("****\n"); */

//     index   = hashkey % t->nrows;
    /* Modulus is slow. Switched to a table size that is a power of 2. */      
    index  = hashkey & (t->nrows - 1);

    *rindex = index;
   
    for( hnode=t->table[index]; hnode; hnode=hnode->next )
    {
        if( !t->sfhashfcn->keycmp_fcn(hnode->key,key,t->keysize) )
        {
            if( t->splay > 0 )
                movetofront(t,hnode);

            t->find_success++;            
            return hnode;
        }
    }

    t->find_fail++;            
    return NULL;
}



/*!
 * Add a key + data pair to the hash table
 *
 * 2003-06-06:
 *  - unique_tracker.c assumes that this splays
 *    nodes to the top when they are added.
 *
 *    This is done because of the successful find.
 *
 * @param t SFXHASH table pointer
 * @param key  users key pointer
 * @param data  users data pointer
 *
 * @return integer
 * @retval SFXHASH_OK      success
 * @retval SFXHASH_INTABLE already in the table, t->cnode points to the node
 * @retval SFXHASH_NOMEM   not enough memory
 */
int sfxhash_add( SFXHASH * t, void * key, void * data )
{
    int            index;
    SFXHASH_NODE * hnode;

    /* Enforce uniqueness: Check for the key in the table */
    hnode = sfxhash_find_node_row( t, key, &index );

    if( hnode )
    {
        t->cnode = hnode;

        return SFXHASH_INTABLE; /* found it - return it. */
    }

    /* 
     *  Alloc new hash node - allocate key space and data space at the same time.
     */
    hnode = sfxhash_newnode( t );
    if( !hnode )
    {
        return SFXHASH_NOMEM;
    }

    /* Set up the new key pointer */
    hnode->key = (char*)hnode + sizeof(SFXHASH_NODE);

    /* Copy the key */
    memcpy(hnode->key,key,t->keysize);

    /* Save our table row index */
    hnode->rindex = index;

    /* Copy the users data - or if datasize is zero set ptr to users data */
    if( t->datasize )
    {
        /* Set up the new data pointer */
        hnode->data= (char*)hnode + sizeof(SFXHASH_NODE) + t->keysize;

        if(data)
        {
           memcpy(hnode->data,data,t->datasize);
        }
    }
    else 
    {
        hnode->data = data;
    }
    
    /* Link the node into the table row list */
    sfxhash_link_node ( t, hnode );

    /* Link at the front of the global node list */
    sfxhash_glink_node( t, hnode );

    /* Track # active nodes */
    t->count++;

    return SFXHASH_OK;
}


/*!
 * Add a key to the hash table, return the hash node
 *
 * 2003-06-06:
 *  - unique_tracker.c assumes that this splays
 *    nodes to the top when they are added.
 *
 *    This is done because of the successful find.
 *
 * @param t SFXHASH table pointer
 * @param key  users key pointer
 *
 * @return integer
 * @retval SFXHASH_OK      success
 * @retval SFXHASH_INTABLE already in the table, t->cnode points to the node
 * @retval SFXHASH_NOMEM   not enough memory
 */
SFXHASH_NODE * sfxhash_get_node( SFXHASH * t, void * key )
{
    int            index;
    SFXHASH_NODE * hnode;

    /* Enforce uniqueness: Check for the key in the table */
    hnode = sfxhash_find_node_row( t, key, &index );

    if( hnode )
    {
        t->cnode = hnode;

        return hnode; /* found it - return it. */
    }

    /* 
     *  Alloc new hash node - allocate key space and data space at the same time.
     */
    hnode = sfxhash_newnode( t );
    if( !hnode )
    {
        return NULL;
    }

    /* Set up the new key pointer */
    hnode->key = (char*)hnode + sizeof(SFXHASH_NODE);

    /* Copy the key */
    memcpy(hnode->key,key,t->keysize);

    /* Save our table row index */
    hnode->rindex = index;

    /* Copy the users data - or if datasize is zero set ptr to users data */
    if( t->datasize )
    {
        /* Set up the new data pointer */
        hnode->data= (char*)hnode + sizeof(SFXHASH_NODE) + t->keysize;
    }
    else 
    {
        hnode->data = NULL;
    }
    
    /* Link the node into the table row list */
    sfxhash_link_node ( t, hnode );

    /* Link at the front of the global node list */
    sfxhash_glink_node( t, hnode );

    /* Track # active nodes */
    t->count++;

    return hnode;
}


/*!
 * Find a Node based on the key
 *
 * @param t SFXHASH table pointer
 * @param key  users key pointer
 *
 * @return SFXHASH_NODE*   valid pointer to the hash node
 * @retval 0               node not found
 *
 */
SFXHASH_NODE * sfxhash_find_node( SFXHASH * t, void * key)
{
    int            rindex;

    return sfxhash_find_node_row( t, key, &rindex );
}

/*!
 * Find the users data based associated with the key
 *
 * @param t SFXHASH table pointer
 * @param key  users key pointer
 *
 * @return void*   valid pointer to the users data
 * @retval 0       node not found
 *
 */
void * sfxhash_find( SFXHASH * t, void * key)
{
    SFXHASH_NODE * hnode;
    int            rindex;

    hnode = sfxhash_find_node_row( t, key, &rindex );

    if( hnode ) return hnode->data;

    return NULL;
}


/** 
 * Get the HEAD of the in use list
 * 
 * @param t table pointer 
 * 
 * @return the head of the list or NULL
 */
SFXHASH_NODE *sfxhash_ghead( SFXHASH * t )
{
    if(t)
    {
        return t->ghead;
    }

    return NULL;