lhash(3)lhash(3)NAME
lhash, lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall,
lh_doall_arg, lh_error - Dynamic hash table
SYNOPSIS
#include <openssl/lhash.h>
LHASH *lh_new(
unsigned long (*hash)(/*void *a*/), int (*compare)(/*void
*a,void *b*/) ); void lh_free(
LHASH *table ); void *lh_insert(
LHASH *table, void *data ); void *lh_delete(
LHASH *table, void *data ); void *lh_retrieve(
LHASH *table, void *data ); void lh_doall(
LHASH *table, void (*func)(/*void *b*/) ); void lh_doall_arg(
LHASH *table, void (*func)(/*void *a,void *b*/), void *arg );
int lh_error(
LHASH *table );
DESCRIPTION
This library implements dynamic hash tables. The hash table entries can
be arbitrary structures. Usually they consist of key and value fields.
The lh_new() function creates a new LHASH structure. The hash takes a
pointer to the structure and returns an unsigned long hash value of its
key field. The hash value is normally truncated to a power of 2, so
make sure that your hash function returns well mixed low order bits.
The compare takes two arguments, and returns 0 if their keys are equal,
non-zero otherwise.
The lh_free() function frees the LHASH structure table. Allocated hash
table entries will not be freed; consider using the lh_doall() function
to deallocate any remaining entries in the hash table.
The lh_insert() function inserts the structure pointed to by data into
table. If there already is an entry with the same key, the old value is
replaced. The lh_insert() function stores pointers; the data are not
copied.
The lh_delete() function deletes an entry from table.
The lh_retrieve() function looks up an entry in table. Normally, data
is a structure with the key field set; the function will return a
pointer to a fully populated structure.
The lh_doall() function will, for every entry in the hash table, call
func with the data item as parameters. This function can be quite use‐
ful when used as follows: void cleanup(STUFF *a) { STUFF_free(a); }
lh_doall(hash,cleanup); lh_free(hash). This can be used to free all
the entries. The lh_free() function then cleans up the 'buckets that
point to nothing. When doing this, be careful if you delete entries
from the hash table in func. The table might decrease in size, moving
items lower in the hash table. This could cause some entries to be
skipped. The best solution to this problem is to set hash->down_load=0
before you start. This will stop the hash table from decreasing in
size.
The lh_doall_arg() function is the same as lh_doall() except that func
will be called with arg as the second argument.
The lh_error() macro can be used to determine if an error occurred in
the last operation.
Internals
The following description is based on the SSLeay documentation:
The lhash library implements a hash table described in the Communica‐
tions of the ACM in 1991. What makes this hash table different is that
as the table fills, the hash table is increased (or decreased) in size
via the OPENSSL_realloc() function. When a resize is done, instead of
all hashes being redistributed over twice as many buckets, one bucket
is split. So when an expand is done, there is only a minimal cost to
redistribute some values. Subsequent inserts will cause more single
bucket redistributions but there will never be a sudden large cost due
to redistributing all the buckets.
The state for a particular hash table is kept in the LHASH structure.
The decision to increase or decrease the hash table size is made
depending on the load of the hash table. The load is the number of
items in the hash table divided by the size of the hash table. The
default values are as follows: if (hash->up_load < load) => expand if
(hash->down_load > load) => contract
The up_load has a default value of 1, and down_load has a default value
of 2. These numbers can be modified by the application by adjusting
the up_load and down_load variables. The load is kept in a form which
is multiplied by 256. So hash->up_load=8*256; will cause a load of 8
to be set.
If you are interested in performance, the field to watch is
num_comp_calls. The hash library keeps track of the hash value for
each item so when a lookup is done, the hashes are compared. If there
is a match, then a full compare is done, and hash->num_comp_calls is
incremented. If num_comp_calls is not equal to num_delete plus
num_retrieve it means that your hash function is generating hashes that
are the same for different values. It is probably worth changing your
hash function if this is the case because even if your hash table has
10 items in a bucket, it can be searched with 10 unsigned long compares
and 10 linked list traverses. This will be much less expensive that 10
calls to your compare function.
The lh_strhash() is a demo string hashing function: unsigned long
lh_strhash(const char *c);
Since the LHASH routines would normally be passed structures, this rou‐
tine would not normally be passed to lh_new(), rather it would be used
in the function passed to the lh_new() function.
RESTRICTIONS
The lh_insert() function returns NULL both for success and error.
RETURN VALUES
The lh_new() function returns NULL on error, otherwise a pointer to the
new LHASH structure.
When a hash table entry is replaced, the lh_insert() function returns
the value being replaced. NULL is returned on normal operation and on
error.
The lh_delete() function returns the entry being deleted. NULL is
returned if there is no such value in the hash table.
The lh_retrieve() function returns the hash table entry if it has been
found, NULL otherwise.
The lh_error() function returns 1 if an error occurred in the last
operation, 0 otherwise.
The lh_free(), lh_doall(), and lh_doall_arg() functions return no val‐
ues.
HISTORY
The lhash library is available in all versions of SSLeay and OpenSSL.
The lh_error() function was added in SSLeay 0.9.1b. This reference page
is derived from the SSLeay documentation.
SEE ALSO
Functions: lh_stats(3)lhash(3)