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

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