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