Generic hash table committed

[Russ Allbery]

I've just committed a generic hash table implementation to CURRENT that
should be able to handle arbitrary keys and values (the only constraint is
that the key must be recoverable from the value via some means that is
implementable by a callback function that's passed to hash_create, so for
most purposes the values will need to be structs that include the key).
I've also written and included a test suite.

This code isn't actually being used anywhere yet, but I want to use it
both as the basis of the new configuration file parser and to replace the
various ad hoc hash tables in various parts of INN, some of which are
badly sized.  (People running tradspool with a lot of newsgroups will
wince when they see the size of the hash table that the current backend
uses.)

Here's the interface; let me know if you have any additional comments or
suggestions (I know that it needs more documentation and I'll work on
that).

/*  $Id: hashtab.h,v 1.1 2001/02/08 02:24:20 rra Exp $
**
**  Generic hash table interface.
**
**  Written by Russ Allbery <rra at stanford.edu>
**  This work is hereby placed in the public domain by its author.
**
**  A hash table takes a hash function that acts on keys, a function to
**  extract the key from a data item stored in a hash, a function that takes
**  a key and a data item and returns true if the key matches, and a
**  function to be called on any data item being deleted from the hash.
**
**  hash_create creates a hash and hash_free frees all the space allocated
**  by one.  hash_insert, hash_replace, and hash_delete modify it, and
**  hash_lookup extracts values.  hash_traverse can be used to walk the
**  hash, and hash_searches, hash_collisions, and hash_expansions extract
**  performance and debugging statistics.
*/

#ifndef INN_HASHTAB_H
#define INN_HASHTAB_H 1

#include <inn/defines.h>

BEGIN_DECLS

/* The layout of this struct is entirely internal to the implementation. */
struct hash;

/* Data types for function pointers used by the hash table interface. */
typedef unsigned long (*hash_func)(const void *);
typedef const void * (*hash_key_func)(const void *);
typedef bool (*hash_equal_func)(const void *, const void *);
typedef void (*hash_delete_func)(void *);
typedef void (*hash_traverse_func)(void *, void *);

/* Generic hash table interface. */
struct hash *   hash_create(size_t, hash_func, hash_key_func,
                            hash_equal_func, hash_delete_func);
void            hash_free(struct hash *);
void *          hash_lookup(struct hash *, const void *key);
bool            hash_insert(struct hash *, const void *key, void *datum);
bool            hash_replace(struct hash *, const void *key, void *datum);
bool            hash_delete(struct hash *, const void *key);
void            hash_traverse(struct hash *, hash_traverse_func, void *);
unsigned long   hash_searches(struct hash *);
unsigned long   hash_collisions(struct hash *);
unsigned long   hash_expansions(struct hash *);

/* Hash functions available for callers. */
unsigned long   hash_string(const void *);

/* Functions useful for constructing new hashes. */
unsigned long   hash_lookup2(const char *, size_t, unsigned long partial);

END_DECLS

#endif /* INN_HASHTAB_H */

-- 
Russ Allbery (rra at stanford.edu)             <http://www.eyrie.org/~eagle/>