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

FreeBSD Manual Pages

  
 
  

home | help
HTABLE(3)			 htable	manual			     HTABLE(3)

NAME
       HTABLE_HEAD,  HTABLE_ENTRY,  HTABLE_SIZE,  HTABLE_COUNT,	 HTABLE_EMPTY,
       HTABLE_COLLS, HTABLE_LOAD, HTABLE_INITIALIZER, HTABLE_INIT, HTABLE_PRO-
       TOTYPE,	HTABLE_GENERATE,  HTABLE_INSERT, HTABLE_REMOVE,	HTABLE_LOOKUP,
       HTABLE_FIRST, HTABLE_NEXT, HTABLE_FOREACH, implementation of  hash  ta-
       bles.

SYNOPSIS
       #include	"htable.h"

       HTABLE_HEAD(NAME, SIZE, TYPE);

       HTABLE_ENTRY(TYPE);

       size_t
       HTABLE_SIZE(HTABLE_HEAD *head);

       uint32_t
       HTABLE_COUNT(HTABLE_HEAD	*head);

       int
       HTABLE_EMPTY(HTABLE_HEAD	*head);

       float
       HTABLE_COLLS(HTABLE_HEAD	*head);

       float
       HTABLE_LOAD(HTABLE_HEAD *head);

       HTABLE_INITIALIZER(HTABLE_HEAD *head);

       HTABLE_INIT(HTABLE_HEAD *head);

       HTABLE_PROTOTYPE(NAME, TYPE);

       HTABLE_GENERATE(NAME, TYPE, KEY,	CMP);

       HTABLE_ENTRY *
       HTABLE_INSERT(NAME, HTABLE_HEAD *head, HTABLE_ENTRY *elm);

       HTABLE_ENTRY *
       HTABLE_REMOVE(NAME, HTABLE_HEAD *head, HTABLE_ENTRY *elm);

       HTABLE_ENTRY *
       HTABLE_LOOKUP(NAME, HTABLE_HEAD *head, HTABLE_ENTRY *elm);

       HTABLE_ENTRY *
       HTABLE_FIRST(NAME, HTABLE_HEAD *head);

       HTABLE_ENTRY *
       HTABLE_NEXT(NAME, HTABLE_HEAD *head, HTABLE_ENTRY *elm);

       HTABLE_FOREACH(HTABLE_ENTRY *elm, NAME, HTABLE_HEAD *head);

DESCRIPTION
       These  macros  define  and operate on a hash table data structure.  The
       following functionalities are supported:

	      1	  Insertion of a new entry in the hash table.

	      2	  Retrieval of an entry	in the hash table.

	      3	  Removal of an	entry from the hash table.

	      4	  Iterating over all entries found in the hash table.

	      5	  Computing the	number of entries found	in the hash table.

	      6	  Computing the	collision percentage for the hash table.

	      7	  Computing the	load percentage	for the	hash table.

       Hash tables are ideal for applications with datasets needing a  lot  of
       adding, searching or removal, as	those are normally constant-time oper-
       ations.	The primary operation it supports  efficiently	is  a  lookup:
       given  a	key (e.g. a person's name), find the corresponding value (e.g.
       that person's telephone number).	It works by transforming the key using
       a  hash	function  into a hash, a number	that is	used as	an index in an
       array to	locate the desired location ("bucket") where the values	should
       be.

       Hash tables support the efficient insertion of new entries, in expected
       O(1) time. The time spent in searching depends on the hash function and
       the  load  of  the  hash	table; both insertion and search approach O(1)
       time with well chosen values and	hashes.

HASH TABLES
       In the macro definitions, TYPE is the name tag of a user	defined	struc-
       ture  that  must	contain	a field	of type	HTABLE_ENTRY.  For example, to
       define a	data structure looking like a phone book that will  be	stored
       in a hash table,	one could write	something like:

	     struct phonebook_s	{
	       char *name, *phone;
	       HTABLE_ENTRY (phonebook_s);
	     };

       The  argument  NAME  in the macro definitions is	the name tag of	a user
       defined structure that must be declared using the  macro	 HTABLE_HEAD()
       as follows:

	     HTABLE_HEAD (NAME,	SIZE, TYPE) hash_table;

       The  argument  NAME has to be a unique name prefix for every hash table
       that is defined.	SIZE is	the number of  buckets	the  hash  table  will
       hold.  A	pointer	to such	a hash table structure could then later	be de-
       fined as:

	     struct NAME *tableptr;

       Once a hash table  was  defined,	 it  must  be  initialized  using  the
       HTABLE_INIT()  macro, head being	a reference to this hash table.	 It is
       also possible to	initialize it statically by using the  HTABLE_INITIAL-
       IZER() macro like this:

	     HTABLE_HEAD (NAME,	SIZE, TYPE) htable =
	       HTABLE_INITIALIZER (&htable);

       In order	to use the functions that manipulate the hash table structure,
       their prototypes	need to	be declared with the HTABLE_PROTOTYPE()	macro,
       where  NAME  is a unique	identifier for this particular hash_table. The
       TYPE argument is	the type of the	structure that is being	managed	by the
       hash table.

       The  function  bodies  are  generated with the HTABLE_GENERATE()	macro,
       which must be used only once.  It takes the same	two first arguments as
       the  HTABLE_PROTOTYPE() macro, and the two last arguments are the names
       of user-defined functions used to extract key information from  a  hash
       table entry and to compare two entries.

       The  function  used  to retrieve	information related to the key given a
       hash table entry	must have the following	prototype:

	void (*key) (HTABLE_ENTRY *elm,	char **key, int	*len);

       where elm is the	given pointer to the hash table	 entry,	 key  and  len
       must  be	 filled	 in with respectively the pointer to the corresponding
       key and with this key's length.

       The function used to compare two	hash tables entries must  follow  this
       prototype:

	int (*cmp) (HTABLE_ENTRY *elm1,	HTABLE_ENTRY *elm2);

       where elm1 and elm2 are the entries to compare.	This function must re-
       turn an integer value, being 0 in case the keys are equal, and a	 value
       different from 0	otherwise.

       See section EXAMPLE for possible	implementations	of such	functions.

       The  HTABLE_INSERT()  macro  inserts  the element elm in	the hash table
       pointed at by head. A pointer to	the element is returned	in case	it was
       successfully  inserted. Otherwise, NULL is returned, meaning the	inser-
       tion did	not occur (e.g.	the element was	already	stored in the hash ta-
       ble).

       The  HTABLE_REMOVE()  macro removes the element elm from	the hash table
       pointed at by head.  The	removed	element	is returned to the user	so  it
       can  be	freed  if necessary. If	the element was	not found, NULL	is re-
       turned.

       The HTABLE_LOOKUP() macro finds the  element  elm  in  the  hash	 table
       pointed	at  by	head. The data corresponding to	the removed element is
       returned	to the user (NULL is returned in  case	the  element  was  not
       found).

       The HTABLE_FIRST() and HTABLE_NEXT() macros can be used to traverse the
       hash table:

	     for (elm =	HTABLE_FIRST (NAME, &head);
		  elm != NULL;
		  elm =	HTABLE_NEXT (NAME, &head, elm))

       Or, for simplicity, one can use the HTABLE_FOREACH() macro:

	     HTABLE_FOREACH (elm, NAME,	&head)

       There are also some macros useful to get	information about a given hash
       table:

       The  HTABLE_SIZE()  macro returns the total number of buckets contained
       in the hash table pointed at by head.

       The HTABLE_COUNT() returns the number of	items contained	 in  the  hash
       table pointed at	by head.

       The HTABLE_COLLS() returns a percentage indicating the collisions (e.g.
       when two	keys hash to the same bucket) there  are  in  the  hash	 table
       pointed at by head.

       The HTABLE_LOAD() macro returns a percentage indicating the load	factor
       (e.g. the number	of filled buckets over the total number	of buckets) of
       the hash	table pointed at by head.

       The HTABLE_EMPTY() macro	should be used to check	wether a hash table is
       empty.

EXAMPLES
       The following example demonstrates how to declare a hash	table.	Values
       are  inserted  into it, and one of them is then retrieved from the hash
       table.  Next, the contents of the hash table are	printed, and one  ele-
       ment  is	 finally removed. Last,	the total number of items contained in
       the hash	table is displayed.

	  #include <stdlib.h>
	  #include <stdio.h>
	  #include <string.h>

	  #include "htable.h"

	  #define HSIZE	 100

	  struct book_s	{
	    char *name,	*phone;
	    HTABLE_ENTRY (book_s);
	  };

	  void
	  extract_key (struct book_s *data, char **key,	int *len)
	  {
	    *key = data->name;
	    *len = strlen (data->name);
	  }

	  int
	  compare (struct book_s *data1, struct	book_s *data2)
	  {
	    const int KEYLEN = strlen (data1->name);

	    if (strlen (data2->name) ==	KEYLEN
		&& !memcmp (data1->name, data2->name, KEYLEN))
	      return 0;
	    else
	      return 1;
	  }

	  int
	  main ()
	  {
	    int	i;
	    struct book_s *elm;
	    struct book_s entries[] = {
	      {"friend1", "555-1111"},
	      {"friend2", "555-2222"},
	      {"person3", "555-3333"},
	      {"person4", "555-4444"}
	    };
	    const int NOENTRIES	= sizeof (entries) / sizeof (struct book_s);

	    HTABLE_HEAD	(pbook,	HSIZE, book_s) htable =
	      HTABLE_INITIALIZER (&htable);

	    HTABLE_GENERATE (pbook, book_s, extract_key, compare);

	    for	(i = 0;	i < NOENTRIES; i++)
	      HTABLE_INSERT (pbook, &htable, &entries[i]);

	    elm	= HTABLE_LOOKUP	(pbook,	&htable, &entries[1]);
	    printf ("friend2's Phone number is:	%s\n", elm->phone);

	    HTABLE_FOREACH (elm, pbook,	&htable)
	      {
		printf ("Entry:\n");
		printf (" name:	%s\n", elm->name);
		printf ("phone:	%s\n", elm->phone);
	      }

	    elm	= HTABLE_REMOVE	(pbook,	&htable, &entries[2]);

	    printf ("Number of items in	hash table: %u\n",
		    HTABLE_COUNT (&htable));

	    return EXIT_SUCCESS;
	  }

NOTES
       If the hash table macros	need to	be used	several	times, it  is  advised
       to  build wrappers around them, as code is inlined and executable could
       have its	size grow needlessly. For example, to remove elements  from  a
       hash  table  and	 free the corresponding	data structure associated with
       it, one could write the following function:

	  /*
	   * Wrapper around the	HTABLE_REMOVE macro.
	   *
	   * A hash table was previously defined using:
	   *	HTABLE_HEAD (my_hash, HSIZE, my_entry) htable =
	   *	  HTABLE_INITIALIZER (&htable);
	   */
	  void
	  htable_free (struct my_hash *ht, struct my_entry *elm)
	  {
	    struct my_entry *removed;

	    removed = HTABLE_REMOVE (my_hash, ht, elm);
	    if (removed	!= NULL)
	      free (removed);
	  }

HASH FUNCTIONS
       By default, Jenkin's hash function "LOOKUP" is used to transform	a  key
       into  a bucket number (reference	can be found in	the SEE	ALSO section).
       However,	other hash functions are available and can be chosen  at  com-
       pile time by defining the HASH_FUNCTION macro.

       The following functions are available:

       HASH_JEN
	      The default hash function, Jenkins' Lookup hash.

       HASH_OAT
	      Jenkins' "One at a time" hash function.

       For  example,  to  specify  that	Jenkins' "One at a time" hash function
       must be used for	the "test" program, one	must compile it	using  a  com-
       mand such as:

	  cc -I/path/to/htable.h -DHASH_FUNCTION=HASH_OAT -o test test.c

       To  determine  the  best	hash function for your key domain, you can use
       the HTABLE_COLLS	and HTABLE_LOAD	macros to compare the  collisions  and
       load factors obtained with the different	hash functions.

SEE ALSO
       Bob  Jenkins' work on hash functions can	be found at: http://burtlebur-
       tle.net/bob/hash/

       Those macros were greatly inspired by the implementations of spray  and
       red-black    trees    found    in    the	  *BSD	 kernels   (see	  file
       /usr/src/sys/sys/tree.h).

AUTHORS
       Frederic	Culot <frederic@culot.org>.

Version	1.2			August 19, 2010			     HTABLE(3)

NAME | SYNOPSIS | DESCRIPTION | HASH TABLES | EXAMPLES | NOTES | HASH FUNCTIONS | SEE ALSO | AUTHORS

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=htable&sektion=3&manpath=FreeBSD+12.0-RELEASE+and+Ports>

home | help