From 542ea353c726f6d552b51128932a9b18ed3ed8f2 Mon Sep 17 00:00:00 2001 From: Brian Aker Date: Thu, 28 May 2009 11:04:05 -0700 Subject: [PATCH] Added memcached_generate_hash() and more tests! :) --- .bzrignore | 3 + ChangeLog | 2 + docs/memcached_generate_hash_value.pod | 9 + libmemcached/common.h | 1 - libmemcached/memcached.h | 4 + tests/function.c | 240 ++++++++++++++++++++++++- tests/output.res | 84 ++++++++- 7 files changed, 335 insertions(+), 8 deletions(-) diff --git a/.bzrignore b/.bzrignore index c66b03b9..7cb02a8e 100644 --- a/.bzrignore +++ b/.bzrignore @@ -163,3 +163,6 @@ ltoptions.m4 ltsugar.m4 ltversion.m4 libtool.m4 +TAGS +*TAGS +*.lo diff --git a/ChangeLog b/ChangeLog index 42241508..a097ebb5 100644 --- a/ChangeLog +++ b/ChangeLog @@ -3,6 +3,8 @@ * Realigned all structures to remove padding (and line up important bits for 64bit caches. * Remove some of sprintf() in storage calls(). * Removed printf() in stat call for unknown stat member. + * memcached_generate_hash() function added. + * Added tests to make sure all hash functions are stable. 0.29 Tue May 19 08:26:48 PDT 2009 * Fixed malloc usage to calloc for spots where we need zero filled memory. diff --git a/docs/memcached_generate_hash_value.pod b/docs/memcached_generate_hash_value.pod index 8f2c78de..dd45ab3e 100644 --- a/docs/memcached_generate_hash_value.pod +++ b/docs/memcached_generate_hash_value.pod @@ -15,6 +15,11 @@ C Client Library for memcached (libmemcached, -lmemcached) size_t key_length, memcached_hash hash_algorithm); + uint32_t + memcached_generate_hash (memcached_st *ptr, + const char *key, + size_t key_length); + =head1 DESCRIPTION memcached_generate_hash_value() allows you to hash a key using one of @@ -25,6 +30,10 @@ for normal memcache operations. The allowed hash algorithm constants are listed in the manpage for memcached_behavior_set(). +memcached_generate_hash() takes a memcached_st struture and produces +the hash value that would have been generated based on the defaults +of the memcached_st structure. + =head1 RETURN A 32-bit integer which is the result of hashing the given key. diff --git a/libmemcached/common.h b/libmemcached/common.h index e5dffe5b..10b434f1 100644 --- a/libmemcached/common.h +++ b/libmemcached/common.h @@ -97,7 +97,6 @@ memcached_return memcached_connect(memcached_server_st *ptr); memcached_return memcached_response(memcached_server_st *ptr, char *buffer, size_t buffer_length, memcached_result_st *result); -uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_length); void memcached_quit_server(memcached_server_st *ptr, uint8_t io_death); #define memcached_server_response_increment(A) (A)->cursor_active++ diff --git a/libmemcached/memcached.h b/libmemcached/memcached.h index 864c042b..8c506021 100644 --- a/libmemcached/memcached.h +++ b/libmemcached/memcached.h @@ -163,7 +163,11 @@ void memcached_quit(memcached_st *ptr); char *memcached_strerror(memcached_st *ptr, memcached_return rc); memcached_return memcached_behavior_set(memcached_st *ptr, memcached_behavior flag, uint64_t data); uint64_t memcached_behavior_get(memcached_st *ptr, memcached_behavior flag); + +/* The two public hash bits */ uint32_t memcached_generate_hash_value(const char *key, size_t key_length, memcached_hash hash_algorithm); +uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_length); + memcached_return memcached_flush_buffers(memcached_st *mem); /* Server Public functions */ diff --git a/tests/function.c b/tests/function.c index ba3c3219..e69335ae 100644 --- a/tests/function.c +++ b/tests/function.c @@ -3272,7 +3272,7 @@ static test_return noreply_test(memcached_st *memc) for (int x=0; x < 100; ++x) { char key[10]; - size_t len=sprintf(key, "%d", x); + size_t len= sprintf(key, "%d", x); switch (count) { case 0: @@ -3312,7 +3312,7 @@ static test_return noreply_test(memcached_st *memc) for (int x=0; x < 100; ++x) { char key[10]; - size_t len=sprintf(key, "%d", x); + size_t len= sprintf(key, "%d", x); size_t length; uint32_t flags; char* value=memcached_get(memc, key, strlen(key), @@ -3833,6 +3833,228 @@ static test_return hsieh_avaibility_test (memcached_st *memc) return TEST_SUCCESS; } +static char *list[]= +{ + "apple", + "beat", + "carrot", + "daikon", + "eggplant", + "flower", + "green", + "hide", + "ick", + "jack", + "kick", + "lime", + "mushrooms", + "nectarine", + "orange", + "peach", + "quant", + "ripen", + "strawberry", + "tang", + "up", + "volumne", + "when", + "yellow", + "zip", + NULL +}; + +static test_return md5_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; + uint32_t values[]= { 3195025439, 2556848621, 3724893440, 3332385401, 245758794, 2550894432, + 121710495, 3053817768, 1250994555, 1862072655, 2631955953, 2951528551, + 1451250070, 2820856945, 2060845566, 3646985608, 2138080750, 217675895, + 2230934345, 1234361223, 3968582726, 2455685270, 1293568479, 199067604, + 2042482093 }; + + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_MD5); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return crc_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; + uint32_t values[]= { 10542, 22009, 14526, 19510, 19432, 10199, 20634, 9369, 11511, 10362, + 7893, 31289, 11313, 9354, 7621, 30628, 15218, 25967, 2695, 9380, + 17300, 28156, 9192, 20484, 16925 }; + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_CRC); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return fnv1_64_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; + uint32_t values[]= { 473199127, 4148981457, 3971873300, 3257986707, 1722477987, 2991193800, + 4147007314, 3633179701, 1805162104, 3503289120, 3395702895, 3325073042, + 2345265314, 3340346032, 2722964135, 1173398992, 2815549194, 2562818319, + 224996066, 2680194749, 3035305390, 246890365, 2395624193, 4145193337, + 1801941682 }; + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_FNV1_64); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return fnv1a_64_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; + uint32_t values[]= { 1488911807, 2500855813, 1510099634, 1390325195, 3647689787, 3241528582, + 1669328060, 2604311949, 734810122, 1516407546, 560948863, 1767346780, + 561034892, 4156330026, 3716417003, 3475297030, 1518272172, 227211583, + 3938128828, 126112909, 3043416448, 3131561933, 1328739897, 2455664041, + 2272238452 }; + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_FNV1A_64); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return fnv1_32_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; + uint32_t values[]= { 67176023, 1190179409, 2043204404, 3221866419, 2567703427, 3787535528, 4147287986, + 3500475733, 344481048, 3865235296, 2181839183, 119581266, 510234242, 4248244304, + 1362796839, 103389328, 1449620010, 182962511, 3554262370, 3206747549, 1551306158, + 4127558461, 1889140833, 2774173721, 1180552018 }; + + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_FNV1_32); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return fnv1a_32_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; + uint32_t values[]= { 280767167, 2421315013, 3072375666, 855001899, 459261019, 3521085446, 18738364, + 1625305005, 2162232970, 777243802, 3323728671, 132336572, 3654473228, 260679466, + 1169454059, 2698319462, 1062177260, 235516991, 2218399068, 405302637, 1128467232, + 3579622413, 2138539289, 96429129, 2877453236 }; + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_FNV1A_32); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return hsieh_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; +#ifdef HAVE_HSIEH_HASH + uint32_t values[]= { 3738850110, 3636226060, 3821074029, 3489929160, 3485772682, 80540287, + 1805464076, 1895033657, 409795758, 979934958, 3634096985, 1284445480, + 2265380744, 707972988, 353823508, 1549198350, 1327930172, 9304163, + 4220749037, 2493964934, 2777873870, 2057831732, 1510213931, 2027828987, + 3395453351 }; +#else + uint32_t values[]= { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; +#endif + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_HSIEH); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return murmur_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; + uint32_t values[]= { 473199127, 4148981457, 3971873300, 3257986707, 1722477987, 2991193800, + 4147007314, 3633179701, 1805162104, 3503289120, 3395702895, 3325073042, + 2345265314, 3340346032, 2722964135, 1173398992, 2815549194, 2562818319, + 224996066, 2680194749, 3035305390, 246890365, 2395624193, 4145193337, + 1801941682 }; + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_FNV1_64); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + +static test_return jenkins_run (memcached_st *memc __attribute__((unused))) +{ + uint32_t x; + char **ptr; + uint32_t values[]= { 1442444624, 4253821186, 1885058256, 2120131735, 3261968576, 3515188778, + 4232909173, 4288625128, 1812047395, 3689182164, 2502979932, 1214050606, + 2415988847, 1494268927, 1025545760, 3920481083, 4153263658, 3824871822, + 3072759809, 798622255, 3065432577, 1453328165, 2691550971, 3408888387, + 2629893356 }; + + + for (ptr= list, x= 0; *ptr; ptr++, x++) + { + uint32_t hash_val; + + hash_val= memcached_generate_hash_value(*ptr, strlen(*ptr), MEMCACHED_HASH_JENKINS); + assert(values[x] == hash_val); + } + + return TEST_SUCCESS; +} + test_st udp_setup_server_tests[] ={ {"set_udp_behavior_test", 0, set_udp_behavior_test}, {"add_tcp_server_udp_client_test", 0, add_tcp_server_udp_client_test}, @@ -4021,6 +4243,19 @@ test_st ketama_auto_eject_hosts[] ={ {0, 0, 0} }; +test_st hash_tests[] ={ + {"md5", 0, md5_run }, + {"crc", 0, crc_run }, + {"fnv1_64", 0, fnv1_64_run }, + {"fnv1a_64", 0, fnv1a_64_run }, + {"fnv1_32", 0, fnv1_32_run }, + {"fnv1a_32", 0, fnv1a_32_run }, + {"hsieh", 0, hsieh_run }, + {"murmur", 0, murmur_run }, + {"jenkis", 0, jenkins_run }, + {0, 0, 0} +}; + collection_st collection[] ={ {"hsieh_availability",0,0,hsieh_availability}, {"udp_setup", init_udp, 0, udp_setup_server_tests}, @@ -4065,6 +4300,7 @@ collection_st collection[] ={ {"consistent_not", 0, 0, consistent_tests}, {"consistent_ketama", pre_behavior_ketama, 0, consistent_tests}, {"consistent_ketama_weighted", pre_behavior_ketama_weighted, 0, consistent_weighted_tests}, + {"test_hashes", 0, 0, hash_tests}, {0, 0, 0, 0} }; diff --git a/tests/output.res b/tests/output.res index 627ed3f9..20bd676f 100644 --- a/tests/output.res +++ b/tests/output.res @@ -671,13 +671,87 @@ Error 33 -> A BAD KEY WAS PROVIDED/CHARACTERS OUT OF RANGE Error 34 -> THE HOST TRANSPORT PROTOCOL DOES NOT MATCH THAT OF THE CLIENT Error 35 -> SERVER IS MARKED DEAD Error 36 -> ENCOUNTERED AN UNKNOWN STAT KEY +Error 0 -> SUCCESS +Error 1 -> FAILURE +Error 2 -> HOSTNAME LOOKUP FAILURE +Error 3 -> CONNECTION FAILURE +Error 4 -> CONNECTION BIND FAILURE +Error 5 -> WRITE FAILURE +Error 6 -> READ FAILURE +Error 7 -> UNKNOWN READ FAILURE +Error 8 -> PROTOCOL ERROR +Error 9 -> CLIENT ERROR +Error 10 -> SERVER ERROR +Error 11 -> CONNECTION SOCKET CREATE FAILURE +Error 12 -> CONNECTION DATA EXISTS +Error 13 -> CONNECTION DATA DOES NOT EXIST +Error 14 -> NOT STORED +Error 15 -> STORED +Error 16 -> NOT FOUND +Error 17 -> MEMORY ALLOCATION FAILURE +Error 18 -> PARTIAL READ +Error 19 -> SOME ERRORS WERE REPORTED +Error 20 -> NO SERVERS DEFINED +Error 21 -> SERVER END +Error 22 -> SERVER DELETE +Error 23 -> SERVER VALUE +Error 24 -> STAT VALUE +Error 25 -> Gibberish returned! +Error 26 -> SYSTEM ERROR +Error 27 -> COULD NOT OPEN UNIX SOCKET +Error 28 -> ACTION NOT SUPPORTED +Error 29 -> A KEY LENGTH OF ZERO WAS PROVIDED +Error 30 -> FETCH WAS NOT COMPLETED +Error 31 -> A TIMEOUT OCCURRED +Error 32 -> ACTION QUEUED +Error 33 -> A BAD KEY WAS PROVIDED/CHARACTERS OUT OF RANGE +Error 34 -> THE HOST TRANSPORT PROTOCOL DOES NOT MATCH THAT OF THE CLIENT +Error 35 -> SERVER IS MARKED DEAD +Error 36 -> ENCOUNTERED AN UNKNOWN STAT KEY +Error 0 -> SUCCESS +Error 1 -> FAILURE +Error 2 -> HOSTNAME LOOKUP FAILURE +Error 3 -> CONNECTION FAILURE +Error 4 -> CONNECTION BIND FAILURE +Error 5 -> WRITE FAILURE +Error 6 -> READ FAILURE +Error 7 -> UNKNOWN READ FAILURE +Error 8 -> PROTOCOL ERROR +Error 9 -> CLIENT ERROR +Error 10 -> SERVER ERROR +Error 11 -> CONNECTION SOCKET CREATE FAILURE +Error 12 -> CONNECTION DATA EXISTS +Error 13 -> CONNECTION DATA DOES NOT EXIST +Error 14 -> NOT STORED +Error 15 -> STORED +Error 16 -> NOT FOUND +Error 17 -> MEMORY ALLOCATION FAILURE +Error 18 -> PARTIAL READ +Error 19 -> SOME ERRORS WERE REPORTED +Error 20 -> NO SERVERS DEFINED +Error 21 -> SERVER END +Error 22 -> SERVER DELETE +Error 23 -> SERVER VALUE +Error 24 -> STAT VALUE +Error 25 -> Gibberish returned! +Error 26 -> SYSTEM ERROR +Error 27 -> COULD NOT OPEN UNIX SOCKET +Error 28 -> ACTION NOT SUPPORTED +Error 29 -> A KEY LENGTH OF ZERO WAS PROVIDED +Error 30 -> FETCH WAS NOT COMPLETED +Error 31 -> A TIMEOUT OCCURRED +Error 32 -> ACTION QUEUED +Error 33 -> A BAD KEY WAS PROVIDED/CHARACTERS OUT OF RANGE +Error 34 -> THE HOST TRANSPORT PROTOCOL DOES NOT MATCH THAT OF THE CLIENT +Error 35 -> SERVER IS MARKED DEAD +Error 36 -> ENCOUNTERED AN UNKNOWN STAT KEY -server 0|localhost|11221 bytes: 3122227 +server 0|localhost|11221 bytes: 8443754 -server 1|localhost|11222 bytes: 3274763 +server 1|localhost|11222 bytes: 10067459 -server 2|localhost|11223 bytes: 3658723 +server 2|localhost|11223 bytes: 10454288 -server 3|localhost|11224 bytes: 3866224 +server 3|localhost|11224 bytes: 9560669 -server 4|localhost|11225 bytes: 3307046 +server 4|localhost|11225 bytes: 7411880 -- 2.30.2