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