git.m6w6.name Git - m6w6/libmemcached/blob - libmemcached/hash.c

   1 #include "common.h"
   2
   3
   4 uint32_t memcached_generate_hash_value(const char *key, size_t key_length, memcached_hash_t hash_algorithm)
   5 {
   6   return libhashkit_digest(key, key_length, (hashkit_hash_algorithm_t)hash_algorithm);
   7 }
   8
   9 uint32_t generate_hash(memcached_st *ptr, const char *key, size_t key_length)
  10 {
  11   uint32_t hash= 1; /* Just here to remove compile warning */
  12
  13
  14   WATCHPOINT_ASSERT(memcached_server_count(ptr));
  15
  16   if (memcached_server_count(ptr) == 1)
  17     return 0;
  18
  19   hash= hashkit_digest(&ptr->hashkit, key, key_length);
  20   WATCHPOINT_ASSERT(hash);
  21
  22   return hash;
  23 }
  24
  25 static uint32_t dispatch_host(memcached_st *ptr, uint32_t hash)
  26 {
  27   switch (ptr->distribution)
  28   {
  29   case MEMCACHED_DISTRIBUTION_CONSISTENT:
  30   case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA:
  31   case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA_SPY:
  32     {
  33       uint32_t num= ptr->continuum_points_counter;
  34       WATCHPOINT_ASSERT(ptr->continuum);
  35
  36       hash= hash;
  37       memcached_continuum_item_st *begin, *end, *left, *right, *middle;
  38       begin= left= ptr->continuum;
  39       end= right= ptr->continuum + num;
  40
  41       while (left < right)
  42       {
  43         middle= left + (right - left) / 2;
  44         if (middle->value < hash)
  45           left= middle + 1;
  46         else
  47           right= middle;
  48       }
  49       if (right == end)
  50         right= begin;
  51       return right->index;
  52     }
  53   case MEMCACHED_DISTRIBUTION_MODULA:
  54     return hash % memcached_server_count(ptr);
  55   case MEMCACHED_DISTRIBUTION_RANDOM:
  56     return (uint32_t) random() % memcached_server_count(ptr);
  57   case MEMCACHED_DISTRIBUTION_CONSISTENT_MAX:
  58   default:
  59     WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */
  60     return hash % memcached_server_count(ptr);
  61   }
  62   /* NOTREACHED */
  63 }
  64
  65 /*
  66   One day make this public, and have it return the actual memcached_server_st
  67   to the calling application.
  68 */
  69 uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_length)
  70 {
  71   uint32_t hash= 1; /* Just here to remove compile warning */
  72
  73   WATCHPOINT_ASSERT(memcached_server_count(ptr));
  74
  75   if (memcached_server_count(ptr) == 1)
  76     return 0;
  77
  78   if (ptr->flags.hash_with_prefix_key)
  79   {
  80     size_t temp_length= ptr->prefix_key_length + key_length;
  81     char temp[temp_length];
  82
  83     if (temp_length > MEMCACHED_MAX_KEY -1)
  84       return 0;
  85
  86     strncpy(temp, ptr->prefix_key, ptr->prefix_key_length);
  87     strncpy(temp + ptr->prefix_key_length, key, key_length);
  88     hash= generate_hash(ptr, temp, temp_length);
  89   }
  90   else
  91   {
  92     hash= generate_hash(ptr, key, key_length);
  93   }
  94
  95   WATCHPOINT_ASSERT(hash);
  96
  97   if (memcached_behavior_get(ptr, MEMCACHED_BEHAVIOR_AUTO_EJECT_HOSTS) && ptr->next_distribution_rebuild)
  98   {
  99     struct timeval now;
 100
 101     if (gettimeofday(&now, NULL) == 0 &&
 102         now.tv_sec > ptr->next_distribution_rebuild)
 103     {
 104       run_distribution(ptr);
 105     }
 106   }
 107
 108   return dispatch_host(ptr, hash);
 109 }