sfxhash.c

Linux snort-2.4.4源代码

 * @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;
}


/** 
 * Walk the global list
 * 
 * @param n current node
 * 
 * @return the next node in the list or NULL when at the end
 */
SFXHASH_NODE *sfxhash_gnext( SFXHASH_NODE *n )
{
    if(n)
    {
        return n->gnext;
    }

    return NULL;
}


/*!
 * Return the most recently used data from the global list
 *
 * @param t SFXHASH table pointer
 *
 * @return void*   valid pointer to the users data
 * @retval 0       node not found
 *
 */
void * sfxhash_mru( SFXHASH * t )
{
    SFXHASH_NODE * hnode;

    hnode = sfxhash_ghead(t);

    if( hnode )
        return hnode->data;
        
    return NULL;
}

/*!
 * Return the least recently used data from the global list
 *
 * @param t SFXHASH table pointer
 *
 * @return void*   valid pointer to the users data
 * @retval 0       node not found
 *
 */
void * sfxhash_lru( SFXHASH * t )
{
    SFXHASH_NODE * hnode;

    hnode = t->gtail;

    if( hnode ) return hnode->data;

    return NULL;
}

/*!
 * Return the most recently used node from the global list
 *
 * @param t SFXHASH table pointer
 *
 * @return SFXHASH_NODE*   valid pointer to a node
 * @retval 0       node not found
 *
 */
SFXHASH_NODE * sfxhash_mru_node( SFXHASH * t )
{
    SFXHASH_NODE * hnode;

    hnode = sfxhash_ghead(t);

    if( hnode )
        return hnode;
        
    return NULL;
}

/*!
 * Return the least recently used node from the global list
 *
 * @param t SFXHASH table pointer
 *
 * @return SFXHASH_NODE*   valid pointer to a node
 * @retval 0       node not found
 *
 */
SFXHASH_NODE * sfxhash_lru_node( SFXHASH * t )
{
    SFXHASH_NODE * hnode;

    hnode = t->gtail;

    if( hnode ) return hnode;

    return NULL;
}

/*!
 * Get some hash table statistics. NOT FOR REAL TIME USE.
 *
 * 
 * @param t SFXHASH table pointer
 * @param filled how many 
 *
 * @return max depth of the table
 *
 */
unsigned sfxhash_maxdepth( SFXHASH * t )
{
    unsigned i;
    unsigned max_depth = 0;

    SFXHASH_NODE * hnode;

    for( i=0; i<t->nrows; i++ )
    {
        unsigned cur_depth = 0;

        for(hnode = t->table[i]; hnode != NULL; hnode = hnode->next)
        {
            cur_depth++;
        }

        if(cur_depth > max_depth)
            max_depth = cur_depth;
    }

    return max_depth;
}

/*
 *  Unlink and free the node
 */
int sfxhash_free_node( SFXHASH * t, SFXHASH_NODE * hnode)
{
    sfxhash_unlink_node( t, hnode ); /* unlink from the hash table row list */

    sfxhash_gunlink_node( t, hnode ); /* unlink from global-hash-node list */

    t->count--;

    if( t->usrfree )
    {
        t->usrfree( hnode->key, hnode->data );
    }

    if( t->recycle_nodes )
    {
        sfxhash_save_free_node( t, hnode );
    }
    else
    {
        s_free( t, hnode );
    }

    return SFXHASH_OK;
}

/*!
 * Remove a Key + Data Pair from the table.
 *
 * @param t SFXHASH table pointer
 * @param key  users key pointer
 *
 * @return 0   success
 * @retval !0  failed
 *
 */
int sfxhash_remove( SFXHASH * t, void * key)
{
    SFXHASH_NODE * hnode;
    unsigned hashkey, index;

    hashkey = t->sfhashfcn->hash_fcn( t->sfhashfcn,
                                      (unsigned char*)key,
                                      t->keysize );
    
    index = hashkey % t->nrows;

    hnode = t->table[index];
    
    for( hnode=t->table[index]; hnode; hnode=hnode->next )
    {
        if( !t->sfhashfcn->keycmp_fcn(hnode->key,key,t->keysize) )
        {
            return sfxhash_free_node( t, hnode );
        }
    }

    return SFXHASH_ERR;  
}

/* 
   Internal use only 
*/
static 
void sfxhash_next( SFXHASH * t )
{
    if( !t->cnode )
        return ;
 
    /* Next node in current node list */
    t->cnode = t->cnode->next;
    if( t->cnode )
    {
        return;
    }

    /* Next row */ 
    /* Get 1st node in next non-emtoy row/node list */
    for( t->crow++; t->crow < t->nrows; t->crow++ )
    {    
        t->cnode = t->table[ t->crow ];
        if( t->cnode ) 
        {
            return;
        }
    }
}
/*!
 * Find and return the first hash table node
 *
 * @param t SFXHASH table pointer
 *
 * @return 0   failed
 * @retval !0  valid SFXHASH_NODE *
 *
 */
SFXHASH_NODE * sfxhash_findfirst( SFXHASH * t )
{
    SFXHASH_NODE * n;

    /* Start with 1st row */
    for( t->crow=0; t->crow < t->nrows; t->crow++ )
    {    
        /* Get 1st Non-Null node in row list */
        t->cnode = t->table[ t->crow ];
        if( t->cnode )
        {
            n = t->cnode;
            sfxhash_next( t ); // load t->cnode with the next entry
            return n;
        }
    }
    
    return NULL;
}

/*!
 * Find and return the next hash table node
 *
 * @param t SFXHASH table pointer
 *
 * @return 0   failed
 * @retval !0  valid SFXHASH_NODE *
 *
 */
SFXHASH_NODE * sfxhash_findnext( SFXHASH * t )
{
    SFXHASH_NODE * n;

    n = t->cnode;
    if( !n ) /* Done, no more entries */
    {
        return NULL;
    }

    /*
      Preload next node into current node 
    */
    sfxhash_next( t ); 

    return  n;
}


/** 
 * Make sfhashfcn use a separate set of operators for the backend.
 *
 * @param h sfhashfcn ptr
 * @param hash_fcn user specified hash function
 * @param keycmp_fcn user specified key comparisoin function
 */

int sfxhash_set_keyops( SFXHASH *h ,
                        unsigned (*hash_fcn)( SFHASHFCN * p,
                                              unsigned char *d,
                                              int n),
                        int (*keycmp_fcn)( const void *s1,
                                           const void *s2,
                                           size_t n))
{
    if(h && hash_fcn && keycmp_fcn)
    {
        return sfhashfcn_set_keyops(h->sfhashfcn, hash_fcn, keycmp_fcn);
    }

    return -1;
}


/*
 * -----------------------------------------------------------------------------------------
 *   Test Driver for Hashing
 * -----------------------------------------------------------------------------------------
 */
#ifdef SFXHASH_MAIN 


/* 
   This is called when the user releases a node or kills the table 
*/
int usrfree( void * key, void * data )
{

    /* Release any data you need to */
    return 0;  
}

/* 
   Auto Node Recovery Callback - optional 

   This is called to ask the user to kill a node, if it reutrns !0 than the hash
   library does not kill this node.  If the user os willing to let the node die,
   the user must do any free'ing or clean up on the node during this call.
*/
int anrfree( void * key, void * data )
{
    static int bx = 0;

    /* Decide if we can free this node. */

    //bx++; if(bx == 4 )bx=0;       /* for testing */

    /* if we are allowing the node to die, kill it */
    if( !bx ) usrfree( key, data );

    return bx;  /* Allow the caller to  kill this nodes data + key */
}

/*
 *       Hash test program : use 'sfxhash 1000 50000' to stress the Auto_NodeRecover feature
 */
int main ( int argc, char ** argv )
{
    int             i;
    SFXHASH      * t;
    SFXHASH_NODE * n;
    char            strkey[256], strdata[256], * p;
    int             num = 100;
    int             mem = 0;

    memset(strkey,0,20);
    memset(strdata,0,20);

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

    if( argc > 2 )
    {
        mem = atoi(argv[2]);
    }

    /* Create a Hash Table */
    t = sfxhash_new( 100,        /* one row per element in table, when possible */
                     20,        /* key size :  padded with zeros */ 
                     20,        /* data size:  padded with zeros */ 
                     mem,       /* max bytes,  0=no max */  
                     1,         /* enable AutoNodeRecovery */
                     anrfree,   /* provide a function to let user know we want to kill a node */
                     usrfree, /* provide a function to release user memory */
                     1);      /* Recycle nodes */
    if(!t)
    {
        printf("Low Memory!\n");
        exit(0);
    }
    /* Add Nodes to the Hash Table */
    for(i=0;i<num;i++) 
    {
        sprintf(strkey, "KeyWord%5.5d",i+1);
        sprintf(strdata,"KeyWord%5.5d",i+1);
        //strupr(strdata);
        sfxhash_add( t, strkey  /* user key */ ,  strdata /* user data */ );
    }  

    /* Find and Display Nodes in the Hash Table */
    printf("\n** FIND KEY TEST\n");
    for(i=0;i<num;i++) 
    {
        sprintf(strkey,"KeyWord%5.5d",i+1);

        p = (char*) sfxhash_find( t, strkey );

        if(p)printf("Hash-key=%*s, data=%*s\n", strlen(strkey),strkey, strlen(strkey), p );
    }  

    /* Show memcap memory */
    printf("\n...******\n");
    sfmemcap_showmem(&t->mc);
    printf("...******\n");

    /* Display All Nodes in the Hash Table findfirst/findnext */
    printf("\n...FINDFIRST / FINDNEXT TEST\n");
    for( n  = sfxhash_findfirst(t); 
         n != 0; 
         n  = sfxhash_findnext(t) )
    {
        printf("hash-findfirst/next: n=%x, key=%s, data=%s\n", n, n->key, n->data );

        /*
          remove node we are looking at, this is first/next safe.
        */
        if( sfxhash_remove(t,n->key) ) 
        {
            printf("...ERROR: Could not remove the key node!\n");
        }
        else  
        {
            printf("...key node removed\n");
        }
    }

    printf("...Auto-Node-Recovery: %d recycle attempts, %d completions.\n",t->anr_tries,t->anr_count);

    /* Free the table and it's user data */
    printf("...sfxhash_delete\n");

    sfxhash_delete( t );
   
    printf("\nnormal pgm finish\n\n");

    return 0;
}
#endif