FreeSWITCH API Documentation  1.7.0
Macros | Typedefs | Enumerations | Functions
switch_hashtable.h File Reference
#include "switch.h"
+ Include dependency graph for switch_hashtable.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define switch_hashtable_insert(_h, _k, _v, _f)   switch_hashtable_insert_destructor(_h, _k, _v, _f, NULL)
 
#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype)
 
#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype)
 
#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype)
 
#define switch_hashtable_first(_h)   switch_hashtable_first_iter(_h, NULL)
 

Typedefs

typedef struct switch_hashtable switch_hashtable_t
 
typedef struct
switch_hashtable_iterator 
switch_hashtable_iterator_t
 

Enumerations

enum  hashtable_flag_t { HASHTABLE_FLAG_NONE = 0, HASHTABLE_FLAG_FREE_KEY = (1 << 0), HASHTABLE_FLAG_FREE_VALUE = (1 << 1), HASHTABLE_DUP_CHECK = (1 << 2) }
 

Functions

switch_status_t switch_create_hashtable (switch_hashtable_t **hp, unsigned int minsize, unsigned int(*hashfunction)(void *), int(*key_eq_fn)(void *, void *))
 
int switch_hashtable_insert_destructor (switch_hashtable_t *h, void *k, void *v, hashtable_flag_t flags, hashtable_destructor_t destructor)
 
void * switch_hashtable_search (switch_hashtable_t *h, void *k)
 
void * switch_hashtable_remove (switch_hashtable_t *h, void *k)
 
unsigned int switch_hashtable_count (switch_hashtable_t *h)
 
void switch_hashtable_destroy (switch_hashtable_t **h)
 
switch_hashtable_iterator_tswitch_hashtable_first_iter (switch_hashtable_t *h, switch_hashtable_iterator_t *it)
 
switch_hashtable_iterator_tswitch_hashtable_next (switch_hashtable_iterator_t **iP)
 
void switch_hashtable_this (switch_hashtable_iterator_t *i, const void **key, switch_ssize_t *klen, void **val)
 
void switch_hashtable_this_val (switch_hashtable_iterator_t *i, void *val)
 
static uint32_t switch_hash_default_int (void *ky)
 
static int switch_hash_equalkeys_int (void *k1, void *k2)
 
static int switch_hash_equalkeys (void *k1, void *k2)
 
static int switch_hash_equalkeys_ci (void *k1, void *k2)
 
static uint32_t switch_hash_default (void *ky)
 
static uint32_t switch_hash_default_ci (void *ky)
 

Macro Definition Documentation

#define DEFINE_HASHTABLE_INSERT (   fnname,
  keytype,
  valuetype 
)
Value:
int fnname (switch_hashtable_t *h, keytype *k, valuetype *v) \
{ \
return hashtable_insert(h,k,v); \
}
unsigned int h
return

Definition at line 130 of file switch_hashtable.h.

#define DEFINE_HASHTABLE_REMOVE (   fnname,
  keytype,
  valuetype 
)
Value:
valuetype * fnname (switch_hashtable_t *h, keytype *k) \
{ \
return (valuetype *) (hashtable_remove(h,k)); \
}
unsigned int h
return

Definition at line 166 of file switch_hashtable.h.

#define DEFINE_HASHTABLE_SEARCH (   fnname,
  keytype,
  valuetype 
)
Value:
valuetype * fnname (switch_hashtable_t *h, keytype *k) \
{ \
return (valuetype *) (hashtable_search(h,k)); \
}
unsigned int h
return

Definition at line 148 of file switch_hashtable.h.

#define switch_hashtable_first (   _h)    switch_hashtable_first_iter(_h, NULL)

Definition at line 196 of file switch_hashtable.h.

#define switch_hashtable_insert (   _h,
  _k,
  _v,
  _f 
)    switch_hashtable_insert_destructor(_h, _k, _v, _f, NULL)

Definition at line 128 of file switch_hashtable.h.

Typedef Documentation

Definition at line 25 of file switch_hashtable.h.

Definition at line 24 of file switch_hashtable.h.

Enumeration Type Documentation

Enumerator
HASHTABLE_FLAG_NONE 
HASHTABLE_FLAG_FREE_KEY 
HASHTABLE_FLAG_FREE_VALUE 
HASHTABLE_DUP_CHECK 

Definition at line 119 of file switch_hashtable.h.

Function Documentation

switch_status_t switch_create_hashtable ( switch_hashtable_t **  hp,
unsigned int  minsize,
unsigned int(*)(void *)  hashfunction,
int(*)(void *, void *)  key_eq_fn 
)

Definition at line 56 of file switch_hashtable.c.

References switch_hashtable::entrycount, switch_hashtable::eqfn, entry::h, switch_hashtable::hashfn, switch_hashtable::loadlimit, memset(), prime_table_length, switch_hashtable::primeindex, primes, SWITCH_STATUS_FALSE, SWITCH_STATUS_SUCCESS, switch_hashtable::table, and switch_hashtable::tablelength.

Referenced by switch_core_hash_init_case(), and switch_core_inthash_init().

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 }
unsigned int h
const unsigned int prime_table_length
const float max_load_factor
unsigned int(* hashfn)(void *k)
int(* eqfn)(void *k1, void *k2)
static const unsigned int primes[]
memset(buf, 0, buflen)
static uint32_t switch_hash_default ( void *  ky)
inlinestatic

Definition at line 224 of file switch_hashtable.h.

References hash.

Referenced by switch_core_hash_init_case().

225 {
226  unsigned char *str = (unsigned char *) ky;
227  uint32_t hash = 0;
228  int c;
229 
230  while ((c = *str)) {
231  str++;
232  hash = c + (hash << 6) + (hash << 16) - hash;
233  }
234 
235  return hash;
236 }
switch_hash_t * hash
Definition: switch_event.c:74
static uint32_t switch_hash_default_ci ( void *  ky)
inlinestatic

Definition at line 238 of file switch_hashtable.h.

References hash, and switch_tolower().

Referenced by switch_core_hash_init_case().

239 {
240  unsigned char *str = (unsigned char *) ky;
241  uint32_t hash = 0;
242  int c;
243 
244  while ((c = switch_tolower(*str))) {
245  str++;
246  hash = c + (hash << 6) + (hash << 16) - hash;
247  }
248 
249  return hash;
250 }
switch_hash_t * hash
Definition: switch_event.c:74
static uint32_t switch_tolower(uint32_t eax)
Definition: switch_utils.h:81
static uint32_t switch_hash_default_int ( void *  ky)
inlinestatic

Definition at line 201 of file switch_hashtable.h.

Referenced by switch_core_inthash_init().

201  {
202  uint32_t x = *((uint32_t *)ky);
203  x = ((x >> 16) ^ x) * 0x45d9f3b;
204  x = ((x >> 16) ^ x) * 0x45d9f3b;
205  x = ((x >> 16) ^ x);
206  return x;
207 }
static int switch_hash_equalkeys ( void *  k1,
void *  k2 
)
inlinestatic

Definition at line 214 of file switch_hashtable.h.

Referenced by switch_core_hash_init_case().

215 {
216  return strcmp((char *) k1, (char *) k2) ? 0 : 1;
217 }
static int switch_hash_equalkeys_ci ( void *  k1,
void *  k2 
)
inlinestatic

Definition at line 219 of file switch_hashtable.h.

Referenced by switch_core_hash_init_case().

220 {
221  return strcasecmp((char *) k1, (char *) k2) ? 0 : 1;
222 }
static int switch_hash_equalkeys_int ( void *  k1,
void *  k2 
)
inlinestatic

Definition at line 209 of file switch_hashtable.h.

Referenced by switch_core_inthash_init().

210 {
211  return *(uint32_t *)k1 == *(uint32_t *)k2;
212 }
unsigned int switch_hashtable_count ( switch_hashtable_t h)

Definition at line 151 of file switch_hashtable.c.

152 {
153  return h->entrycount;
154 }
void switch_hashtable_destroy ( switch_hashtable_t **  h)

Definition at line 253 of file switch_hashtable.c.

References entry::destructor, entry::flags, freekey, HASHTABLE_FLAG_FREE_KEY, HASHTABLE_FLAG_FREE_VALUE, entry::k, entry::next, switch_safe_free, and entry::v.

Referenced by switch_core_hash_destroy(), and switch_core_inthash_destroy().

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 }
#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 flags
#define freekey(X)
hashtable_destructor_t destructor
struct entry * next
switch_hashtable_iterator_t* switch_hashtable_first_iter ( switch_hashtable_t h,
switch_hashtable_iterator_t it 
)

Definition at line 316 of file switch_hashtable.c.

References switch_hashtable_iterator::e, entry::h, switch_hashtable_iterator::h, switch_hashtable_iterator::pos, switch_assert, switch_hashtable_next(), and switch_zmalloc.

Referenced by switch_core_hash_first_iter().

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 }
unsigned int h
struct switch_hashtable * h
#define switch_zmalloc(ptr, len)
#define switch_assert(expr)
switch_hashtable_iterator_t * switch_hashtable_next(switch_hashtable_iterator_t **iP)
int switch_hashtable_insert_destructor ( switch_hashtable_t h,
void *  k,
void *  v,
hashtable_flag_t  flags,
hashtable_destructor_t  destructor 
)

Definition at line 194 of file switch_hashtable.c.

References _switch_hashtable_remove(), entry::destructor, entry::flags, entry::h, hash, HASHTABLE_DUP_CHECK, hashtable_expand(), indexFor(), entry::k, entry::next, and entry::v.

Referenced by switch_core_hash_insert_destructor(), and switch_core_inthash_insert().

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 }
unsigned int h
static __inline__ unsigned int indexFor(unsigned int tablelength, unsigned int hashvalue)
switch_hash_t * hash
Definition: switch_event.c:74
static int hashtable_expand(switch_hashtable_t *h)
hashtable_flag_t flags
static void * _switch_hashtable_remove(switch_hashtable_t *h, void *k, unsigned int hashvalue, unsigned int index)
hashtable_destructor_t destructor
struct entry * next
switch_hashtable_iterator_t* switch_hashtable_next ( switch_hashtable_iterator_t **  iP)

Definition at line 283 of file switch_hashtable.c.

References switch_hashtable_iterator::e, switch_hashtable_iterator::h, entry::next, switch_hashtable_iterator::pos, switch_hashtable::table, and switch_hashtable::tablelength.

Referenced by switch_core_hash_next(), and switch_hashtable_first_iter().

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 }
struct switch_hashtable * h
struct entry * next
void* switch_hashtable_remove ( switch_hashtable_t h,
void *  k 
)

Definition at line 244 of file switch_hashtable.c.

References _switch_hashtable_remove(), hash, and indexFor().

Referenced by switch_core_hash_delete(), and switch_core_inthash_delete().

245 {
246  unsigned int hashvalue = hash(h,k);
247  return _switch_hashtable_remove(h, k, hashvalue, indexFor(h->tablelength,hashvalue));
248 }
static __inline__ unsigned int indexFor(unsigned int tablelength, unsigned int hashvalue)
switch_hash_t * hash
Definition: switch_event.c:74
static void * _switch_hashtable_remove(switch_hashtable_t *h, void *k, unsigned int hashvalue, unsigned int index)
void* switch_hashtable_search ( switch_hashtable_t h,
void *  k 
)

Definition at line 227 of file switch_hashtable.c.

References entry::h, hash, indexFor(), entry::k, entry::next, and entry::v.

Referenced by switch_core_hash_find(), and switch_core_inthash_find().

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 }
unsigned int h
static __inline__ unsigned int indexFor(unsigned int tablelength, unsigned int hashvalue)
switch_hash_t * hash
Definition: switch_event.c:74
int(* eqfn)(void *k1, void *k2)
struct entry * next
void switch_hashtable_this ( switch_hashtable_iterator_t i,
const void **  key,
switch_ssize_t klen,
void **  val 
)

Definition at line 342 of file switch_hashtable.c.

Referenced by switch_core_hash_this().

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 }
void switch_hashtable_this_val ( switch_hashtable_iterator_t i,
void *  val 
)

Definition at line 335 of file switch_hashtable.c.

Referenced by switch_core_hash_this_val().

336 {
337  if (i->e) {
338  i->e->v = val;
339  }
340 }