A simple C hash table (open addressing and rehashing) for embedding into projects
C Makefile Meson M4 Shell
Switch branches/tags
Nothing to show
Clone or download
thohel and anholt Use set_foreach instead of rolling our own.
This follows the same pattern as in the hash_table.

(taken from Mesa commit 03e37ec6d720bb5d416e98d6f6d9663086939e4d and
extended to the other loop as well, by anholt)
Latest commit b1590a2 Mar 17, 2018
Permalink
Failed to load latest commit information.
tests Add a testcase for the replacement bug fixed in the previous commit. Mar 2, 2016
.editorconfig Add an editorconfig file for our style. Dec 1, 2017
.gitignore Update .gitignore files Oct 25, 2013
COPYING Initial import of hash_table. Nov 23, 2009
Makefile.am
README Add a set implementation derived from the hash_table implementation. Aug 18, 2011
autogen.sh Remove AM_MAINTAINER_MODE stuff. Nov 23, 2009
configure.ac Add a new int-set structure for a set of integers Oct 25, 2013
fnv_hash.c Add a variant of the hash funciton for arbitrary data. Nov 25, 2014
fnv_hash.h
hash_table.c Add asserts that the user doesn't try to add the empty or deleted val… Dec 1, 2017
hash_table.h Teach the hash table itself to know its own hash function Oct 25, 2013
int-set.c Do a full search when adding new items Mar 2, 2016
int-set.h Add set_contains and int_set_contains functions. Oct 25, 2013
meson.build Add a meson build system. Dec 1, 2017
set.c Use set_foreach instead of rolling our own. Mar 16, 2018
set.h Add missing set_foreach(). Mar 16, 2018

README

This is a simple hash table implementation written in plain old C.  The goal
is for this code to be reusable in many of the projects I've worked on that
could use something better than a poorly-tuned chaining implementation.

A variant is included which is just a set -- hash and key, not hash, key, and
data.

The intention is that users of this code copy it directly into their
repositories, as it's quite small and should see very little development.

The summary of this implementation would be that it uses open addressing
with rehashing.  The table stores for each entry:

 * uint32_t hash of the key.
 * pointer to the key.
 * pointer to the data.

Inserts occur at key->hash % hash->size.  When an insert collides, the insert
steps through the table using the reprobe stride until a free or dead entry is
found.  When an insert occurs with a key matching a key already in the table,
the new data is associated with the key.  Note that old key/data is not freed,
so if memory management is required, do a search before insert.

When searching, the search starts at key % hash_size and continues at
increments of reprobe as with inserts, until the matching entry or an
unallocated entry is found.

When deleting an entry, the entry is marked deleted.

Performance considerations:

 * Only an extra 10% free entries is given at any table size.

	This means that as entries are added, the performance of insertion and
	lookups will degrade as one approaches maximum entries until the table
	gets resized.  Unless an outside entry manager results in a maximum
	number of entries close to the hash table's current size limit, this
	shouldn't be a concern.

 * Repeated deletions fill the table with deleted entry markers.

	This means that a table that was filled, then emptied, will have
	performance for unsuccessful searches in O(hash->size)

	This is worked around in practice by later inserts into a hash table
	with many deletes in it triggering a rehash at the current size.

In addition to the core hash_table implementation, a sample of the FNV-1a
32-bit hash function is included for convenience for those that don't wish
to analyze hash functions on their own.