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. | |
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. | |
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. | |
ast_hashtab_iter * | ast_hashtab_start_traversal (struct ast_hashtab *tab) |
Gives an iterator to hastable. | |
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. |
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 631 of file hashtab.c.
References ast_hashtab::hash_tab_size.
00632 { 00633 return tab->hash_tab_size; 00634 }
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 66 of file hashtab.c.
00067 { 00068 int ai = *((int *) a); 00069 int bi = *((int *) b); 00070 00071 if (ai < bi) 00072 return -1; 00073 00074 return !(ai == bi); 00075 }
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 77 of file hashtab.c.
00078 { 00079 short as = *((short *) a); 00080 short bs = *((short *) b); 00081 00082 if (as < bs) 00083 return -1; 00084 00085 return !(as == bs); 00086 }
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 | |||
) |
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 226 of file hashtab.c.
References __ast_calloc(), ast_calloc, ast_hashtab_newsize_java(), ast_hashtab_resize_java(), ast_is_prime(), ast_rwlock_init, compare(), ast_hashtab::do_locking, and free.
Referenced by ast_add_extension2_lockopt(), ast_context_find_or_create(), lua_register_switches(), pbx_load_module(), and sched_context_create().
00236 { 00237 struct ast_hashtab *ht; 00238 00239 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00240 if (!(ht = __ast_calloc(1, sizeof(*ht), file, lineno, function))) 00241 #else 00242 if (!(ht = ast_calloc(1, sizeof(*ht)))) 00243 #endif 00244 return NULL; 00245 00246 while (!ast_is_prime(initial_buckets)) /* make sure this is prime */ 00247 initial_buckets++; 00248 00249 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00250 if (!(ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)), file, lineno, function))) { 00251 #else 00252 if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) { 00253 #endif 00254 free(ht); 00255 return NULL; 00256 } 00257 00258 ht->hash_tab_size = initial_buckets; 00259 ht->compare = compare; 00260 ht->resize = resize; 00261 ht->newsize = newsize; 00262 ht->hash = hash; 00263 ht->do_locking = do_locking; 00264 00265 if (do_locking) 00266 ast_rwlock_init(&ht->lock); 00267 00268 if (!ht->resize) 00269 ht->resize = ast_hashtab_resize_java; 00270 00271 if (!ht->newsize) 00272 ht->newsize = ast_hashtab_newsize_java; 00273 00274 return ht; 00275 }
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 388 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().
00389 { 00390 /* this func will free the hash table and all its memory. It 00391 doesn't touch the objects stored in it */ 00392 if (tab) { 00393 00394 if (tab->do_locking) 00395 ast_rwlock_wrlock(&tab->lock); 00396 00397 if (tab->array) { 00398 /* go thru and destroy the buckets */ 00399 struct ast_hashtab_bucket *t; 00400 int i; 00401 00402 while (tab->tlist) { 00403 t = tab->tlist; 00404 if (t->object && objdestroyfunc) { 00405 /* I cast this because I'm not going to MOD it, I'm going to DESTROY 00406 * it. 00407 */ 00408 (*objdestroyfunc)((void *) t->object); 00409 } 00410 00411 tlist_del_item(&(tab->tlist), tab->tlist); 00412 free(t); 00413 } 00414 00415 for (i = 0; i < tab->hash_tab_size; i++) { 00416 /* Not totally necessary, but best to destroy old pointers */ 00417 tab->array[i] = NULL; 00418 } 00419 free(tab->array); 00420 } 00421 if (tab->do_locking) { 00422 ast_rwlock_unlock(&tab->lock); 00423 ast_rwlock_destroy(&tab->lock); 00424 } 00425 free(tab); 00426 } 00427 }
void ast_hashtab_destroylock | ( | struct ast_hashtab * | tab | ) |
Call this before you destroy the table.
Definition at line 378 of file hashtab.c.
References ast_rwlock_destroy, and ast_hashtab::lock.
00379 { 00380 ast_rwlock_destroy(&tab->lock); 00381 }
struct ast_hashtab* ast_hashtab_dup | ( | struct ast_hashtab * | tab, | |
void *(*)(const void *obj) | obj_dup_func | |||
) |
Return a copy of the hash table.
Definition at line 280 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::newsize, and ast_hashtab::resize.
00282 { 00283 struct ast_hashtab *ht; 00284 unsigned int i; 00285 00286 if (!(ht = ast_calloc(1, sizeof(*ht)))) 00287 return NULL; 00288 00289 if (!(ht->array = 00290 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00291 __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)), file, lineno, func) 00292 #else 00293 ast_calloc(tab->hash_tab_size, sizeof(*(ht->array))) 00294 #endif 00295 )) { 00296 free(ht); 00297 return NULL; 00298 } 00299 00300 ht->hash_tab_size = tab->hash_tab_size; 00301 ht->compare = tab->compare; 00302 ht->resize = tab->resize; 00303 ht->newsize = tab->newsize; 00304 ht->hash = tab->hash; 00305 ht->do_locking = tab->do_locking; 00306 00307 if (ht->do_locking) 00308 ast_rwlock_init(&ht->lock); 00309 00310 /* now, dup the objects in the buckets and get them into the table */ 00311 /* the fast way is to use the existing array index, and not have to hash 00312 the objects again */ 00313 for (i = 0; i < ht->hash_tab_size; i++) { 00314 struct ast_hashtab_bucket *b = tab->array[i]; 00315 while (b) { 00316 void *newobj = (*obj_dup_func)(b->object); 00317 if (newobj) 00318 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00319 _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func); 00320 #else 00321 ast_hashtab_insert_immediate_bucket(ht, newobj, i); 00322 #endif 00323 b = b->next; 00324 } 00325 } 00326 00327 return ht; 00328 }
void ast_hashtab_end_traversal | ( | struct ast_hashtab_iter * | it | ) |
end the traversal, free the iterator, unlock if necc.
Definition at line 746 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().
00747 { 00748 if (it->tab->do_locking) 00749 ast_rwlock_unlock(&it->tab->lock); 00750 free(it); 00751 }
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 611 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().
00612 { 00613 /* returns key stats for the table */ 00614 if (tab->do_locking) 00615 ast_rwlock_rdlock(&tab->lock); 00616 *biggest_bucket_size = tab->largest_bucket_size; 00617 *resize_count = tab->resize_count; 00618 *num_objects = tab->hash_tab_elements; 00619 *num_buckets = tab->hash_tab_size; 00620 if (tab->do_locking) 00621 ast_rwlock_unlock(&tab->lock); 00622 }
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 157 of file hashtab.c.
Referenced by ast_hashtab_hash_contexts(), hashtab_hash_extens(), and hashtab_hash_labels().
00158 { 00159 unsigned char *str = (unsigned char *) obj; 00160 unsigned int total; 00161 00162 for (total = 0; *str; str++) { 00163 unsigned int tmp = total; 00164 total <<= 1; /* multiply by 2 */ 00165 total += tmp; /* multiply by 3 */ 00166 total <<= 2; /* multiply by 12 */ 00167 total += tmp; /* multiply by 13 */ 00168 00169 total += ((unsigned int)(*str)); 00170 } 00171 return total; 00172 }
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 185 of file hashtab.c.
00186 { 00187 const unsigned char *str = obj; 00188 unsigned int total; 00189 00190 for (total = 0; *str; str++) { 00191 unsigned int tmp = total; 00192 unsigned int charval = toupper(*str); 00193 00194 /* hopefully, the following is faster than multiplication by 7 */ 00195 /* why do I go to this bother? A good compiler will do this 00196 anyway, if I say total *= 13 */ 00197 /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */ 00198 total <<= 1; /* multiply by 2 */ 00199 total += tmp; /* multiply by 3 */ 00200 total <<= 2; /* multiply by 12 */ 00201 total += tmp; /* multiply by 13 */ 00202 00203 total += (charval); 00204 } 00205 00206 return total; 00207 }
unsigned int ast_hashtab_hash_string_sax | ( | const void * | obj | ) |
Hashes a string to a number using a modified Shift-And-XOR algorithm.
obj | the string to hash |
ast_hastable_hash_string_nocase
Definition at line 174 of file hashtab.c.
00175 { 00176 const unsigned char *str = obj; 00177 unsigned int total = 0, c = 0; 00178 00179 while ((c = *str++)) 00180 total ^= (total << 5) + (total >> 2) + (total << 10) + c; 00181 00182 return total; 00183 }
void ast_hashtab_initlock | ( | struct ast_hashtab * | tab | ) |
Call this after you create the table to init the lock.
Definition at line 373 of file hashtab.c.
References ast_rwlock_init, and ast_hashtab::lock.
00374 { 00375 ast_rwlock_init(&tab->lock); 00376 }
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 432 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().
00434 { 00435 unsigned int h; 00436 int res=0; 00437 00438 if (!tab || !obj) 00439 return res; 00440 00441 if (tab->do_locking) 00442 ast_rwlock_wrlock(&tab->lock); 00443 00444 h = (*tab->hash)(obj) % tab->hash_tab_size; 00445 00446 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00447 res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func); 00448 #else 00449 res = ast_hashtab_insert_immediate_bucket(tab, obj, h); 00450 #endif 00451 00452 if (tab->do_locking) 00453 ast_rwlock_unlock(&tab->lock); 00454 00455 return res; 00456 }
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 461 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::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().
00463 { 00464 int c; 00465 struct ast_hashtab_bucket *b; 00466 00467 if (!tab || !obj) 00468 return 0; 00469 00470 for (c = 0, b = tab->array[h]; b; b= b->next) 00471 c++; 00472 00473 if (c + 1 > tab->largest_bucket_size) 00474 tab->largest_bucket_size = c + 1; 00475 00476 if (!(b = 00477 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00478 __ast_calloc(1, sizeof(*b), file, lineno, func) 00479 #else 00480 ast_calloc(1, sizeof(*b)) 00481 #endif 00482 )) return 0; 00483 00484 b->object = obj; 00485 b->next = tab->array[h]; 00486 tab->array[h] = b; 00487 00488 if (b->next) 00489 b->next->prev = b; 00490 00491 tlist_add_head(&(tab->tlist), b); 00492 tab->hash_tab_elements++; 00493 00494 if ((*tab->resize)(tab)) 00495 ast_hashtab_resize(tab); 00496 00497 return 1; 00498 }
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 503 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 ast_add_extension2_lockopt(), ast_context_find_or_create(), and schedule().
00505 { 00506 /* check to see if the element is already there; insert only if 00507 it is not there. */ 00508 /* will force a resize if the resize func returns 1 */ 00509 /* returns 1 on success, 0 if there's a problem, or it's already there. */ 00510 unsigned int bucket = 0; 00511 00512 if (tab->do_locking) 00513 ast_rwlock_wrlock(&tab->lock); 00514 00515 if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) { 00516 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00517 int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func); 00518 #else 00519 int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket); 00520 #endif 00521 00522 if (tab->do_locking) 00523 ast_rwlock_unlock(&tab->lock); 00524 00525 return ret2; 00526 } 00527 00528 if (tab->do_locking) 00529 ast_rwlock_unlock(&tab->lock); 00530 00531 return 0; 00532 }
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 534 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_remove_extension_callerid2(), ast_sched_del(), ast_sched_find_data(), ast_sched_when(), context_merge(), find_context(), find_context_locked(), new_find_extension(), and pbx_find_extension().
00535 { 00536 /* lookup this object in the hash table. return a ptr if found, or NULL if not */ 00537 unsigned int h; 00538 void *ret; 00539 00540 if (!tab || !obj) 00541 return 0; 00542 00543 if (tab->do_locking) 00544 ast_rwlock_rdlock(&tab->lock); 00545 00546 h = (*tab->hash)(obj) % tab->hash_tab_size; 00547 00548 ret = ast_hashtab_lookup_internal(tab,obj,h); 00549 00550 if (tab->do_locking) 00551 ast_rwlock_unlock(&tab->lock); 00552 00553 return ret; 00554 }
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 579 of file hashtab.c.
References ast_hashtab_lookup_internal(), ast_hashtab::hash, and ast_hashtab::hash_tab_size.
Referenced by ast_hashtab_insert_safe().
00580 { 00581 /* lookup this object in the hash table. return a ptr if found, or NULL if not */ 00582 unsigned int h; 00583 void *ret; 00584 00585 if (!tab || !obj) 00586 return 0; 00587 00588 h = (*tab->hash)(obj) % tab->hash_tab_size; 00589 00590 ret = ast_hashtab_lookup_internal(tab,obj,h); 00591 00592 *bucket = h; 00593 00594 return ret; 00595 }
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 557 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.
00558 { 00559 /* lookup this object in the hash table. return a ptr if found, or NULL if not */ 00560 unsigned int h; 00561 void *ret; 00562 00563 if (!tab || !obj) 00564 return 0; 00565 00566 if (tab->do_locking) 00567 ast_rwlock_rdlock(&tab->lock); 00568 00569 h = hashval % tab->hash_tab_size; 00570 00571 ret = ast_hashtab_lookup_internal(tab,obj,h); 00572 00573 if (tab->do_locking) 00574 ast_rwlock_unlock(&tab->lock); 00575 00576 return ret; 00577 }
int ast_hashtab_newsize_java | ( | struct ast_hashtab * | tab | ) |
Create a prime number roughly 2x the current table size.
Definition at line 131 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().
00132 { 00133 int i = (tab->hash_tab_size << 1); /* multiply by two */ 00134 00135 while (!ast_is_prime(i)) 00136 i++; 00137 00138 return i; 00139 }
int ast_hashtab_newsize_none | ( | struct ast_hashtab * | tab | ) |
always return current size -- no resizing
Definition at line 152 of file hashtab.c.
References ast_hashtab::hash_tab_size.
00153 { 00154 return tab->hash_tab_size; 00155 }
int ast_hashtab_newsize_tight | ( | struct ast_hashtab * | tab | ) |
Definition at line 141 of file hashtab.c.
References ast_is_prime(), and ast_hashtab::hash_tab_size.
00142 { 00143 int x = (tab->hash_tab_size << 1); 00144 int i = (tab->hash_tab_size + x); 00145 00146 while (!ast_is_prime(i)) 00147 i++; 00148 00149 return i; 00150 }
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 753 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().
00754 { 00755 /* returns the next object in the list, advances iter one step */ 00756 struct ast_hashtab_bucket *retval; 00757 00758 if (it && it->next) { /* there's a next in the bucket list */ 00759 retval = it->next; 00760 it->next = retval->tnext; 00761 return (void *) retval->object; 00762 } 00763 00764 return NULL; 00765 }
void ast_hashtab_rdlock | ( | struct ast_hashtab * | tab | ) |
Request a read-lock on the table -- don't change anything!
Definition at line 368 of file hashtab.c.
References ast_rwlock_rdlock, and ast_hashtab::lock.
00369 { 00370 ast_rwlock_rdlock(&tab->lock); 00371 }
void* ast_hashtab_remove_object_via_lookup | ( | struct ast_hashtab * | tab, | |
void * | obj | |||
) |
Looks up the object, removes the corresponding bucket.
Definition at line 816 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.
00817 { 00818 /* looks up the object; removes the corresponding bucket */ 00819 const void *obj2; 00820 00821 if (!tab || !obj) 00822 return 0; 00823 00824 if (tab->do_locking) 00825 ast_rwlock_wrlock(&tab->lock); 00826 00827 obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj); 00828 00829 if (tab->do_locking) 00830 ast_rwlock_unlock(&tab->lock); 00831 00832 return (void *)obj2; 00833 }
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 835 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().
00836 { 00837 /* looks up the object; removes the corresponding bucket */ 00838 unsigned int h; 00839 struct ast_hashtab_bucket *b; 00840 00841 if (!tab || !obj) 00842 return 0; 00843 00844 h = (*tab->hash)(obj) % tab->hash_tab_size; 00845 for (b = tab->array[h]; b; b = b->next) { 00846 00847 if (!(*tab->compare)(obj, b->object)) { 00848 const void *obj2; 00849 00850 obj2 = ast_hashtab_remove_object_internal(tab, b, h); 00851 00852 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ 00853 } 00854 } 00855 00856 return 0; 00857 }
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 859 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().
00860 { 00861 /* looks up the object by hash and then comparing pts in bucket list instead of 00862 calling the compare routine; removes the bucket -- a slightly cheaper operation */ 00863 /* looks up the object; removes the corresponding bucket */ 00864 const void *obj2; 00865 00866 if (!tab || !obj) 00867 return 0; 00868 00869 if (tab->do_locking) 00870 ast_rwlock_wrlock(&tab->lock); 00871 00872 obj2 = ast_hashtab_remove_this_object_nolock(tab,obj); 00873 00874 if (tab->do_locking) 00875 ast_rwlock_unlock(&tab->lock); 00876 00877 return (void *)obj2; 00878 }
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 880 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().
00881 { 00882 /* looks up the object by hash and then comparing pts in bucket list instead of 00883 calling the compare routine; removes the bucket -- a slightly cheaper operation */ 00884 /* looks up the object; removes the corresponding bucket */ 00885 unsigned int h; 00886 struct ast_hashtab_bucket *b; 00887 00888 if (!tab || !obj) 00889 return 0; 00890 00891 h = (*tab->hash)(obj) % tab->hash_tab_size; 00892 for (b = tab->array[h]; b; b = b->next) { 00893 00894 if (obj == b->object) { 00895 const void *obj2; 00896 obj2 = ast_hashtab_remove_object_internal(tab, b, h); 00897 00898 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ 00899 } 00900 } 00901 00902 return 0; 00903 }
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 88 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().
00089 { 00090 double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size; 00091 00092 return (loadfactor > 0.75); 00093 }
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 95 of file hashtab.c.
References ast_hashtab::hash_tab_elements, and ast_hashtab::hash_tab_size.
00096 { 00097 return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */ 00098 }
int ast_hashtab_size | ( | struct ast_hashtab * | tab | ) |
Returns the number of elements stored in the hashtab.
Definition at line 625 of file hashtab.c.
References ast_hashtab::hash_tab_elements.
Referenced by ast_context_remove_extension_callerid2().
00626 { 00627 return tab->hash_tab_elements; 00628 }
struct ast_hashtab_iter* ast_hashtab_start_traversal | ( | struct ast_hashtab * | tab | ) |
Gives an iterator to hastable.
Definition at line 696 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().
00698 { 00699 /* returns an iterator */ 00700 struct ast_hashtab_iter *it; 00701 00702 if (!(it = 00703 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00704 __ast_calloc(1, sizeof(*it), file, lineno, func) 00705 #else 00706 ast_calloc(1, sizeof(*it)) 00707 #endif 00708 )) 00709 return NULL; 00710 00711 it->next = tab->tlist; 00712 it->tab = tab; 00713 if (tab->do_locking) 00714 ast_rwlock_rdlock(&tab->lock); 00715 00716 return it; 00717 }
struct ast_hashtab_iter* ast_hashtab_start_write_traversal | ( | struct ast_hashtab * | tab | ) |
Gives an iterator to hastable.
Definition at line 723 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.
00725 { 00726 /* returns an iterator */ 00727 struct ast_hashtab_iter *it; 00728 00729 if (!(it = 00730 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00731 __ast_calloc(1, sizeof(*it), file, lineno, func) 00732 #else 00733 ast_calloc(1, sizeof(*it)) 00734 #endif 00735 )) 00736 return NULL; 00737 00738 it->next = tab->tlist; 00739 it->tab = tab; 00740 if (tab->do_locking) 00741 ast_rwlock_wrlock(&tab->lock); 00742 00743 return it; 00744 }
void ast_hashtab_unlock | ( | struct ast_hashtab * | tab | ) |
release a read- or write- lock.
Definition at line 383 of file hashtab.c.
References ast_rwlock_unlock, and ast_hashtab::lock.
00384 { 00385 ast_rwlock_unlock(&tab->lock); 00386 }
void ast_hashtab_wrlock | ( | struct ast_hashtab * | tab | ) |
Request a write-lock on the table.
Definition at line 363 of file hashtab.c.
References ast_rwlock_wrlock, and ast_hashtab::lock.
00364 { 00365 ast_rwlock_wrlock(&tab->lock); 00366 }
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 105 of file hashtab.c.
Referenced by ast_hashtab_create(), ast_hashtab_newsize_java(), and ast_hashtab_newsize_tight().
00106 { 00107 int tnum, limit; 00108 00109 if (!(num & 0x1)) /* even number -- not prime */ 00110 return 0; 00111 00112 /* Loop through ODD numbers starting with 3 */ 00113 00114 tnum = 3; 00115 limit = num; 00116 while (tnum < limit) { 00117 if (!(num % tnum)) 00118 return 0; 00119 00120 /* really, we only need to check sqrt(num) numbers */ 00121 limit = num / tnum; 00122 00123 /* we only check odd numbers */ 00124 tnum = tnum + 2; 00125 } 00126 00127 /* if we made it through the loop, the number is a prime */ 00128 return 1; 00129 }