#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 *);
=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
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
=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
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
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.
+
+In OpenSSL 0.9.9, the lhash interface was revamped for even better
+type checking.
+
=cut