[Sheepdog] [PATCH 2/5] sheep: add some candy helpers in util.c

[MORITA Kazutaka]

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