Antonie
hash.h
Go to the documentation of this file.
00001 /* CC0 (Public domain) - see LICENSE file for details */
00002 #ifndef CCAN_HASH_H
00003 #define CCAN_HASH_H
00004 
00005 #include "config.h"
00006 #include <stdint.h>
00007 #include <stdlib.h>
00008 #include <ccan/build_assert/build_assert.h>
00009 
00010 /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
00011  * 
00012  * http://burtleburtle.net/bob/c/lookup3.c
00013  */
00014 
00054 #define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base))
00055 
00095 #define hash_stable(p, num, base)                                       \
00096         (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4    \
00097                               || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
00098          sizeof(*(p)) == 8 ? hash_stable_64((p), (num), (base))         \
00099          : sizeof(*(p)) == 4 ? hash_stable_32((p), (num), (base))       \
00100          : sizeof(*(p)) == 2 ? hash_stable_16((p), (num), (base))       \
00101          : hash_stable_8((p), (num), (base)))
00102 
00117 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
00118 
00131 static inline uint32_t hash_string(const char *string)
00132 {
00133         /* This is Karl Nelson <kenelson@ece.ucdavis.edu>'s X31 hash.
00134          * It's a little faster than the (much better) lookup3 hash(): 56ns vs
00135          * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */
00136         uint32_t ret;
00137 
00138         for (ret = 0; *string; string++)
00139                 ret = (ret << 5) - ret + *string;
00140 
00141         return ret;
00142 }
00143 
00183 #define hash64(p, num, base) hash64_any((p), (num)*sizeof(*(p)), (base))
00184 
00224 #define hash64_stable(p, num, base)                                     \
00225         (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4    \
00226                               || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
00227          sizeof(*(p)) == 8 ? hash64_stable_64((p), (num), (base))       \
00228          : sizeof(*(p)) == 4 ? hash64_stable_32((p), (num), (base))     \
00229          : sizeof(*(p)) == 2 ? hash64_stable_16((p), (num), (base))     \
00230          : hash64_stable_8((p), (num), (base)))
00231 
00232 
00241 #define hashl(p, num, base)                                             \
00242         (BUILD_ASSERT_OR_ZERO(sizeof(long) == sizeof(uint32_t)          \
00243                               || sizeof(long) == sizeof(uint64_t)) +    \
00244         (sizeof(long) == sizeof(uint64_t)                               \
00245          ? hash64((p), (num), (base)) : hash((p), (num), (base))))
00246 
00247 /* Our underlying operations. */
00248 uint32_t hash_any(const void *key, size_t length, uint32_t base);
00249 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base);
00250 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base);
00251 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base);
00252 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base);
00253 uint64_t hash64_any(const void *key, size_t length, uint64_t base);
00254 uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base);
00255 uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base);
00256 uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base);
00257 uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base);
00258 
00301 static inline uint32_t hash_pointer(const void *p, uint32_t base)
00302 {
00303         if (sizeof(p) % sizeof(uint32_t) == 0) {
00304                 /* This convoluted union is the right way of aliasing. */
00305                 union {
00306                         uint32_t a[sizeof(p) / sizeof(uint32_t)];
00307                         const void *p2;
00308                 } u;
00309                 u.p2 = p;
00310                 return hash_u32(u.a, sizeof(p) / sizeof(uint32_t), base);
00311         } else
00312                 return hash(&p, 1, base);
00313 }
00314 
00315 #endif /* HASH_H */
 All Classes Files Functions Variables Typedefs Friends Defines