Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk. More...
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... | |
Defines | |
#define | __USE_UNIX98 1 |
Functions | |
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. | |
int | ast_hashtab_compare_shorts (const void *a, const void *b) |
Compares two shorts for equality. | |
int | ast_hashtab_compare_strings (const void *a, const void *b) |
Compares two strings for equality. | |
int | ast_hashtab_compare_strings_nocase (const void *a, const void *b) |
Compares two strings for equality, ignoring case. | |
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) |
Create the hashtable list. | |
void | ast_hashtab_destroy (struct ast_hashtab *tab, void(*objdestroyfunc)(void *obj)) |
This func will free the hash table and all its memory. | |
void | ast_hashtab_destroylock (struct ast_hashtab *tab) |
Call this before you destroy the table. | |
struct ast_hashtab * | ast_hashtab_dup (struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj)) |
Return a copy of the hash 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. | |
unsigned int | ast_hashtab_hash_string_nocase (const void *obj) |
Hashes a string to a number ignoring case. | |
unsigned int | ast_hashtab_hash_string_sax (const void *obj) |
Hashes a string to a number using a modified Shift-And-XOR algorithm. | |
void | ast_hashtab_initlock (struct ast_hashtab *tab) |
Call this after you create the table to init the lock. | |
int | ast_hashtab_insert_immediate (struct ast_hashtab *tab, const void *obj) |
Insert without checking. | |
int | ast_hashtab_insert_immediate_bucket (struct ast_hashtab *tab, const void *obj, unsigned int h) |
Insert without checking, hashing or locking. | |
int | ast_hashtab_insert_safe (struct ast_hashtab *tab, const void *obj) |
Check and insert new object only if it is not there. | |
void * | ast_hashtab_lookup (struct ast_hashtab *tab, const void *obj) |
Lookup this object in the hash table. | |
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. | |
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. | |
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). | |
int | ast_hashtab_resize_none (struct ast_hashtab *tab) |
Effectively disables resizing by always returning 0, regardless of of load factor. | |
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. | |
int | ast_hashtab_size (struct ast_hashtab *tab) |
Returns the number of elements stored in the hashtab. | |
struct ast_hashtab_iter * | ast_hashtab_start_traversal (struct ast_hashtab *tab) |
Gives an iterator to hastable. | |
struct ast_hashtab_iter * | ast_hashtab_start_write_traversal (struct ast_hashtab *tab) |
Gives an iterator to hastable. | |
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. |
Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk.
Definition in file hashtab.h.
int ast_hashtab_capacity | ( | struct ast_hashtab * | tab | ) |
Returns the size of the bucket array in the hashtab.
Definition at line 627 of file hashtab.c.
References ast_hashtab::hash_tab_size.
{ return tab->hash_tab_size; }
int ast_hashtab_compare_ints | ( | const void * | a, |
const void * | b | ||
) |
Compares two integers for equality.
a | an integer pointer (int *) |
b | an integer pointer (int *) |
0 | if the integers pointed to are equal |
1 | if a is greater than b |
-1 | if a is less than b |
Definition at line 62 of file hashtab.c.
{ int ai = *((int *) a); int bi = *((int *) b); if (ai < bi) return -1; return !(ai == bi); }
int ast_hashtab_compare_shorts | ( | const void * | a, |
const void * | b | ||
) |
Compares two shorts for equality.
a | a short pointer (short *) |
b | a short pointer (short *) |
0 | if the shorts pointed to are equal |
1 | if a is greater than b |
-1 | if a is less than b |
Definition at line 73 of file hashtab.c.
{ short as = *((short *) a); short bs = *((short *) b); if (as < bs) return -1; return !(as == bs); }
int ast_hashtab_compare_strings | ( | const void * | a, |
const void * | b | ||
) |
int ast_hashtab_compare_strings_nocase | ( | const void * | a, |
const void * | b | ||
) |
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 | ||
) | [read] |
Create the hashtable list.
initial_buckets | starting number of buckets |
compare | a func ptr to compare two elements in the hash -- cannot be null |
resize | a func ptr to decide if the table needs to be resized, a NULL ptr here will cause a default to be used |
newsize | a func ptr that returns a new size of the array. A NULL will cause a default to be used |
hash | a func ptr to do the hashing |
do_locking | use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now |
Definition at line 222 of file hashtab.c.
References __ast_calloc(), ast_hashtab::array, ast_calloc, ast_hashtab_newsize_java(), ast_hashtab_resize_java(), ast_is_prime(), ast_rwlock_init(), compare(), ast_hashtab::compare, ast_hashtab::do_locking, free, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab::newsize, and ast_hashtab::resize.
Referenced by ast_add_extension2_lockopt(), ast_context_find_or_create(), lua_register_switches(), pbx_load_module(), and sched_context_create().
{ struct ast_hashtab *ht; #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) if (!(ht = __ast_calloc(1, sizeof(*ht), file, lineno, function))) #else if (!(ht = ast_calloc(1, sizeof(*ht)))) #endif return NULL; while (!ast_is_prime(initial_buckets)) /* make sure this is prime */ initial_buckets++; #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) if (!(ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)), file, lineno, function))) { #else if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) { #endif free(ht); return NULL; } ht->hash_tab_size = initial_buckets; ht->compare = compare; ht->resize = resize; ht->newsize = newsize; ht->hash = hash; ht->do_locking = do_locking; if (do_locking) ast_rwlock_init(&ht->lock); if (!ht->resize) ht->resize = ast_hashtab_resize_java; if (!ht->newsize) ht->newsize = ast_hashtab_newsize_java; return ht; }
void ast_hashtab_destroy | ( | struct ast_hashtab * | tab, |
void(*)(void *obj) | objdestroyfunc | ||
) |
This func will free the hash table and all its memory.
tab | |
objdestroyfunc |
Definition at line 384 of file hashtab.c.
References ast_hashtab::array, ast_rwlock_destroy(), ast_rwlock_unlock(), ast_rwlock_wrlock(), ast_hashtab::do_locking, free, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab_bucket::object, ast_hashtab::tlist, and tlist_del_item().
Referenced by __ast_internal_context_destroy(), ast_merge_contexts_and_delete(), destroy_exten(), and sched_context_destroy().
{ /* this func will free the hash table and all its memory. It doesn't touch the objects stored in it */ if (tab) { if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); if (tab->array) { /* go thru and destroy the buckets */ struct ast_hashtab_bucket *t; int i; while (tab->tlist) { t = tab->tlist; if (t->object && objdestroyfunc) { /* I cast this because I'm not going to MOD it, I'm going to DESTROY * it. */ (*objdestroyfunc)((void *) t->object); } tlist_del_item(&(tab->tlist), tab->tlist); free(t); } for (i = 0; i < tab->hash_tab_size; i++) { /* Not totally necessary, but best to destroy old pointers */ tab->array[i] = NULL; } free(tab->array); } if (tab->do_locking) { ast_rwlock_unlock(&tab->lock); ast_rwlock_destroy(&tab->lock); } free(tab); } }
void ast_hashtab_destroylock | ( | struct ast_hashtab * | tab | ) |
Call this before you destroy the table.
Definition at line 374 of file hashtab.c.
References ast_rwlock_destroy(), and ast_hashtab::lock.
{ ast_rwlock_destroy(&tab->lock); }
struct ast_hashtab* ast_hashtab_dup | ( | struct ast_hashtab * | tab, |
void *(*)(const void *obj) | obj_dup_func | ||
) | [read] |
Return a copy of the hash table.
Definition at line 276 of file hashtab.c.
References __ast_calloc(), ast_hashtab::array, ast_calloc, ast_hashtab_insert_immediate_bucket(), ast_rwlock_init(), ast_hashtab::compare, ast_hashtab::do_locking, free, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab::newsize, ast_hashtab_bucket::next, ast_hashtab_bucket::object, and ast_hashtab::resize.
{ struct ast_hashtab *ht; unsigned int i; if (!(ht = ast_calloc(1, sizeof(*ht)))) return NULL; if (!(ht->array = #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)), file, lineno, func) #else ast_calloc(tab->hash_tab_size, sizeof(*(ht->array))) #endif )) { free(ht); return NULL; } ht->hash_tab_size = tab->hash_tab_size; ht->compare = tab->compare; ht->resize = tab->resize; ht->newsize = tab->newsize; ht->hash = tab->hash; ht->do_locking = tab->do_locking; if (ht->do_locking) ast_rwlock_init(&ht->lock); /* now, dup the objects in the buckets and get them into the table */ /* the fast way is to use the existing array index, and not have to hash the objects again */ for (i = 0; i < ht->hash_tab_size; i++) { struct ast_hashtab_bucket *b = tab->array[i]; while (b) { void *newobj = (*obj_dup_func)(b->object); if (newobj) #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func); #else ast_hashtab_insert_immediate_bucket(ht, newobj, i); #endif b = b->next; } } return ht; }
void ast_hashtab_end_traversal | ( | struct ast_hashtab_iter * | it | ) |
end the traversal, free the iterator, unlock if necc.
Definition at line 742 of file hashtab.c.
References ast_rwlock_unlock(), ast_hashtab::do_locking, free, ast_hashtab::lock, and ast_hashtab_iter::tab.
Referenced by __ast_context_destroy(), ast_merge_contexts_and_delete(), context_merge(), and create_match_char_tree().
{ if (it->tab->do_locking) ast_rwlock_unlock(&it->tab->lock); free(it); }
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 607 of file hashtab.c.
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().
{ /* returns key stats for the table */ if (tab->do_locking) ast_rwlock_rdlock(&tab->lock); *biggest_bucket_size = tab->largest_bucket_size; *resize_count = tab->resize_count; *num_objects = tab->hash_tab_elements; *num_buckets = tab->hash_tab_size; if (tab->do_locking) ast_rwlock_unlock(&tab->lock); }
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.
obj | the string to hash |
Definition at line 153 of file hashtab.c.
Referenced by ast_hashtab_hash_contexts(), hashtab_hash_extens(), and hashtab_hash_labels().
{ unsigned char *str = (unsigned char *) obj; unsigned int total; for (total = 0; *str; str++) { unsigned int tmp = total; total <<= 1; /* multiply by 2 */ total += tmp; /* multiply by 3 */ total <<= 2; /* multiply by 12 */ total += tmp; /* multiply by 13 */ total += ((unsigned int)(*str)); } return total; }
unsigned int ast_hashtab_hash_string_nocase | ( | const void * | obj | ) |
Hashes a string to a number ignoring case.
obj | the string to hash |
Definition at line 181 of file hashtab.c.
{ const unsigned char *str = obj; unsigned int total; for (total = 0; *str; str++) { unsigned int tmp = total; unsigned int charval = toupper(*str); /* hopefully, the following is faster than multiplication by 7 */ /* why do I go to this bother? A good compiler will do this anyway, if I say total *= 13 */ /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */ total <<= 1; /* multiply by 2 */ total += tmp; /* multiply by 3 */ total <<= 2; /* multiply by 12 */ total += tmp; /* multiply by 13 */ total += (charval); } return total; }
unsigned int ast_hashtab_hash_string_sax | ( | const void * | obj | ) |
void ast_hashtab_initlock | ( | struct ast_hashtab * | tab | ) |
Call this after you create the table to init the lock.
Definition at line 369 of file hashtab.c.
References ast_rwlock_init(), and ast_hashtab::lock.
{ ast_rwlock_init(&tab->lock); }
int ast_hashtab_insert_immediate | ( | struct ast_hashtab * | tab, |
const void * | obj | ||
) |
Insert without checking.
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. |
1 | on success |
0 | if there's a problem |
Definition at line 428 of file hashtab.c.
References ast_hashtab_insert_immediate_bucket(), ast_rwlock_unlock(), ast_rwlock_wrlock(), ast_hashtab::do_locking, ast_hashtab::hash, ast_hashtab::hash_tab_size, and ast_hashtab::lock.
Referenced by ast_context_find_or_create(), and ast_context_remove_extension_callerid2().
{ unsigned int h; int res=0; if (!tab || !obj) return res; if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); h = (*tab->hash)(obj) % tab->hash_tab_size; #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func); #else res = ast_hashtab_insert_immediate_bucket(tab, obj, h); #endif if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return res; }
int ast_hashtab_insert_immediate_bucket | ( | struct ast_hashtab * | tab, |
const void * | obj, | ||
unsigned int | h | ||
) |
Insert without checking, hashing or locking.
tab | |
obj | |
h | hashed index value |
1 | on success |
0 | if there's a problem |
Definition at line 457 of file hashtab.c.
References __ast_calloc(), ast_hashtab::array, ast_calloc, ast_hashtab_resize(), ast_hashtab::hash_tab_elements, ast_hashtab::largest_bucket_size, ast_hashtab_bucket::next, ast_hashtab_bucket::object, ast_hashtab_bucket::prev, ast_hashtab::resize, ast_hashtab::tlist, and tlist_add_head().
Referenced by ast_hashtab_dup(), ast_hashtab_insert_immediate(), and ast_hashtab_insert_safe().
{ int c; struct ast_hashtab_bucket *b; if (!tab || !obj) return 0; for (c = 0, b = tab->array[h]; b; b= b->next) c++; if (c + 1 > tab->largest_bucket_size) tab->largest_bucket_size = c + 1; if (!(b = #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) __ast_calloc(1, sizeof(*b), file, lineno, func) #else ast_calloc(1, sizeof(*b)) #endif )) return 0; b->object = obj; b->next = tab->array[h]; tab->array[h] = b; if (b->next) b->next->prev = b; tlist_add_head(&(tab->tlist), b); tab->hash_tab_elements++; if ((*tab->resize)(tab)) ast_hashtab_resize(tab); return 1; }
int ast_hashtab_insert_safe | ( | struct ast_hashtab * | tab, |
const void * | obj | ||
) |
Check and insert new object only if it is not there.
1 | on success |
0 | if there's a problem, or it's already there. |
Definition at line 499 of file hashtab.c.
References ast_hashtab_insert_immediate_bucket(), ast_hashtab_lookup_bucket(), ast_rwlock_unlock(), ast_rwlock_wrlock(), ast_hashtab::do_locking, and ast_hashtab::lock.
Referenced by add_pri_lockopt(), ast_add_extension2_lockopt(), ast_context_find_or_create(), and schedule().
{ /* check to see if the element is already there; insert only if it is not there. */ /* will force a resize if the resize func returns 1 */ /* returns 1 on success, 0 if there's a problem, or it's already there. */ unsigned int bucket = 0; if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) { #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func); #else int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket); #endif if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return ret2; } if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return 0; }
void* ast_hashtab_lookup | ( | struct ast_hashtab * | tab, |
const void * | obj | ||
) |
Lookup this object in the hash table.
tab | |
obj |
a | ptr if found |
NULL | if not found |
Definition at line 530 of file hashtab.c.
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_lockmacro(), ast_context_remove_extension_callerid2(), ast_context_unlockmacro(), ast_sched_del(), ast_sched_find_data(), ast_sched_when(), context_merge(), find_context(), find_context_locked(), and pbx_find_extension().
{ /* lookup this object in the hash table. return a ptr if found, or NULL if not */ unsigned int h; void *ret; if (!tab || !obj) return 0; if (tab->do_locking) ast_rwlock_rdlock(&tab->lock); h = (*tab->hash)(obj) % tab->hash_tab_size; ret = ast_hashtab_lookup_internal(tab,obj,h); if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return ret; }
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.
Definition at line 575 of file hashtab.c.
References ast_hashtab_lookup_internal(), ast_hashtab::hash, and ast_hashtab::hash_tab_size.
Referenced by ast_hashtab_insert_safe().
{ /* lookup this object in the hash table. return a ptr if found, or NULL if not */ unsigned int h; void *ret; if (!tab || !obj) return 0; h = (*tab->hash)(obj) % tab->hash_tab_size; ret = ast_hashtab_lookup_internal(tab,obj,h); *bucket = h; return ret; }
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.
Definition at line 553 of file hashtab.c.
References ast_hashtab_lookup_internal(), ast_rwlock_rdlock(), ast_rwlock_unlock(), ast_hashtab::do_locking, ast_hashtab::hash_tab_size, and ast_hashtab::lock.
{ /* lookup this object in the hash table. return a ptr if found, or NULL if not */ unsigned int h; void *ret; if (!tab || !obj) return 0; if (tab->do_locking) ast_rwlock_rdlock(&tab->lock); h = hashval % tab->hash_tab_size; ret = ast_hashtab_lookup_internal(tab,obj,h); if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return ret; }
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.
References ast_is_prime(), and ast_hashtab::hash_tab_size.
Referenced by ast_add_extension2_lockopt(), ast_context_find_or_create(), ast_hashtab_create(), lua_register_switches(), pbx_load_module(), and sched_context_create().
{ int i = (tab->hash_tab_size << 1); /* multiply by two */ while (!ast_is_prime(i)) i++; return i; }
int ast_hashtab_newsize_none | ( | struct ast_hashtab * | tab | ) |
always return current size -- no resizing
Definition at line 148 of file hashtab.c.
References ast_hashtab::hash_tab_size.
{ return tab->hash_tab_size; }
int ast_hashtab_newsize_tight | ( | struct ast_hashtab * | tab | ) |
Definition at line 137 of file hashtab.c.
References ast_is_prime(), and ast_hashtab::hash_tab_size.
{ int x = (tab->hash_tab_size << 1); int i = (tab->hash_tab_size + x); while (!ast_is_prime(i)) i++; return i; }
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 749 of file hashtab.c.
References ast_hashtab_iter::next, ast_hashtab_bucket::object, and ast_hashtab_bucket::tnext.
Referenced by __ast_context_destroy(), ast_merge_contexts_and_delete(), context_merge(), and create_match_char_tree().
void ast_hashtab_rdlock | ( | struct ast_hashtab * | tab | ) |
Request a read-lock on the table -- don't change anything!
Definition at line 364 of file hashtab.c.
References ast_rwlock_rdlock(), and ast_hashtab::lock.
{ ast_rwlock_rdlock(&tab->lock); }
void* ast_hashtab_remove_object_via_lookup | ( | struct ast_hashtab * | tab, |
void * | obj | ||
) |
Looks up the object, removes the corresponding bucket.
Definition at line 812 of file hashtab.c.
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_pri_lockopt().
{ /* looks up the object; removes the corresponding bucket */ const void *obj2; if (!tab || !obj) return 0; if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj); if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return (void *)obj2; }
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 831 of file hashtab.c.
References ast_hashtab::array, ast_hashtab_remove_object_internal(), ast_hashtab::compare, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab_bucket::next, and ast_hashtab_bucket::object.
Referenced by ast_hashtab_remove_object_via_lookup().
{ /* looks up the object; removes the corresponding bucket */ unsigned int h; struct ast_hashtab_bucket *b; if (!tab || !obj) return 0; h = (*tab->hash)(obj) % tab->hash_tab_size; for (b = tab->array[h]; b; b = b->next) { if (!(*tab->compare)(obj, b->object)) { const void *obj2; obj2 = ast_hashtab_remove_object_internal(tab, b, h); return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ } } return 0; }
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 855 of file hashtab.c.
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_context_remove_extension_callerid2(), ast_sched_del(), and ast_sched_runq().
{ /* looks up the object by hash and then comparing pts in bucket list instead of calling the compare routine; removes the bucket -- a slightly cheaper operation */ /* looks up the object; removes the corresponding bucket */ const void *obj2; if (!tab || !obj) return 0; if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); obj2 = ast_hashtab_remove_this_object_nolock(tab,obj); if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return (void *)obj2; }
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 876 of file hashtab.c.
References ast_hashtab::array, ast_hashtab_remove_object_internal(), ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab_bucket::next, and ast_hashtab_bucket::object.
Referenced by ast_hashtab_remove_this_object().
{ /* looks up the object by hash and then comparing pts in bucket list instead of calling the compare routine; removes the bucket -- a slightly cheaper operation */ /* looks up the object; removes the corresponding bucket */ unsigned int h; struct ast_hashtab_bucket *b; if (!tab || !obj) return 0; h = (*tab->hash)(obj) % tab->hash_tab_size; for (b = tab->array[h]; b; b = b->next) { if (obj == b->object) { const void *obj2; obj2 = ast_hashtab_remove_object_internal(tab, b, h); return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ } } return 0; }
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).
tab | the hash table to operate on |
0 | if the table load factor is less than or equal to 75% |
1 | if the table load factor is greater than 75% |
Definition at line 84 of file 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(), ast_hashtab_create(), lua_register_switches(), pbx_load_module(), and sched_context_create().
{ double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size; return (loadfactor > 0.75); }
int ast_hashtab_resize_none | ( | struct ast_hashtab * | tab | ) |
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.
tab | the hash table to operate on |
0 | if the number of elements in the table is less than or equal to the number of buckets |
1 | if the number of elements in the table exceeds the number of buckets |
Definition at line 91 of file hashtab.c.
References ast_hashtab::hash_tab_elements, and ast_hashtab::hash_tab_size.
{ return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */ }
int ast_hashtab_size | ( | struct ast_hashtab * | tab | ) |
Returns the number of elements stored in the hashtab.
Definition at line 621 of file hashtab.c.
References ast_hashtab::hash_tab_elements.
Referenced by ast_context_remove_extension_callerid2().
{ return tab->hash_tab_elements; }
struct ast_hashtab_iter* ast_hashtab_start_traversal | ( | struct ast_hashtab * | tab | ) | [read] |
Gives an iterator to hastable.
Definition at line 692 of file hashtab.c.
References __ast_calloc(), ast_calloc, ast_rwlock_rdlock(), ast_hashtab::do_locking, ast_hashtab::lock, ast_hashtab_iter::next, ast_hashtab_iter::tab, and ast_hashtab::tlist.
Referenced by __ast_context_destroy(), ast_merge_contexts_and_delete(), context_merge(), and create_match_char_tree().
{ /* returns an iterator */ struct ast_hashtab_iter *it; if (!(it = #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) __ast_calloc(1, sizeof(*it), file, lineno, func) #else ast_calloc(1, sizeof(*it)) #endif )) return NULL; it->next = tab->tlist; it->tab = tab; if (tab->do_locking) ast_rwlock_rdlock(&tab->lock); return it; }
struct ast_hashtab_iter* ast_hashtab_start_write_traversal | ( | struct ast_hashtab * | tab | ) | [read] |
Gives an iterator to hastable.
Definition at line 719 of file hashtab.c.
References __ast_calloc(), ast_calloc, ast_rwlock_wrlock(), ast_hashtab::do_locking, ast_hashtab::lock, ast_hashtab_iter::next, ast_hashtab_iter::tab, and ast_hashtab::tlist.
{ /* returns an iterator */ struct ast_hashtab_iter *it; if (!(it = #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) __ast_calloc(1, sizeof(*it), file, lineno, func) #else ast_calloc(1, sizeof(*it)) #endif )) return NULL; it->next = tab->tlist; it->tab = tab; if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); return it; }
void ast_hashtab_unlock | ( | struct ast_hashtab * | tab | ) |
release a read- or write- lock.
Definition at line 379 of file hashtab.c.
References ast_rwlock_unlock(), and ast_hashtab::lock.
{ ast_rwlock_unlock(&tab->lock); }
void ast_hashtab_wrlock | ( | struct ast_hashtab * | tab | ) |
Request a write-lock on the table.
Definition at line 359 of file hashtab.c.
References ast_rwlock_wrlock(), and ast_hashtab::lock.
{ ast_rwlock_wrlock(&tab->lock); }
int ast_is_prime | ( | int | num | ) |
Determines if the specified number is prime.
num | the number to test |
0 | if the number is not prime |
1 | if the number is prime |
Definition at line 101 of file hashtab.c.
References num.
Referenced by ast_hashtab_create(), ast_hashtab_newsize_java(), and ast_hashtab_newsize_tight().
{ int tnum, limit; if (!(num & 0x1)) /* even number -- not prime */ return 0; /* Loop through ODD numbers starting with 3 */ tnum = 3; limit = num; while (tnum < limit) { if (!(num % tnum)) return 0; /* really, we only need to check sqrt(num) numbers */ limit = num / tnum; /* we only check odd numbers */ tnum = tnum + 2; } /* if we made it through the loop, the number is a prime */ return 1; }