2 +--------------------------------------------------------------------+
3 | libmemcached - C/C++ Client Library for memcached |
4 +--------------------------------------------------------------------+
5 | Redistribution and use in source and binary forms, with or without |
6 | modification, are permitted under the terms of the BSD license. |
7 | You should have received a copy of the license in a bundled file |
8 | named LICENSE; in case you did not receive a copy you can review |
9 | the terms online at: https://opensource.org/licenses/BSD-3-Clause |
10 +--------------------------------------------------------------------+
11 | Copyright (c) 2006-2014 Brian Aker https://datadifferential.com/ |
12 | Copyright (c) 2020 Michael Wallner <mike@php.net> |
13 +--------------------------------------------------------------------+
16 #include "libmemcached/common.h"
19 # include <sys/time.h>
23 #include "libmemcached/virtual_bucket.h"
25 uint32_t memcached_generate_hash_value(const char *key
, size_t key_length
,
26 memcached_hash_t hash_algorithm
) {
27 return libhashkit_digest(key
, key_length
, (hashkit_hash_algorithm_t
) hash_algorithm
);
30 static inline uint32_t generate_hash(const Memcached
*ptr
, const char *key
, size_t key_length
) {
31 return hashkit_digest(&ptr
->hashkit
, key
, key_length
);
34 static uint32_t dispatch_host(const Memcached
*ptr
, uint32_t hash
) {
35 switch (ptr
->distribution
) {
36 case MEMCACHED_DISTRIBUTION_CONSISTENT
:
37 case MEMCACHED_DISTRIBUTION_CONSISTENT_WEIGHTED
:
38 case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA
:
39 case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA_SPY
: {
40 uint32_t num
= ptr
->ketama
.continuum_points_counter
;
41 WATCHPOINT_ASSERT(ptr
->ketama
.continuum
);
43 memcached_continuum_item_st
*begin
, *end
, *left
, *right
, *middle
;
44 begin
= left
= ptr
->ketama
.continuum
;
45 end
= right
= ptr
->ketama
.continuum
+ num
;
47 while (left
< right
) {
48 middle
= left
+ (right
- left
) / 2;
49 if (middle
->value
< hash
)
58 case MEMCACHED_DISTRIBUTION_MODULA
:
59 return hash
% memcached_server_count(ptr
);
60 case MEMCACHED_DISTRIBUTION_RANDOM
:
61 return (uint32_t) random() % memcached_server_count(ptr
);
62 case MEMCACHED_DISTRIBUTION_VIRTUAL_BUCKET
: {
63 return memcached_virtual_bucket_get(ptr
, hash
);
66 case MEMCACHED_DISTRIBUTION_CONSISTENT_MAX
:
67 WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */
68 return hash
% memcached_server_count(ptr
);
74 One version is public and will not modify the distribution hash, the other will.
76 static inline uint32_t _generate_hash_wrapper(const Memcached
*ptr
, const char *key
,
78 WATCHPOINT_ASSERT(memcached_server_count(ptr
));
80 if (memcached_server_count(ptr
) == 1)
83 if (ptr
->flags
.hash_with_namespace
) {
84 size_t temp_length
= memcached_array_size(ptr
->_namespace
) + key_length
;
85 char temp
[MEMCACHED_MAX_KEY
];
87 if (temp_length
> MEMCACHED_MAX_KEY
- 1)
90 strncpy(temp
, memcached_array_string(ptr
->_namespace
), memcached_array_size(ptr
->_namespace
));
91 strncpy(temp
+ memcached_array_size(ptr
->_namespace
), key
, key_length
);
93 return generate_hash(ptr
, temp
, temp_length
);
95 return generate_hash(ptr
, key
, key_length
);
99 static inline void _regen_for_auto_eject(Memcached
*ptr
) {
100 if (_is_auto_eject_host(ptr
) && ptr
->ketama
.next_distribution_rebuild
) {
103 if (gettimeofday(&now
, NULL
) == 0 and now
.tv_sec
> ptr
->ketama
.next_distribution_rebuild
) {
104 run_distribution(ptr
);
109 void memcached_autoeject(memcached_st
*ptr
) {
110 _regen_for_auto_eject(ptr
);
113 uint32_t memcached_generate_hash_with_redistribution(memcached_st
*ptr
, const char *key
,
115 uint32_t hash
= _generate_hash_wrapper(ptr
, key
, key_length
);
117 _regen_for_auto_eject(ptr
);
119 return dispatch_host(ptr
, hash
);
122 uint32_t memcached_generate_hash(const memcached_st
*shell
, const char *key
, size_t key_length
) {
123 const Memcached
*ptr
= memcached2Memcached(shell
);
125 return dispatch_host(ptr
, _generate_hash_wrapper(ptr
, key
, key_length
));
131 const hashkit_st
*memcached_get_hashkit(const memcached_st
*shell
) {
132 const Memcached
*ptr
= memcached2Memcached(shell
);
134 return &ptr
->hashkit
;
140 memcached_return_t
memcached_set_hashkit(memcached_st
*shell
, hashkit_st
*hashk
) {
141 Memcached
*self
= memcached2Memcached(shell
);
143 hashkit_free(&self
->hashkit
);
144 hashkit_clone(&self
->hashkit
, hashk
);
146 return MEMCACHED_SUCCESS
;
149 return MEMCACHED_INVALID_ARGUMENTS
;
152 const char *libmemcached_string_hash(memcached_hash_t type
) {
153 return libhashkit_string_hash((hashkit_hash_algorithm_t
) type
);