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

   1 /* CC0 (Public domain) - see LICENSE file for details */
   2 #ifndef CCAN_HASH_H
   3 #define CCAN_HASH_H
   4 #include "config.h"
   5 #include <stdint.h>
   6 #include <stdlib.h>
   7 #include <ccan/build_assert/build_assert.h>
   8
   9 /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  10  *
  11  * http://burtleburtle.net/bob/c/lookup3.c
  12  */
  13
  14 /**
  15  * hash - fast hash of an array for internal use
  16  * @p: the array or pointer to first element
  17  * @num: the number of elements to hash
  18  * @base: the base number to roll into the hash (usually 0)
  19  *
  20  * The memory region pointed to by p is combined with the base to form
  21  * a 32-bit hash.
  22  *
  23  * This hash will have different results on different machines, so is
  24  * only useful for internal hashes (ie. not hashes sent across the
  25  * network or saved to disk).
  26  *
  27  * It may also change with future versions: it could even detect at runtime
  28  * what the fastest hash to use is.
  29  *
  30  * See also: hash64, hash_stable.
  31  *
  32  * Example:
  33  *      #include <ccan/hash/hash.h>
  34  *      #include <err.h>
  35  *      #include <stdio.h>
  36  *      #include <string.h>
  37  *
  38  *      // Simple demonstration: idential strings will have the same hash, but
  39  *      // two different strings will probably not.
  40  *      int main(int argc, char *argv[])
  41  *      {
  42  *              uint32_t hash1, hash2;
  43  *
  44  *              if (argc != 3)
  45  *                      err(1, "Usage: %s <string1> <string2>", argv[0]);
  46  *
  47  *              hash1 = hash(argv[1], strlen(argv[1]), 0);
  48  *              hash2 = hash(argv[2], strlen(argv[2]), 0);
  49  *              printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
  50  *              return 0;
  51  *      }
  52  */
  53 #define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base))
  54
  55 /**
  56  * hash_stable - hash of an array for external use
  57  * @p: the array or pointer to first element
  58  * @num: the number of elements to hash
  59  * @base: the base number to roll into the hash (usually 0)
  60  *
  61  * The array of simple integer types pointed to by p is combined with
  62  * the base to form a 32-bit hash.
  63  *
  64  * This hash will have the same results on different machines, so can
  65  * be used for external hashes (ie. hashes sent across the network or
  66  * saved to disk).  The results will not change in future versions of
  67  * this module.
  68  *
  69  * Note that it is only legal to hand an array of simple integer types
  70  * to this hash (ie. char, uint16_t, int64_t, etc).  In these cases,
  71  * the same values will have the same hash result, even though the
  72  * memory representations of integers depend on the machine
  73  * endianness.
  74  *
  75  * See also:
  76  *      hash64_stable
  77  *
  78  * Example:
  79  *      #include <ccan/hash/hash.h>
  80  *      #include <err.h>
  81  *      #include <stdio.h>
  82  *      #include <string.h>
  83  *
  84  *      int main(int argc, char *argv[])
  85  *      {
  86  *              if (argc != 2)
  87  *                      err(1, "Usage: %s <string-to-hash>", argv[0]);
  88  *
  89  *              printf("Hash stable result is %u\n",
  90  *                     hash_stable(argv[1], strlen(argv[1]), 0));
  91  *              return 0;
  92  *      }
  93  */
  94 #define hash_stable(p, num, base)                                       \
  95         (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4    \
  96                               || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
  97          sizeof(*(p)) == 8 ? hash_stable_64((p), (num), (base))         \
  98          : sizeof(*(p)) == 4 ? hash_stable_32((p), (num), (base))       \
  99          : sizeof(*(p)) == 2 ? hash_stable_16((p), (num), (base))       \
 100          : hash_stable_8((p), (num), (base)))
 101
 102 /**
 103  * hash_u32 - fast hash an array of 32-bit values for internal use
 104  * @key: the array of uint32_t
 105  * @num: the number of elements to hash
 106  * @base: the base number to roll into the hash (usually 0)
 107  *
 108  * The array of uint32_t pointed to by @key is combined with the base
 109  * to form a 32-bit hash.  This is 2-3 times faster than hash() on small
 110  * arrays, but the advantage vanishes over large hashes.
 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 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
 117
 118 /**
 119  * hash_string - very fast hash of an ascii string
 120  * @str: the nul-terminated string
 121  *
 122  * The string is hashed, using a hash function optimized for ASCII and
 123  * similar strings.  It's weaker than the other hash functions.
 124  *
 125  * This hash may have different results on different machines, so is
 126  * only useful for internal hashes (ie. not hashes sent across the
 127  * network or saved to disk).  The results will be different from the
 128  * other hash functions in this module, too.
 129  */
 130 static inline uint32_t hash_string(const char *string)
 131 {
 132         /* This is Karl Nelson <kenelson@ece.ucdavis.edu>'s X31 hash.
 133          * It's a little faster than the (much better) lookup3 hash(): 56ns vs
 134          * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */
 135         uint32_t ret;
 136
 137         for (ret = 0; *string; string++)
 138                 ret = (ret << 5) - ret + *string;
 139
 140         return ret;
 141 }
 142
 143 /**
 144  * hash64 - fast 64-bit hash of an array for internal use
 145  * @p: the array or pointer to first element
 146  * @num: the number of elements to hash
 147  * @base: the 64-bit base number to roll into the hash (usually 0)
 148  *
 149  * The memory region pointed to by p is combined with the base to form
 150  * a 64-bit hash.
 151  *
 152  * This hash will have different results on different machines, so is
 153  * only useful for internal hashes (ie. not hashes sent across the
 154  * network or saved to disk).
 155  *
 156  * It may also change with future versions: it could even detect at runtime
 157  * what the fastest hash to use is.
 158  *
 159  * See also: hash.
 160  *
 161  * Example:
 162  *      #include <ccan/hash/hash.h>
 163  *      #include <err.h>
 164  *      #include <stdio.h>
 165  *      #include <string.h>
 166  *
 167  *      // Simple demonstration: idential strings will have the same hash, but
 168  *      // two different strings will probably not.
 169  *      int main(int argc, char *argv[])
 170  *      {
 171  *              uint64_t hash1, hash2;
 172  *
 173  *              if (argc != 3)
 174  *                      err(1, "Usage: %s <string1> <string2>", argv[0]);
 175  *
 176  *              hash1 = hash64(argv[1], strlen(argv[1]), 0);
 177  *              hash2 = hash64(argv[2], strlen(argv[2]), 0);
 178  *              printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
 179  *              return 0;
 180  *      }
 181  */
 182 #define hash64(p, num, base) hash64_any((p), (num)*sizeof(*(p)), (base))
 183
 184 /**
 185  * hash64_stable - 64 bit hash of an array for external use
 186  * @p: the array or pointer to first element
 187  * @num: the number of elements to hash
 188  * @base: the base number to roll into the hash (usually 0)
 189  *
 190  * The array of simple integer types pointed to by p is combined with
 191  * the base to form a 64-bit hash.
 192  *
 193  * This hash will have the same results on different machines, so can
 194  * be used for external hashes (ie. hashes sent across the network or
 195  * saved to disk).  The results will not change in future versions of
 196  * this module.
 197  *
 198  * Note that it is only legal to hand an array of simple integer types
 199  * to this hash (ie. char, uint16_t, int64_t, etc).  In these cases,
 200  * the same values will have the same hash result, even though the
 201  * memory representations of integers depend on the machine
 202  * endianness.
 203  *
 204  * See also:
 205  *      hash_stable
 206  *
 207  * Example:
 208  *      #include <ccan/hash/hash.h>
 209  *      #include <err.h>
 210  *      #include <stdio.h>
 211  *      #include <string.h>
 212  *
 213  *      int main(int argc, char *argv[])
 214  *      {
 215  *              if (argc != 2)
 216  *                      err(1, "Usage: %s <string-to-hash>", argv[0]);
 217  *
 218  *              printf("Hash stable result is %llu\n",
 219  *                     (long long)hash64_stable(argv[1], strlen(argv[1]), 0));
 220  *              return 0;
 221  *      }
 222  */
 223 #define hash64_stable(p, num, base)                                     \
 224         (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4    \
 225                               || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
 226          sizeof(*(p)) == 8 ? hash64_stable_64((p), (num), (base))       \
 227          : sizeof(*(p)) == 4 ? hash64_stable_32((p), (num), (base))     \
 228          : sizeof(*(p)) == 2 ? hash64_stable_16((p), (num), (base))     \
 229          : hash64_stable_8((p), (num), (base)))
 230
 231
 232 /**
 233  * hashl - fast 32/64-bit hash of an array for internal use
 234  * @p: the array or pointer to first element
 235  * @num: the number of elements to hash
 236  * @base: the base number to roll into the hash (usually 0)
 237  *
 238  * This is either hash() or hash64(), on 32/64 bit long machines.
 239  */
 240 #define hashl(p, num, base)                                             \
 241         (BUILD_ASSERT_OR_ZERO(sizeof(long) == sizeof(uint32_t)          \
 242                               || sizeof(long) == sizeof(uint64_t)) +    \
 243         (sizeof(long) == sizeof(uint64_t)                               \
 244          ? hash64((p), (num), (base)) : hash((p), (num), (base))))
 245
 246 /* Our underlying operations. */
 247 uint32_t hash_any(const void *key, size_t length, uint32_t base);
 248 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base);
 249 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base);
 250 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base);
 251 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base);
 252 uint64_t hash64_any(const void *key, size_t length, uint64_t base);
 253 uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base);
 254 uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base);
 255 uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base);
 256 uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base);
 257
 258 /**
 259  * hash_pointer - hash a pointer for internal use
 260  * @p: the pointer value to hash
 261  * @base: the base number to roll into the hash (usually 0)
 262  *
 263  * The pointer p (not what p points to!) is combined with the base to form
 264  * a 32-bit hash.
 265  *
 266  * This hash will have different results on different machines, so is
 267  * only useful for internal hashes (ie. not hashes sent across the
 268  * network or saved to disk).
 269  *
 270  * Example:
 271  *      #include <ccan/hash/hash.h>
 272  *
 273  *      // Code to keep track of memory regions.
 274  *      struct region {
 275  *              struct region *chain;
 276  *              void *start;
 277  *              unsigned int size;
 278  *      };
 279  *      // We keep a simple hash table.
 280  *      static struct region *region_hash[128];
 281  *
 282  *      static void add_region(struct region *r)
 283  *      {
 284  *              unsigned int h = hash_pointer(r->start, 0);
 285  *
 286  *              r->chain = region_hash[h];
 287  *              region_hash[h] = r->chain;
 288  *      }
 289  *
 290  *      static struct region *find_region(const void *start)
 291  *      {
 292  *              struct region *r;
 293  *
 294  *              for (r = region_hash[hash_pointer(start, 0)]; r; r = r->chain)
 295  *                      if (r->start == start)
 296  *                              return r;
 297  *              return NULL;
 298  *      }
 299  */
 300 static inline uint32_t hash_pointer(const void *p, uint32_t base)
 301 {
 302         if (sizeof(p) % sizeof(uint32_t) == 0) {
 303                 /* This convoluted union is the right way of aliasing. */
 304                 union {
 305                         uint32_t a[sizeof(p) / sizeof(uint32_t)];
 306                         const void *p;
 307                 } u;
 308                 u.p = p;
 309                 return hash_u32(u.a, sizeof(p) / sizeof(uint32_t), base);
 310         } else
 311                 return hash(&p, 1, base);
 312 }
 313 #endif /* HASH_H */