Asterisk - The Open Source Telephony Project  21.4.1
Data Structures | Macros | Functions
hashtab.h File Reference

Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk. More...

#include "asterisk/lock.h"

Go to the source code of this file.

Data Structures

struct  ast_hashtab
 
struct  ast_hashtab_bucket
 
struct  ast_hashtab_iter
 an iterator for traversing the buckets More...
 

Macros

#define __USE_UNIX98   1 /* to get the MUTEX_RECURSIVE stuff */
 
#define ast_hashtab_create(initial_buckets, compare, resize, newsize, hash, do_locking)   _ast_hashtab_create(initial_buckets, compare, resize, newsize, hash, do_locking, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 Create the hashtable list. More...
 
#define ast_hashtab_dup(tab, obj_dup_func)   _ast_hashtab_dup(tab, obj_dup_func, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 
#define ast_hashtab_insert_immediate(tab, obj)   _ast_hashtab_insert_immediate(tab, obj, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 Insert without checking. More...
 
#define ast_hashtab_insert_immediate_bucket(tab, obj, h)   _ast_hashtab_insert_immediate_bucket(tab, obj, h, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 Insert without checking, hashing or locking. More...
 
#define ast_hashtab_insert_safe(tab, obj)   _ast_hashtab_insert_safe(tab, obj, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 
#define ast_hashtab_start_traversal(tab)   _ast_hashtab_start_traversal(tab, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 
#define ast_hashtab_start_write_traversal(tab)   _ast_hashtab_start_write_traversal(tab, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 

Functions

struct ast_hashtab_ast_hashtab_create (int initial_buckets, int(*compare)(const void *a, const void *b), int(*resize)(struct ast_hashtab *), int(*newsize)(struct ast_hashtab *tab), unsigned int(*hash)(const void *obj), int do_locking, const char *file, int lineno, const char *function)
 
struct ast_hashtab_ast_hashtab_dup (struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj), const char *file, int lineno, const char *func)
 Return a copy of the hash table.
 
int _ast_hashtab_insert_immediate (struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
 
int _ast_hashtab_insert_immediate_bucket (struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func)
 
int _ast_hashtab_insert_safe (struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
 Check and insert new object only if it is not there. More...
 
struct ast_hashtab_iter_ast_hashtab_start_traversal (struct ast_hashtab *tab, const char *file, int lineno, const char *func)
 Gives an iterator to hastable.
 
struct ast_hashtab_iter_ast_hashtab_start_write_traversal (struct ast_hashtab *tab, const char *file, int lineno, const char *func)
 Gives an iterator to hastable.
 
int ast_hashtab_capacity (struct ast_hashtab *tab)
 Returns the size of the bucket array in the hashtab.
 
int ast_hashtab_compare_ints (const void *a, const void *b)
 Compares two integers for equality. More...
 
int ast_hashtab_compare_shorts (const void *a, const void *b)
 Compares two shorts for equality. More...
 
int ast_hashtab_compare_strings (const void *a, const void *b)
 Compares two strings for equality. More...
 
int ast_hashtab_compare_strings_nocase (const void *a, const void *b)
 Compares two strings for equality, ignoring case. More...
 
void ast_hashtab_destroy (struct ast_hashtab *tab, void(*objdestroyfunc)(void *obj))
 This func will free the hash table and all its memory. More...
 
void ast_hashtab_destroylock (struct ast_hashtab *tab)
 Call this before you destroy the table.
 
void ast_hashtab_end_traversal (struct ast_hashtab_iter *it)
 end the traversal, free the iterator, unlock if necc.
 
void ast_hashtab_get_stats (struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets)
 Returns key stats for the table.
 
unsigned int ast_hashtab_hash_int (const int num)
 
unsigned int ast_hashtab_hash_short (const short num)
 
unsigned int ast_hashtab_hash_string (const void *obj)
 Hashes a string to a number. More...
 
unsigned int ast_hashtab_hash_string_nocase (const void *obj)
 Hashes a string to a number ignoring case. More...
 
unsigned int ast_hashtab_hash_string_sax (const void *obj)
 Hashes a string to a number using a modified Shift-And-XOR algorithm. More...
 
void ast_hashtab_initlock (struct ast_hashtab *tab)
 Call this after you create the table to init the lock.
 
void * ast_hashtab_lookup (struct ast_hashtab *tab, const void *obj)
 Lookup this object in the hash table. More...
 
void * ast_hashtab_lookup_bucket (struct ast_hashtab *tab, const void *obj, unsigned int *h)
 Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails. More...
 
void * ast_hashtab_lookup_with_hash (struct ast_hashtab *tab, const void *obj, unsigned int hashval)
 Use this if have the hash val for the object. More...
 
int ast_hashtab_newsize_java (struct ast_hashtab *tab)
 Create a prime number roughly 2x the current table size.
 
int ast_hashtab_newsize_none (struct ast_hashtab *tab)
 always return current size – no resizing
 
int ast_hashtab_newsize_tight (struct ast_hashtab *tab)
 
void * ast_hashtab_next (struct ast_hashtab_iter *it)
 Gets the next object in the list, advances iter one step returns null on end of traversal.
 
void ast_hashtab_rdlock (struct ast_hashtab *tab)
 Request a read-lock on the table – don't change anything!
 
void * ast_hashtab_remove_object_via_lookup (struct ast_hashtab *tab, void *obj)
 Looks up the object, removes the corresponding bucket.
 
void * ast_hashtab_remove_object_via_lookup_nolock (struct ast_hashtab *tab, void *obj)
 Looks up the object, removes the corresponding bucket.
 
void * ast_hashtab_remove_this_object (struct ast_hashtab *tab, void *obj)
 Hash the object and then compare ptrs in bucket list instead of calling the compare routine, will remove the bucket.
 
void * ast_hashtab_remove_this_object_nolock (struct ast_hashtab *tab, void *obj)
 Hash the object and then compare ptrs in bucket list instead of calling the compare routine, will remove the bucket.
 
int ast_hashtab_resize_java (struct ast_hashtab *tab)
 Determines if a table resize should occur using the Java algorithm (if the table load factor is 75% or higher). More...
 
int ast_hashtab_resize_none (struct ast_hashtab *tab)
 Effectively disables resizing by always returning 0, regardless of of load factor. More...
 
int ast_hashtab_resize_tight (struct ast_hashtab *tab)
 Causes a resize whenever the number of elements stored in the table exceeds the number of buckets in the table. More...
 
int ast_hashtab_size (struct ast_hashtab *tab)
 Returns the number of elements stored in the hashtab.
 
void ast_hashtab_unlock (struct ast_hashtab *tab)
 release a read- or write- lock.
 
void ast_hashtab_wrlock (struct ast_hashtab *tab)
 Request a write-lock on the table.
 
int ast_is_prime (int num)
 Determines if the specified number is prime. More...
 

Detailed Description

Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk.

Definition in file hashtab.h.

Macro Definition Documentation

#define ast_hashtab_create (   initial_buckets,
  compare,
  resize,
  newsize,
  hash,
  do_locking 
)    _ast_hashtab_create(initial_buckets, compare, resize, newsize, hash, do_locking, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Create the hashtable list.

Parameters
initial_bucketsstarting number of buckets
comparea func ptr to compare two elements in the hash – cannot be null
resizea func ptr to decide if the table needs to be resized, a NULL ptr here will cause a default to be used
newsizea func ptr that returns a new size of the array. A NULL will cause a default to be used
hasha func ptr to do the hashing
do_lockinguse locks to guarantee safety of iterators/insertion/deletion – real simpleminded right now

Definition at line 254 of file hashtab.h.

Referenced by ast_add_extension2_lockopt(), ast_context_find_or_create(), lua_register_hints(), and lua_register_switches().

#define ast_hashtab_insert_immediate (   tab,
  obj 
)    _ast_hashtab_insert_immediate(tab, obj, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Insert without checking.

Parameters
tab
objNormally, you'd insert "safely" by checking to see if the element is already there; in this case, you must already have checked. If an element is already in the hashtable, that matches this one, most likely this one will be found first.
Note
will force a resize if the resize func returns 1
Return values
1on success
0if there's a problem

Definition at line 290 of file hashtab.h.

Referenced by ast_context_find_or_create().

#define ast_hashtab_insert_immediate_bucket (   tab,
  obj,
 
)    _ast_hashtab_insert_immediate_bucket(tab, obj, h, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Insert without checking, hashing or locking.

Parameters
tab
obj
hhashed index value
Note
Will force a resize if the resize func returns 1
Return values
1on success
0if there's a problem

Definition at line 304 of file hashtab.h.

Function Documentation

int _ast_hashtab_insert_safe ( struct ast_hashtab tab,
const void *  obj,
const char *  file,
int  lineno,
const char *  func 
)

Check and insert new object only if it is not there.

Note
Will force a resize if the resize func returns 1
Return values
1on success
0if there's a problem, or it's already there.

Definition at line 460 of file main/hashtab.c.

References ast_hashtab_lookup_bucket(), and ast_hashtab::do_locking.

461 {
462  /* check to see if the element is already there; insert only if
463  it is not there. */
464  /* will force a resize if the resize func returns 1 */
465  /* returns 1 on success, 0 if there's a problem, or it's already there. */
466  unsigned int bucket = 0;
467 
468  if (tab->do_locking)
469  ast_rwlock_wrlock(&tab->lock);
470 
471  if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
472  int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func);
473 
474  if (tab->do_locking)
475  ast_rwlock_unlock(&tab->lock);
476 
477  return ret2;
478  }
479 
480  if (tab->do_locking)
481  ast_rwlock_unlock(&tab->lock);
482 
483  return 0;
484 }
int do_locking
Definition: hashtab.h:99
void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *bucket)
Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.
Definition: main/hashtab.c:531
int ast_hashtab_compare_ints ( const void *  a,
const void *  b 
)

Compares two integers for equality.

Parameters
aan integer pointer (int *)
ban integer pointer (int *)
Return values
0if the integers pointed to are equal
1if a is greater than b
-1if a is less than b

Definition at line 62 of file main/hashtab.c.

63 {
64  int ai = *((int *) a);
65  int bi = *((int *) b);
66 
67  if (ai < bi)
68  return -1;
69 
70  return !(ai == bi);
71 }
int ast_hashtab_compare_shorts ( const void *  a,
const void *  b 
)

Compares two shorts for equality.

Parameters
aa short pointer (short *)
ba short pointer (short *)
Return values
0if the shorts pointed to are equal
1if a is greater than b
-1if a is less than b

Definition at line 73 of file main/hashtab.c.

74 {
75  short as = *((short *) a);
76  short bs = *((short *) b);
77 
78  if (as < bs)
79  return -1;
80 
81  return !(as == bs);
82 }
int ast_hashtab_compare_strings ( const void *  a,
const void *  b 
)

Compares two strings for equality.

Parameters
aa character string
ba character string
Return values
0if the strings match
negativeif string a is less than string b
positiveif string a is greater than string b

Definition at line 52 of file main/hashtab.c.

53 {
54  return strcmp(a, b);
55 }
int ast_hashtab_compare_strings_nocase ( const void *  a,
const void *  b 
)

Compares two strings for equality, ignoring case.

Parameters
aa character string
ba character string
Return values
0if the strings match
negativeif string a is less than string b
positiveif string a is greater than string b

Definition at line 57 of file main/hashtab.c.

58 {
59  return strcasecmp(a, b);
60 }
void ast_hashtab_destroy ( struct ast_hashtab tab,
void(*)(void *obj)  objdestroyfunc 
)

This func will free the hash table and all its memory.

Note
It doesn't touch the objects stored in it, unless you specify a destroy func; it will call that func for each object in the hashtab, remove all the objects, and then free the hashtab itself. If no destroyfunc is specified then the routine will assume you will free it yourself.
Parameters
tab
objdestroyfunc

Definition at line 363 of file main/hashtab.c.

References ast_hashtab::do_locking, ast_hashtab::hash_tab_size, ast_hashtab_bucket::object, and ast_hashtab::tlist.

Referenced by ast_merge_contexts_and_delete().

364 {
365  /* this func will free the hash table and all its memory. It
366  doesn't touch the objects stored in it */
367  if (tab) {
368 
369  if (tab->do_locking)
370  ast_rwlock_wrlock(&tab->lock);
371 
372  if (tab->array) {
373  /* go thru and destroy the buckets */
374  struct ast_hashtab_bucket *t;
375  int i;
376 
377  while (tab->tlist) {
378  t = tab->tlist;
379  if (t->object && objdestroyfunc) {
380  /* I cast this because I'm not going to MOD it, I'm going to DESTROY
381  * it.
382  */
383  (*objdestroyfunc)((void *) t->object);
384  }
385 
386  tlist_del_item(&(tab->tlist), tab->tlist);
387  ast_free(t);
388  }
389 
390  for (i = 0; i < tab->hash_tab_size; i++) {
391  /* Not totally necessary, but best to destroy old pointers */
392  tab->array[i] = NULL;
393  }
394  ast_free(tab->array);
395  }
396  if (tab->do_locking) {
397  ast_rwlock_unlock(&tab->lock);
398  ast_rwlock_destroy(&tab->lock);
399  }
400  ast_free(tab);
401  }
402 }
int hash_tab_size
Definition: hashtab.h:94
int do_locking
Definition: hashtab.h:99
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
const void * object
Definition: hashtab.h:76
unsigned int ast_hashtab_hash_string ( const void *  obj)

Hashes a string to a number.

Parameters
objthe string to hash
Returns
Integer hash of the specified string
See also
ast_hashtable_hash_string_nocase
ast_hashtab_hash_string_sax
Note
A modulus will be applied to the return value of this function

Definition at line 153 of file main/hashtab.c.

Referenced by stasis_message_type_create().

154 {
155  unsigned char *str = (unsigned char *) obj;
156  unsigned int total;
157 
158  for (total = 0; *str; str++) {
159  unsigned int tmp = total;
160  total <<= 1; /* multiply by 2 */
161  total += tmp; /* multiply by 3 */
162  total <<= 2; /* multiply by 12 */
163  total += tmp; /* multiply by 13 */
164 
165  total += ((unsigned int)(*str));
166  }
167  return total;
168 }
unsigned int ast_hashtab_hash_string_nocase ( const void *  obj)

Hashes a string to a number ignoring case.

Parameters
objthe string to hash
Returns
Integer hash of the specified string
See also
ast_hashtable_hash_string
ast_hashtab_hash_string_sax
Note
A modulus will be applied to the return value of this function

Definition at line 181 of file main/hashtab.c.

182 {
183  const unsigned char *str = obj;
184  unsigned int total;
185 
186  for (total = 0; *str; str++) {
187  unsigned int tmp = total;
188  unsigned int charval = toupper(*str);
189 
190  /* hopefully, the following is faster than multiplication by 7 */
191  /* why do I go to this bother? A good compiler will do this
192  anyway, if I say total *= 13 */
193  /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */
194  total <<= 1; /* multiply by 2 */
195  total += tmp; /* multiply by 3 */
196  total <<= 2; /* multiply by 12 */
197  total += tmp; /* multiply by 13 */
198 
199  total += (charval);
200  }
201 
202  return total;
203 }
unsigned int ast_hashtab_hash_string_sax ( const void *  obj)

Hashes a string to a number using a modified Shift-And-XOR algorithm.

Parameters
objthe string to hash
Returns
Integer has of the specified string
See also
ast_hastable_hash_string
ast_hastable_hash_string_nocase

Definition at line 170 of file main/hashtab.c.

171 {
172  const unsigned char *str = obj;
173  unsigned int total = 0, c = 0;
174 
175  while ((c = *str++))
176  total ^= (total << 5) + (total >> 2) + (total << 10) + c;
177 
178  return total;
179 }
void* ast_hashtab_lookup ( struct ast_hashtab tab,
const void *  obj 
)

Lookup this object in the hash table.

Parameters
tab
obj
Returns
a ptr if found
Return values
NULLif not found

Definition at line 486 of file main/hashtab.c.

References ast_hashtab::do_locking, ast_hashtab::hash, and ast_hashtab::hash_tab_size.

Referenced by ast_add_extension2_lockopt(), ast_context_find(), ast_context_find_or_create(), find_context(), and find_context_locked().

487 {
488  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
489  unsigned int h;
490  void *ret;
491 
492  if (!tab || !obj)
493  return 0;
494 
495  if (tab->do_locking)
496  ast_rwlock_rdlock(&tab->lock);
497 
498  h = (*tab->hash)(obj) % tab->hash_tab_size;
499 
500  ret = ast_hashtab_lookup_internal(tab,obj,h);
501 
502  if (tab->do_locking)
503  ast_rwlock_unlock(&tab->lock);
504 
505  return ret;
506 }
int hash_tab_size
Definition: hashtab.h:94
int do_locking
Definition: hashtab.h:99
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
void* ast_hashtab_lookup_bucket ( struct ast_hashtab tab,
const void *  obj,
unsigned int *  h 
)

Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.

Note
This has the modulus applied, and will not be useful for long term storage if the table is resizable.

Definition at line 531 of file main/hashtab.c.

References ast_hashtab::hash, and ast_hashtab::hash_tab_size.

Referenced by _ast_hashtab_insert_safe().

532 {
533  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
534  unsigned int h;
535  void *ret;
536 
537  if (!tab || !obj)
538  return 0;
539 
540  h = (*tab->hash)(obj) % tab->hash_tab_size;
541 
542  ret = ast_hashtab_lookup_internal(tab,obj,h);
543 
544  *bucket = h;
545 
546  return ret;
547 }
int hash_tab_size
Definition: hashtab.h:94
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
void* ast_hashtab_lookup_with_hash ( struct ast_hashtab tab,
const void *  obj,
unsigned int  hashval 
)

Use this if have the hash val for the object.

Note
This and avoid the recalc of the hash (the modulus (table_size) is not applied)

Definition at line 509 of file main/hashtab.c.

References ast_hashtab::do_locking, and ast_hashtab::hash_tab_size.

510 {
511  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
512  unsigned int h;
513  void *ret;
514 
515  if (!tab || !obj)
516  return 0;
517 
518  if (tab->do_locking)
519  ast_rwlock_rdlock(&tab->lock);
520 
521  h = hashval % tab->hash_tab_size;
522 
523  ret = ast_hashtab_lookup_internal(tab,obj,h);
524 
525  if (tab->do_locking)
526  ast_rwlock_unlock(&tab->lock);
527 
528  return ret;
529 }
int hash_tab_size
Definition: hashtab.h:94
int do_locking
Definition: hashtab.h:99
int ast_hashtab_resize_java ( struct ast_hashtab tab)

Determines if a table resize should occur using the Java algorithm (if the table load factor is 75% or higher).

Parameters
tabthe hash table to operate on
Return values
0if the table load factor is less than or equal to 75%
1if the table load factor is greater than 75%

Definition at line 84 of file main/hashtab.c.

References ast_hashtab::hash_tab_elements, and ast_hashtab::hash_tab_size.

Referenced by ast_add_extension2_lockopt(), ast_context_find_or_create(), lua_register_hints(), and lua_register_switches().

85 {
86  double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
87 
88  return (loadfactor > 0.75);
89 }
int hash_tab_size
Definition: hashtab.h:94
int hash_tab_elements
Definition: hashtab.h:95
int ast_hashtab_resize_none ( struct ast_hashtab tab)

Effectively disables resizing by always returning 0, regardless of of load factor.

Parameters
tabthe hash table to operate on
Return values
0is always returned

Definition at line 96 of file main/hashtab.c.

97 {
98  return 0;
99 }
int ast_hashtab_resize_tight ( struct ast_hashtab tab)

Causes a resize whenever the number of elements stored in the table exceeds the number of buckets in the table.

Parameters
tabthe hash table to operate on
Return values
0if the number of elements in the table is less than or equal to the number of buckets
1if the number of elements in the table exceeds the number of buckets

Definition at line 91 of file main/hashtab.c.

References ast_hashtab::hash_tab_elements, and ast_hashtab::hash_tab_size.

92 {
93  return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
94 }
int hash_tab_size
Definition: hashtab.h:94
int hash_tab_elements
Definition: hashtab.h:95
int ast_is_prime ( int  num)

Determines if the specified number is prime.

Parameters
numthe number to test
Return values
0if the number is not prime
1if the number is prime

Definition at line 101 of file main/hashtab.c.

Referenced by ast_hashtab_newsize_java().

102 {
103  int tnum, limit;
104 
105  if (!(num & 0x1)) /* even number -- not prime */
106  return 0;
107 
108  /* Loop through ODD numbers starting with 3 */
109 
110  tnum = 3;
111  limit = num;
112  while (tnum < limit) {
113  if (!(num % tnum))
114  return 0;
115 
116  /* really, we only need to check sqrt(num) numbers */
117  limit = num / tnum;
118 
119  /* we only check odd numbers */
120  tnum = tnum + 2;
121  }
122 
123  /* if we made it through the loop, the number is a prime */
124  return 1;
125 }