sfxhash.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sfxhash.h"

Function Documentation

static int calcNextPrime ( int num ) [static]

Definition at line 142 of file sfxhash.c.
References isPrime().

static int isPrime ( int num ) [static]

Definition at line 129 of file sfxhash.c.

static void movetofront ( SFXHASH * t,

SFXHASH_NODE * n

) [static]

Definition at line 513 of file sfxhash.c.
References _sfxhash_node::rindex, sfxhash_gmovetofront(), sfxhash_link_node(), sfxhash_unlink_node(), and _sfxhash::table.

static void s_free ( SFXHASH * t,

void * p

) [static]

Definition at line 87 of file sfxhash.c.
References _sfxhash::mc, and sfmemcap_free().

static void* s_malloc ( SFXHASH * t,

int n

) [static]

sfxhash.c
A Customized hash table library for storing and accessing key + data pairs.
This table incorporates a memory manager (memcap.c) to provide a memory cap, and an automatic node recovery system for out of memory management. Keys and Data are copied into the hash table during the add operation. The data may be allocated and free'd by the user (by setting the datasize to zero ). A user callback is provided to allow the user to do cleanup whenever a node is released, by either the ANR system or the relase() function.
Users can and should delete nodes when they know they are not needed anymore, but this custom table is designed for the case where nodes are allocated permanently, we have to limit memory, and we wish to recycle old nodes. Many problems have a natural node ageing paradigm working in our favor, so automated node aging makes sense. i.e. thresholding, tcp state.
This hash table maps keys to data. All keys must be unique. Uniqueness is enforcedby the code.
Features:
1) Keys must be fixed length (per table) binary byte sequences. keys are copied during the add function 2) Data must be fixed length (per table) binary byte sequences. data is copied during the add function - if datasize > 0 Data may be managed by the user as well. 3) Table row sizes can be automatically adjusted to the nearest prime number size during table initialization/creation. 4) Memory management includes tracking the size of each allocation, number of allocations, enforcing a memory cap, and automatic node recovery - when memory is low the oldest untouched node is unlinked and recycled for use as a new node.
Per Node Memory Usage: ---------------------- SFXHASH_NODE bytes KEYSIZE bytes [DATASIZE bytes] if datasize > 0 during call to sfxhash_new.
The hash node memory (sfxhash_node,key,and data) is allocated with one call to s_malloc/memcap_alloc.
Copyright (C) 2001 Marc A Norton. Copyright (C) 2003 Sourcefire,Inc.
2003-06-03: cmg - added sfxhash_{l,m}ru to return {least,most} recently used node from the global list

added _anrcount function
changed count function to return unsigned to match structure

2003-06-11: cmg added overhead_bytes + blocks to separate out the memcap constraints from the hash table itself find success v fail
2003-06-19: cmg added
ability to set own hash function ability to set own key cmp function
2003-06-30: rdempster fixed bug in that would anr from the freelist
2005-11-15: modified sfxhash_add to check if 'data' is zero before memcpy'ing. this allows user to pass null for data, and set up the data area themselves after the call - this is much more flexible.
Definition at line 82 of file sfxhash.c.
References _sfxhash::mc, and sfmemcap_alloc().

int sfxhash_add ( SFXHASH * t,

void * key,

void * data

)

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.

Parameters:

t SFXHASH table pointer

key users key pointer

data users data pointer

Returns:
integer

Return values:

SFXHASH_OK success

SFXHASH_INTABLE already in the table, t->cnode points to the node

SFXHASH_NOMEM not enough memory

Definition at line 654 of file sfxhash.c.
References _sfxhash::cnode, _sfxhash::count, _sfxhash_node::data, _sfxhash::datasize, index, _sfxhash_node::key, _sfxhash::keysize, memcpy, _sfxhash_node::rindex, sfxhash_find_node_row(), sfxhash_glink_node(), SFXHASH_INTABLE, sfxhash_link_node(), sfxhash_newnode(), SFXHASH_NOMEM, and SFXHASH_OK.
Referenced by flowcache_newflow(), Frag3NewTracker(), ps_tracker_get(), scoreboard_add(), server_stats_add_ipv4(), server_stats_load(), sfthd_test_gobject(), sfthd_test_object(), and ut_check().

void* sfxhash_alloc ( SFXHASH * t,

unsigned nbytes

)

Definition at line 95 of file sfxhash.c.
References s_malloc().

unsigned sfxhash_anr_count ( SFXHASH * t )

Get the # auto recovery

Parameters:

t SFXHASH table pointer

Definition at line 318 of file sfxhash.c.
References _sfxhash::anr_count.
Referenced by flowcache_stats(), scoreboard_stats(), server_stats(), and ut_stats().

unsigned sfxhash_count ( SFXHASH * t )

Get the # of Nodes in HASH the table

Parameters:

t SFXHASH table pointer

Definition at line 307 of file sfxhash.c.
References _sfxhash::count.
Referenced by CleanHashTable(), flowcache_stats(), Frag3Defrag(), Frag3GetTracker(), PrintSessionCache(), scoreboard_stats(), server_stats(), and ut_stats().

void sfxhash_delete ( SFXHASH * h )

Delete the hash Table
free key's, free node's, and free the users data.

Parameters:

h SFXHASH table pointer

Definition at line 269 of file sfxhash.c.
References _sfxhash_node::data, _sfxhash_node::key, _sfxhash_node::next, _sfxhash::nrows, s_free(), _sfxhash::sfhashfcn, sfhashfcn_free(), _sfxhash::table, and _sfxhash::usrfree.
Referenced by flowcache_destroy(), flowcache_init(), scoreboard_destroy(), server_stats_destroy(), server_stats_init(), and ut_destroy().

void* sfxhash_find ( SFXHASH * t,

void * key

)

Find the users data based associated with the key

Parameters:

t SFXHASH table pointer

key users key pointer

Returns:
void* valid pointer to the users data

Return values:

0 node not found

Definition at line 817 of file sfxhash.c.
References _sfxhash_node::data, NULL, and sfxhash_find_node_row().
Referenced by flowcache_find(), Frag3GetTracker(), ps_tracker_get(), scoreboard_find(), and server_stats_hitcount_ipv4().

unsigned sfxhash_find_fail ( SFXHASH * t )

Get the # unsucessful finds

Parameters:

t SFXHASH table pointer

Definition at line 340 of file sfxhash.c.
References _sfxhash::find_fail.
Referenced by scoreboard_stats(), server_stats(), and ut_stats().

SFXHASH_NODE* sfxhash_find_node ( SFXHASH * t,

void * key

)

Find a Node based on the key

Parameters:

t SFXHASH table pointer

key users key pointer

Returns:
SFXHASH_NODE* valid pointer to the hash node

Return values:

0 node not found

Definition at line 800 of file sfxhash.c.
References sfxhash_find_node_row().
Referenced by GetSessionFromHashTable().

static SFXHASH_NODE* sfxhash_find_node_row ( SFXHASH * t,

void * key,

int * rindex

) [static]

Definition at line 600 of file sfxhash.c.
References _sfxhash::find_fail, _sfxhash::find_success, _SFHASHFCN::hash_fcn, index, _sfxhash_node::key, _SFHASHFCN::keycmp_fcn, _sfxhash::keysize, movetofront(), _sfxhash_node::next, _sfxhash::nrows, NULL, _sfxhash::sfhashfcn, _sfxhash::splay, and _sfxhash::table.
Referenced by sfxhash_add(), sfxhash_find(), sfxhash_find_node(), and sfxhash_get_node().

unsigned sfxhash_find_success ( SFXHASH * t )

Get the # sucessful finds

Parameters:

t SFXHASH table pointer

Definition at line 351 of file sfxhash.c.
References _sfxhash::find_success.
Referenced by scoreboard_stats(), server_stats(), and ut_stats().

unsigned sfxhash_find_total ( SFXHASH * t )

Get the # finds

Parameters:

t SFXHASH table pointer

Definition at line 329 of file sfxhash.c.
References _sfxhash::find_fail, and _sfxhash::find_success.
Referenced by scoreboard_stats(), server_stats(), and ut_stats().

SFXHASH_NODE* sfxhash_findfirst ( SFXHASH * t )

Find and return the first hash table node

Parameters:

t SFXHASH table pointer

Returns:
0 failed

Return values:

!0 valid SFXHASH_NODE *

Definition at line 1079 of file sfxhash.c.
References _sfxhash::cnode, _sfxhash::crow, _sfxhash::nrows, NULL, sfxhash_next(), and _sfxhash::table.

SFXHASH_NODE* sfxhash_findnext ( SFXHASH * t )

Find and return the next hash table node

Parameters:

t SFXHASH table pointer

Returns:
0 failed

Return values:

!0 valid SFXHASH_NODE *

Definition at line 1108 of file sfxhash.c.
References _sfxhash::cnode, NULL, and sfxhash_next().

void sfxhash_free ( SFXHASH * t,

void * p

)

Definition at line 99 of file sfxhash.c.
References s_free().

int sfxhash_free_node ( SFXHASH * t,

SFXHASH_NODE * hnode

)

Definition at line 984 of file sfxhash.c.
References _sfxhash::count, _sfxhash_node::data, _sfxhash_node::key, _sfxhash::recycle_nodes, s_free(), sfxhash_gunlink_node(), SFXHASH_OK, sfxhash_save_free_node(), sfxhash_unlink_node(), and _sfxhash::usrfree.
Referenced by Frag3Expire(), and sfxhash_remove().

static SFXHASH_NODE* sfxhash_get_free_node ( SFXHASH * t ) [static]

Definition at line 405 of file sfxhash.c.
References _sfxhash::fhead, _sfxhash::ftail, _sfxhash_node::gnext, and _sfxhash_node::gprev.
Referenced by sfxhash_newnode().

SFXHASH_NODE* sfxhash_get_node ( SFXHASH * t,

void * key

)

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.

Parameters:

t SFXHASH table pointer

key users key pointer

Returns:
integer

Return values:

SFXHASH_OK success

SFXHASH_INTABLE already in the table, t->cnode points to the node

SFXHASH_NOMEM not enough memory

Definition at line 733 of file sfxhash.c.
References _sfxhash::cnode, _sfxhash::count, _sfxhash_node::data, _sfxhash::datasize, index, _sfxhash_node::key, _sfxhash::keysize, memcpy, NULL, _sfxhash_node::rindex, sfxhash_find_node_row(), sfxhash_glink_node(), sfxhash_link_node(), and sfxhash_newnode().
Referenced by flowcache_newflow(), Frag3NewTracker(), and GetNewSession().

SFXHASH_NODE* sfxhash_ghead ( SFXHASH * t )

Get the HEAD of the in use list

Parameters:

t table pointer

Returns:
the head of the list or NULL

Definition at line 837 of file sfxhash.c.
References _sfxhash::ghead, and NULL.
Referenced by scoreboard_dump(), server_stats_dump(), server_stats_save(), sfxhash_mru(), sfxhash_mru_node(), and unique_tracker_dump().

static void sfxhash_glink_node ( SFXHASH * t,

SFXHASH_NODE * hnode

) [static]

Definition at line 424 of file sfxhash.c.
References _sfxhash::ghead, _sfxhash_node::gnext, _sfxhash_node::gprev, and _sfxhash::gtail.
Referenced by sfxhash_add(), sfxhash_get_node(), and sfxhash_gmovetofront().

void sfxhash_gmovetofront ( SFXHASH * t,

SFXHASH_NODE * hnode

)

Definition at line 462 of file sfxhash.c.
References _sfxhash::ghead, sfxhash_glink_node(), and sfxhash_gunlink_node().
Referenced by CleanHashTable(), Frag3Prune(), and movetofront().

SFXHASH_NODE* sfxhash_gnext ( SFXHASH_NODE * n )

Walk the global list

Parameters:

n current node

Returns:
the next node in the list or NULL when at the end

Definition at line 855 of file sfxhash.c.
References _sfxhash_node::gnext, and NULL.
Referenced by scoreboard_dump(), server_stats_dump(), server_stats_save(), and unique_tracker_dump().

static void sfxhash_gunlink_node ( SFXHASH * t,

SFXHASH_NODE * hnode

) [static]

Definition at line 445 of file sfxhash.c.
References _sfxhash::ghead, _sfxhash_node::gnext, _sfxhash_node::gprev, and _sfxhash::gtail.
Referenced by sfxhash_free_node(), sfxhash_gmovetofront(), and sfxhash_newnode().

static void sfxhash_link_node ( SFXHASH * t,

SFXHASH_NODE * hnode

) [static]

Definition at line 475 of file sfxhash.c.
References _sfxhash_node::next, _sfxhash_node::prev, _sfxhash_node::rindex, and _sfxhash::table.
Referenced by movetofront(), sfxhash_add(), and sfxhash_get_node().

void* sfxhash_lru ( SFXHASH * t )

Return the least recently used data from the global list

Parameters:

t SFXHASH table pointer

Returns:
void* valid pointer to the users data

Return values:

0 node not found

Definition at line 896 of file sfxhash.c.
References _sfxhash_node::data, _sfxhash::gtail, and NULL.
Referenced by CleanHashTable(), flowcache_lru(), Frag3Expire(), and scoreboard_lru().

SFXHASH_NODE* sfxhash_lru_node ( SFXHASH * t )

Return the least recently used node from the global list

Parameters:

t SFXHASH table pointer

Returns:
SFXHASH_NODE* valid pointer to a node

Return values:

0 node not found

Definition at line 937 of file sfxhash.c.
References _sfxhash::gtail, and NULL.
Referenced by CleanHashTable(), Frag3Expire(), and Frag3Prune().

unsigned sfxhash_maxdepth ( SFXHASH * t )

Get some hash table statistics. NOT FOR REAL TIME USE.

Parameters:

t SFXHASH table pointer

filled how many

Returns:
max depth of the table

Definition at line 958 of file sfxhash.c.
References _sfxhash_node::next, _sfxhash::nrows, NULL, and _sfxhash::table.
Referenced by flowcache_stats().

void* sfxhash_mru ( SFXHASH * t )

Return the most recently used data from the global list

Parameters:

t SFXHASH table pointer

Returns:
void* valid pointer to the users data

Return values:

0 node not found

Definition at line 875 of file sfxhash.c.
References _sfxhash_node::data, NULL, and sfxhash_ghead().
Referenced by flowcache_mru(), ps_tracker_get(), PurgeSessionCache(), scoreboard_mru(), and server_stats_add_ipv4().

SFXHASH_NODE* sfxhash_mru_node ( SFXHASH * t )

Return the most recently used node from the global list

Parameters:

t SFXHASH table pointer

Returns:
SFXHASH_NODE* valid pointer to a node

Return values:

0 node not found

Definition at line 916 of file sfxhash.c.
References NULL, and sfxhash_ghead().

SFXHASH* sfxhash_new ( int nrows,

int keysize,

int datasize,

int maxmem,

int anr_flag,

int(*)(void *key, void *data) anrfree,

int(*)(void *key, void *data) usrfree,

int recycle_flag

)

Create a new hash table
By default, this will "splay" nodes to the top of a free list.

Parameters:

nrows number of rows in hash table

keysize key size in bytes, same for all keys

datasize datasize in bytes, zero indicates user manages data

maxmem maximum memory to use in bytes

anr_flag Automatic Node Recovery boolean flag

anrfree users Automatic Node Recovery memory release function

usrfree users standard memory release function

Returns:
SFXHASH*

Return values:

0 out of memory

!0 Valid SFXHASH pointer

Definition at line 175 of file sfxhash.c.
References _sfxhash::anr_count, _sfxhash::anr_flag, _sfxhash::anr_tries, _sfxhash::anrfree, calcNextPrime(), _sfxhash::cnode, _sfxhash::count, _sfxhash::crow, _sfxhash::datasize, _sfxhash::find_fail, _sfxhash::find_success, _sfxhash::ghead, _sfxhash::gtail, _sfxhash::keysize, _sfxhash::mc, MEMCAP::memused, MEMCAP::nblocks, _sfxhash::nrows, _sfxhash::overhead_blocks, _sfxhash::overhead_bytes, _sfxhash::recycle_nodes, s_malloc(), _sfxhash::sfhashfcn, sfhashfcn_new(), sfmemcap_init(), _sfxhash::splay, _sfxhash::table, and _sfxhash::usrfree.
Referenced by flowcache_init(), Frag3GlobalInit(), InitSessionCache(), ps_init(), scoreboard_init(), server_stats_init(), sfthd_new(), and ut_init().

static SFXHASH_NODE* sfxhash_newnode ( SFXHASH * t ) [static]

Definition at line 540 of file sfxhash.c.
References _sfxhash::anr_count, _sfxhash::anr_flag, _sfxhash::anr_tries, _sfxhash::anrfree, _sfxhash::count, _sfxhash_node::data, _sfxhash::datasize, _sfxhash_node::gprev, _sfxhash::gtail, _sfxhash_node::key, _sfxhash::keysize, s_malloc(), sfxhash_get_free_node(), sfxhash_gunlink_node(), and sfxhash_unlink_node().
Referenced by sfxhash_add(), and sfxhash_get_node().

static void sfxhash_next ( SFXHASH * t ) [static]

Definition at line 1047 of file sfxhash.c.
References _sfxhash::cnode, _sfxhash::crow, _sfxhash_node::next, _sfxhash::nrows, and _sfxhash::table.
Referenced by sfxhash_findfirst(), and sfxhash_findnext().

unsigned sfxhash_overhead_blocks ( SFXHASH * t )

Get the # of overhead blocks

Parameters:

t SFXHASH table pointer

Definition at line 376 of file sfxhash.c.
References _sfxhash::overhead_blocks.
Referenced by flowcache_overhead_blocks().

unsigned sfxhash_overhead_bytes ( SFXHASH * t )

Get the # of overhead bytes

Parameters:

t SFXHASH table pointer

Definition at line 365 of file sfxhash.c.
References _sfxhash::overhead_bytes.
Referenced by flowcache_overhead_bytes(), scoreboard_overhead_bytes(), scoreboard_stats(), server_stats_overhead_bytes(), and ut_overhead_bytes().

int sfxhash_remove ( SFXHASH * t,

void * key

)

Remove a Key + Data Pair from the table.

Parameters:

t SFXHASH table pointer

key users key pointer

Returns:
0 success

Return values:

!0 failed

Definition at line 1019 of file sfxhash.c.
References _SFHASHFCN::hash_fcn, index, _sfxhash_node::key, _SFHASHFCN::keycmp_fcn, _sfxhash::keysize, _sfxhash_node::next, _sfxhash::nrows, _sfxhash::sfhashfcn, SFXHASH_ERR, sfxhash_free_node(), and _sfxhash::table.
Referenced by flowcache_releaseflow(), Frag3RemoveTracker(), RemoveSessionFromHashTable(), scoreboard_remove(), and server_stats_remove_ipv4().

static void sfxhash_save_free_node ( SFXHASH * t,

SFXHASH_NODE * hnode

) [static]

Definition at line 385 of file sfxhash.c.
References _sfxhash::fhead, _sfxhash::ftail, _sfxhash_node::gnext, and _sfxhash_node::gprev.
Referenced by sfxhash_free_node().

int sfxhash_set_keyops ( SFXHASH * h,

unsigned(*)(SFHASHFCN *p, unsigned char *d, int n) hash_fcn,

int(*)(const void *s1, const void *s2, size_t n) keycmp_fcn

)

Make sfhashfcn use a separate set of operators for the backend.

Parameters:

h sfhashfcn ptr

hash_fcn user specified hash function

keycmp_fcn user specified key comparisoin function

Definition at line 1135 of file sfxhash.c.
References _sfxhash::sfhashfcn, and sfhashfcn_set_keyops().
Referenced by flowcache_init().

void sfxhash_splaymode ( SFXHASH * t,

int n

)

Set Splay mode : Splays nodes to front of list on each access

Parameters:

t SFXHASH table pointer

n boolean flag toggles splaying of hash nodes

Definition at line 255 of file sfxhash.c.
References _sfxhash::splay.

static void sfxhash_unlink_node ( SFXHASH * t,

SFXHASH_NODE * hnode

) [static]

Definition at line 494 of file sfxhash.c.
References _sfxhash_node::next, _sfxhash_node::prev, _sfxhash_node::rindex, and _sfxhash::table.
Referenced by movetofront(), sfxhash_free_node(), and sfxhash_newnode().

Generated on Sun May 14 14:51:26 2006 by

1.4.2


Functions
static void *	s_malloc (SFXHASH *t, int n)
static void	s_free (SFXHASH t, void p)
void *	sfxhash_alloc (SFXHASH *t, unsigned nbytes)
void	sfxhash_free (SFXHASH t, void p)
static int	isPrime (int num)
static int	calcNextPrime (int num)
SFXHASH *	sfxhash_new (int nrows, int keysize, int datasize, int maxmem, int anr_flag, int(anrfree)(void key, void data), int(usrfree)(void key, void data), int recycle_flag)
void	sfxhash_splaymode (SFXHASH *t, int n)
void	sfxhash_delete (SFXHASH *h)
unsigned	sfxhash_count (SFXHASH *t)
unsigned	sfxhash_anr_count (SFXHASH *t)
unsigned	sfxhash_find_total (SFXHASH *t)
unsigned	sfxhash_find_fail (SFXHASH *t)
unsigned	sfxhash_find_success (SFXHASH *t)
unsigned	sfxhash_overhead_bytes (SFXHASH *t)
unsigned	sfxhash_overhead_blocks (SFXHASH *t)
static void	sfxhash_save_free_node (SFXHASH t, SFXHASH_NODE hnode)
static SFXHASH_NODE *	sfxhash_get_free_node (SFXHASH *t)
static void	sfxhash_glink_node (SFXHASH t, SFXHASH_NODE hnode)
static void	sfxhash_gunlink_node (SFXHASH t, SFXHASH_NODE hnode)
void	sfxhash_gmovetofront (SFXHASH t, SFXHASH_NODE hnode)
static void	sfxhash_link_node (SFXHASH t, SFXHASH_NODE hnode)
static void	sfxhash_unlink_node (SFXHASH t, SFXHASH_NODE hnode)
static void	movetofront (SFXHASH t, SFXHASH_NODE n)
static SFXHASH_NODE *	sfxhash_newnode (SFXHASH *t)
static SFXHASH_NODE *	sfxhash_find_node_row (SFXHASH t, void key, int *rindex)
int	sfxhash_add (SFXHASH t, void key, void *data)
SFXHASH_NODE *	sfxhash_get_node (SFXHASH t, void key)
SFXHASH_NODE *	sfxhash_find_node (SFXHASH t, void key)
void *	sfxhash_find (SFXHASH t, void key)
SFXHASH_NODE *	sfxhash_ghead (SFXHASH *t)
SFXHASH_NODE *	sfxhash_gnext (SFXHASH_NODE *n)
void *	sfxhash_mru (SFXHASH *t)
void *	sfxhash_lru (SFXHASH *t)
SFXHASH_NODE *	sfxhash_mru_node (SFXHASH *t)
SFXHASH_NODE *	sfxhash_lru_node (SFXHASH *t)
unsigned	sfxhash_maxdepth (SFXHASH *t)
int	sfxhash_free_node (SFXHASH t, SFXHASH_NODE hnode)
int	sfxhash_remove (SFXHASH t, void key)
static void	sfxhash_next (SFXHASH *t)
SFXHASH_NODE *	sfxhash_findfirst (SFXHASH *t)
SFXHASH_NODE *	sfxhash_findnext (SFXHASH *t)
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))

sfxhash.c File Reference

Functions

Function Documentation