At Wed, 16 Nov 2011 13:26:45 +0800, Liu Yuan wrote: > > On 11/16/2011 01:14 PM, MORITA Kazutaka wrote: > > > At Tue, 15 Nov 2011 11:16:43 +0800, > > Liu Yuan wrote: > >> > >> From: Liu Yuan <tailai.ly at taobao.com> > >> > >> These are trivial helper wrappers around standard IO functions > >> and interger hash function. "stolen" from git and Linux kernel. > >> > >> Signed-off-by: Liu Yuan <tailai.ly at taobao.com> > >> --- > >> include/util.h | 63 +++++++++++++++++++++++ > >> sheep/util.c | 150 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > >> 2 files changed, 213 insertions(+), 0 deletions(-) > >> create mode 100644 sheep/util.c > >> > >> diff --git a/include/util.h b/include/util.h > >> index 2dccd16..c73a6d5 100644 > >> --- a/include/util.h > >> +++ b/include/util.h > >> @@ -2,6 +2,8 @@ > >> #define __UTIL_H__ > >> > >> #include <string.h> > >> +#include <limits.h> > >> +#include <stdint.h> > >> > >> #include "bitops.h" > >> > >> @@ -53,4 +55,65 @@ static inline void *zalloc(size_t size) > >> return calloc(1, size); > >> } > >> > >> +typedef void (*try_to_free_t)(size_t); > >> +extern try_to_free_t set_try_to_free_routine(try_to_free_t); > >> + > >> +extern void *xmalloc(size_t size); > >> +extern void *xzalloc(size_t size); > >> +extern void *xrealloc(void *ptr, size_t size); > >> +extern void *xcalloc(size_t nmemb, size_t size); > >> +extern ssize_t xread(int fd, void *buf, size_t len); > >> +extern ssize_t xwrite(int fd, const void *buf, size_t len); > >> + > >> +/* Integer hash functions, taken from Linux kernel. > >> + * Use hash_long() to get most out of your cpu. > >> + */ > >> + > >> +/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ > >> +#define GOLDEN_RATIO_PRIME_32 0x9e370001UL > >> +/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ > >> +#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL > >> + > >> +#if __SIZEOF_POINTER__ == 4 > >> +#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32 > >> +#define hash_long(val, bits) hash_32(val, bits) > >> +#elif __SIZEOF_POINTER__ == 8 > >> +#define hash_long(val, bits) hash_64(val, bits) > >> +#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64 > >> +#else > >> +#error Wordsize not 32 or 64 > >> +#endif > >> + > >> +static inline uint64_t hash_64(uint64_t val, unsigned int bits) > >> +{ > >> + uint64_t hash = val; > >> + > >> + /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ > >> + uint64_t n = hash; > >> + n <<= 18; > >> + hash -= n; > >> + n <<= 33; > >> + hash -= n; > >> + n <<= 3; > >> + hash += n; > >> + n <<= 3; > >> + hash -= n; > >> + n <<= 4; > >> + hash += n; > >> + n <<= 2; > >> + hash += n; > >> + > >> + /* High bits are more random, so use them. */ > >> + return hash >> (64 - bits); > >> +} > >> + > >> +static inline uint32_t hash_32(uint32_t val, unsigned int bits) > >> +{ > >> + /* On some cpus multiply is faster, on others gcc will do shifts */ > >> + uint32_t hash = val * GOLDEN_RATIO_PRIME_32; > >> + > >> + /* High bits are more random, so use them. */ > >> + return hash >> (32 - bits); > >> +} > > > > We already have a hash function, fnv_64a_buf(). How about using it > > instead of introducing new one? > > > > > When I need a hash function that inputs an integer and outputs an > integer for specified bits, I looked at the fnv_64a_buf(), it seems to > me it tries to hash an string to integer. So I think these hash > functions do a different thing, no? We already use it to calculate a hash value from a 64 bit object id: fnv_64a_buf(&oid, sizeof(uint64_t), FNV1A_64_INIT); I guess this generates a less random value than hash_64(), though. Thanks, Kazutaka |