From dec0636927f5d0ae4cf06ad2710d022990419879 Mon Sep 17 00:00:00 2001 From: Brian Aker Date: Thu, 17 Dec 2009 09:28:30 -0800 Subject: [PATCH] Adding back libhashkit. --- Makefile.am | 6 +- configure.ac | 4 + libhashkit/Makefile.am | 45 +++++ libhashkit/algorithm.h | 49 +++++ libhashkit/behavior.c | 147 ++++++++++++++ libhashkit/behavior.h | 68 +++++++ libhashkit/common.h | 33 ++++ libhashkit/crc32.c | 85 ++++++++ libhashkit/default.c | 28 +++ libhashkit/fnv.c | 75 +++++++ libhashkit/hashkit.c | 252 ++++++++++++++++++++++++ libhashkit/hashkit.h | 112 +++++++++++ libhashkit/hsieh.c | 68 +++++++ libhashkit/jenkins.c | 213 ++++++++++++++++++++ libhashkit/ketama.c | 161 +++++++++++++++ libhashkit/md5.c | 365 +++++++++++++++++++++++++++++++++++ libhashkit/murmur.c | 76 ++++++++ libhashkit/strerror.c | 26 +++ libhashkit/strerror.h | 22 +++ libhashkit/types.h | 92 +++++++++ libhashkit/visibility.h | 51 +++++ support/libmemcached.spec.in | 1 + tests/Makefile.am | 17 +- tests/hashkit_functions.c | 363 ++++++++++++++++++++++++++++++++++ 24 files changed, 2353 insertions(+), 6 deletions(-) create mode 100644 libhashkit/Makefile.am create mode 100644 libhashkit/algorithm.h create mode 100644 libhashkit/behavior.c create mode 100644 libhashkit/behavior.h create mode 100644 libhashkit/common.h create mode 100644 libhashkit/crc32.c create mode 100644 libhashkit/default.c create mode 100644 libhashkit/fnv.c create mode 100644 libhashkit/hashkit.c create mode 100644 libhashkit/hashkit.h create mode 100644 libhashkit/hsieh.c create mode 100644 libhashkit/jenkins.c create mode 100644 libhashkit/ketama.c create mode 100644 libhashkit/md5.c create mode 100644 libhashkit/murmur.c create mode 100644 libhashkit/strerror.c create mode 100644 libhashkit/strerror.h create mode 100644 libhashkit/types.h create mode 100644 libhashkit/visibility.h create mode 100644 tests/hashkit_functions.c diff --git a/Makefile.am b/Makefile.am index e687f9ce..f807c697 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,6 +1,6 @@ ACLOCAL_AMFLAGS = -I m4 -SUBDIRS = docs libmemcached support clients tests example +SUBDIRS = docs libmemcached support clients tests example libhashkit EXTRA_dist = README.FIRST check-local: test-no-outputdiff @@ -20,7 +20,7 @@ test-no-outputdiff: fedora: rm -f ~/rpmbuild/RPMS/x86_64/libmemcached-$(VERSION)*.rpm rm -f ~/rpmbuild/SRPMS/libmemcached-$(VERSION)*.rpm - cp libmemcached-$(VERSION).tar.gz /home/brian/rpmbuild/SOURCES/ + cp libmemcached-$(VERSION).tar.gz ~/rpmbuild/SOURCES/ rpmbuild -ba support/libmemcached.spec cp ~/rpmbuild/RPMS/x86_64/libmemcached-$(VERSION)*.rpm . cp ~/rpmbuild/SRPMS/libmemcached-$(VERSION)*.rpm . @@ -28,7 +28,7 @@ fedora: generic: rm -f ~/rpmbuild/RPMS/x86_64/libmemcached-$(VERSION)*.rpm rm -f ~/rpmbuild/SRPMS/libmemcached-$(VERSION)*.rpm - cp libmemcached-$(VERSION).tar.gz /home/brian/rpmbuild/SOURCES/ + cp libmemcached-$(VERSION).tar.gz ~/rpmbuild/SOURCES/ rpmbuild -ba support/libmemcached.spec cp ~/rpmbuild/RPMS/x86_64/libmemcached-$(VERSION)*.rpm . cp ~/rpmbuild/SRPMS/libmemcached-$(VERSION)*.rpm . diff --git a/configure.ac b/configure.ac index 98557c2f..f5e1e574 100644 --- a/configure.ac +++ b/configure.ac @@ -14,6 +14,9 @@ AC_CONFIG_MACRO_DIR([m4]) PANDORA_CANONICAL_TARGET +HASHKIT_LIBRARY_VERSION=0:0:0 +AC_SUBST(HASHKIT_LIBRARY_VERSION) + AC_SEARCH_LIBS(getopt_long, gnugetopt) AC_SEARCH_LIBS(gethostbyname, nsl) @@ -52,6 +55,7 @@ AC_CONFIG_FILES([ example/Makefile libmemcached/Makefile libmemcached/memcached_configure.h + libhashkit/Makefile support/Makefile support/libmemcached.pc support/libmemcached.spec diff --git a/libhashkit/Makefile.am b/libhashkit/Makefile.am new file mode 100644 index 00000000..55a2cf7d --- /dev/null +++ b/libhashkit/Makefile.am @@ -0,0 +1,45 @@ +# HashKit +# Copyright (C) 2009 Brian Aker +# All rights reserved. +# +# Use and distribution licensed under the BSD license. See +# the COPYING file in the parent directory for full text. + +lib_LTLIBRARIES= libhashkit.la + +libhashkitincludedir= ${includedir}/libhashkit + +dist_libhashkitinclude_HEADERS= \ + algorithm.h \ + behavior.h \ + hashkit.h \ + strerror.h \ + types.h \ + visibility.h + +noinst_HEADERS= \ + common.h + +libhashkit_la_SOURCES= \ + crc32.c \ + behavior.c \ + default.c \ + fnv.c \ + hashkit.c \ + jenkins.c \ + ketama.c \ + md5.c \ + murmur.c \ + strerror.c + +if INCLUDE_HSIEH_SRC +libhashkit_la_SOURCES+= hsieh.c +endif + +libhashkit_la_CFLAGS= \ + ${AM_CFLAGS} \ + -DBUILDING_HASHKIT + +libhashkit_la_LDFLAGS= \ + $(LIBM) \ + -version-info $(HASHKIT_LIBRARY_VERSION) diff --git a/libhashkit/algorithm.h b/libhashkit/algorithm.h new file mode 100644 index 00000000..acf29509 --- /dev/null +++ b/libhashkit/algorithm.h @@ -0,0 +1,49 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +/** + * @file + * @brief HashKit Header + */ + +#ifndef HASHKIT_ALGORITHM_H +#define HASHKIT_ALGORITHM_H + +#ifdef __cplusplus +extern "C" { +#endif + +HASHKIT_API +uint32_t hashkit_default(const char *key, size_t key_length); +HASHKIT_API +uint32_t hashkit_fnv1_64(const char *key, size_t key_length); +HASHKIT_API +uint32_t hashkit_fnv1a_64(const char *key, size_t key_length); +HASHKIT_API +uint32_t hashkit_fnv1_32(const char *key, size_t key_length); +HASHKIT_API +uint32_t hashkit_fnv1a_32(const char *key, size_t key_length); +HASHKIT_API +uint32_t hashkit_crc32(const char *key, size_t key_length); +HASHKIT_API +#ifdef HAVE_HSIEH_HASH +HASHKIT_API +uint32_t hashkit_hsieh(const char *key, size_t key_length); +#endif +HASHKIT_API +uint32_t hashkit_murmur(const char *key, size_t key_length); +HASHKIT_API +uint32_t hashkit_jenkins(const char *key, size_t key_length); +HASHKIT_API +uint32_t hashkit_md5(const char *key, size_t key_length); + +#ifdef __cplusplus +} +#endif + +#endif /* HASHKIT_ALGORITHM_H */ diff --git a/libhashkit/behavior.c b/libhashkit/behavior.c new file mode 100644 index 00000000..19f08b1b --- /dev/null +++ b/libhashkit/behavior.c @@ -0,0 +1,147 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +#include "common.h" + +static hashkit_fn *fetch_hash_fn(hashkit_hash_algorithm_t hash_algorithm) +{ + switch (hash_algorithm) + { + case HASHKIT_HASH_DEFAULT: + return hashkit_default; + case HASHKIT_HASH_MD5: + return hashkit_md5; + case HASHKIT_HASH_CRC: + return hashkit_crc32; + case HASHKIT_HASH_FNV1_64: + return hashkit_fnv1_64; + case HASHKIT_HASH_FNV1A_64: + return hashkit_fnv1a_64; + case HASHKIT_HASH_FNV1_32: + return hashkit_fnv1_32; + case HASHKIT_HASH_FNV1A_32: + return hashkit_fnv1a_32; + case HASHKIT_HASH_HSIEH: +#ifdef HAVE_HSIEH_HASH + return hashkit_hsieh; +#else + return NULL; +#endif + case HASHKIT_HASH_MURMUR: + return hashkit_murmur; + case HASHKIT_HASH_JENKINS: + return hashkit_jenkins; + case HASHKIT_HASH_MAX: + default: +#ifdef HAVE_DEBUG + fprintf(stderr, "hashkit_hash_t was extended but hashkit_generate_value was not updated\n"); + fflush(stderr); + assert(0); +#endif + break; + } + + return NULL; +} + +hashkit_return_t hashkit_behavior_set_distribution(hashkit_st *hashkit, hashkit_distribution_t distribution) +{ + hashkit->distribution= distribution; + + return HASHKIT_SUCCESS; +} + + +hashkit_distribution_t hashkit_behavior_get_distribution(hashkit_st *hashkit) +{ + return hashkit->distribution; +} + + +/** + @note For the moment we will not allow the user to set the distribution hash type. +*/ +hashkit_return_t hashkit_behavior_set_key_hash_algorithm(hashkit_st *hashkit, hashkit_hash_algorithm_t hash_algorithm) +{ + hashkit_fn *hash_fn= fetch_hash_fn(hash_algorithm); + + if (hash_fn == NULL) + return HASHKIT_FAILURE; + + hashkit->hash_fn= hash_fn; + hashkit->for_key= hash_algorithm; + hashkit->for_distribution= hash_algorithm; + + return HASHKIT_SUCCESS; +} + + +hashkit_hash_algorithm_t hashkit_behavior_get_key_hash_algorithm(hashkit_st *hashkit) +{ + return hashkit->for_key; +} + + +void hashkit_behavior_set_active_fn(hashkit_st *hashkit, hashkit_active_fn *function) +{ + hashkit->active_fn= function; +} + + +hashkit_active_fn * hashkit_behavior_get_active_fn(hashkit_st *hashkit) +{ + return hashkit->active_fn; +} + + +void hashkit_behavior_set_continuum_hash_fn(hashkit_st *hashkit, hashkit_fn *function) +{ + hashkit->continuum_hash_fn= function; +} + + +hashkit_fn * hashkit_behavior_get_continuum_hash_fn(hashkit_st *hashkit) +{ + return hashkit->continuum_hash_fn; +} + + +void hashkit_behavior_set_continuum_key_fn(hashkit_st *hashkit, hashkit_key_fn *function) +{ + hashkit->continuum_key_fn= function; +} + + +hashkit_key_fn * hashkit_behavior_get_continuum_key_fn(hashkit_st *hashkit) +{ + return hashkit->continuum_key_fn; +} + + +void hashkit_behavior_set_sort_fn(hashkit_st *hashkit, hashkit_sort_fn *function) +{ + hashkit->sort_fn= function; +} + + +hashkit_sort_fn * hashkit_behavior_get_sort_fn(hashkit_st *hashkit) +{ + return hashkit->sort_fn; +} + + +void hashkit_behavior_set_weight_fn(hashkit_st *hashkit, hashkit_weight_fn *function) +{ + hashkit->weight_fn= function; +} + + +hashkit_weight_fn * hashkit_behavior_get_weight_fn(hashkit_st *hashkit) +{ + return hashkit->weight_fn; +} diff --git a/libhashkit/behavior.h b/libhashkit/behavior.h new file mode 100644 index 00000000..126a7c97 --- /dev/null +++ b/libhashkit/behavior.h @@ -0,0 +1,68 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +/** + * @file + * @brief HashKit Header + */ + +#ifndef HASHKIT_BEHAVIOR_H +#define HASHKIT_BEHAVIORH + +#ifdef __cplusplus +extern "C" { +#endif + + +HASHKIT_API +hashkit_return_t hashkit_behavior_set_distribution(hashkit_st *hashkit, hashkit_distribution_t distribution); + +HASHKIT_API +hashkit_distribution_t hashkit_behavior_get_distribution(hashkit_st *hashkit); + +HASHKIT_API +hashkit_return_t hashkit_behavior_set_key_hash_algorithm(hashkit_st *hashkit, hashkit_hash_algorithm_t hash_algorithm); + +HASHKIT_API +hashkit_hash_algorithm_t hashkit_behavior_get_key_hash_algorithm(hashkit_st *hashkit); + +HASHKIT_API +void hashkit_behavior_set_active_fn(hashkit_st *hash, hashkit_active_fn *function); + +HASHKIT_API +hashkit_active_fn * hashkit_behavior_get_active_fn(hashkit_st *hash); + +HASHKIT_API +void hashkit_behavior_set_continuum_hash_fn(hashkit_st *hash, hashkit_fn *function); + +HASHKIT_API +hashkit_fn * hashkit_behavior_get_continuum_hash_fn(hashkit_st *hash); + +HASHKIT_API +void hashkit_behavior_set_continuum_key_fn(hashkit_st *hash, hashkit_key_fn *function); + +HASHKIT_API +hashkit_key_fn * hashkit_behavior_get_continuum_key_fn(hashkit_st *hash); + +HASHKIT_API +void hashkit_behavior_set_sort_fn(hashkit_st *hash, hashkit_sort_fn *function); + +HASHKIT_API +hashkit_sort_fn * hashkit_behavior_get_sort_fn(hashkit_st *hash); + +HASHKIT_API +void hashkit_behavior_set_weight_fn(hashkit_st *hash, hashkit_weight_fn *function); + +HASHKIT_API +hashkit_weight_fn * hashkit_behavior_get_weight_fn(hashkit_st *hash); + +#ifdef __cplusplus +} +#endif + +#endif /* HASHKIT_BEHAVIOR_H */ diff --git a/libhashkit/common.h b/libhashkit/common.h new file mode 100644 index 00000000..0a7ac845 --- /dev/null +++ b/libhashkit/common.h @@ -0,0 +1,33 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +/** + * @file + * @brief System Include Files + */ + +#ifndef HASHKIT_COMMON_H +#define HASHKIT_COMMON_H + +#include "config.h" + +#include +#include +#include +#include +#include + +#include "hashkit.h" + +HASHKIT_LOCAL +void md5_signature(const unsigned char *key, unsigned int length, unsigned char *result); + +HASHKIT_LOCAL +int update_continuum(hashkit_st *hashkit); + +#endif /* HASHKIT_COMMON_H */ diff --git a/libhashkit/crc32.c b/libhashkit/crc32.c new file mode 100644 index 00000000..023abbb6 --- /dev/null +++ b/libhashkit/crc32.c @@ -0,0 +1,85 @@ +/* The crc32 functions and data was originally written by Spencer + * Garrett and was gleaned from the PostgreSQL source + * tree via the files contrib/ltree/crc32.[ch] and from FreeBSD at + * src/usr.bin/cksum/crc32.c. + */ + +#include "common.h" + +static const uint32_t crc32tab[256] = { + 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, + 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, + 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, + 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, + 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, + 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, + 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, + 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, + 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, + 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, + 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, + 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, + 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, + 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, + 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, + 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, + 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, + 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, + 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, + 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, + 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, + 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, + 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, + 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, + 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, + 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, + 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, + 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, + 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, + 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, + 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, + 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, + 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, + 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, + 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, + 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, + 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, + 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, + 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, + 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, + 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, + 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, + 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, + 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, + 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, + 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, + 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, + 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, + 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, + 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, + 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, + 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, + 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, + 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, + 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, + 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, + 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, + 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, + 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, + 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, + 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, + 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, + 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, + 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d, +}; + +uint32_t hashkit_crc32(const char *key, size_t key_length) +{ + uint64_t x; + uint32_t crc= UINT32_MAX; + + for (x= 0; x < key_length; x++) + crc= (crc >> 8) ^ crc32tab[(crc ^ (uint64_t)key[x]) & 0xff]; + + return ((~crc) >> 16) & 0x7fff; +} diff --git a/libhashkit/default.c b/libhashkit/default.c new file mode 100644 index 00000000..bc0d4529 --- /dev/null +++ b/libhashkit/default.c @@ -0,0 +1,28 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +#include "common.h" + +uint32_t hashkit_default(const char *key, size_t key_length) +{ + const char *ptr= key; + uint32_t value= 0; + + while (key_length--) + { + uint32_t val= (uint32_t) *ptr++; + value += val; + value += (value << 10); + value ^= (value >> 6); + } + value += (value << 3); + value ^= (value >> 11); + value += (value << 15); + + return value; +} diff --git a/libhashkit/fnv.c b/libhashkit/fnv.c new file mode 100644 index 00000000..fd171cef --- /dev/null +++ b/libhashkit/fnv.c @@ -0,0 +1,75 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +#include "common.h" + +/* FNV hash'es lifted from Dustin Sallings work */ +static uint64_t FNV_64_INIT= UINT64_C(0xcbf29ce484222325); +static uint64_t FNV_64_PRIME= UINT64_C(0x100000001b3); +static uint32_t FNV_32_INIT= 2166136261UL; +static uint32_t FNV_32_PRIME= 16777619; + +uint32_t hashkit_fnv1_64(const char *key, size_t key_length) +{ + /* Thanks to pierre@demartines.com for the pointer */ + uint64_t hash= FNV_64_INIT; + size_t x= 0; + + for (x= 0; x < key_length; x++) + { + hash *= FNV_64_PRIME; + hash ^= (uint64_t)key[x]; + } + + return (uint32_t)hash; +} + +uint32_t hashkit_fnv1a_64(const char *key, size_t key_length) +{ + uint32_t hash= (uint32_t) FNV_64_INIT; + size_t x= 0; + + for (x= 0; x < key_length; x++) + { + uint32_t val= (uint32_t)key[x]; + hash ^= val; + hash *= (uint32_t) FNV_64_PRIME; + } + + return hash; +} + +uint32_t hashkit_fnv1_32(const char *key, size_t key_length) +{ + uint32_t hash= FNV_32_INIT; + size_t x= 0; + + for (x= 0; x < key_length; x++) + { + uint32_t val= (uint32_t)key[x]; + hash *= FNV_32_PRIME; + hash ^= val; + } + + return hash; +} + +uint32_t hashkit_fnv1a_32(const char *key, size_t key_length) +{ + uint32_t hash= FNV_32_INIT; + size_t x= 0; + + for (x= 0; x < key_length; x++) + { + uint32_t val= (uint32_t)key[x]; + hash ^= val; + hash *= FNV_32_PRIME; + } + + return hash; +} diff --git a/libhashkit/hashkit.c b/libhashkit/hashkit.c new file mode 100644 index 00000000..54033132 --- /dev/null +++ b/libhashkit/hashkit.c @@ -0,0 +1,252 @@ +/* HashKit + * Copyright (C) 2006-2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +#include "common.h" + +inline static bool _is_allocated(const hashkit_st *hashk) +{ + return hashk->options.is_allocated == true; +} + +inline static bool _is_initialized(const hashkit_st *hashk) +{ + return hashk->options.is_initialized == true; +} + +/** + @note We make no assumptions that "hashk" has been, or not been allocated from heap/stack. We just know we didn't do it. +*/ +hashkit_st *hashkit_create(hashkit_st *hashk) +{ + if (hashk == NULL) + { + hashk= (hashkit_st *)malloc(sizeof(hashkit_st)); + if (hashk == NULL) + { + return NULL; + } + + hashk->options.is_allocated= true; + } + else + { + hashk->options.is_allocated= false; + } + + hashk->options.is_initialized= true; + + hashk->distribution= HASHKIT_DISTRIBUTION_MODULA; + hashk->continuum_count= 0; + hashk->continuum_points_count= 0; + hashk->list_size= 0; + hashk->context_size= 0; + hashk->continuum= NULL; + hashk->hash_fn= NULL; + hashk->active_fn= NULL; + hashk->continuum_hash_fn= NULL; + hashk->continuum_key_fn= NULL; + hashk->sort_fn= NULL; + hashk->weight_fn= NULL; + hashk->list= NULL; + + return hashk; +} + + +void hashkit_free(hashkit_st *hashk) +{ + assert(_is_initialized(hashk) == true); + + if (hashk->continuum != NULL) + { + free(hashk->continuum); + } + + /** + We don't know if hashk is pointing to something else, + so we go on and set is_initialized. + */ + hashk->options.is_initialized= false; + + if (_is_allocated(hashk)) + { + free(hashk); + } +} + +/** + @note We do assume source is valid. If source does not exist, we allocate. +*/ +hashkit_st *hashkit_clone(hashkit_st *destination, const hashkit_st *source) +{ + hashkit_st *new_clone; + + if (source == NULL) + { + return hashkit_create(destination); + } + else + { + assert(_is_initialized(source) == true); + } + + /* new_clone will be a pointer to destination */ + new_clone= hashkit_create(destination); + assert((destination ? ((_is_allocated(new_clone) == false)) : (_is_allocated(new_clone) == true))); + + // Should only happen on allocation failure. + if (new_clone == NULL) + { + return NULL; + } + + // For the moment we will not clone this. + new_clone->continuum= NULL; + + new_clone->distribution= source->distribution; + new_clone->continuum_count= source->continuum_count; + new_clone->continuum_points_count= source->continuum_points_count; + new_clone->list_size= source->list_size; + new_clone->context_size= source->context_size; + + + new_clone->hash_fn= source->hash_fn; + new_clone->active_fn= source->active_fn; + new_clone->continuum_hash_fn= source->continuum_hash_fn; + new_clone->continuum_key_fn= source->continuum_key_fn; + new_clone->sort_fn= source->sort_fn; + new_clone->weight_fn= source->weight_fn; + new_clone->list= source->list; + + return new_clone; +} + + +#if 0 +void hashkit_set_list(hashkit_st *hashkit, void *list, size_t list_size, size_t context_size) +{ + hashkit->list= list; + hashkit->list_size= list_size; + hashkit->context_size= context_size; +} + + +uint32_t hashkit_value(hashkit_st *hashkit, const char *key, size_t key_length) +{ + if (hashkit->hash_fn == NULL) + return hashkit_default(key, key_length); + + return hashkit->hash_fn(key, key_length); +} + + +uint32_t hashkit_index(hashkit_st *hashkit, uint32_t hash_value) +{ + if (hashkit->list_size == 1) + return 0; + + switch (hashkit->distribution) + { + case HASHKIT_DISTRIBUTION_MODULA: + return hash_value % (uint32_t)hashkit->list_size; + + case HASHKIT_DISTRIBUTION_RANDOM: + return (uint32_t)random() % (uint32_t)hashkit->list_size; + + case HASHKIT_DISTRIBUTION_KETAMA: + { + hashkit_continuum_point_st *begin, *end, *left, *right, *middle; + begin= left= hashkit->continuum; + end= right= hashkit->continuum + hashkit->continuum_points_count; + + while (left < right) + { + middle= left + (right - left) / 2; + if (middle->value < hash_value) + left= middle + 1; + else + right= middle; + } + if (right == end) + right= begin; + return right->index; + } + + case HASHKIT_DISTRIBUTION_MAX: + default: + /* We have added a distribution without extending the logic */ + return hash_value % (uint32_t)hashkit->list_size; + } + + /* NOTREACHED */ +} + + +int hashkit_run_distribution(hashkit_st *hashkit) +{ + switch (hashkit->distribution) + { + case HASHKIT_DISTRIBUTION_MODULA: + if (hashkit->sort_fn != NULL && hashkit->list_size > 1) + hashkit->sort_fn(hashkit->list, hashkit->list_size); + break; + case HASHKIT_DISTRIBUTION_RANDOM: + break; + case HASHKIT_DISTRIBUTION_KETAMA: + return update_continuum(hashkit); + case HASHKIT_DISTRIBUTION_MAX: + default: + /* We have added a distribution without extending the logic */ + break; + } + + return 0; +} +#endif + + +uint32_t hashkit_generate_value(const char *key, size_t key_length, hashkit_hash_algorithm_t hash_algorithm) +{ + switch (hash_algorithm) + { + case HASHKIT_HASH_DEFAULT: + return hashkit_default(key, key_length); + case HASHKIT_HASH_MD5: + return hashkit_md5(key, key_length); + case HASHKIT_HASH_CRC: + return hashkit_crc32(key, key_length); + case HASHKIT_HASH_FNV1_64: + return hashkit_fnv1_64(key, key_length); + case HASHKIT_HASH_FNV1A_64: + return hashkit_fnv1a_64(key, key_length); + case HASHKIT_HASH_FNV1_32: + return hashkit_fnv1_32(key, key_length); + case HASHKIT_HASH_FNV1A_32: + return hashkit_fnv1a_32(key, key_length); + case HASHKIT_HASH_HSIEH: +#ifdef HAVE_HSIEH_HASH + return hashkit_hsieh(key, key_length); +#else + return 1; +#endif + case HASHKIT_HASH_MURMUR: + return hashkit_murmur(key, key_length); + case HASHKIT_HASH_JENKINS: + return hashkit_jenkins(key, key_length); + case HASHKIT_HASH_MAX: + default: +#ifdef HAVE_DEBUG + fprintf(stderr, "hashkit_hash_t was extended but hashkit_generate_value was not updated\n"); + fflush(stderr); + assert(0); +#endif + break; + } + + return 1; +} diff --git a/libhashkit/hashkit.h b/libhashkit/hashkit.h new file mode 100644 index 00000000..6dd08f43 --- /dev/null +++ b/libhashkit/hashkit.h @@ -0,0 +1,112 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +/** + * @file + * @brief HashKit Header + */ + +#ifndef HASHKIT_H +#define HASHKIT_H + +#if !defined(__cplusplus) +# include +#endif +#include +#include +#include +#include +#include +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * @addtogroup hashkit_constants Constants + * @ingroup hashkit + * @{ + */ + +/* Defines. */ +#define HASHKIT_MAX_KEY 251 +#define HASHKIT_POINTS_PER_NODE 100 +#define HASHKIT_POINTS_PER_NODE_WEIGHTED 160 +#define HASHKIT_CONTINUUM_ADDITION 10 +#define HASHKIT_CONTINUUM_KEY_SIZE 86 + +/** @} */ + +/** + * @ingroup hashkit + */ +struct hashkit_st +{ + hashkit_options_st options; + hashkit_distribution_t distribution; + uint32_t continuum_count; + uint32_t continuum_points_count; + size_t list_size; + size_t context_size; + + /** + @note There are two places we use hashing, one is for when we have a key + and we want to find out what server it should be placed on. The second is + for when we are placing a value into the continuum. + */ + hashkit_hash_algorithm_t for_key; + hashkit_hash_algorithm_t for_distribution; + + hashkit_continuum_point_st *continuum; + hashkit_fn *hash_fn; + hashkit_active_fn *active_fn; + hashkit_fn *continuum_hash_fn; + hashkit_key_fn *continuum_key_fn; + hashkit_sort_fn *sort_fn; + hashkit_weight_fn *weight_fn; + void *list; +}; + +/** + * @ingroup hashkit + */ +struct hashkit_continuum_point_st +{ + uint32_t index; + uint32_t value; +}; + +/** + * @addtogroup hashkit Pandora Hash Declarations + * @{ + */ + +HASHKIT_API +hashkit_st *hashkit_create(hashkit_st *hash); + +HASHKIT_API +hashkit_st *hashkit_clone(hashkit_st *destination, const hashkit_st *ptr); + +HASHKIT_API +void hashkit_free(hashkit_st *hash); + +HASHKIT_API +uint32_t hashkit_generate_value(const char *key, size_t key_length, hashkit_hash_algorithm_t hash_algorithm); + +#define hashkit_is_allocated(__object) ((__object)->options.is_allocated) +#define hashkit_is_initialized(__object) ((__object)->options.is_initialized) + +/** @} */ + +#ifdef __cplusplus +} +#endif + +#endif /* HASHKIT_H */ diff --git a/libhashkit/hsieh.c b/libhashkit/hsieh.c new file mode 100644 index 00000000..cd44b67f --- /dev/null +++ b/libhashkit/hsieh.c @@ -0,0 +1,68 @@ +/* By Paul Hsieh (C) 2004, 2005. Covered under the Paul Hsieh + * derivative license. + * See: http://www.azillionmonkeys.com/qed/weblicense.html for license + * details. + * http://www.azillionmonkeys.com/qed/hash.html +*/ + +#include "hash_common.h" + +#undef get16bits +#if (defined(__GNUC__) && defined(__i386__)) +#define get16bits(d) (*((const uint16_t *) (d))) +#endif + +#if !defined (get16bits) +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ + +(uint32_t)(((const uint8_t *)(d))[0]) ) +#endif + +uint32_t hashkit_hsieh(const char *key, size_t key_length) +{ + uint32_t hash = 0, tmp; + int rem; + + if (key_length <= 0 || key == NULL) + return 0; + + rem = key_length & 3; + key_length >>= 2; + + /* Main loop */ + for (;key_length > 0; key_length--) + { + hash += get16bits (key); + tmp = (get16bits (key+2) << 11) ^ hash; + hash = (hash << 16) ^ tmp; + key += 2*sizeof (uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) + { + case 3: hash += get16bits (key); + hash ^= hash << 16; + hash ^= key[sizeof (uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: hash += get16bits (key); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: hash += *key; + hash ^= hash << 10; + hash += hash >> 1; + } + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return hash; +} + diff --git a/libhashkit/jenkins.c b/libhashkit/jenkins.c new file mode 100644 index 00000000..29d9454e --- /dev/null +++ b/libhashkit/jenkins.c @@ -0,0 +1,213 @@ +/* +* +* By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this +* code any way you wish, private, educational, or commercial. It's free. +* Use for hash table lookup, or anything where one collision in 2^^32 is +* acceptable. Do NOT use for cryptographic purposes. +* http://burtleburtle.net/bob/hash/index.html +* +* Modified by Brian Pontz for libmemcached +* TODO: +* Add big endian support +*/ + +#include "common.h" + +#define hashsize(n) ((uint32_t)1<<(n)) +#define hashmask(n) (hashsize(n)-1) +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +#define mix(a,b,c) \ +{ \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c,16); c += b; \ + b -= a; b ^= rot(a,19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} + +#define final(a,b,c) \ +{ \ + c ^= b; c -= rot(b,14); \ + a ^= c; a -= rot(c,11); \ + b ^= a; b -= rot(a,25); \ + c ^= b; c -= rot(b,16); \ + a ^= c; a -= rot(c,4); \ + b ^= a; b -= rot(a,14); \ + c ^= b; c -= rot(b,24); \ +} + +#define JENKINS_INITVAL 13 + +/* +jenkins_hash() -- hash a variable-length key into a 32-bit value + k : the key (the unaligned variable-length array of bytes) + length : the length of the key, counting by bytes + initval : can be any 4-byte value +Returns a 32-bit value. Every bit of the key affects every bit of +the return value. Two keys differing by one or two bits will have +totally different hash values. + +The best hash table sizes are powers of 2. There is no need to do +mod a prime (mod is sooo slow!). If you need less than 32 bits, +use a bitmask. For example, if you need only 10 bits, do + h = (h & hashmask(10)); +In which case, the hash table should have hashsize(10) elements. +*/ + +uint32_t hashkit_jenkins(const char *key, size_t length) +{ + uint32_t a,b,c; /* internal state */ + union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + JENKINS_INITVAL; + + u.ptr = key; +#ifndef WORDS_BIGENDIAN + if ((u.i & 0x3) == 0) + { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]&0xffffff" actually reads beyond the end of the string, but + * then masks off the part it's not allowed to read. Because the + * string is aligned, the masked-off tail is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + */ + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; + case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; + case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=k[1]&0xffffff; a+=k[0]; break; + case 6 : b+=k[1]&0xffff; a+=k[0]; break; + case 5 : b+=k[1]&0xff; a+=k[0]; break; + case 4 : a+=k[0]; break; + case 3 : a+=k[0]&0xffffff; break; + case 2 : a+=k[0]&0xffff; break; + case 1 : a+=k[0]&0xff; break; + case 0 : return c; /* zero length strings require no mixing */ + default: return c; + } + + } + else if ((u.i & 0x1) == 0) + { + const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ + const uint8_t *k8; + + /*--------------- all but last block: aligned reads and different mixing */ + while (length > 12) + { + a += k[0] + (((uint32_t)k[1])<<16); + b += k[2] + (((uint32_t)k[3])<<16); + c += k[4] + (((uint32_t)k[5])<<16); + mix(a,b,c); + length -= 12; + k += 6; + } + + /*----------------------------- handle the last (probably partial) block */ + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[4]+(((uint32_t)k[5])<<16); + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=k[4]; + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=k[2]; + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=k[0]; + break; + case 1 : a+=k8[0]; + break; + case 0 : return c; /* zero length requires no mixing */ + default: return c; + } + + } + else + { /* need to read the key one byte at a time */ +#endif /* little endian */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + a += ((uint32_t)k[1])<<8; + a += ((uint32_t)k[2])<<16; + a += ((uint32_t)k[3])<<24; + b += k[4]; + b += ((uint32_t)k[5])<<8; + b += ((uint32_t)k[6])<<16; + b += ((uint32_t)k[7])<<24; + c += k[8]; + c += ((uint32_t)k[9])<<8; + c += ((uint32_t)k[10])<<16; + c += ((uint32_t)k[11])<<24; + mix(a,b,c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch(length) /* all the case statements fall through */ + { + case 12: c+=((uint32_t)k[11])<<24; + case 11: c+=((uint32_t)k[10])<<16; + case 10: c+=((uint32_t)k[9])<<8; + case 9 : c+=k[8]; + case 8 : b+=((uint32_t)k[7])<<24; + case 7 : b+=((uint32_t)k[6])<<16; + case 6 : b+=((uint32_t)k[5])<<8; + case 5 : b+=k[4]; + case 4 : a+=((uint32_t)k[3])<<24; + case 3 : a+=((uint32_t)k[2])<<16; + case 2 : a+=((uint32_t)k[1])<<8; + case 1 : a+=k[0]; + break; + case 0 : return c; + default : return c; + } +#ifndef WORDS_BIGENDIAN + } +#endif + + final(a,b,c); + return c; +} diff --git a/libhashkit/ketama.c b/libhashkit/ketama.c new file mode 100644 index 00000000..50309bbc --- /dev/null +++ b/libhashkit/ketama.c @@ -0,0 +1,161 @@ +/* HashKit + * Copyright (C) 2006-2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +#include "common.h" + +static uint32_t ketama_server_hash(const char *key, unsigned int key_length, int alignment) +{ + unsigned char results[16]; + + md5_signature((unsigned char*)key, key_length, results); + return ((uint32_t) (results[3 + alignment * 4] & 0xFF) << 24) + | ((uint32_t) (results[2 + alignment * 4] & 0xFF) << 16) + | ((uint32_t) (results[1 + alignment * 4] & 0xFF) << 8) + | (results[0 + alignment * 4] & 0xFF); +} + +static int continuum_points_cmp(const void *t1, const void *t2) +{ + hashkit_continuum_point_st *ct1= (hashkit_continuum_point_st *)t1; + hashkit_continuum_point_st *ct2= (hashkit_continuum_point_st *)t2; + + if (ct1->value == ct2->value) + return 0; + else if (ct1->value > ct2->value) + return 1; + else + return -1; +} + +int update_continuum(hashkit_st *hashkit) +{ + uint32_t count; + uint32_t continuum_index= 0; + uint32_t value; + uint32_t points_index; + uint32_t points_count= 0; + uint32_t points_per_server; + uint32_t points_per_hash; + uint64_t total_weight= 0; + uint32_t live_servers; + uint8_t *context; + + if (hashkit->active_fn != NULL || hashkit->weight_fn != NULL) + { + live_servers= 0; + + for (count= 0, context= hashkit->list; count < hashkit->list_size; + count++, context+= hashkit->context_size) + { + if (hashkit->active_fn != NULL) + { + if (hashkit->active_fn(context)) + live_servers++; + else + continue; + } + + if (hashkit->weight_fn != NULL) + total_weight+= hashkit->weight_fn(context); + } + } + + if (hashkit->active_fn == NULL) + live_servers= (uint32_t)hashkit->list_size; + + if (live_servers == 0) + return 0; + + if (hashkit->weight_fn == NULL) + { + points_per_server= HASHKIT_POINTS_PER_NODE; + points_per_hash= 1; + } + else + { + points_per_server= HASHKIT_POINTS_PER_NODE_WEIGHTED; + points_per_hash= 4; + } + + if (live_servers > hashkit->continuum_count) + { + hashkit_continuum_point_st *new_continuum; + + new_continuum= realloc(hashkit->continuum, + sizeof(hashkit_continuum_point_st) * + (live_servers + HASHKIT_CONTINUUM_ADDITION) * + points_per_server); + + if (new_continuum == NULL) + return ENOMEM; + + hashkit->continuum= new_continuum; + hashkit->continuum_count= live_servers + HASHKIT_CONTINUUM_ADDITION; + } + + for (count= 0, context= hashkit->list; count < hashkit->list_size; + count++, context+= hashkit->context_size) + { + if (hashkit->active_fn != NULL && hashkit->active_fn(context) == false) + continue; + + if (hashkit->weight_fn != NULL) + { + float pct = (float)hashkit->weight_fn(context) / (float)total_weight; + points_per_server= (uint32_t) ((floorf((float) (pct * HASHKIT_POINTS_PER_NODE_WEIGHTED / 4 * (float)live_servers + 0.0000000001))) * 4); + } + + for (points_index= 0; + points_index < points_per_server / points_per_hash; + points_index++) + { + char sort_host[HASHKIT_CONTINUUM_KEY_SIZE]= ""; + size_t sort_host_length; + + if (hashkit->continuum_key_fn == NULL) + { + sort_host_length= (size_t) snprintf(sort_host, HASHKIT_CONTINUUM_KEY_SIZE, "%d", + points_index); + } + else + { + sort_host_length= hashkit->continuum_key_fn(sort_host, HASHKIT_CONTINUUM_KEY_SIZE, + points_index, context); + } + + if (hashkit->weight_fn == NULL) + { + if (hashkit->continuum_hash_fn == NULL) + value= hashkit_default(sort_host, sort_host_length); + else + value= hashkit->continuum_hash_fn(sort_host, sort_host_length); + + hashkit->continuum[continuum_index].index= count; + hashkit->continuum[continuum_index++].value= value; + } + else + { + unsigned int i; + for (i = 0; i < points_per_hash; i++) + { + value= ketama_server_hash(sort_host, (uint32_t) sort_host_length, (int) i); + hashkit->continuum[continuum_index].index= count; + hashkit->continuum[continuum_index++].value= value; + } + } + } + + points_count+= points_per_server; + } + + hashkit->continuum_points_count= points_count; + qsort(hashkit->continuum, hashkit->continuum_points_count, sizeof(hashkit_continuum_point_st), + continuum_points_cmp); + + return 0; +} diff --git a/libhashkit/md5.c b/libhashkit/md5.c new file mode 100644 index 00000000..d550c773 --- /dev/null +++ b/libhashkit/md5.c @@ -0,0 +1,365 @@ +/* + This Library has been modified from its original form by + Brian Aker (brian@tangent.org) + + See below for original Copyright. +*/ +/* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm + */ + +/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All +rights reserved. + +License to copy and use this software is granted provided that it +is identified as the "RSA Data Security, Inc. MD5 Message-Digest +Algorithm" in all material mentioning or referencing this software +or this function. + +License is also granted to make and use derivative works provided +that such works are identified as "derived from the RSA Data +Security, Inc. MD5 Message-Digest Algorithm" in all material +mentioning or referencing the derived work. + +RSA Data Security, Inc. makes no representations concerning either +the merchantability of this software or the suitability of this +software for any particular purpose. It is provided "as is" +without express or implied warranty of any kind. + +These notices must be retained in any copies of any part of this +documentation and/or software. +*/ + +#include "common.h" + +#include +#include + +/* POINTER defines a generic pointer type */ +typedef unsigned char *POINTER; + + +/* UINT4 defines a four byte word */ +typedef unsigned int UINT4; + + +/* MD5 context. */ +typedef struct { + UINT4 state[4]; /* state (ABCD) */ + UINT4 count[2]; /* number of bits, modulo 2^64 (lsb first) */ + unsigned char buffer[64]; /* input buffer */ +} MD5_CTX; + +static void MD5Init (MD5_CTX *context); /* context */ +static void MD5Update ( MD5_CTX *context, /* context */ + const unsigned char *input, /* input block */ + unsigned int inputLen); /* length of input block */ +static void MD5Final ( unsigned char digest[16], /* message digest */ + MD5_CTX *context); /* context */ + +/* Constants for MD5Transform routine. */ + +#define S11 7 +#define S12 12 +#define S13 17 +#define S14 22 +#define S21 5 +#define S22 9 +#define S23 14 +#define S24 20 +#define S31 4 +#define S32 11 +#define S33 16 +#define S34 23 +#define S41 6 +#define S42 10 +#define S43 15 +#define S44 21 + + +static void MD5Transform (UINT4 state[4], + unsigned char block[64]); +static void Encode (unsigned char *output, + UINT4 *input, + unsigned int len); +static void Decode(UINT4 *output, unsigned char *input, unsigned int len); + +static unsigned char PADDING[64] = { + 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 +}; + +/* F, G, H and I are basic MD5 functions. + */ +#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) +#define G(x, y, z) (((x) & (z)) | ((y) & (~z))) +#define H(x, y, z) ((x) ^ (y) ^ (z)) +#define I(x, y, z) ((y) ^ ((x) | (~z))) + +/* ROTATE_LEFT rotates x left n bits. + */ +#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) + +/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4. +Rotation is separate from addition to prevent recomputation. + */ +#define FF(a, b, c, d, x, s, ac) { \ + (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \ + (a) = ROTATE_LEFT ((a), (s)); \ + (a) += (b); \ + } +#define GG(a, b, c, d, x, s, ac) { \ + (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \ + (a) = ROTATE_LEFT ((a), (s)); \ + (a) += (b); \ + } +#define HH(a, b, c, d, x, s, ac) { \ + (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \ + (a) = ROTATE_LEFT ((a), (s)); \ + (a) += (b); \ + } +#define II(a, b, c, d, x, s, ac) { \ + (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \ + (a) = ROTATE_LEFT ((a), (s)); \ + (a) += (b); \ + } + + +/* + Just a simple method for getting the signature + result must be == 16 +*/ +void md5_signature(const unsigned char *key, unsigned int length, unsigned char *result) +{ + MD5_CTX my_md5; + + MD5Init(&my_md5); + (void)MD5Update(&my_md5, key, length); + MD5Final(result, &my_md5); +} + +/* MD5 initialization. Begins an MD5 operation, writing a new context. + */ +static void MD5Init (MD5_CTX *context) /* context */ +{ + context->count[0] = context->count[1] = 0; + /* Load magic initialization constants. +*/ + context->state[0] = 0x67452301; + context->state[1] = 0xefcdab89; + context->state[2] = 0x98badcfe; + context->state[3] = 0x10325476; +} + +/* MD5 block update operation. Continues an MD5 message-digest + operation, processing another message block, and updating the + context. + */ + +static void MD5Update ( + MD5_CTX *context, /* context */ + const unsigned char *input, /* input block */ + unsigned int inputLen) /* length of input block */ +{ + unsigned int i, idx, partLen; + + /* Compute number of bytes mod 64 */ + idx = (unsigned int)((context->count[0] >> 3) & 0x3F); + + + /* Update number of bits */ + if ((context->count[0] += ((UINT4)inputLen << 3)) + < ((UINT4)inputLen << 3)) + context->count[1]++; + context->count[1] += ((UINT4)inputLen >> 29); + + partLen = 64 - idx; + + /* Transform as many times as possible. +*/ + if (inputLen >= partLen) { + memcpy((POINTER)&context->buffer[idx], (POINTER)input, partLen); + MD5Transform(context->state, context->buffer); + + for (i = partLen; i + 63 < inputLen; i += 64) + MD5Transform (context->state, (unsigned char *)&input[i]); + + idx = 0; + } + else + i = 0; + + /* Buffer remaining input */ + memcpy((POINTER)&context->buffer[idx], (POINTER)&input[i], + inputLen-i); +} + +/* MD5 finalization. Ends an MD5 message-digest operation, writing the + the message digest and zeroizing the context. + */ + +static void MD5Final ( + unsigned char digest[16], /* message digest */ + MD5_CTX *context) /* context */ +{ + unsigned char bits[8]; + unsigned int idx, padLen; + + /* Save number of bits */ + Encode (bits, context->count, 8); + + /* Pad out to 56 mod 64. +*/ + idx = (unsigned int)((context->count[0] >> 3) & 0x3f); + padLen = (idx < 56) ? (56 - idx) : (120 - idx); + MD5Update (context, PADDING, padLen); + + /* Append length (before padding) */ + MD5Update (context, bits, 8); + + /* Store state in digest */ + Encode (digest, context->state, 16); + + /* Zeroize sensitive information. +*/ + memset((POINTER)context, 0, sizeof (*context)); +} + +/* MD5 basic transformation. Transforms state based on block. + */ +static void MD5Transform ( + UINT4 state[4], + unsigned char block[64]) +{ + UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16]; + + Decode (x, block, 64); + + /* Round 1 */ + FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */ + FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */ + FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */ + FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */ + FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */ + FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */ + FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */ + FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */ + FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */ + FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */ + FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */ + FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */ + FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */ + FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */ + FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */ + FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */ + + /* Round 2 */ + GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */ + GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */ + GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */ + GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */ + GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */ + GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */ + GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */ + GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */ + GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */ + GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */ + GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */ + GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */ + GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */ + GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */ + GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */ + GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */ + + /* Round 3 */ + HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */ + HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */ + HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */ + HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */ + HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */ + HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */ + HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */ + HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */ + HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */ + HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */ + HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */ + HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */ + HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */ + HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */ + HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */ + HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */ + + /* Round 4 */ + II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */ + II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */ + II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */ + II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */ + II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */ + II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */ + II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */ + II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */ + II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */ + II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */ + II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */ + II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */ + II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */ + II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */ + II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */ + II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */ + + + state[0] += a; + state[1] += b; + state[2] += c; + state[3] += d; + + /* Zeroize sensitive information. +*/ + memset((POINTER)x, 0, sizeof (x)); +} + +/* Encodes input (UINT4) into output (unsigned char). Assumes len is + a multiple of 4. + */ +static void Encode ( +unsigned char *output, +UINT4 *input, +unsigned int len) +{ + unsigned int i, j; + + for (i = 0, j = 0; j < len; i++, j += 4) { + output[j] = (unsigned char)(input[i] & 0xff); + output[j+1] = (unsigned char)((input[i] >> 8) & 0xff); + output[j+2] = (unsigned char)((input[i] >> 16) & 0xff); + output[j+3] = (unsigned char)((input[i] >> 24) & 0xff); + } +} + + +/* Decodes input (unsigned char) into output (UINT4). Assumes len is + a multiple of 4. + */ +static void Decode ( +UINT4 *output, +unsigned char *input, +unsigned int len) +{ + unsigned int i, j; + + for (i = 0, j = 0; j < len; i++, j += 4) + output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) | + (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24); +} + +uint32_t hashkit_md5(const char *key, size_t key_length) +{ + unsigned char results[16]; + + md5_signature((unsigned char*)key, (unsigned int)key_length, results); + + return ((uint32_t) (results[3] & 0xFF) << 24) + | ((uint32_t) (results[2] & 0xFF) << 16) + | ((uint32_t) (results[1] & 0xFF) << 8) + | (results[0] & 0xFF); +} diff --git a/libhashkit/murmur.c b/libhashkit/murmur.c new file mode 100644 index 00000000..cd5e6419 --- /dev/null +++ b/libhashkit/murmur.c @@ -0,0 +1,76 @@ +/* + "Murmur" hash provided by Austin, tanjent@gmail.com + http://murmurhash.googlepages.com/ + + Note - This code makes a few assumptions about how your machine behaves - + + 1. We can read a 4-byte value from any address without crashing + 2. sizeof(int) == 4 + + And it has a few limitations - + 1. It will not work incrementally. + 2. It will not produce the same results on little-endian and big-endian + machines. + + Updated to murmur2 hash - BP +*/ + +#include "common.h" + +uint32_t hashkit_murmur(const char *key, size_t length) +{ + /* + 'm' and 'r' are mixing constants generated offline. They're not + really 'magic', they just happen to work well. + */ + + const unsigned int m= 0x5bd1e995; + const uint32_t seed= (0xdeadbeef * (uint32_t)length); + const int r= 24; + + + // Initialize the hash to a 'random' value + + uint32_t h= seed ^ (uint32_t)length; + + // Mix 4 bytes at a time into the hash + + const unsigned char * data= (const unsigned char *)key; + + while(length >= 4) + { + unsigned int k = *(unsigned int *)data; + + k *= m; + k ^= k >> r; + k *= m; + + h *= m; + h ^= k; + + data += 4; + length -= 4; + } + + // Handle the last few bytes of the input array + + switch(length) + { + case 3: h ^= ((uint32_t)data[2]) << 16; + case 2: h ^= ((uint32_t)data[1]) << 8; + case 1: h ^= data[0]; + h *= m; + default: break; + }; + + /* + Do a few final mixes of the hash to ensure the last few bytes are + well-incorporated. + */ + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; +} diff --git a/libhashkit/strerror.c b/libhashkit/strerror.c new file mode 100644 index 00000000..270fa214 --- /dev/null +++ b/libhashkit/strerror.c @@ -0,0 +1,26 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +#include "common.h" + +const char *hashkit_strerror(hashkit_st *ptr __attribute__((unused)), hashkit_return_t rc) +{ + switch (rc) + { + case HASHKIT_SUCCESS: + return "SUCCESS"; + case HASHKIT_FAILURE: + return "FAILURE"; + case HASHKIT_MEMORY_ALLOCATION_FAILURE: + return "MEMORY ALLOCATION FAILURE"; + case HASHKIT_MAXIMUM_RETURN: + return "Gibberish returned!"; + default: + return "Gibberish returned!"; + } +} diff --git a/libhashkit/strerror.h b/libhashkit/strerror.h new file mode 100644 index 00000000..4cb91972 --- /dev/null +++ b/libhashkit/strerror.h @@ -0,0 +1,22 @@ +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +#ifndef HASHKIT_STRERROR_H +#define HASHKIT_STRERROR_H + +#ifdef __cplusplus +extern "C" { +#endif + +const char *hashkit_strerror(hashkit_st *ptr __attribute__((unused)), hashkit_return_t rc); + +#ifdef __cplusplus +} +#endif + +#endif /* HASHKIT_STRERROR_H */ diff --git a/libhashkit/types.h b/libhashkit/types.h new file mode 100644 index 00000000..a06be2fb --- /dev/null +++ b/libhashkit/types.h @@ -0,0 +1,92 @@ + +/* HashKit + * Copyright (C) 2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +/** + * @file + * @brief HashKit Header + */ + +#ifndef HASHKIT_TYPES_H +#define HASHKIT_TYPES_H + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * @addtogroup hashkit_types Types + * @ingroup hashkit + * @{ + */ + +typedef enum { + HASHKIT_SUCCESS, + HASHKIT_FAILURE, + HASHKIT_MEMORY_ALLOCATION_FAILURE, + HASHKIT_MAXIMUM_RETURN /* Always add new error code before */ +} hashkit_return_t; + +/** + @todo hashkit_options_t is for future use, currently we do not define any user options. + */ + +typedef enum +{ + HASHKIT_OPTION_MAX +} hashkit_options_t; + +typedef struct +{ + /* We use the following for internal book keeping. */ + bool is_initialized:1; + bool is_allocated:1; +} hashkit_options_st; + +typedef enum { + HASHKIT_HASH_DEFAULT= 0, + HASHKIT_HASH_MD5, + HASHKIT_HASH_CRC, + HASHKIT_HASH_FNV1_64, + HASHKIT_HASH_FNV1A_64, + HASHKIT_HASH_FNV1_32, + HASHKIT_HASH_FNV1A_32, + HASHKIT_HASH_HSIEH, + HASHKIT_HASH_MURMUR, + HASHKIT_HASH_JENKINS, + HASHKIT_HASH_MAX +} hashkit_hash_algorithm_t; + +/** + * Hash distributions that are available to use. + */ +typedef enum +{ + HASHKIT_DISTRIBUTION_MODULA, + HASHKIT_DISTRIBUTION_RANDOM, + HASHKIT_DISTRIBUTION_KETAMA, + HASHKIT_DISTRIBUTION_MAX /* Always add new values before this. */ +} hashkit_distribution_t; + + +typedef struct hashkit_st hashkit_st; +typedef struct hashkit_continuum_point_st hashkit_continuum_point_st; +typedef bool (hashkit_active_fn)(void *context); +typedef uint32_t (hashkit_fn)(const char *key, size_t key_length); +typedef size_t (hashkit_key_fn)(char *key, size_t key_length, uint32_t point_index, void *context); +typedef void (hashkit_sort_fn)(void *context, size_t count); +typedef uint32_t (hashkit_weight_fn)(void *context); + +/** @} */ + + +#ifdef __cplusplus +} +#endif + +#endif /* HASHKIT_TYPES_H */ diff --git a/libhashkit/visibility.h b/libhashkit/visibility.h new file mode 100644 index 00000000..7691d4b5 --- /dev/null +++ b/libhashkit/visibility.h @@ -0,0 +1,51 @@ +/* + * Summary: interface for HashKit functions + * Description: visibitliy macros for HashKit library + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in this directory for full text. + * + * Author: Monty Taylor + */ + +/** + * @file + * @brief Visibility control macros + */ + +#ifndef HASHKIT_VISIBILITY_H +#define HASHKIT_VISIBILITY_H + +/** + * + * HASHKIT_API is used for the public API symbols. It either DLL imports or + * DLL exports (or does nothing for static build). + * + * HASHKIT_LOCAL is used for non-api symbols. + */ + +#if defined(BUILDING_HASHKIT) +# if defined(HAVE_VISIBILITY) && HAVE_VISIBILITY +# define HASHKIT_API __attribute__ ((visibility("default"))) +# define HASHKIT_LOCAL __attribute__ ((visibility("hidden"))) +# elif defined (__SUNPRO_C) && (__SUNPRO_C >= 0x550) +# define HASHKIT_API __global +# define HASHKIT_LOCAL __hidden +# elif defined(_MSC_VER) +# define HASHKIT_API extern __declspec(dllexport) +# define HASHKIT_LOCAL +# else +# define HASHKIT_API +# define HASHKIT_LOCAL +# endif /* defined(HAVE_VISIBILITY) */ +#else /* defined(BUILDING_HASHKIT) */ +# if defined(_MSC_VER) +# define HASHKIT_API extern __declspec(dllimport) +# define HASHKIT_LOCAL +# else +# define HASHKIT_API +# define HASHKIT_LOCAL +# endif /* defined(_MSC_VER) */ +#endif /* defined(BUILDING_HASHKIT) */ + +#endif /* HASHKIT_VISIBILITY_H */ diff --git a/support/libmemcached.spec.in b/support/libmemcached.spec.in index 648ee53f..ceeb36fb 100644 --- a/support/libmemcached.spec.in +++ b/support/libmemcached.spec.in @@ -88,6 +88,7 @@ you will need to install %{name}-devel. %{_libdir}/libmemcachedutil.so.* %{_libdir}/libmemcachedprotocol.so.* %{_mandir}/man1/mem* +%exclude libhashkit/* %files devel diff --git a/tests/Makefile.am b/tests/Makefile.am index 6c51d28f..edca779c 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -19,7 +19,7 @@ EXTRA_DIST = \ LIBS = noinst_HEADERS = test.h server.h ketama_test_cases.h ketama_test_cases_spy.h hash_results.h libmemcached_world.h -noinst_PROGRAMS = testapp testplus udptest atomsmasher startservers +noinst_PROGRAMS = testapp testplus udptest atomsmasher startservers testhashkit noinst_LTLIBRARIES= libserver.la libtest.la libserver_la_SOURCES= server.c @@ -41,6 +41,9 @@ atomsmasher_LDADD = $(top_builddir)/clients/libgenexec.la libtest.la libserver.l startservers_SOURCES = start.c startservers_LDADD = libserver.la $(LDADDS) +testhashkit_SOURCES = hashkit_functions.c +testhashkit_LDADD = libtest.la $(top_builddir)/libhashkit/libhashkit.la + client-record: sh t/memcat.test > r/memcat.res sh t/memcp.test > r/memcp.res @@ -48,12 +51,14 @@ client-record: sh t/memslap.test > r/memslap.res sh t/memstat.test > r/memstat.res -test: testapp testplus library_test memcapable +test: testapp testhashkit testplus library_test libmhashkit_test memcapable echo "Tests completed" library_test: ./testapp -# ./testplus + +libmhashkit_test: + ./testhashkit memcapable: @MEMC_BINARY@ -d -P /tmp/Xumemc.pid -p 12555 @@ -77,6 +82,12 @@ clients: cat /tmp/Xumemc.pid | xargs kill rm /tmp/Xumemc.pid +gdb-mem: + $(LIBTOOL) --mode=execute gdb testapp + +gdb-hash: + $(LIBTOOL) --mode=execute gdb testhashkit + valgrind: $(LIBTOOL) --mode=execute valgrind --leak-check=yes --show-reachable=yes testapp diff --git a/tests/hashkit_functions.c b/tests/hashkit_functions.c new file mode 100644 index 00000000..1302011e --- /dev/null +++ b/tests/hashkit_functions.c @@ -0,0 +1,363 @@ +/* libHashKit Functions Test + * Copyright (C) 2006-2009 Brian Aker + * All rights reserved. + * + * Use and distribution licensed under the BSD license. See + * the COPYING file in the parent directory for full text. + */ + +#include +#include +#include +#include + +#include + +#include "test.h" + +#include "hash_results.h" + +static hashkit_st global_hashk; + +/** + @brief hash_test_st is a structure we use in testing. It is currently empty. +*/ +typedef struct hash_test_st hash_test_st; + +struct hash_test_st +{ + bool _unused; +}; + +static test_return_t init_test(void *not_used __attribute__((unused))) +{ + hashkit_st hashk; + hashkit_st *hashk_ptr; + + hashk_ptr= hashkit_create(&hashk); + test_truth(hashk_ptr); + test_truth(hashk_ptr == &hashk); + test_truth(hashkit_is_initialized(&hashk) == true); + test_truth(hashkit_is_allocated(hashk_ptr) == false); + + hashkit_free(hashk_ptr); + + test_truth(hashkit_is_initialized(&hashk) == false); + + return TEST_SUCCESS; +} + +static test_return_t allocation_test(void *not_used __attribute__((unused))) +{ + hashkit_st *hashk_ptr; + + hashk_ptr= hashkit_create(NULL); + test_truth(hashk_ptr); + test_truth(hashkit_is_allocated(hashk_ptr) == true); + test_truth(hashkit_is_initialized(hashk_ptr) == true); + hashkit_free(hashk_ptr); + + return TEST_SUCCESS; +} + +static test_return_t clone_test(hashkit_st *hashk) +{ + // First we make sure that the testing system is giving us what we expect. + assert(&global_hashk == hashk); + + // Second we test if hashk is even valid + test_truth(hashkit_is_initialized(hashk) == true); + + /* All null? */ + { + hashkit_st *hashk_ptr; + hashk_ptr= hashkit_clone(NULL, NULL); + test_truth(hashk_ptr); + test_truth(hashkit_is_allocated(hashk_ptr) == true); + test_truth(hashkit_is_initialized(hashk_ptr) == true); + hashkit_free(hashk_ptr); + } + + /* Can we init from null? */ + { + hashkit_st *hashk_ptr; + + hashk_ptr= hashkit_clone(NULL, hashk); + + test_truth(hashk_ptr); + test_truth(hashkit_is_allocated(hashk_ptr) == true); + test_truth(hashkit_is_initialized(hashk_ptr) == true); + + test_truth(hashk_ptr->distribution == hashk->distribution); + test_truth(hashk_ptr->continuum_count == hashk->continuum_count); + test_truth(hashk_ptr->continuum_points_count == hashk->continuum_points_count); + test_truth(hashk_ptr->list_size == hashk->list_size); + test_truth(hashk_ptr->context_size == hashk->context_size); + test_truth(hashk_ptr->continuum == NULL); + test_truth(hashk_ptr->hash_fn == hashk->hash_fn); + test_truth(hashk_ptr->active_fn == hashk->active_fn); + test_truth(hashk_ptr->continuum_hash_fn == hashk->continuum_hash_fn); + test_truth(hashk_ptr->continuum_key_fn == hashk->continuum_key_fn); + test_truth(hashk_ptr->sort_fn == hashk->sort_fn); + test_truth(hashk_ptr->weight_fn == hashk->weight_fn); + test_truth(hashk_ptr->list == hashk->list); + + hashkit_free(hashk_ptr); + } + + /* Can we init from struct? */ + { + hashkit_st declared_clone; + hashkit_st *hash_clone; + + hash_clone= hashkit_clone(&declared_clone, NULL); + test_truth(hash_clone); + + hashkit_free(hash_clone); + } + + /* Can we init from struct? */ + { + hashkit_st declared_clone; + hashkit_st *hash_clone; + memset(&declared_clone, 0 , sizeof(hashkit_st)); + hash_clone= hashkit_clone(&declared_clone, hashk); + test_truth(hash_clone); + hashkit_free(hash_clone); + } + + return TEST_SUCCESS; +} + + +static test_return_t md5_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= hashkit_md5(*ptr, strlen(*ptr)); + test_truth(md5_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return_t crc_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= hashkit_crc32(*ptr, strlen(*ptr)); + assert(crc_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return_t fnv1_64_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= hashkit_fnv1_64(*ptr, strlen(*ptr)); + assert(fnv1_64_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return_t fnv1a_64_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= hashkit_fnv1a_64(*ptr, strlen(*ptr)); + assert(fnv1a_64_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return_t fnv1_32_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= hashkit_fnv1_32(*ptr, strlen(*ptr)); + assert(fnv1_32_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return_t fnv1a_32_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= hashkit_fnv1a_32(*ptr, strlen(*ptr)); + assert(fnv1a_32_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return_t hsieh_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + +#ifdef HAVE_HSIEH_HASH + hash_val= hashkit_hsieh(*ptr, strlen(*ptr)); +#else + hash_val= 1; +#endif + assert(hsieh_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return_t murmur_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= hashkit_murmur(*ptr, strlen(*ptr)); + assert(murmur_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return_t jenkins_run (hashkit_st *hashk __attribute__((unused))) +{ + uint32_t x; + const char **ptr; + + + for (ptr= list_to_hash, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= hashkit_jenkins(*ptr, strlen(*ptr)); + assert(jenkins_values[x] == hash_val); + } + + return TEST_SUCCESS; +} + + + + +/** + @brief now we list out the tests. +*/ + +test_st allocation[]= { + {"init", 0, (test_callback_fn)init_test}, + {"create and free", 0, (test_callback_fn)allocation_test}, + {"clone", 0, (test_callback_fn)clone_test}, + {0, 0, 0} +}; + +test_st hash_tests[] ={ + {"md5", 0, (test_callback_fn)md5_run }, + {"crc", 0, (test_callback_fn)crc_run }, + {"fnv1_64", 0, (test_callback_fn)fnv1_64_run }, + {"fnv1a_64", 0, (test_callback_fn)fnv1a_64_run }, + {"fnv1_32", 0, (test_callback_fn)fnv1_32_run }, + {"fnv1a_32", 0, (test_callback_fn)fnv1a_32_run }, + {"hsieh", 0, (test_callback_fn)hsieh_run }, + {"murmur", 0, (test_callback_fn)murmur_run }, + {"jenkis", 0, (test_callback_fn)jenkins_run }, + {0, 0, (test_callback_fn)0} +}; + +/* + * The following test suite is used to verify that we don't introduce + * regression bugs. If you want more information about the bug / test, + * you should look in the bug report at + * http://bugs.launchpad.net/libmemcached + */ +test_st regression[]= { + {0, 0, 0} +}; + +collection_st collection[] ={ + {"allocation", 0, 0, allocation}, + {"regression", 0, 0, regression}, + {"hashing", 0, 0, hash_tests}, + {0, 0, 0, 0} +}; + +/* Prototypes for functions we will pass to test framework */ +void *world_create(void); +test_return_t world_destroy(hashkit_st *hashk); + +void *world_create(void) +{ + hashkit_st *hashk_ptr; + + hashk_ptr= hashkit_create(&global_hashk); + + assert(hashk_ptr == &global_hashk); + + // First we test if hashk is even valid + assert(hashkit_is_initialized(hashk_ptr) == true); + assert(hashkit_is_allocated(hashk_ptr) == false); + assert(hashk_ptr->continuum == NULL); + + return hashk_ptr; +} + + +test_return_t world_destroy(hashkit_st *hashk) +{ + // Did we get back what we expected? + assert(hashkit_is_initialized(hashk) == true); + assert(hashkit_is_allocated(hashk) == false); + hashkit_free(&global_hashk); + + return TEST_SUCCESS; +} + +void get_world(world_st *world) +{ + world->collections= collection; + world->create= (test_callback_create_fn)world_create; + world->destroy= (test_callback_fn)world_destroy; +} -- 2.30.2