diff options
Diffstat (limited to 'doc/crypto/lhash.pod')
| -rw-r--r-- | doc/crypto/lhash.pod | 244 |
1 files changed, 126 insertions, 118 deletions
diff --git a/doc/crypto/lhash.pod b/doc/crypto/lhash.pod index dcdbb43a8ed6..73a19b6c7e56 100644 --- a/doc/crypto/lhash.pod +++ b/doc/crypto/lhash.pod @@ -8,18 +8,20 @@ lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall, lh_doall_arg, lh_e #include <openssl/lhash.h> - LHASH *lh_new(LHASH_HASH_FN_TYPE hash, LHASH_COMP_FN_TYPE compare); - void lh_free(LHASH *table); + DECLARE_LHASH_OF(<type>); - void *lh_insert(LHASH *table, void *data); - void *lh_delete(LHASH *table, void *data); - void *lh_retrieve(LHASH *table, void *data); + LHASH *lh_<type>_new(); + void lh_<type>_free(LHASH_OF(<type> *table); - void lh_doall(LHASH *table, LHASH_DOALL_FN_TYPE func); - void lh_doall_arg(LHASH *table, LHASH_DOALL_ARG_FN_TYPE func, - void *arg); + <type> *lh_<type>_insert(LHASH_OF(<type> *table, <type> *data); + <type> *lh_<type>_delete(LHASH_OF(<type> *table, <type> *data); + <type> *lh_retrieve(LHASH_OF<type> *table, <type> *data); - int lh_error(LHASH *table); + void lh_<type>_doall(LHASH_OF(<type> *table, LHASH_DOALL_FN_TYPE func); + void lh_<type>_doall_arg(LHASH_OF(<type> *table, LHASH_DOALL_ARG_FN_TYPE func, + <type2>, <type2> *arg); + + int lh_<type>_error(LHASH_OF(<type> *table); typedef int (*LHASH_COMP_FN_TYPE)(const void *, const void *); typedef unsigned long (*LHASH_HASH_FN_TYPE)(const void *); @@ -28,113 +30,115 @@ lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall, lh_doall_arg, lh_e =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; +This library implements type-checked dynamic hash tables. The hash +table entries can be arbitrary structures. Usually they consist of key +and value fields. + +lh_<type>_new() creates a new B<LHASH_OF(<type>> 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_<type>_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(name, o_type) \ + unsigned long name##_LHASH_HASH(const void *); + #define IMPLEMENT_LHASH_HASH_FN(name, o_type) \ + unsigned long name##_LHASH_HASH(const void *arg) { \ + const o_type *a = arg; \ + return name##_hash(a); } + #define LHASH_HASH_FN(name) name##_LHASH_HASH + + #define DECLARE_LHASH_COMP_FN(name, o_type) \ + int name##_LHASH_COMP(const void *, const void *); + #define IMPLEMENT_LHASH_COMP_FN(name, o_type) \ + int name##_LHASH_COMP(const void *arg1, const void *arg2) { \ + const o_type *a = arg1; \ + const o_type *b = arg2; \ + return name##_cmp(a,b); } + #define LHASH_COMP_FN(name) name##_LHASH_COMP + + #define DECLARE_LHASH_DOALL_FN(name, o_type) \ + void name##_LHASH_DOALL(void *); + #define IMPLEMENT_LHASH_DOALL_FN(name, o_type) \ + void name##_LHASH_DOALL(void *arg) { \ + o_type *a = arg; \ + name##_doall(a); } + #define LHASH_DOALL_FN(name) name##_LHASH_DOALL + + #define DECLARE_LHASH_DOALL_ARG_FN(name, o_type, a_type) \ + void name##_LHASH_DOALL_ARG(void *, void *); + #define IMPLEMENT_LHASH_DOALL_ARG_FN(name, o_type, a_type) \ + void name##_LHASH_DOALL_ARG(void *arg1, void *arg2) { \ + o_type *a = arg1; \ + a_type *b = arg2; \ + name##_doall_arg(a, b); } + #define LHASH_DOALL_ARG_FN(name) 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); + 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 *); + static IMPLEMENT_LHASH_HASH_FN(stuff, STUFF); + static IMPLEMENT_LHASH_COMP_FN(stuff, 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_OF(STUFF) *hashtable = lh_STUFF_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_<type>_free() frees the B<LHASH_OF(<type>> structure +B<table>. Allocated hash table entries will not be freed; consider +using lh_<type>_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_<type>_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_<type>_insert() stores pointers, the +data are not copied. -lh_delete() deletes an entry from B<table>. +lh_<type>_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 +lh_<type>_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: +lh_<type>_doall() will, for every entry in the hash table, call +B<func> with the data item as its parameter. For lh_<type>_doall() +and lh_<type>_doall_arg(), function pointer casting should be avoided +in the callbacks (see B<NOTE>) - instead use the declare/implement +macros to create type-checked 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); + void STUFF_cleanup_doall(STUFF *a); /* Implement a prototype-compatible wrapper for "STUFF_cleanup" */ - IMPLEMENT_LHASH_DOALL_FN(STUFF_cleanup, STUFF *) + 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)); + lh_STUFF_doall(hashtable, LHASH_DOALL_FN(STUFF_cleanup)); /* Then the hash table itself can be deallocated */ - lh_free(hashtable); + lh_STUFF_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 @@ -145,51 +149,52 @@ 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): +lh_<type>_doall_arg() is the same as lh_<type>_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); + void STUFF_print_doall_arg(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 *) + static IMPLEMENT_LHASH_DOALL_ARG_FN(STUFF, 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_STUFF_doall_arg(hashtable, LHASH_DOALL_ARG_FN(STUFF_print), BIO, + logging_bio); -lh_error() can be used to determine if an error occurred in the last -operation. lh_error() is a macro. +lh_<type>_error() can be used to determine if an error occurred in the last +operation. lh_<type>_error() is a macro. =head1 RETURN VALUES -lh_new() returns B<NULL> on error, otherwise a pointer to the new +lh_<type>_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 +When a hash table entry is replaced, lh_<type>_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 +lh_<type>_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, +lh_<type>_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 +lh_<type>_error() returns 1 if an error occurred in the last operation, 0 otherwise. -lh_free(), lh_doall() and lh_doall_arg() return no values. +lh_<type>_free(), lh_<type>_doall() and lh_<type>_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 +to write type-checked 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 @@ -227,7 +232,7 @@ without any "const" qualifiers. =head1 BUGS -lh_insert() returns B<NULL> both for success and error. +lh_<type>_insert() returns B<NULL> both for success and error. =head1 INTERNALS @@ -272,8 +277,8 @@ 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(). +routine would not normally be passed to lh_<type>_new(), rather it would be +used in the function passed to lh_<type>_new(). =head1 SEE ALSO @@ -291,4 +296,7 @@ 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. +In OpenSSL 1.0.0, the lhash interface was revamped for even better +type checking. + =cut |