1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
|
/* 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 <libhashkit/common.h>
#include <math.h>
#if 0
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, "%u",
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;
}
#endif
|