diff options
Diffstat (limited to 'crypto/openssl/doc/crypto/lhash.pod')
| -rw-r--r-- | crypto/openssl/doc/crypto/lhash.pod | 294 |
1 files changed, 0 insertions, 294 deletions
diff --git a/crypto/openssl/doc/crypto/lhash.pod b/crypto/openssl/doc/crypto/lhash.pod deleted file mode 100644 index dcdbb43a8ed6..000000000000 --- a/crypto/openssl/doc/crypto/lhash.pod +++ /dev/null @@ -1,294 +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(LHASH_HASH_FN_TYPE hash, LHASH_COMP_FN_TYPE compare); - 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, LHASH_DOALL_FN_TYPE func); - void lh_doall_arg(LHASH *table, LHASH_DOALL_ARG_FN_TYPE func, - void *arg); - - int lh_error(LHASH *table); - - typedef int (*LHASH_COMP_FN_TYPE)(const void *, const void *); - typedef unsigned long (*LHASH_HASH_FN_TYPE)(const void *); - typedef void (*LHASH_DOALL_FN_TYPE)(const void *); - typedef void (*LHASH_DOALL_ARG_FN_TYPE)(const void *, const void *); - -=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 to store arbitrary data -entries, and provides the 'hash' and 'compare' callbacks to be used in -organising the table's entries. The B<hash> callback takes a pointer -to a table entry as its argument and returns an unsigned long hash -value for 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 B<compare> callback takes two arguments (pointers -to two hash table entries), and returns 0 if their keys are equal, -non-zero otherwise. If your hash table will contain items of some -particular type and the B<hash> and B<compare> callbacks hash/compare -these types, then the B<DECLARE_LHASH_HASH_FN> and -B<IMPLEMENT_LHASH_COMP_FN> macros can be used to create callback -wrappers of the prototypes required by lh_new(). These provide -per-variable casts before calling the type-specific callbacks written -by the application author. These macros, as well as those used for -the "doall" callbacks, are defined as; - - #define DECLARE_LHASH_HASH_FN(f_name,o_type) \ - unsigned long f_name##_LHASH_HASH(const void *); - #define IMPLEMENT_LHASH_HASH_FN(f_name,o_type) \ - unsigned long f_name##_LHASH_HASH(const void *arg) { \ - o_type a = (o_type)arg; \ - return f_name(a); } - #define LHASH_HASH_FN(f_name) f_name##_LHASH_HASH - - #define DECLARE_LHASH_COMP_FN(f_name,o_type) \ - int f_name##_LHASH_COMP(const void *, const void *); - #define IMPLEMENT_LHASH_COMP_FN(f_name,o_type) \ - int f_name##_LHASH_COMP(const void *arg1, const void *arg2) { \ - o_type a = (o_type)arg1; \ - o_type b = (o_type)arg2; \ - return f_name(a,b); } - #define LHASH_COMP_FN(f_name) f_name##_LHASH_COMP - - #define DECLARE_LHASH_DOALL_FN(f_name,o_type) \ - void f_name##_LHASH_DOALL(const void *); - #define IMPLEMENT_LHASH_DOALL_FN(f_name,o_type) \ - void f_name##_LHASH_DOALL(const void *arg) { \ - o_type a = (o_type)arg; \ - f_name(a); } - #define LHASH_DOALL_FN(f_name) f_name##_LHASH_DOALL - - #define DECLARE_LHASH_DOALL_ARG_FN(f_name,o_type,a_type) \ - void f_name##_LHASH_DOALL_ARG(const void *, const void *); - #define IMPLEMENT_LHASH_DOALL_ARG_FN(f_name,o_type,a_type) \ - void f_name##_LHASH_DOALL_ARG(const void *arg1, const void *arg2) { \ - o_type a = (o_type)arg1; \ - a_type b = (a_type)arg2; \ - f_name(a,b); } - #define LHASH_DOALL_ARG_FN(f_name) f_name##_LHASH_DOALL_ARG - -An example of a hash table storing (pointers to) structures of type 'STUFF' -could be defined as follows; - - /* Calculates the hash value of 'tohash' (implemented elsewhere) */ - unsigned long STUFF_hash(const STUFF *tohash); - /* Orders 'arg1' and 'arg2' (implemented elsewhere) */ - int STUFF_cmp(const STUFF *arg1, const STUFF *arg2); - /* Create the type-safe wrapper functions for use in the LHASH internals */ - static IMPLEMENT_LHASH_HASH_FN(STUFF_hash, const STUFF *) - static IMPLEMENT_LHASH_COMP_FN(STUFF_cmp, const STUFF *); - /* ... */ - int main(int argc, char *argv[]) { - /* Create the new hash table using the hash/compare wrappers */ - LHASH *hashtable = lh_new(LHASH_HASH_FN(STUFF_hash), - LHASH_COMP_FN(STUFF_cmp)); - /* ... */ - } - -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 (see below). - -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 its parameter. For lh_doall() and lh_doall_arg(), -function pointer casting should be avoided in the callbacks (see -B<NOTE>) - instead, either declare the callbacks to match the -prototype required in lh_new() or use the declare/implement macros to -create type-safe wrappers that cast variables prior to calling your -type-specific callbacks. An example of this is illustrated here where -the callback is used to cleanup resources for items in the hash table -prior to the hashtable itself being deallocated: - - /* Cleans up resources belonging to 'a' (this is implemented elsewhere) */ - void STUFF_cleanup(STUFF *a); - /* Implement a prototype-compatible wrapper for "STUFF_cleanup" */ - IMPLEMENT_LHASH_DOALL_FN(STUFF_cleanup, STUFF *) - /* ... then later in the code ... */ - /* So to run "STUFF_cleanup" against all items in a hash table ... */ - lh_doall(hashtable, LHASH_DOALL_FN(STUFF_cleanup)); - /* Then the hash table itself can be deallocated */ - lh_free(hashtable); - -When doing this, be careful if you delete entries from the hash table -in your callbacks: the table may decrease in size, moving the item -that you are currently on down lower in the hash table - this could -cause some entries to be skipped during the iteration. The second -best solution to this problem is to set hash-E<gt>down_load=0 before -you start (which will stop the hash table ever decreasing in size). -The best solution is probably to avoid deleting items from the hash -table inside a "doall" callback! - -lh_doall_arg() is the same as lh_doall() except that B<func> will be -called with B<arg> as the second argument and B<func> should be of -type B<LHASH_DOALL_ARG_FN_TYPE> (a callback prototype that is passed -both the table entry and an extra argument). As with lh_doall(), you -can instead choose to declare your callback with a prototype matching -the types you are dealing with and use the declare/implement macros to -create compatible wrappers that cast variables before calling your -type-specific callbacks. An example of this is demonstrated here -(printing all hash table entries to a BIO that is provided by the -caller): - - /* Prints item 'a' to 'output_bio' (this is implemented elsewhere) */ - void STUFF_print(const STUFF *a, BIO *output_bio); - /* Implement a prototype-compatible wrapper for "STUFF_print" */ - static IMPLEMENT_LHASH_DOALL_ARG_FN(STUFF_print, const STUFF *, BIO *) - /* ... then later in the code ... */ - /* Print out the entire hashtable to a particular BIO */ - lh_doall_arg(hashtable, LHASH_DOALL_ARG_FN(STUFF_print), logging_bio); - -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 NOTE - -The various LHASH macros and callback types exist to make it possible -to write type-safe code without resorting to function-prototype -casting - an evil that makes application code much harder to -audit/verify and also opens the window of opportunity for stack -corruption and other hard-to-find bugs. It also, apparently, violates -ANSI-C. - -The LHASH code regards table entries as constant data. As such, it -internally represents lh_insert()'d items with a "const void *" -pointer type. This is why callbacks such as those used by lh_doall() -and lh_doall_arg() declare their prototypes with "const", even for the -parameters that pass back the table items' data pointers - for -consistency, user-provided data is "const" at all times as far as the -LHASH code is concerned. However, as callers are themselves providing -these pointers, they can choose whether they too should be treating -all such parameters as constant. - -As an example, a hash table may be maintained by code that, for -reasons of encapsulation, has only "const" access to the data being -indexed in the hash table (ie. it is returned as "const" from -elsewhere in their code) - in this case the LHASH prototypes are -appropriate as-is. Conversely, if the caller is responsible for the -life-time of the data in question, then they may well wish to make -modifications to table item passed back in the lh_doall() or -lh_doall_arg() callbacks (see the "STUFF_cleanup" example above). If -so, the caller can either cast the "const" away (if they're providing -the raw callbacks themselves) or use the macros to declare/implement -the wrapper functions without "const" types. - -Callers that only have "const" access to data they're indexing in a -table, yet declare callbacks without constant types (or cast the -"const" away themselves), are therefore creating their own risks/bugs -without being encouraged to do so by the API. On a related note, -those auditing code should pay special attention to any instances of -DECLARE/IMPLEMENT_LHASH_DOALL_[ARG_]_FN macros that provide types -without any "const" qualifiers. - -=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 your 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. - -In OpenSSL 0.9.7, all lhash functions that were passed function pointers -were changed for better type safety, and the function types LHASH_COMP_FN_TYPE, -LHASH_HASH_FN_TYPE, LHASH_DOALL_FN_TYPE and LHASH_DOALL_ARG_FN_TYPE -became available. - -=cut |