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) |
assumes a & b are int * | |
int | ast_hashtab_compare_shorts (const void *a, const void *b) |
assumes a & b are short * | |
int | ast_hashtab_compare_strings (const void *a, const void *b) |
assumes a and b are char * | |
int | ast_hashtab_compare_strings_nocase (const void *a, const void *b) |
assumes a & b are strings | |
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) |
Upperases each char before using them for a hash. | |
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. | |
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) |
determine if resize should occur | |
int | ast_hashtab_resize_none (struct ast_hashtab *tab) |
no resizing; always return 0 | |
int | ast_hashtab_resize_tight (struct ast_hashtab *tab) |
no resizing; always return 0 | |
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) |
For sizing the hash table, tells if num is prime or not. |
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 578 of file hashtab.c.
References ast_hashtab::hash_tab_size.
00579 { 00580 return tab->hash_tab_size; 00581 }
int ast_hashtab_compare_ints | ( | const void * | a, | |
const void * | b | |||
) |
int ast_hashtab_compare_shorts | ( | const void * | a, | |
const void * | b | |||
) |
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 218 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().
00228 { 00229 struct ast_hashtab *ht; 00230 00231 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00232 if (!(ht = __ast_calloc(1, sizeof(*ht), file, lineno, function))) 00233 #else 00234 if (!(ht = ast_calloc(1, sizeof(*ht)))) 00235 #endif 00236 return NULL; 00237 00238 while (!ast_is_prime(initial_buckets)) /* make sure this is prime */ 00239 initial_buckets++; 00240 00241 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00242 if (!(ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)), file, lineno, function))) { 00243 #else 00244 if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) { 00245 #endif 00246 free(ht); 00247 return NULL; 00248 } 00249 00250 ht->hash_tab_size = initial_buckets; 00251 ht->compare = compare; 00252 ht->resize = resize; 00253 ht->newsize = newsize; 00254 ht->hash = hash; 00255 ht->do_locking = do_locking; 00256 00257 if (do_locking) 00258 ast_rwlock_init(&ht->lock); 00259 00260 if (!ht->resize) 00261 ht->resize = ast_hashtab_resize_java; 00262 00263 if (!ht->newsize) 00264 ht->newsize = ast_hashtab_newsize_java; 00265 00266 return ht; 00267 }
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 366 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().
00367 { 00368 /* this func will free the hash table and all its memory. It 00369 doesn't touch the objects stored in it */ 00370 if (tab) { 00371 00372 if (tab->do_locking) 00373 ast_rwlock_wrlock(&tab->lock); 00374 00375 if (tab->array) { 00376 /* go thru and destroy the buckets */ 00377 struct ast_hashtab_bucket *t; 00378 int i; 00379 00380 while (tab->tlist) { 00381 t = tab->tlist; 00382 if (t->object && objdestroyfunc) 00383 (*objdestroyfunc)((void *) t->object); /* I cast this because I'm not going to MOD it, I'm going to DESTROY it */ 00384 00385 tlist_del_item(&(tab->tlist), tab->tlist); 00386 free(t); 00387 } 00388 00389 for (i = 0; i < tab->hash_tab_size; i++) 00390 tab->array[i] = NULL; /* not totally necc., but best to destroy old ptrs */ 00391 00392 free(tab->array); 00393 } 00394 if (tab->do_locking) { 00395 ast_rwlock_unlock(&tab->lock); 00396 ast_rwlock_destroy(&tab->lock); 00397 } 00398 free(tab); 00399 } 00400 }
void ast_hashtab_destroylock | ( | struct ast_hashtab * | tab | ) |
Call this before you destroy the table.
Definition at line 356 of file hashtab.c.
References ast_rwlock_destroy(), and ast_hashtab::lock.
00357 { 00358 ast_rwlock_destroy(&tab->lock); 00359 }
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 269 of file hashtab.c.
References 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.
00270 { 00271 struct ast_hashtab *ht; 00272 unsigned int i; 00273 00274 if (!(ht = ast_calloc(1, sizeof(*ht)))) 00275 return NULL; 00276 00277 if (!(ht->array = ast_calloc(tab->hash_tab_size, sizeof(*(ht->array))))) { 00278 free(ht); 00279 return NULL; 00280 } 00281 00282 ht->hash_tab_size = tab->hash_tab_size; 00283 ht->compare = tab->compare; 00284 ht->resize = tab->resize; 00285 ht->newsize = tab->newsize; 00286 ht->hash = tab->hash; 00287 ht->do_locking = tab->do_locking; 00288 00289 if (ht->do_locking) 00290 ast_rwlock_init(&ht->lock); 00291 00292 /* now, dup the objects in the buckets and get them into the table */ 00293 /* the fast way is to use the existing array index, and not have to hash 00294 the objects again */ 00295 for (i = 0; i < ht->hash_tab_size; i++) { 00296 struct ast_hashtab_bucket *b = tab->array[i]; 00297 while (b) { 00298 void *newobj = (*obj_dup_func)(b->object); 00299 if (newobj) 00300 ast_hashtab_insert_immediate_bucket(ht, newobj, i); 00301 b = b->next; 00302 } 00303 } 00304 00305 return ht; 00306 }
void ast_hashtab_end_traversal | ( | struct ast_hashtab_iter * | it | ) |
end the traversal, free the iterator, unlock if necc.
Definition at line 666 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().
00667 { 00668 if (it->tab->do_locking) 00669 ast_rwlock_unlock(&it->tab->lock); 00670 free(it); 00671 }
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 558 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().
00559 { 00560 /* returns key stats for the table */ 00561 if (tab->do_locking) 00562 ast_rwlock_rdlock(&tab->lock); 00563 *biggest_bucket_size = tab->largest_bucket_size; 00564 *resize_count = tab->resize_count; 00565 *num_objects = tab->hash_tab_elements; 00566 *num_buckets = tab->hash_tab_size; 00567 if (tab->do_locking) 00568 ast_rwlock_unlock(&tab->lock); 00569 }
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 |
Definition at line 148 of file hashtab.c.
Referenced by ast_hashtab_hash_contexts(), hashtab_hash_extens(), and hashtab_hash_labels().
00149 { 00150 unsigned char *str = (unsigned char *) obj; 00151 unsigned int total; 00152 00153 for (total = 0; *str; str++) 00154 { 00155 unsigned int tmp = total; 00156 total <<= 1; /* multiply by 2 */ 00157 total += tmp; /* multiply by 3 */ 00158 total <<= 2; /* multiply by 12 */ 00159 total += tmp; /* multiply by 13 */ 00160 00161 total += ((unsigned int)(*str)); 00162 } 00163 return total; 00164 }
unsigned int ast_hashtab_hash_string_nocase | ( | const void * | obj | ) |
Upperases each char before using them for a hash.
Definition at line 177 of file hashtab.c.
00178 { 00179 const unsigned char *str = obj; 00180 unsigned int total; 00181 00182 for (total = 0; *str; str++) { 00183 unsigned int tmp = total; 00184 unsigned int charval = toupper(*str); 00185 00186 /* hopefully, the following is faster than multiplication by 7 */ 00187 /* why do I go to this bother? A good compiler will do this 00188 anyway, if I say total *= 13 */ 00189 /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */ 00190 total <<= 1; /* multiply by 2 */ 00191 total += tmp; /* multiply by 3 */ 00192 total <<= 2; /* multiply by 12 */ 00193 total += tmp; /* multiply by 13 */ 00194 00195 total += (charval); 00196 } 00197 00198 return total; 00199 }
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 351 of file hashtab.c.
References ast_rwlock_init(), and ast_hashtab::lock.
00352 { 00353 ast_rwlock_init(&tab->lock); 00354 }
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 402 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().
00403 { 00404 unsigned int h; 00405 int res=0; 00406 00407 if (!tab || !obj) 00408 return res; 00409 00410 if (tab->do_locking) 00411 ast_rwlock_wrlock(&tab->lock); 00412 00413 h = (*tab->hash)(obj) % tab->hash_tab_size; 00414 00415 res = ast_hashtab_insert_immediate_bucket(tab,obj,h); 00416 00417 if (tab->do_locking) 00418 ast_rwlock_unlock(&tab->lock); 00419 00420 return res; 00421 }
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 423 of file hashtab.c.
References 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().
00424 { 00425 int c; 00426 struct ast_hashtab_bucket *b; 00427 00428 if (!tab || !obj) 00429 return 0; 00430 00431 for (c = 0, b = tab->array[h]; b; b= b->next) 00432 c++; 00433 00434 if (c + 1 > tab->largest_bucket_size) 00435 tab->largest_bucket_size = c + 1; 00436 00437 if (!(b = ast_calloc(1, sizeof(*b)))) 00438 return 0; 00439 00440 b->object = obj; 00441 b->next = tab->array[h]; 00442 tab->array[h] = b; 00443 00444 if (b->next) 00445 b->next->prev = b; 00446 00447 tlist_add_head(&(tab->tlist), b); 00448 tab->hash_tab_elements++; 00449 00450 if ((*tab->resize)(tab)) 00451 ast_hashtab_resize(tab); 00452 00453 return 1; 00454 }
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 456 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().
00457 { 00458 /* check to see if the element is already there; insert only if 00459 it is not there. */ 00460 /* will force a resize if the resize func returns 1 */ 00461 /* returns 1 on success, 0 if there's a problem, or it's already there. */ 00462 unsigned int bucket = 0; 00463 00464 if (tab->do_locking) 00465 ast_rwlock_wrlock(&tab->lock); 00466 00467 if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) { 00468 int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket); 00469 00470 if (tab->do_locking) 00471 ast_rwlock_unlock(&tab->lock); 00472 00473 return ret2; 00474 } 00475 00476 if (tab->do_locking) 00477 ast_rwlock_unlock(&tab->lock); 00478 00479 return 0; 00480 }
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 482 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(), new_find_extension(), and pbx_find_extension().
00483 { 00484 /* lookup this object in the hash table. return a ptr if found, or NULL if not */ 00485 unsigned int h; 00486 void *ret; 00487 00488 if (!tab || !obj) 00489 return 0; 00490 00491 if (tab->do_locking) 00492 ast_rwlock_rdlock(&tab->lock); 00493 00494 h = (*tab->hash)(obj) % tab->hash_tab_size; 00495 00496 ret = ast_hashtab_lookup_internal(tab,obj,h); 00497 00498 if (tab->do_locking) 00499 ast_rwlock_unlock(&tab->lock); 00500 00501 return ret; 00502 }
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 527 of file hashtab.c.
References ast_hashtab_lookup_internal(), ast_hashtab::hash, and ast_hashtab::hash_tab_size.
Referenced by ast_hashtab_insert_safe().
00528 { 00529 /* lookup this object in the hash table. return a ptr if found, or NULL if not */ 00530 unsigned int h; 00531 void *ret; 00532 00533 if (!tab || !obj) 00534 return 0; 00535 00536 h = (*tab->hash)(obj) % tab->hash_tab_size; 00537 00538 ret = ast_hashtab_lookup_internal(tab,obj,h); 00539 00540 *bucket = h; 00541 00542 return ret; 00543 }
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 505 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.
00506 { 00507 /* lookup this object in the hash table. return a ptr if found, or NULL if not */ 00508 unsigned int h; 00509 void *ret; 00510 00511 if (!tab || !obj) 00512 return 0; 00513 00514 if (tab->do_locking) 00515 ast_rwlock_rdlock(&tab->lock); 00516 00517 h = hashval % tab->hash_tab_size; 00518 00519 ret = ast_hashtab_lookup_internal(tab,obj,h); 00520 00521 if (tab->do_locking) 00522 ast_rwlock_unlock(&tab->lock); 00523 00524 return ret; 00525 }
int ast_hashtab_newsize_java | ( | struct ast_hashtab * | tab | ) |
Create a prime number roughly 2x the current table size.
Definition at line 122 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().
00123 { 00124 int i = (tab->hash_tab_size << 1); /* multiply by two */ 00125 00126 while (!ast_is_prime(i)) 00127 i++; 00128 00129 return i; 00130 }
int ast_hashtab_newsize_none | ( | struct ast_hashtab * | tab | ) |
always return current size -- no resizing
Definition at line 143 of file hashtab.c.
References ast_hashtab::hash_tab_size.
00144 { 00145 return tab->hash_tab_size; 00146 }
int ast_hashtab_newsize_tight | ( | struct ast_hashtab * | tab | ) |
Definition at line 132 of file hashtab.c.
References ast_is_prime(), and ast_hashtab::hash_tab_size.
00133 { 00134 int x = (tab->hash_tab_size << 1); 00135 int i = (tab->hash_tab_size + x); 00136 00137 while (!ast_is_prime(i)) 00138 i++; 00139 00140 return i; 00141 }
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 673 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().
00674 { 00675 /* returns the next object in the list, advances iter one step */ 00676 struct ast_hashtab_bucket *retval; 00677 00678 if (it && it->next) { /* there's a next in the bucket list */ 00679 retval = it->next; 00680 it->next = retval->tnext; 00681 return (void *) retval->object; 00682 } 00683 00684 return NULL; 00685 }
void ast_hashtab_rdlock | ( | struct ast_hashtab * | tab | ) |
Request a read-lock on the table -- don't change anything!
Definition at line 346 of file hashtab.c.
References ast_rwlock_rdlock(), and ast_hashtab::lock.
00347 { 00348 ast_rwlock_rdlock(&tab->lock); 00349 }
void* ast_hashtab_remove_object_via_lookup | ( | struct ast_hashtab * | tab, | |
void * | obj | |||
) |
Looks up the object, removes the corresponding bucket.
Definition at line 736 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.
00737 { 00738 /* looks up the object; removes the corresponding bucket */ 00739 const void *obj2; 00740 00741 if (!tab || !obj) 00742 return 0; 00743 00744 if (tab->do_locking) 00745 ast_rwlock_wrlock(&tab->lock); 00746 00747 obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj); 00748 00749 if (tab->do_locking) 00750 ast_rwlock_unlock(&tab->lock); 00751 00752 return (void *)obj2; 00753 }
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 755 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().
00756 { 00757 /* looks up the object; removes the corresponding bucket */ 00758 unsigned int h; 00759 struct ast_hashtab_bucket *b; 00760 00761 if (!tab || !obj) 00762 return 0; 00763 00764 h = (*tab->hash)(obj) % tab->hash_tab_size; 00765 for (b = tab->array[h]; b; b = b->next) { 00766 00767 if (!(*tab->compare)(obj, b->object)) { 00768 const void *obj2; 00769 00770 obj2 = ast_hashtab_remove_object_internal(tab, b, h); 00771 00772 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ 00773 } 00774 } 00775 00776 return 0; 00777 }
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 779 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().
00780 { 00781 /* looks up the object by hash and then comparing pts in bucket list instead of 00782 calling the compare routine; removes the bucket -- a slightly cheaper operation */ 00783 /* looks up the object; removes the corresponding bucket */ 00784 const void *obj2; 00785 00786 if (!tab || !obj) 00787 return 0; 00788 00789 if (tab->do_locking) 00790 ast_rwlock_wrlock(&tab->lock); 00791 00792 obj2 = ast_hashtab_remove_this_object_nolock(tab,obj); 00793 00794 if (tab->do_locking) 00795 ast_rwlock_unlock(&tab->lock); 00796 00797 return (void *)obj2; 00798 }
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 800 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().
00801 { 00802 /* looks up the object by hash and then comparing pts in bucket list instead of 00803 calling the compare routine; removes the bucket -- a slightly cheaper operation */ 00804 /* looks up the object; removes the corresponding bucket */ 00805 unsigned int h; 00806 struct ast_hashtab_bucket *b; 00807 00808 if (!tab || !obj) 00809 return 0; 00810 00811 h = (*tab->hash)(obj) % tab->hash_tab_size; 00812 for (b = tab->array[h]; b; b = b->next) { 00813 00814 if (obj == b->object) { 00815 const void *obj2; 00816 obj2 = ast_hashtab_remove_object_internal(tab, b, h); 00817 00818 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ 00819 } 00820 } 00821 00822 return 0; 00823 }
int ast_hashtab_resize_java | ( | struct ast_hashtab * | tab | ) |
determine if resize should occur
Definition at line 78 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().
00079 { 00080 double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size; 00081 00082 return (loadfactor > 0.75); 00083 }
int ast_hashtab_resize_none | ( | struct ast_hashtab * | tab | ) |
int ast_hashtab_resize_tight | ( | struct ast_hashtab * | tab | ) |
no resizing; always return 0
Definition at line 85 of file hashtab.c.
References ast_hashtab::hash_tab_elements, and ast_hashtab::hash_tab_size.
00086 { 00087 return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */ 00088 }
int ast_hashtab_size | ( | struct ast_hashtab * | tab | ) |
Returns the number of elements stored in the hashtab.
Definition at line 572 of file hashtab.c.
References ast_hashtab::hash_tab_elements.
Referenced by ast_context_remove_extension_callerid2().
00573 { 00574 return tab->hash_tab_elements; 00575 }
struct ast_hashtab_iter* ast_hashtab_start_traversal | ( | struct ast_hashtab * | tab | ) |
Gives an iterator to hastable.
Definition at line 633 of file hashtab.c.
References 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().
00634 { 00635 /* returns an iterator */ 00636 struct ast_hashtab_iter *it; 00637 00638 if (!(it = ast_calloc(1, sizeof(*it)))) 00639 return NULL; 00640 00641 it->next = tab->tlist; 00642 it->tab = tab; 00643 if (tab->do_locking) 00644 ast_rwlock_rdlock(&tab->lock); 00645 00646 return it; 00647 }
struct ast_hashtab_iter* ast_hashtab_start_write_traversal | ( | struct ast_hashtab * | tab | ) |
Gives an iterator to hastable.
Definition at line 650 of file hashtab.c.
References ast_calloc, ast_rwlock_wrlock(), ast_hashtab::do_locking, ast_hashtab::lock, ast_hashtab_iter::next, ast_hashtab_iter::tab, and ast_hashtab::tlist.
00651 { 00652 /* returns an iterator */ 00653 struct ast_hashtab_iter *it; 00654 00655 if (!(it = ast_calloc(1, sizeof(*it)))) 00656 return NULL; 00657 00658 it->next = tab->tlist; 00659 it->tab = tab; 00660 if (tab->do_locking) 00661 ast_rwlock_wrlock(&tab->lock); 00662 00663 return it; 00664 }
void ast_hashtab_unlock | ( | struct ast_hashtab * | tab | ) |
release a read- or write- lock.
Definition at line 361 of file hashtab.c.
References ast_rwlock_unlock(), and ast_hashtab::lock.
00362 { 00363 ast_rwlock_unlock(&tab->lock); 00364 }
void ast_hashtab_wrlock | ( | struct ast_hashtab * | tab | ) |
Request a write-lock on the table.
Definition at line 341 of file hashtab.c.
References ast_rwlock_wrlock(), and ast_hashtab::lock.
00342 { 00343 ast_rwlock_wrlock(&tab->lock); 00344 }
int ast_is_prime | ( | int | num | ) |
For sizing the hash table, tells if num is prime or not.
Definition at line 95 of file hashtab.c.
Referenced by ast_hashtab_create(), ast_hashtab_newsize_java(), and ast_hashtab_newsize_tight().
00096 { 00097 int tnum, limit; 00098 00099 if (!(num & 0x1)) /* even number -- not prime */ 00100 return 0; 00101 00102 /* Loop through ODD numbers starting with 3 */ 00103 00104 tnum = 3; 00105 limit = num; 00106 while (tnum < limit) { 00107 if (!(num % tnum)) 00108 return 0; 00109 00110 /* really, we only need to check sqrt(num) numbers */ 00111 limit = num / tnum; 00112 00113 /* we only check odd numbers */ 00114 tnum = tnum + 2; 00115 } 00116 00117 /* if we made it through the loop, the number is a prime */ 00118 00119 return 1; 00120 }