diff options
Diffstat (limited to 'doc/crypto/lhash.pod')
| -rw-r--r-- | doc/crypto/lhash.pod | 155 |
1 files changed, 0 insertions, 155 deletions
diff --git a/doc/crypto/lhash.pod b/doc/crypto/lhash.pod deleted file mode 100644 index 4e87aee8242..00000000000 --- a/doc/crypto/lhash.pod +++ /dev/null @@ -1,155 +0,0 @@ -=pod - -=head1 NAME - -lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall, -lh_doall_arg, lh_error - dynamic hash table - -=head1 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); - -=head1 DESCRIPTION - -This library implements dynamic hash tables. The hash table entries -can be arbitrary structures. Usually they consist of key and value -fields. - -lh_new() creates a new B<LHASH> structure. B<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. B<compare> takes two arguments, and returns 0 if their keys are -equal, non-zero otherwise. - -lh_free() frees the B<LHASH> structure B<table>. Allocated hash table -entries will not be freed; consider using lh_doall() to deallocate any -remaining entries in the hash table. - -lh_insert() inserts the structure pointed to by B<data> into B<table>. -If there already is an entry with the same key, the old value is -replaced. Note that lh_insert() stores pointers, the data are not -copied. - -lh_delete() deletes an entry from B<table>. - -lh_retrieve() looks up an entry in B<table>. Normally, B<data> is -a structure with the key field(s) set; the function will return a -pointer to a fully populated structure. - -lh_doall() will, for every entry in the hash table, call B<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. lh_free() then cleans up the -'buckets' that point to nothing. When doing this, be careful if you -delete entries from the hash table in B<func>: the table may decrease -in size, moving item that you are currently on down lower in the hash -table. This could cause some entries to be skipped. The best -solution to this problem is to set hash-E<gt>down_load=0 before you -start. This will stop the hash table ever being decreased in size. - -lh_doall_arg() is the same as lh_doall() except that B<func> will -be called with B<arg> as the second argument. - -lh_error() can be used to determine if an error occurred in the last -operation. lh_error() is a macro. - -=head1 RETURN VALUES - -lh_new() returns B<NULL> on error, otherwise a pointer to the new -B<LHASH> structure. - -When a hash table entry is replaced, lh_insert() returns the value -being replaced. B<NULL> is returned on normal operation and on error. - -lh_delete() returns the entry being deleted. B<NULL> is returned if -there is no such value in the hash table. - -lh_retrieve() returns the hash table entry if it has been found, -B<NULL> otherwise. - -lh_error() returns 1 if an error occurred in the last operation, 0 -otherwise. - -lh_free(), lh_doall() and lh_doall_arg() return no values. - -=head1 BUGS - -lh_insert() returns B<NULL> both for success and error. - -=head1 INTERNALS - -The following description is based on the SSLeay documentation: - -The B<lhash> library implements a hash table described in the -I<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 OPENSSL_realloc(). 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 B<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 E<lt> load) =E<gt> -expand. if (hash-E<gt>down_load E<gt> load) =E<gt> contract. The -B<up_load> has a default value of 1 and B<down_load> has a default value -of 2. These numbers can be modified by the application by just -playing with the B<up_load> and B<down_load> variables. The 'load' is -kept in a form which is multiplied by 256. So -hash-E<gt>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-E<gt>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 B<unsigned long> compares and 10 linked list traverses. This -will be much less expensive that 10 calls to you compare function. - -lh_strhash() is a demo string hashing function: - - unsigned long lh_strhash(const char *c); - -Since the B<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 lh_new(). - -=head1 SEE ALSO - -L<lh_stats(3)|lh_stats(3)> - -=head1 HISTORY - -The B<lhash> library is available in all versions of SSLeay and OpenSSL. -lh_error() was added in SSLeay 0.9.1b. - -This manpage is derived from the SSLeay documentation. - -=cut |
