include/inn/hashtab.h

   1 /*  $Id: hashtab.h 5944 2002-12-08 02:33:08Z rra $
   2 **
   3 **  Generic hash table interface.
   4 **
   5 **  Written by Russ Allbery <rra@stanford.edu>
   6 **  This work is hereby placed in the public domain by its author.
   7 **
   8 **  A hash table takes a hash function that acts on keys, a function to
   9 **  extract the key from a data item stored in a hash, a function that takes
  10 **  a key and a data item and returns true if the key matches, and a
  11 **  function to be called on any data item being deleted from the hash.
  12 **
  13 **  hash_create creates a hash and hash_free frees all the space allocated
  14 **  by one.  hash_insert, hash_replace, and hash_delete modify it, and
  15 **  hash_lookup extracts values.  hash_traverse can be used to walk the
  16 **  hash, and hash_count returns the number of elements currently stored in
  17 **  the hash.  hash_searches, hash_collisions, and hash_expansions extract
  18 **  performance and debugging statistics.
  19 */
  20
  21 #ifndef INN_HASHTAB_H
  22 #define INN_HASHTAB_H 1
  23
  24 #include <inn/defines.h>
  25
  26 BEGIN_DECLS
  27
  28 /* The layout of this struct is entirely internal to the implementation. */
  29 struct hash;
  30
  31 /* Data types for function pointers used by the hash table interface. */
  32 typedef unsigned long (*hash_func)(const void *);
  33 typedef const void * (*hash_key_func)(const void *);
  34 typedef bool (*hash_equal_func)(const void *, const void *);
  35 typedef void (*hash_delete_func)(void *);
  36 typedef void (*hash_traverse_func)(void *, void *);
  37
  38 /* Generic hash table interface. */
  39 struct hash *   hash_create(size_t, hash_func, hash_key_func,
  40                             hash_equal_func, hash_delete_func);
  41 void            hash_free(struct hash *);
  42 void *          hash_lookup(struct hash *, const void *key);
  43 bool            hash_insert(struct hash *, const void *key, void *datum);
  44 bool            hash_replace(struct hash *, const void *key, void *datum);
  45 bool            hash_delete(struct hash *, const void *key);
  46 void            hash_traverse(struct hash *, hash_traverse_func, void *);
  47 unsigned long   hash_count(struct hash *);
  48 unsigned long   hash_searches(struct hash *);
  49 unsigned long   hash_collisions(struct hash *);
  50 unsigned long   hash_expansions(struct hash *);
  51
  52 /* Hash functions available for callers. */
  53 unsigned long   hash_string(const void *);
  54
  55 /* Functions useful for constructing new hashes. */
  56 unsigned long   hash_lookup2(const char *, size_t, unsigned long partial);
  57
  58 END_DECLS
  59
  60 #endif /* INN_HASHTAB_H */