Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
LH_NEW(3)		 BSD Library Functions Manual		     LH_NEW(3)

     lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall,
     lh_doall_arg, lh_error -- dynamic hash table

     #include <openssl/lhash.h>


     LHASH *

     lh_<type>_free(LHASH_OF(_type_) *table);

     _type_ *
     lh_<type>_insert(LHASH_OF(_type_) *table, _type_ *data);

     _type_ *
     lh_<type>_delete(LHASH_OF(_type_) *table, _type_ *data);

     _type_ *
     lh_<type>_retrieve(LHASH_OF_type_)	*table,	_type_ *data);

     lh_<type>_doall(LHASH_OF(_type_) *table, LHASH_DOALL_FN_TYPE func);

     lh_<type>_doall_arg(LHASH_OF(_type_) *table,
	 LHASH_DOALL_ARG_FN_TYPE func, _type2_,	_type2_	*arg);

     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 *);

     typedef void
     (*LHASH_DOALL_FN_TYPE)(const void *);

     typedef void
     (*LHASH_DOALL_ARG_FN_TYPE)(const void *, const void *);

     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 LHASH_OF(_type_) structure to store arbi-
     trary data	entries, and provides the hash and compare callbacks to	be
     used in organising	the table's entries.  The 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 compare callback takes two arguments (pointers to	two
     hash table	entries), and returns 0	if their keys are equal, non-zero oth-
     erwise.  If your hash table will contain items of some particular type
     and the hash and compare callbacks	hash and compare these types, then the
     DECLARE_LHASH_HASH_FN() and 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;

       /* Calculate the	hash value of 'tohash' (implemented elsewhere) */
       unsigned	long STUFF_hash(const STUFF *tohash);
       /* Order	'arg1' and 'arg2' (implemented elsewhere) */
       int stuff_cmp(const STUFF *arg1,	const STUFF *arg2);
       /* Create type-safe wrapper functions for use in	the LHASH internals */
       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_OF(STUFF) *hashtable =
	       /* ... */

     lh_<type>_free() frees the	LHASH_OF(_type_) structure 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_<type>_insert()	inserts	the structure pointed to by data into table.
     If	there already is an entry with the same	key, the old value is re-
     placed.  Note that	lh_<type>_insert() stores pointers, the	data are not

     lh_<type>_delete()	deletes	an entry from table.

     lh_<type>_retrieve() looks	up an entry in table.  Normally, data is a
     structure with the	key field(s) set; the function will return a pointer
     to	a fully	populated structure.

     lh_<type>_doall() will, for every entry in	the hash table,	call 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 NOTES) -- instead use the declare/implement	macros to cre-
     ate 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:

       /* Clean	up resources belonging to 'a' (this is implemented elsewhere) */
       void STUFF_cleanup_doall(STUFF *a);
       /* Implement a prototype-compatible wrapper for "STUFF_cleanup" */
	       /* ... then later in the	code ... */
       /* So to	run "STUFF_cleanup" against all	items in a hash	table ... */
       lh_STUFF_doall(hashtable, LHASH_DOALL_FN(STUFF_cleanup));
       /* Then the hash	table itself can be deallocated	*/

     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->down_load=0 before you start (which will
     stop the hash table ever decreasing in size).  The	best solution is prob-
     ably to avoid deleting items from the hash	table inside a doall callback!

     lh_<type>_doall_arg() is the same as lh_<type>_doall() except that	func
     will be called with arg as	the second argument and	func should be of type
     LHASH_DOALL_ARG_FN_TYPE (a	callback prototype that	is passed both the ta-
     ble entry and an extra argument).	As with	lh_<type>_doall(), you can in-
     stead choose to declare your callback with	a prototype matching the types
     you are dealing with and use the declare/implement	macros to create com-
     patible 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):

       /* Print	item 'a' to 'output_bio' (this is implemented elsewhere) */
       void STUFF_print_doall_arg(const	STUFF *a, BIO *output_bio);
       /* Implement a prototype-compatible wrapper for "STUFF_print" */
	       /* ... then later in the	code ... */
       /* Print	out the	entire hashtable to a particular BIO */
       lh_STUFF_doall_arg(hashtable, LHASH_DOALL_ARG_FN(STUFF_print), BIO,

     lh_<type>_error() can be used to determine	if an error occurred in	the
     last operation.  lh_<type>_error()	is a macro.

     lh_<type>_new() returns NULL on error, otherwise a	pointer	to the new
     LHASH structure.

     When a hash table entry is	replaced, lh_<type>_insert() returns the value
     being replaced.  NULL is returned on normal operation and on error.

     lh_<type>_delete()	returns	the entry being	deleted.  NULL is returned if
     there is no such value in the hash	table.

     lh_<type>_retrieve() returns the hash table entry if it has been found,
     or	NULL otherwise.

     lh_<type>_error() returns 1 if an error occurred in the last operation,
     or	0 otherwise.

     The various LHASH macros and callback types exist to make it possible 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 ANSI-C.

     The LHASH code regards table entries as constant data.  As	such, it in-
     ternally represents lh_<type>_insert()'ed items with a const void *
     pointer type.  This is why	callbacks such as those	used by
     lh_<type>_doall() and lh_<type>_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 them-
     selves 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 (i.e. it is	returned as "const" from elsewhere in their
     code) -- in this case the LHASH prototypes	are appropriate	as-is.	Con-
     versely, 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_<type>_doall() or lh_<type>_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	are indexing in	a ta-
     ble, yet declare callbacks	without	constant types (or cast	the "const"
     away themselves), are therefore creating their own	risks/bugs without be-
     ing encouraged to do so by	the API.  On a related note, those auditing
     code should pay special attention to any instances	of DECLARE/IMPLE-
     MENT_LHASH_DOALL_[ARG_]_FN	macros that provide types without any "const"

     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
     reallocarray(3).  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' redistribu-
     tions 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 depend-
     ing 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 just	playing	with the up_load and down_load vari-
     ables.  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 in-
     cremented.	 If num_comp_calls is not equal	to num_delete plus num_re-
     trieve it means that your hash function is	generating hashes that are the
     same for different	values.	 It is probably	worth changing your hash func-
     tion 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.

     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	rou-
     tine would	not normally be	passed to lh_<type>_new(), rather it would be
     used in the function passed to lh_<type>_new().

     crypto(3),	lh_stats(3)

     lh_new(), lh_free(), lh_insert(), lh_delete(), lh_retrieve(), and
     lh_doall()	appeared in SSLeay 0.4 or earlier.  lh_doall_arg() first ap-
     peared in SSLeay 0.5.1.  These functions have been	available since
     OpenBSD 2.4.

     lh_<type>_error() was added in SSLeay 0.9.1b.

     In	OpenSSL	0.9.7, all lhash functions that	were passed function pointers
     were changed for better type safety, and the function types
     LHASH_DOALL_ARG_FN_TYPE became available.

     In	OpenSSL	1.0.0, the lhash interface was revamped	for even better	type

     lh_<type>_insert()	returns	NULL both for success and error.

BSD				March 28, 2020				   BSD


Want to link to this manual page? Use this URL:

home | help