Asterisk - The Open Source Telephony Project GIT-master-3dae2cf
Data Structures | Macros | Functions
hashtab.h File Reference

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

#include "asterisk/lock.h"
Include dependency graph for hashtab.h:
This graph shows which files directly or indirectly include this file:

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. More...
 
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. More...
 
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. More...
 
int ast_hashtab_capacity (struct ast_hashtab *tab)
 Returns the size of the bucket array in the hashtab. More...
 
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. More...
 
void ast_hashtab_end_traversal (struct ast_hashtab_iter *it)
 end the traversal, free the iterator, unlock if necc. More...
 
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. More...
 
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. More...
 
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. More...
 
int ast_hashtab_newsize_none (struct ast_hashtab *tab)
 always return current size – no resizing More...
 
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. More...
 
void ast_hashtab_rdlock (struct ast_hashtab *tab)
 Request a read-lock on the table – don't change anything! More...
 
void * ast_hashtab_remove_object_via_lookup (struct ast_hashtab *tab, void *obj)
 Looks up the object, removes the corresponding bucket. More...
 
void * ast_hashtab_remove_object_via_lookup_nolock (struct ast_hashtab *tab, void *obj)
 Looks up the object, removes the corresponding bucket. More...
 
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. More...
 
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. More...
 
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. More...
 
void ast_hashtab_unlock (struct ast_hashtab *tab)
 release a read- or write- lock. More...
 
void ast_hashtab_wrlock (struct ast_hashtab *tab)
 Request a write-lock on the table. More...
 
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

◆ __USE_UNIX98

#define __USE_UNIX98   1 /* to get the MUTEX_RECURSIVE stuff */

Definition at line 20 of file hashtab.h.

◆ ast_hashtab_create

#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.

◆ ast_hashtab_dup

#define ast_hashtab_dup (   tab,
  obj_dup_func 
)     _ast_hashtab_dup(tab, obj_dup_func, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Definition at line 351 of file hashtab.h.

◆ ast_hashtab_insert_immediate

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

Insert without checking.

Parameters
tab
obj

Normally, 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.

◆ ast_hashtab_insert_immediate_bucket

#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.

◆ ast_hashtab_insert_safe

#define ast_hashtab_insert_safe (   tab,
  obj 
)     _ast_hashtab_insert_safe(tab, obj, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Definition at line 316 of file hashtab.h.

◆ ast_hashtab_start_traversal

#define ast_hashtab_start_traversal (   tab)     _ast_hashtab_start_traversal(tab, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Definition at line 356 of file hashtab.h.

◆ ast_hashtab_start_write_traversal

#define ast_hashtab_start_write_traversal (   tab)     _ast_hashtab_start_write_traversal(tab, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Definition at line 378 of file hashtab.h.

Function Documentation

◆ _ast_hashtab_create()

struct ast_hashtab * _ast_hashtab_create ( int  initial_buckets,
int(*)(const void *a, const void *b compare,
int(*)(struct ast_hashtab *)  resize,
int(*)(struct ast_hashtab *tab)  newsize,
unsigned int(*)(const void *obj)  hash,
int  do_locking,
const char *  file,
int  lineno,
const char *  function 
)

Definition at line 216 of file hashtab.c.

224{
225 struct ast_hashtab *ht;
226
227 ht = __ast_calloc(1, sizeof(*ht), file, lineno, function);
228 if (!ht) {
229 return NULL;
230 }
231
232 while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
233 initial_buckets++;
234
235 ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)),
236 file, lineno, function);
237 if (!ht->array) {
238 ast_free(ht);
239 return NULL;
240 }
241
242 ht->hash_tab_size = initial_buckets;
243 ht->compare = compare;
244 ht->resize = resize;
245 ht->newsize = newsize;
246 ht->hash = hash;
248
249 if (do_locking)
250 ast_rwlock_init(&ht->lock);
251
252 if (!ht->resize)
254
255 if (!ht->newsize)
257
258 return ht;
259}
static int compare(const char *text, const char *template)
#define ast_free(a)
Definition: astmm.h:180
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1603
int ast_hashtab_newsize_java(struct ast_hashtab *tab)
Create a prime number roughly 2x the current table size.
Definition: hashtab.c:127
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:101
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% o...
Definition: hashtab.c:84
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:224
#define NULL
Definition: resample.c:96
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
int hash_tab_size
Definition: hashtab.h:94
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
int do_locking
Definition: hashtab.h:99
ast_rwlock_t lock
Definition: hashtab.h:101
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85

References __ast_calloc(), ast_hashtab::array, ast_free, ast_hashtab_newsize_java(), ast_hashtab_resize_java(), ast_is_prime(), ast_rwlock_init, compare(), ast_hashtab::compare, ast_hashtab::do_locking, make_ari_stubs::file, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab::newsize, NULL, and ast_hashtab::resize.

◆ _ast_hashtab_dup()

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

Return a copy of the hash table.

Definition at line 261 of file hashtab.c.

262{
263 struct ast_hashtab *ht;
264 unsigned int i;
265
266 ht = __ast_calloc(1, sizeof(*ht), file, lineno, func);
267 if (!ht) {
268 return NULL;
269 }
270
271 ht->array = __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)),
272 file, lineno, func);
273 if (!ht->array) {
274 ast_free(ht);
275 return NULL;
276 }
277
278 ht->hash_tab_size = tab->hash_tab_size;
279 ht->compare = tab->compare;
280 ht->resize = tab->resize;
281 ht->newsize = tab->newsize;
282 ht->hash = tab->hash;
283 ht->do_locking = tab->do_locking;
284
285 if (ht->do_locking)
286 ast_rwlock_init(&ht->lock);
287
288 /* now, dup the objects in the buckets and get them into the table */
289 /* the fast way is to use the existing array index, and not have to hash
290 the objects again */
291 for (i = 0; i < ht->hash_tab_size; i++) {
292 struct ast_hashtab_bucket *b = tab->array[i];
293 while (b) {
294 void *newobj = (*obj_dup_func)(b->object);
295 if (newobj) {
296 _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func);
297 }
298 b = b->next;
299 }
300 }
301
302 return ht;
303}
int _ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func)
Definition: hashtab.c:425
struct test_val * next
static struct test_val b

References __ast_calloc(), _ast_hashtab_insert_immediate_bucket(), ast_hashtab::array, ast_free, ast_rwlock_init, b, ast_hashtab::compare, ast_hashtab::do_locking, make_ari_stubs::file, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab::newsize, test_val::next, NULL, and ast_hashtab::resize.

◆ _ast_hashtab_insert_immediate()

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

Definition at line 404 of file hashtab.c.

405{
406 unsigned int h;
407 int res=0;
408
409 if (!tab || !obj)
410 return res;
411
412 if (tab->do_locking)
413 ast_rwlock_wrlock(&tab->lock);
414
415 h = (*tab->hash)(obj) % tab->hash_tab_size;
416
417 res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func);
418
419 if (tab->do_locking)
420 ast_rwlock_unlock(&tab->lock);
421
422 return res;
423}
#define ast_rwlock_wrlock(a)
Definition: lock.h:236
#define ast_rwlock_unlock(a)
Definition: lock.h:234

References _ast_hashtab_insert_immediate_bucket(), ast_rwlock_unlock, ast_rwlock_wrlock, ast_hashtab::do_locking, make_ari_stubs::file, ast_hashtab::hash, ast_hashtab::hash_tab_size, and ast_hashtab::lock.

◆ _ast_hashtab_insert_immediate_bucket()

int _ast_hashtab_insert_immediate_bucket ( struct ast_hashtab tab,
const void *  obj,
unsigned int  h,
const char *  file,
int  lineno,
const char *  func 
)

Definition at line 425 of file hashtab.c.

426{
427 int c;
428 struct ast_hashtab_bucket *b;
429
430 if (!tab || !obj)
431 return 0;
432
433 for (c = 0, b = tab->array[h]; b; b= b->next)
434 c++;
435
436 if (c + 1 > tab->largest_bucket_size)
437 tab->largest_bucket_size = c + 1;
438
439 b = __ast_calloc(1, sizeof(*b), file, lineno, func);
440 if (!b) {
441 return 0;
442 }
443
444 b->object = obj;
445 b->next = tab->array[h];
446 tab->array[h] = b;
447
448 if (b->next)
449 b->next->prev = b;
450
451 tlist_add_head(&(tab->tlist), b);
452 tab->hash_tab_elements++;
453
454 if ((*tab->resize)(tab))
456
457 return 1;
458}
static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:320
#define ast_hashtab_resize(tab)
Definition: hashtab.c:45
int hash_tab_elements
Definition: hashtab.h:95
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
int largest_bucket_size
Definition: hashtab.h:96
static struct test_val c

References __ast_calloc(), ast_hashtab::array, ast_hashtab_resize, b, c, make_ari_stubs::file, ast_hashtab::hash_tab_elements, ast_hashtab::largest_bucket_size, test_val::next, ast_hashtab::resize, ast_hashtab::tlist, and tlist_add_head().

Referenced by _ast_hashtab_dup(), _ast_hashtab_insert_immediate(), and _ast_hashtab_insert_safe().

◆ _ast_hashtab_insert_safe()

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 hashtab.c.

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}
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: hashtab.c:531

References _ast_hashtab_insert_immediate_bucket(), ast_hashtab_lookup_bucket(), ast_rwlock_unlock, ast_rwlock_wrlock, ast_hashtab::do_locking, make_ari_stubs::file, and ast_hashtab::lock.

◆ _ast_hashtab_start_traversal()

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.

Definition at line 637 of file hashtab.c.

638{
639 /* returns an iterator */
640 struct ast_hashtab_iter *it;
641
642 it = __ast_calloc(1, sizeof(*it), file, lineno, func);
643 if (!it) {
644 return NULL;
645 }
646
647 it->next = tab->tlist;
648 it->tab = tab;
649 if (tab->do_locking)
651
652 return it;
653}
#define ast_rwlock_rdlock(a)
Definition: lock.h:235
an iterator for traversing the buckets
Definition: hashtab.h:106
struct ast_hashtab_bucket * next
Definition: hashtab.h:108
struct ast_hashtab * tab
Definition: hashtab.h:107

References __ast_calloc(), ast_rwlock_rdlock, ast_hashtab::do_locking, make_ari_stubs::file, ast_hashtab::lock, ast_hashtab_iter::next, NULL, ast_hashtab_iter::tab, and ast_hashtab::tlist.

◆ _ast_hashtab_start_write_traversal()

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.

Definition at line 656 of file hashtab.c.

657{
658 /* returns an iterator */
659 struct ast_hashtab_iter *it;
660
661 it = __ast_calloc(1, sizeof(*it), file, lineno, func);
662 if (!it) {
663 return NULL;
664 }
665
666 it->next = tab->tlist;
667 it->tab = tab;
668 if (tab->do_locking)
670
671 return it;
672}

References __ast_calloc(), ast_rwlock_wrlock, ast_hashtab::do_locking, make_ari_stubs::file, ast_hashtab::lock, ast_hashtab_iter::next, NULL, ast_hashtab_iter::tab, and ast_hashtab::tlist.

◆ ast_hashtab_capacity()

int ast_hashtab_capacity ( struct ast_hashtab tab)

Returns the size of the bucket array in the hashtab.

Definition at line 583 of file hashtab.c.

584{
585 return tab->hash_tab_size;
586}

References ast_hashtab::hash_tab_size.

◆ ast_hashtab_compare_ints()

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 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}
static struct test_val a

References a, and b.

◆ ast_hashtab_compare_shorts()

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 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}
char * bs
Definition: eagi_proxy.c:73

References a, b, and bs.

◆ ast_hashtab_compare_strings()

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 hashtab.c.

53{
54 return strcmp(a, b);
55}

References a, and b.

◆ ast_hashtab_compare_strings_nocase()

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 hashtab.c.

58{
59 return strcasecmp(a, b);
60}

References a, and b.

Referenced by AST_TEST_DEFINE().

◆ ast_hashtab_destroy()

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 hashtab.c.

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);
399 }
400 ast_free(tab);
401 }
402}
static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:305
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:233
const void * object
Definition: hashtab.h:76

References ast_hashtab::array, ast_free, ast_rwlock_destroy, ast_rwlock_unlock, ast_rwlock_wrlock, ast_hashtab::do_locking, ast_hashtab::hash_tab_size, ast_hashtab::lock, NULL, ast_hashtab_bucket::object, ast_hashtab::tlist, and tlist_del_item().

Referenced by __ast_internal_context_destroy(), ast_merge_contexts_and_delete(), AST_TEST_DEFINE(), destroy_exten(), pbx_load_module(), and pbx_shutdown().

◆ ast_hashtab_destroylock()

void ast_hashtab_destroylock ( struct ast_hashtab tab)

Call this before you destroy the table.

Definition at line 353 of file hashtab.c.

354{
356}

References ast_rwlock_destroy, and ast_hashtab::lock.

◆ ast_hashtab_end_traversal()

void ast_hashtab_end_traversal ( struct ast_hashtab_iter it)

end the traversal, free the iterator, unlock if necc.

Definition at line 674 of file hashtab.c.

675{
676 if (!it)
677 return;
678 if (it->tab->do_locking)
680 ast_free(it);
681}

References ast_free, ast_rwlock_unlock, ast_hashtab::do_locking, ast_hashtab::lock, and ast_hashtab_iter::tab.

Referenced by __ast_context_destroy(), ast_merge_contexts_and_delete(), context_merge(), context_table_create_autohints(), create_match_char_tree(), and hash_test_count().

◆ ast_hashtab_get_stats()

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.

Definition at line 563 of file hashtab.c.

564{
565 /* returns key stats for the table */
566 if (tab->do_locking)
567 ast_rwlock_rdlock(&tab->lock);
568 *biggest_bucket_size = tab->largest_bucket_size;
569 *resize_count = tab->resize_count;
570 *num_objects = tab->hash_tab_elements;
571 *num_buckets = tab->hash_tab_size;
572 if (tab->do_locking)
573 ast_rwlock_unlock(&tab->lock);
574}
int resize_count
Definition: hashtab.h:97

References ast_rwlock_rdlock, ast_rwlock_unlock, ast_hashtab::do_locking, ast_hashtab::hash_tab_elements, ast_hashtab::hash_tab_size, ast_hashtab::largest_bucket_size, ast_hashtab::lock, and ast_hashtab::resize_count.

Referenced by create_match_char_tree().

◆ ast_hashtab_hash_int()

unsigned int ast_hashtab_hash_int ( const int  num)

Definition at line 205 of file hashtab.c.

206{
207 return x;
208}

Referenced by hashtab_hash_priority().

◆ ast_hashtab_hash_short()

unsigned int ast_hashtab_hash_short ( const short  num)

Definition at line 210 of file hashtab.c.

211{
212 /* hmmmm.... modulus is best < 65535 !! */
213 return x;
214}

◆ ast_hashtab_hash_string()

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 hashtab.c.

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}
const char * str
Definition: app_jack.c:147
static int tmp()
Definition: bt_open.c:389
static int total
Definition: res_adsi.c:970

References str, tmp(), and total.

Referenced by ast_hashtab_hash_contexts(), cache_entry_compute_hash(), hashtab_hash_extens(), hashtab_hash_labels(), and stasis_message_type_create().

◆ ast_hashtab_hash_string_nocase()

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 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}

References str, tmp(), and total.

Referenced by AST_TEST_DEFINE(), and hash_string().

◆ ast_hashtab_hash_string_sax()

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 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}

References c, str, and total.

◆ ast_hashtab_initlock()

void ast_hashtab_initlock ( struct ast_hashtab tab)

Call this after you create the table to init the lock.

Definition at line 348 of file hashtab.c.

349{
350 ast_rwlock_init(&tab->lock);
351}

References ast_rwlock_init, and ast_hashtab::lock.

◆ ast_hashtab_lookup()

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 hashtab.c.

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}
static void * ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
Definition: hashtab.c:549

References ast_hashtab_lookup_internal(), ast_rwlock_rdlock, ast_rwlock_unlock, ast_hashtab::do_locking, ast_hashtab::hash, ast_hashtab::hash_tab_size, and ast_hashtab::lock.

Referenced by ast_add_extension2_lockopt(), ast_context_find(), ast_context_find_or_create(), ast_context_remove_extension_callerid2(), context_merge(), find_context(), find_context_locked(), hash_test_lookup(), and pbx_find_extension().

◆ ast_hashtab_lookup_bucket()

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 hashtab.c.

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}

References ast_hashtab_lookup_internal(), ast_hashtab::hash, and ast_hashtab::hash_tab_size.

Referenced by _ast_hashtab_insert_safe().

◆ ast_hashtab_lookup_with_hash()

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 hashtab.c.

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}

References ast_hashtab_lookup_internal(), ast_rwlock_rdlock, ast_rwlock_unlock, ast_hashtab::do_locking, ast_hashtab::hash_tab_size, and ast_hashtab::lock.

◆ ast_hashtab_newsize_java()

int ast_hashtab_newsize_java ( struct ast_hashtab tab)

Create a prime number roughly 2x the current table size.

Definition at line 127 of file hashtab.c.

128{
129 int i = (tab->hash_tab_size << 1); /* multiply by two */
130
131 while (!ast_is_prime(i))
132 i++;
133
134 return i;
135}

References ast_is_prime(), and ast_hashtab::hash_tab_size.

Referenced by _ast_hashtab_create(), ast_add_extension2_lockopt(), ast_context_find_or_create(), AST_TEST_DEFINE(), lua_register_hints(), lua_register_switches(), and pbx_load_module().

◆ ast_hashtab_newsize_none()

int ast_hashtab_newsize_none ( struct ast_hashtab tab)

always return current size – no resizing

Definition at line 148 of file hashtab.c.

149{
150 return tab->hash_tab_size;
151}

References ast_hashtab::hash_tab_size.

◆ ast_hashtab_newsize_tight()

int ast_hashtab_newsize_tight ( struct ast_hashtab tab)

Definition at line 137 of file hashtab.c.

138{
139 int x = (tab->hash_tab_size << 1);
140 int i = (tab->hash_tab_size + x);
141
142 while (!ast_is_prime(i))
143 i++;
144
145 return i;
146}

References ast_is_prime(), and ast_hashtab::hash_tab_size.

◆ ast_hashtab_next()

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.

Definition at line 683 of file hashtab.c.

684{
685 /* returns the next object in the list, advances iter one step */
687
688 if (it && it->next) { /* there's a next in the bucket list */
689 retval = it->next;
690 it->next = retval->tnext;
691 return (void *) retval->object;
692 }
693
694 return NULL;
695}
static ENTRY retval
Definition: hsearch.c:50

References ast_hashtab_iter::next, NULL, and retval.

Referenced by __ast_context_destroy(), ast_merge_contexts_and_delete(), context_merge(), context_table_create_autohints(), create_match_char_tree(), and hash_test_count().

◆ ast_hashtab_rdlock()

void ast_hashtab_rdlock ( struct ast_hashtab tab)

Request a read-lock on the table – don't change anything!

Definition at line 343 of file hashtab.c.

344{
345 ast_rwlock_rdlock(&tab->lock);
346}

References ast_rwlock_rdlock, and ast_hashtab::lock.

◆ ast_hashtab_remove_object_via_lookup()

void * ast_hashtab_remove_object_via_lookup ( struct ast_hashtab tab,
void *  obj 
)

Looks up the object, removes the corresponding bucket.

Definition at line 746 of file hashtab.c.

747{
748 /* looks up the object; removes the corresponding bucket */
749 const void *obj2;
750
751 if (!tab || !obj)
752 return 0;
753
754 if (tab->do_locking)
755 ast_rwlock_wrlock(&tab->lock);
756
758
759 if (tab->do_locking)
760 ast_rwlock_unlock(&tab->lock);
761
762 return (void *)obj2;
763}
void * ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
Looks up the object, removes the corresponding bucket.
Definition: hashtab.c:765

References ast_hashtab_remove_object_via_lookup_nolock(), ast_rwlock_unlock, ast_rwlock_wrlock, ast_hashtab::do_locking, and ast_hashtab::lock.

Referenced by add_priority(), and hash_test_shrink().

◆ ast_hashtab_remove_object_via_lookup_nolock()

void * ast_hashtab_remove_object_via_lookup_nolock ( struct ast_hashtab tab,
void *  obj 
)

Looks up the object, removes the corresponding bucket.

Definition at line 765 of file hashtab.c.

766{
767 /* looks up the object; removes the corresponding bucket */
768 unsigned int h;
769 struct ast_hashtab_bucket *b;
770
771 if (!tab || !obj)
772 return 0;
773
774 h = (*tab->hash)(obj) % tab->hash_tab_size;
775 for (b = tab->array[h]; b; b = b->next) {
776
777 if (!(*tab->compare)(obj, b->object)) {
778 const void *obj2;
779
781
782 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
783 }
784 }
785
786 return 0;
787}
static void * ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
Definition: hashtab.c:697

References ast_hashtab::array, ast_hashtab_remove_object_internal(), b, ast_hashtab::compare, ast_hashtab::hash, ast_hashtab::hash_tab_size, and test_val::next.

Referenced by ast_hashtab_remove_object_via_lookup().

◆ ast_hashtab_remove_this_object()

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.

Definition at line 789 of file hashtab.c.

790{
791 /* looks up the object by hash and then comparing pts in bucket list instead of
792 calling the compare routine; removes the bucket -- a slightly cheaper operation */
793 /* looks up the object; removes the corresponding bucket */
794 const void *obj2;
795
796 if (!tab || !obj)
797 return 0;
798
799 if (tab->do_locking)
800 ast_rwlock_wrlock(&tab->lock);
801
803
804 if (tab->do_locking)
805 ast_rwlock_unlock(&tab->lock);
806
807 return (void *)obj2;
808}
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,...
Definition: hashtab.c:810

References ast_hashtab_remove_this_object_nolock(), ast_rwlock_unlock, ast_rwlock_wrlock, ast_hashtab::do_locking, and ast_hashtab::lock.

Referenced by __ast_context_destroy(), ast_add_extension2_lockopt(), and ast_context_remove_extension_callerid2().

◆ ast_hashtab_remove_this_object_nolock()

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.

Definition at line 810 of file hashtab.c.

811{
812 /* looks up the object by hash and then comparing pts in bucket list instead of
813 calling the compare routine; removes the bucket -- a slightly cheaper operation */
814 /* looks up the object; removes the corresponding bucket */
815 unsigned int h;
816 struct ast_hashtab_bucket *b;
817
818 if (!tab || !obj)
819 return 0;
820
821 h = (*tab->hash)(obj) % tab->hash_tab_size;
822 for (b = tab->array[h]; b; b = b->next) {
823
824 if (obj == b->object) {
825 const void *obj2;
827
828 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
829 }
830 }
831
832 return 0;
833}

References ast_hashtab::array, ast_hashtab_remove_object_internal(), b, ast_hashtab::hash, ast_hashtab::hash_tab_size, and test_val::next.

Referenced by ast_hashtab_remove_this_object().

◆ ast_hashtab_resize_java()

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 hashtab.c.

85{
86 double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
87
88 return (loadfactor > 0.75);
89}

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

Referenced by _ast_hashtab_create(), ast_add_extension2_lockopt(), ast_context_find_or_create(), AST_TEST_DEFINE(), lua_register_hints(), lua_register_switches(), and pbx_load_module().

◆ ast_hashtab_resize_none()

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 hashtab.c.

97{
98 return 0;
99}

◆ ast_hashtab_resize_tight()

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 hashtab.c.

92{
93 return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
94}

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

◆ ast_hashtab_size()

int ast_hashtab_size ( struct ast_hashtab tab)

Returns the number of elements stored in the hashtab.

Definition at line 577 of file hashtab.c.

578{
579 return tab->hash_tab_elements;
580}

References ast_hashtab::hash_tab_elements.

Referenced by ast_context_remove_extension_callerid2(), and AST_TEST_DEFINE().

◆ ast_hashtab_unlock()

void ast_hashtab_unlock ( struct ast_hashtab tab)

release a read- or write- lock.

Definition at line 358 of file hashtab.c.

359{
360 ast_rwlock_unlock(&tab->lock);
361}

References ast_rwlock_unlock, and ast_hashtab::lock.

◆ ast_hashtab_wrlock()

void ast_hashtab_wrlock ( struct ast_hashtab tab)

Request a write-lock on the table.

Definition at line 338 of file hashtab.c.

339{
340 ast_rwlock_wrlock(&tab->lock);
341}

References ast_rwlock_wrlock, and ast_hashtab::lock.

◆ ast_is_prime()

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 hashtab.c.

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}

Referenced by _ast_hashtab_create(), ast_hashtab_newsize_java(), ast_hashtab_newsize_tight(), and sorcery_config_internal_load().