Antonie
|
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 */