 |
Index for
Section 3 |
|
 |
Alphabetical
listing for L |
|
 |
Bottom of
page |
|
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 useful 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 Communications
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 routine
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 values.
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)
|
Index for
Section 3 |
|
|
Alphabetical
listing for L |
|
 |
Top of
page |
|