FreeSWITCH API Documentation  1.7.0
switch_hashtable.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2002, Christopher Clark
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * * Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  *
12  * * Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in the
14  * documentation and/or other materials provided with the distribution.
15  *
16  * * Neither the name of the original author; nor the names of any contributors
17  * may be used to endorse or promote products derived from this software
18  * without specific prior written permission.
19  *
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
25  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33 
34 #include "switch.h"
36 
37 /*
38  Credit for primes table: Aaron Krowne
39  http://br.endernet.org/~akrowne/
40  http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
41 */
42 static const unsigned int primes[] = {
43  53, 97, 193, 389,
44  769, 1543, 3079, 6151,
45  12289, 24593, 49157, 98317,
46  196613, 393241, 786433, 1572869,
47  3145739, 6291469, 12582917, 25165843,
48  50331653, 100663319, 201326611, 402653189,
49  805306457, 1610612741
50 };
51 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
52 const float max_load_factor = 0.65f;
53 
54 /*****************************************************************************/
56 switch_create_hashtable(switch_hashtable_t **hp, unsigned int minsize,
57  unsigned int (*hashf) (void*),
58  int (*eqf) (void*,void*))
59 {
61  unsigned int pindex, size = primes[0];
62 
63  /* Check requested hashtable isn't too large */
64  if (minsize > (1u << 30)) {*hp = NULL; return SWITCH_STATUS_FALSE;}
65  /* Enforce size as prime */
66  for (pindex=0; pindex < prime_table_length; pindex++) {
67  if (primes[pindex] > minsize) {
68  size = primes[pindex];
69  break;
70  }
71  }
72  h = (switch_hashtable_t *) malloc(sizeof(switch_hashtable_t));
73 
74  if (NULL == h) abort(); /*oom*/
75 
76  h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
77 
78  if (NULL == h->table) abort(); /*oom*/
79 
80  memset(h->table, 0, size * sizeof(struct entry *));
81  h->tablelength = size;
82  h->primeindex = pindex;
83  h->entrycount = 0;
84  h->hashfn = hashf;
85  h->eqfn = eqf;
86  h->loadlimit = (unsigned int) ceil(size * max_load_factor);
87 
88  *hp = h;
89  return SWITCH_STATUS_SUCCESS;
90 }
91 
92 /*****************************************************************************/
93 static int
95 {
96  /* Double the size of the table to accomodate more entries */
97  struct entry **newtable;
98  struct entry *e;
99  struct entry **pE;
100  unsigned int newsize, i, index;
101  /* Check we're not hitting max capacity */
102  if (h->primeindex == (prime_table_length - 1)) return 0;
103  newsize = primes[++(h->primeindex)];
104 
105  newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
106  if (NULL != newtable)
107  {
108  memset(newtable, 0, newsize * sizeof(struct entry *));
109  /* This algorithm is not 'stable'. ie. it reverses the list
110  * when it transfers entries between the tables */
111  for (i = 0; i < h->tablelength; i++) {
112  while (NULL != (e = h->table[i])) {
113  h->table[i] = e->next;
114  index = indexFor(newsize,e->h);
115  e->next = newtable[index];
116  newtable[index] = e;
117  }
118  }
120  h->table = newtable;
121  }
122  /* Plan B: realloc instead */
123  else
124  {
125  newtable = (struct entry **)
126  realloc(h->table, newsize * sizeof(struct entry *));
127  if (NULL == newtable) { (h->primeindex)--; return 0; }
128  h->table = newtable;
129  memset(newtable[h->tablelength], 0, newsize - h->tablelength);
130  for (i = 0; i < h->tablelength; i++) {
131  for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
132  index = indexFor(newsize,e->h);
133 
134  if (index == i) {
135  pE = &(e->next);
136  } else {
137  *pE = e->next;
138  e->next = newtable[index];
139  newtable[index] = e;
140  }
141  }
142  }
143  }
144  h->tablelength = newsize;
145  h->loadlimit = (unsigned int) ceil(newsize * max_load_factor);
146  return -1;
147 }
148 
149 /*****************************************************************************/
150 SWITCH_DECLARE(unsigned int)
152 {
153  return h->entrycount;
154 }
155 
156 static void * _switch_hashtable_remove(switch_hashtable_t *h, void *k, unsigned int hashvalue, unsigned int index) {
157  /* TODO: consider compacting the table when the load factor drops enough,
158  * or provide a 'compact' method. */
159 
160  struct entry *e;
161  struct entry **pE;
162  void *v;
163 
164 
165  pE = &(h->table[index]);
166  e = *pE;
167  while (NULL != e) {
168  /* Check hash value to short circuit heavier comparison */
169  if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
170  *pE = e->next;
171  h->entrycount--;
172  v = e->v;
173  if (e->flags & HASHTABLE_FLAG_FREE_KEY) {
174  freekey(e->k);
175  }
176  if (e->flags & HASHTABLE_FLAG_FREE_VALUE) {
177  switch_safe_free(e->v);
178  v = NULL;
179  } else if (e->destructor) {
180  e->destructor(e->v);
181  v = e->v = NULL;
182  }
183  switch_safe_free(e);
184  return v;
185  }
186  pE = &(e->next);
187  e = e->next;
188  }
189  return NULL;
190 }
191 
192 /*****************************************************************************/
193 SWITCH_DECLARE(int)
195 {
196  struct entry *e;
197  unsigned int hashvalue = hash(h, k);
198  unsigned index = indexFor(h->tablelength, hashvalue);
199 
200  if (flags & HASHTABLE_DUP_CHECK) {
201  _switch_hashtable_remove(h, k, hashvalue, index);
202  }
203 
204  if (++(h->entrycount) > h->loadlimit)
205  {
206  /* Ignore the return value. If expand fails, we should
207  * still try cramming just this value into the existing table
208  * -- we may not have memory for a larger table, but one more
209  * element may be ok. Next time we insert, we'll try expanding again.*/
210  hashtable_expand(h);
211  index = indexFor(h->tablelength, hashvalue);
212  }
213  e = (struct entry *)malloc(sizeof(struct entry));
214  if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
215  e->h = hashvalue;
216  e->k = k;
217  e->v = v;
218  e->flags = flags;
219  e->destructor = destructor;
220  e->next = h->table[index];
221  h->table[index] = e;
222  return -1;
223 }
224 
225 /*****************************************************************************/
226 SWITCH_DECLARE(void *) /* returns value associated with key */
228 {
229  struct entry *e;
230  unsigned int hashvalue, index;
231  hashvalue = hash(h,k);
232  index = indexFor(h->tablelength,hashvalue);
233  e = h->table[index];
234  while (NULL != e) {
235  /* Check hash value to short circuit heavier comparison */
236  if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
237  e = e->next;
238  }
239  return NULL;
240 }
241 
242 /*****************************************************************************/
243 SWITCH_DECLARE(void *) /* returns value associated with key */
245 {
246  unsigned int hashvalue = hash(h,k);
247  return _switch_hashtable_remove(h, k, hashvalue, indexFor(h->tablelength,hashvalue));
248 }
249 
250 /*****************************************************************************/
251 /* destroy */
252 SWITCH_DECLARE(void)
254 {
255  unsigned int i;
256  struct entry *e, *f;
257  struct entry **table = (*h)->table;
258 
259  for (i = 0; i < (*h)->tablelength; i++) {
260  e = table[i];
261  while (NULL != e) {
262  f = e; e = e->next;
263 
264  if (f->flags & HASHTABLE_FLAG_FREE_KEY) {
265  freekey(f->k);
266  }
267 
268  if (f->flags & HASHTABLE_FLAG_FREE_VALUE) {
269  switch_safe_free(f->v);
270  } else if (f->destructor) {
271  f->destructor(f->v);
272  f->v = NULL;
273  }
274  switch_safe_free(f);
275  }
276  }
277 
278  switch_safe_free((*h)->table);
279  free(*h);
280  *h = NULL;
281 }
282 
284 {
285 
287 
288  if (i->e) {
289  if ((i->e = i->e->next) != 0) {
290  return i;
291  } else {
292  i->pos++;
293  }
294  }
295 
296  while(i->pos < i->h->tablelength && !i->h->table[i->pos]) {
297  i->pos++;
298  }
299 
300  if (i->pos >= i->h->tablelength) {
301  goto end;
302  }
303 
304  if ((i->e = i->h->table[i->pos]) != 0) {
305  return i;
306  }
307 
308  end:
309 
310  free(i);
311  *iP = NULL;
312 
313  return NULL;
314 }
315 
317 {
318  switch_hashtable_iterator_t *iterator;
319 
320  if (it) {
321  iterator = it;
322  } else {
323  switch_zmalloc(iterator, sizeof(*iterator));
324  }
325 
326  switch_assert(iterator);
327 
328  iterator->pos = 0;
329  iterator->e = NULL;
330  iterator->h = h;
331 
332  return switch_hashtable_next(&iterator);
333 }
334 
336 {
337  if (i->e) {
338  i->e->v = val;
339  }
340 }
341 
343 {
344  if (i->e) {
345  if (key) {
346  *key = i->e->k;
347  }
348  if (klen) {
349  *klen = (int)strlen(i->e->k);
350  }
351  if (val) {
352  *val = i->e->v;
353  }
354  } else {
355  if (key) {
356  *key = NULL;
357  }
358  if (klen) {
359  *klen = 0;
360  }
361  if (val) {
362  *val = NULL;
363  }
364  }
365 }
366 
367 
368 /* For Emacs:
369  * Local Variables:
370  * mode:c
371  * indent-tabs-mode:t
372  * tab-width:4
373  * c-basic-offset:4
374  * End:
375  * For VIM:
376  * vim:set softtabstop=4 shiftwidth=4 tabstop=4 noet:
377  */
378 
unsigned int h
struct switch_hashtable * h
const unsigned int prime_table_length
const float max_load_factor
void switch_hashtable_destroy(switch_hashtable_t **h)
void * switch_hashtable_search(switch_hashtable_t *h, void *k)
static __inline__ unsigned int indexFor(unsigned int tablelength, unsigned int hashvalue)
unsigned int switch_hashtable_count(switch_hashtable_t *h)
unsigned int(* hashfn)(void *k)
switch_hash_t * hash
Definition: switch_event.c:74
int switch_hashtable_insert_destructor(switch_hashtable_t *h, void *k, void *v, hashtable_flag_t flags, hashtable_destructor_t destructor)
intptr_t switch_ssize_t
#define switch_zmalloc(ptr, len)
#define switch_safe_free(it)
Free a pointer and set it to NULL unless it already is NULL.
Definition: switch_utils.h:789
hashtable_flag_t
void * switch_hashtable_remove(switch_hashtable_t *h, void *k)
static int hashtable_expand(switch_hashtable_t *h)
hashtable_flag_t flags
switch_status_t
Common return values.
void switch_hashtable_this_val(switch_hashtable_iterator_t *i, void *val)
Main Library Header.
#define SWITCH_DECLARE(type)
static void * _switch_hashtable_remove(switch_hashtable_t *h, void *k, unsigned int hashvalue, unsigned int index)
switch_status_t switch_create_hashtable(switch_hashtable_t **hp, unsigned int minsize, unsigned int(*hashf)(void *), int(*eqf)(void *, void *))
void switch_hashtable_this(switch_hashtable_iterator_t *i, const void **key, switch_ssize_t *klen, void **val)
int(* eqfn)(void *k1, void *k2)
static const unsigned int primes[]
#define freekey(X)
switch_hashtable_iterator_t * switch_hashtable_first_iter(switch_hashtable_t *h, switch_hashtable_iterator_t *it)
#define switch_assert(expr)
memset(buf, 0, buflen)
hashtable_destructor_t destructor
switch_hashtable_iterator_t * switch_hashtable_next(switch_hashtable_iterator_t **iP)
void(* hashtable_destructor_t)(void *ptr)
struct entry * next