← Back to branch summary

~mordred/libmemcached/fix-weird-link

« back to all changes in this revision

Viewing changes to libhashkit/hashkit.c

  • Committer: Brian Aker
  • Date: 2009-12-17 17:28:30 UTC
  • Revision ID: brian@gir.tangent.org-20091217172830-h298d0m4x2wxmqlo
Adding back libhashkit.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
}