X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhash%2Fhash.h;h=0400e6a3b29bbc4505e707ed5231ed197ad6f22a;hp=1c531cf9edccd1f86c4298b19402246e261bfc22;hb=cc2d609dfca7192305ad477b8c2b52cfdc1aa9be;hpb=7449ae0ff0ef5c96b7a76010986e00ebb28b2a65 diff --git a/ccan/hash/hash.h b/ccan/hash/hash.h index 1c531cf9..0400e6a3 100644 --- a/ccan/hash/hash.h +++ b/ccan/hash/hash.h @@ -1,8 +1,8 @@ #ifndef CCAN_HASH_H #define CCAN_HASH_H +#include "config.h" #include #include -#include "config.h" #include /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain. @@ -29,9 +29,10 @@ * See also: hash64, hash_stable. * * Example: - * #include "hash/hash.h" + * #include * #include * #include + * #include * * // Simple demonstration: idential strings will have the same hash, but * // two different strings will probably not. @@ -74,9 +75,10 @@ * hash64_stable * * Example: - * #include "hash/hash.h" + * #include * #include * #include + * #include * * int main(int argc, char *argv[]) * { @@ -89,8 +91,8 @@ * } */ #define hash_stable(p, num, base) \ - (EXPR_BUILD_ASSERT(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \ - || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \ + (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \ + || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \ sizeof(*(p)) == 8 ? hash_stable_64((p), (num), (base)) \ : sizeof(*(p)) == 4 ? hash_stable_32((p), (num), (base)) \ : sizeof(*(p)) == 2 ? hash_stable_16((p), (num), (base)) \ @@ -112,18 +114,6 @@ */ uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base); -/* Our underlying operations. */ -uint32_t hash_any(const void *key, size_t length, uint32_t base); -uint32_t hash_stable_64(const void *key, size_t n, uint32_t base); -uint32_t hash_stable_32(const void *key, size_t n, uint32_t base); -uint32_t hash_stable_16(const void *key, size_t n, uint32_t base); -uint32_t hash_stable_8(const void *key, size_t n, uint32_t base); -uint64_t hash64_any(const void *key, size_t length, uint32_t base); -uint64_t hash64_stable_64(const void *key, size_t n, uint32_t base); -uint64_t hash64_stable_32(const void *key, size_t n, uint32_t base); -uint64_t hash64_stable_16(const void *key, size_t n, uint32_t base); -uint64_t hash64_stable_8(const void *key, size_t n, uint32_t base); - /** * hash_string - very fast hash of an ascii string * @str: the nul-terminated string @@ -149,67 +139,11 @@ static inline uint32_t hash_string(const char *string) return ret; } -/** - * hash_pointer - hash a pointer for internal use - * @p: the pointer value to hash - * @base: the base number to roll into the hash (usually 0) - * - * The pointer p (not what p points to!) is combined with the base to form - * a 32-bit hash. - * - * This hash will have different results on different machines, so is - * only useful for internal hashes (ie. not hashes sent across the - * network or saved to disk). - * - * Example: - * #include "hash/hash.h" - * - * // Code to keep track of memory regions. - * struct region { - * struct region *chain; - * void *start; - * unsigned int size; - * }; - * // We keep a simple hash table. - * static struct region *region_hash[128]; - * - * static void add_region(struct region *r) - * { - * unsigned int h = hash_pointer(r->start); - * - * r->chain = region_hash[h]; - * region_hash[h] = r->chain; - * } - * - * static void find_region(const void *start) - * { - * struct region *r; - * - * for (r = region_hash[hash_pointer(start)]; r; r = r->chain) - * if (r->start == start) - * return r; - * return NULL; - * } - */ -static inline uint32_t hash_pointer(const void *p, uint32_t base) -{ - if (sizeof(p) % sizeof(uint32_t) == 0) { - /* This convoluted union is the right way of aliasing. */ - union { - uint32_t u32[sizeof(p) / sizeof(uint32_t)]; - const void *p; - } u; - u.p = p; - return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base); - } else - return hash(&p, 1, base); -} - /** * hash64 - fast 64-bit hash of an array for internal use * @p: the array or pointer to first element * @num: the number of elements to hash - * @base: the base number to roll into the hash (usually 0) + * @base: the 64-bit base number to roll into the hash (usually 0) * * The memory region pointed to by p is combined with the base to form * a 64-bit hash. @@ -227,6 +161,7 @@ static inline uint32_t hash_pointer(const void *p, uint32_t base) * #include * #include * #include + * #include * * // Simple demonstration: idential strings will have the same hash, but * // two different strings will probably not. @@ -272,6 +207,7 @@ static inline uint32_t hash_pointer(const void *p, uint32_t base) * #include * #include * #include + * #include * * int main(int argc, char *argv[]) * { @@ -284,8 +220,8 @@ static inline uint32_t hash_pointer(const void *p, uint32_t base) * } */ #define hash64_stable(p, num, base) \ - (EXPR_BUILD_ASSERT(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \ - || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \ + (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \ + || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \ sizeof(*(p)) == 8 ? hash64_stable_64((p), (num), (base)) \ : sizeof(*(p)) == 4 ? hash64_stable_32((p), (num), (base)) \ : sizeof(*(p)) == 2 ? hash64_stable_16((p), (num), (base)) \ @@ -301,9 +237,76 @@ static inline uint32_t hash_pointer(const void *p, uint32_t base) * This is either hash() or hash64(), on 32/64 bit long machines. */ #define hashl(p, num, base) \ - (EXPR_BUILD_ASSERT(sizeof(long) == sizeof(uint32_t) \ - || sizeof(long) == sizeof(uint64_t)) + \ + (BUILD_ASSERT_OR_ZERO(sizeof(long) == sizeof(uint32_t) \ + || sizeof(long) == sizeof(uint64_t)) + \ (sizeof(long) == sizeof(uint64_t) \ ? hash64((p), (num), (base)) : hash((p), (num), (base)))) +/* Our underlying operations. */ +uint32_t hash_any(const void *key, size_t length, uint32_t base); +uint32_t hash_stable_64(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_32(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_16(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_8(const void *key, size_t n, uint32_t base); +uint64_t hash64_any(const void *key, size_t length, uint64_t base); +uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base); + +/** + * hash_pointer - hash a pointer for internal use + * @p: the pointer value to hash + * @base: the base number to roll into the hash (usually 0) + * + * The pointer p (not what p points to!) is combined with the base to form + * a 32-bit hash. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + * + * Example: + * #include + * + * // Code to keep track of memory regions. + * struct region { + * struct region *chain; + * void *start; + * unsigned int size; + * }; + * // We keep a simple hash table. + * static struct region *region_hash[128]; + * + * static void add_region(struct region *r) + * { + * unsigned int h = hash_pointer(r->start, 0); + * + * r->chain = region_hash[h]; + * region_hash[h] = r->chain; + * } + * + * static struct region *find_region(const void *start) + * { + * struct region *r; + * + * for (r = region_hash[hash_pointer(start, 0)]; r; r = r->chain) + * if (r->start == start) + * return r; + * return NULL; + * } + */ +static inline uint32_t hash_pointer(const void *p, uint32_t base) +{ + if (sizeof(p) % sizeof(uint32_t) == 0) { + /* This convoluted union is the right way of aliasing. */ + union { + uint32_t u32[sizeof(p) / sizeof(uint32_t)]; + const void *p; + } u; + u.p = p; + return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base); + } else + return hash(&p, 1, base); +} #endif /* HASH_H */