git.ozlabs.org Git - ccan/blob - hash/hash.h

   1 #ifndef CCAN_HASH_H
   2 #define CCAN_HASH_H
   3 #include <stdint.h>
   4 #include <stdlib.h>
   5 #include "config.h"
   6
   7 /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
   8  *
   9  * http://burtleburtle.net/bob/c/lookup3.c
  10  */
  11
  12 /**
  13  * hash - fast hash of an array for internal use
  14  * @p: the array or pointer to first element
  15  * @num: the number of elements to hash
  16  * @base: the base number to roll into the hash (usually 0)
  17  *
  18  * The memory region pointed to by p is combined with the base to form
  19  * a 32-bit hash.
  20  *
  21  * This hash will have different results on different machines, so is
  22  * only useful for internal hashes (ie. not hashes sent across the
  23  * network or saved to disk).
  24  *
  25  * It may also change with future versions: it could even detect at runtime
  26  * what the fastest hash to use is.
  27  *
  28  * See also: hash_stable.
  29  *
  30  * Example:
  31  *      #include "hash/hash.h"
  32  *      #include <err.h>
  33  *      #include <stdio.h>
  34  *
  35  *      // Simple demonstration: idential strings will have the same hash, but
  36  *      // two different strings will probably not.
  37  *      int main(int argc, char *argv[])
  38  *      {
  39  *              uint32_t hash1, hash2;
  40  *
  41  *              if (argc != 3)
  42  *                      err(1, "Usage: %s <string1> <string2>", argv[0]);
  43  *
  44  *              hash1 = hash(argv[1], strlen(argv[1]), 0);
  45  *              hash2 = hash(argv[2], strlen(argv[2]), 0);
  46  *              printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
  47  *              return 0;
  48  *      }
  49  */
  50 #define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base))
  51
  52 /**
  53  * hash_stable - hash of an array for external use
  54  * @p: the array or pointer to first element
  55  * @num: the number of elements to hash
  56  * @base: the base number to roll into the hash (usually 0)
  57  *
  58  * The memory region pointed to by p is combined with the base to form
  59  * a 32-bit hash.
  60  *
  61  * This hash will have the same results on different machines, so can
  62  * be used for external hashes (ie. not hashes sent across the network
  63  * or saved to disk).  The results will not change in future versions
  64  * of this package.
  65  *
  66  * Example:
  67  *      #include "hash/hash.h"
  68  *      #include <err.h>
  69  *      #include <stdio.h>
  70  *
  71  *      int main(int argc, char *argv[])
  72  *      {
  73  *              if (argc != 2)
  74  *                      err(1, "Usage: %s <string-to-hash>", argv[0]);
  75  *
  76  *              printf("Hash stable result is %u\n",
  77  *                     hash_stable(argv[1], strlen(argv[1]), 0));
  78  *              return 0;
  79  *      }
  80  */
  81 #define hash_stable(p, num, base) \
  82         hash_any_stable((p), (num)*sizeof(*(p)), (base))
  83
  84 /**
  85  * hash_u32 - fast hash an array of 32-bit values for internal use
  86  * @key: the array of uint32_t
  87  * @num: the number of elements to hash
  88  * @base: the base number to roll into the hash (usually 0)
  89  *
  90  * The array of uint32_t pointed to by @key is combined with the base
  91  * to form a 32-bit hash.  This is 2-3 times faster than hash() on small
  92  * arrays, but the advantage vanishes over large hashes.
  93  *
  94  * This hash will have different results on different machines, so is
  95  * only useful for internal hashes (ie. not hashes sent across the
  96  * network or saved to disk).
  97  */
  98 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
  99
 100 /* Our underlying operations. */
 101 uint32_t hash_any(const void *key, size_t length, uint32_t base);
 102 uint32_t hash_any_stable(const void *key, size_t length, uint32_t base);
 103
 104 /**
 105  * hash_pointer - hash a pointer for internal use
 106  * @p: the pointer value to hash
 107  * @base: the base number to roll into the hash (usually 0)
 108  *
 109  * The pointer p (not what p points to!) is combined with the base to form
 110  * a 32-bit hash.
 111  *
 112  * This hash will have different results on different machines, so is
 113  * only useful for internal hashes (ie. not hashes sent across the
 114  * network or saved to disk).
 115  *
 116  * Example:
 117  *      #include "hash/hash.h"
 118  *
 119  *      // Code to keep track of memory regions.
 120  *      struct region {
 121  *              struct region *chain;
 122  *              void *start;
 123  *              unsigned int size;
 124  *      };
 125  *      // We keep a simple hash table.
 126  *      static struct region *region_hash[128];
 127  *
 128  *      static void add_region(struct region *r)
 129  *      {
 130  *              unsigned int h = hash_pointer(r->start);
 131  *
 132  *              r->chain = region_hash[h];
 133  *              region_hash[h] = r->chain;
 134  *      }
 135  *
 136  *      static void find_region(const void *start)
 137  *      {
 138  *              struct region *r;
 139  *
 140  *              for (r = region_hash[hash_pointer(start)]; r; r = r->chain)
 141  *                      if (r->start == start)
 142  *                              return r;
 143  *              return NULL;
 144  *      }
 145  */
 146 static inline uint32_t hash_pointer(const void *p, uint32_t base)
 147 {
 148         if (sizeof(p) % sizeof(uint32_t) == 0) {
 149                 /* This convoluted union is the right way of aliasing. */
 150                 union {
 151                         uint32_t u32[sizeof(p) / sizeof(uint32_t)];
 152                         const void *p;
 153                 } u;
 154                 u.p = p;
 155                 return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base);
 156         }
 157         return hash(&p, 1, base);
 158 }
 159 #endif /* HASH_H */