git.m6w6.name Git - m6w6/libmemcached/blob - libhashkit/hashkit.c

   1 /* HashKit
   2  * Copyright (C) 2006-2009 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
   9 #include "common.h"
  10
  11 inline static bool _is_allocated(const hashkit_st *hashk)
  12 {
  13   return hashk->options.is_allocated == true;
  14 }
  15
  16 inline static bool _is_initialized(const hashkit_st *hashk)
  17 {
  18   return hashk->options.is_initialized == true;
  19 }
  20
  21 /**
  22   @note We make no assumptions that "hashk" has been, or not been allocated from heap/stack. We just know we didn't do it.
  23 */
  24 hashkit_st *hashkit_create(hashkit_st *hashk)
  25 {
  26   if (hashk == NULL)
  27   {
  28     hashk= (hashkit_st *)malloc(sizeof(hashkit_st));
  29     if (hashk == NULL)
  30     {
  31       return NULL;
  32     }
  33
  34     hashk->options.is_allocated= true;
  35   }
  36   else
  37   {
  38     hashk->options.is_allocated= false;
  39   }
  40
  41   hashk->options.is_initialized= true;
  42
  43   hashk->distribution= HASHKIT_DISTRIBUTION_MODULA;
  44   hashk->continuum_count= 0;
  45   hashk->continuum_points_count= 0;
  46   hashk->list_size= 0;
  47   hashk->context_size= 0;
  48   hashk->continuum= NULL;
  49   hashk->hash_fn= NULL;
  50   hashk->active_fn= NULL;
  51   hashk->continuum_hash_fn= NULL;
  52   hashk->continuum_key_fn= NULL;
  53   hashk->sort_fn= NULL;
  54   hashk->weight_fn= NULL;
  55   hashk->list= NULL;
  56
  57   return hashk;
  58 }
  59
  60
  61 void hashkit_free(hashkit_st *hashk)
  62 {
  63   assert(_is_initialized(hashk) == true);
  64
  65   if (hashk->continuum != NULL)
  66   {
  67     free(hashk->continuum);
  68   }
  69
  70   /**
  71     We don't know if hashk is pointing to something else,
  72     so we go on and set is_initialized.
  73   */
  74   hashk->options.is_initialized= false;
  75
  76   if (_is_allocated(hashk))
  77   {
  78     free(hashk);
  79   }
  80 }
  81
  82 /**
  83   @note We do assume source is valid. If source does not exist, we allocate.
  84 */
  85 hashkit_st *hashkit_clone(hashkit_st *destination, const hashkit_st *source)
  86 {
  87   hashkit_st *new_clone;
  88
  89   if (source == NULL)
  90   {
  91     return hashkit_create(destination);
  92   }
  93   else
  94   {
  95     assert(_is_initialized(source) == true);
  96   }
  97
  98   /* new_clone will be a pointer to destination */
  99   new_clone= hashkit_create(destination);
 100   assert((destination ?  ((_is_allocated(new_clone) == false)) : (_is_allocated(new_clone) == true)));
 101
 102   // Should only happen on allocation failure.
 103   if (new_clone == NULL)
 104   {
 105     return NULL;
 106   }
 107
 108   // For the moment we will not clone this.
 109   new_clone->continuum= NULL;
 110
 111   new_clone->distribution= source->distribution;
 112   new_clone->continuum_count= source->continuum_count;
 113   new_clone->continuum_points_count= source->continuum_points_count;
 114   new_clone->list_size= source->list_size;
 115   new_clone->context_size= source->context_size;
 116
 117
 118   new_clone->hash_fn= source->hash_fn;
 119   new_clone->active_fn= source->active_fn;
 120   new_clone->continuum_hash_fn= source->continuum_hash_fn;
 121   new_clone->continuum_key_fn= source->continuum_key_fn;
 122   new_clone->sort_fn= source->sort_fn;
 123   new_clone->weight_fn= source->weight_fn;
 124   new_clone->list= source->list;
 125
 126   return new_clone;
 127 }
 128
 129
 130 #if 0
 131 void hashkit_set_list(hashkit_st *hashkit, void *list, size_t list_size, size_t context_size)
 132 {
 133   hashkit->list= list;
 134   hashkit->list_size= list_size;
 135   hashkit->context_size= context_size;
 136 }
 137
 138
 139 uint32_t hashkit_value(hashkit_st *hashkit, const char *key, size_t key_length)
 140 {
 141   if (hashkit->hash_fn == NULL)
 142     return hashkit_default(key, key_length);
 143
 144   return hashkit->hash_fn(key, key_length);
 145 }
 146
 147
 148 uint32_t hashkit_index(hashkit_st *hashkit, uint32_t hash_value)
 149 {
 150   if (hashkit->list_size == 1)
 151     return 0;
 152
 153   switch (hashkit->distribution)
 154   {
 155   case HASHKIT_DISTRIBUTION_MODULA:
 156     return hash_value % (uint32_t)hashkit->list_size;
 157
 158   case HASHKIT_DISTRIBUTION_RANDOM:
 159     return (uint32_t)random() % (uint32_t)hashkit->list_size;
 160
 161   case HASHKIT_DISTRIBUTION_KETAMA:
 162   {
 163     hashkit_continuum_point_st *begin, *end, *left, *right, *middle;
 164     begin= left= hashkit->continuum;
 165     end= right= hashkit->continuum + hashkit->continuum_points_count;
 166
 167     while (left < right)
 168     {
 169       middle= left + (right - left) / 2;
 170       if (middle->value < hash_value)
 171         left= middle + 1;
 172       else
 173         right= middle;
 174     }
 175     if (right == end)
 176       right= begin;
 177     return right->index;
 178   }
 179
 180   case HASHKIT_DISTRIBUTION_MAX:
 181   default:
 182     /* We have added a distribution without extending the logic */
 183     return hash_value % (uint32_t)hashkit->list_size;
 184   }
 185
 186   /* NOTREACHED */
 187 }
 188
 189
 190 int hashkit_run_distribution(hashkit_st *hashkit)
 191 {
 192   switch (hashkit->distribution)
 193   {
 194   case HASHKIT_DISTRIBUTION_MODULA:
 195     if (hashkit->sort_fn != NULL && hashkit->list_size > 1)
 196       hashkit->sort_fn(hashkit->list, hashkit->list_size);
 197     break;
 198   case HASHKIT_DISTRIBUTION_RANDOM:
 199     break;
 200   case HASHKIT_DISTRIBUTION_KETAMA:
 201     return update_continuum(hashkit);
 202   case HASHKIT_DISTRIBUTION_MAX:
 203   default:
 204     /* We have added a distribution without extending the logic */
 205     break;
 206   }
 207
 208   return 0;
 209 }
 210 #endif
 211
 212
 213 uint32_t hashkit_generate_value(const char *key, size_t key_length, hashkit_hash_algorithm_t hash_algorithm)
 214 {
 215   switch (hash_algorithm)
 216   {
 217   case HASHKIT_HASH_DEFAULT:
 218     return hashkit_default(key, key_length);
 219   case HASHKIT_HASH_MD5:
 220     return hashkit_md5(key, key_length);
 221   case HASHKIT_HASH_CRC:
 222     return hashkit_crc32(key, key_length);
 223   case HASHKIT_HASH_FNV1_64:
 224     return hashkit_fnv1_64(key, key_length);
 225   case HASHKIT_HASH_FNV1A_64:
 226     return hashkit_fnv1a_64(key, key_length);
 227   case HASHKIT_HASH_FNV1_32:
 228     return hashkit_fnv1_32(key, key_length);
 229   case HASHKIT_HASH_FNV1A_32:
 230     return hashkit_fnv1a_32(key, key_length);
 231   case HASHKIT_HASH_HSIEH:
 232 #ifdef HAVE_HSIEH_HASH
 233     return hashkit_hsieh(key, key_length);
 234 #else
 235     return 1;
 236 #endif
 237   case HASHKIT_HASH_MURMUR:
 238     return hashkit_murmur(key, key_length);
 239   case HASHKIT_HASH_JENKINS:
 240     return hashkit_jenkins(key, key_length);
 241   case HASHKIT_HASH_MAX:
 242   default:
 243 #ifdef HAVE_DEBUG
 244     fprintf(stderr, "hashkit_hash_t was extended but hashkit_generate_value was not updated\n");
 245     fflush(stderr);
 246     assert(0);
 247 #endif
 248     break;
 249   }
 250
 251   return 1;
 252 }