Thu Jul 9 13:41:20 2009

Asterisk developer's documentation


hashtab.h File Reference

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)
 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_hashtabast_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_hashtabast_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_iterast_hashtab_start_traversal (struct ast_hashtab *tab)
 Gives an iterator to hastable.
ast_hashtab_iterast_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.


Detailed Description

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

Definition in file hashtab.h.


Define Documentation

#define __USE_UNIX98   1

Definition at line 20 of file hashtab.h.


Function Documentation

int ast_hashtab_capacity ( struct ast_hashtab tab  ) 

Returns the size of the bucket array in the hashtab.

Definition at line 560 of file hashtab.c.

References ast_hashtab::hash_tab_size.

00561 {
00562    return tab->hash_tab_size;
00563 }

int ast_hashtab_compare_ints ( const void *  a,
const void *  b 
)

assumes a & b are int *

Return values:
0 if match
1 a > b
-1 a < b

Definition at line 56 of file hashtab.c.

00057 {
00058    int ai = *((int *) a);
00059    int bi = *((int *) b);
00060 
00061    if (ai < bi)
00062       return -1;
00063    
00064    return !(ai == bi);
00065 }

int ast_hashtab_compare_shorts ( const void *  a,
const void *  b 
)

assumes a & b are short *

Return values:
0 if match
1 a > b
-1 a < b

Definition at line 67 of file hashtab.c.

00068 {
00069    short as = *((short *) a);
00070    short bs = *((short *) b);
00071    
00072    if (as < bs)
00073       return -1;
00074 
00075    return !(as == bs);
00076 }

int ast_hashtab_compare_strings ( const void *  a,
const void *  b 
)

assumes a and b are char *

Returns:
0 if they match

Definition at line 46 of file hashtab.c.

00047 {
00048    return strcmp(a, b);
00049 }

int ast_hashtab_compare_strings_nocase ( const void *  a,
const void *  b 
)

assumes a & b are strings

Returns:
0 if they match (strcasecmp)

Definition at line 51 of file hashtab.c.

00052 {
00053    return strcasecmp(a, b);
00054 }

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.

Parameters:
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 212 of file hashtab.c.

References ast_calloc, ast_hashtab_newsize_java(), ast_hashtab_resize_java(), ast_is_prime(), ast_rwlock_init(), and free.

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

00218 {
00219    struct ast_hashtab *ht;
00220    
00221    if (!(ht = ast_calloc(1, sizeof(*ht))))
00222       return NULL;
00223 
00224    while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
00225       initial_buckets++;
00226 
00227    if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) {
00228       free(ht);
00229       return NULL;
00230    }
00231 
00232    ht->hash_tab_size = initial_buckets;
00233    ht->compare = compare;
00234    ht->resize = resize;
00235    ht->newsize = newsize;
00236    ht->hash = hash;
00237    ht->do_locking = do_locking;
00238 
00239    if (do_locking)
00240       ast_rwlock_init(&ht->lock);
00241 
00242    if (!ht->resize)
00243       ht->resize = ast_hashtab_resize_java;
00244 
00245    if (!ht->newsize)
00246       ht->newsize = ast_hashtab_newsize_java;
00247 
00248    return ht;
00249 }

void ast_hashtab_destroy ( struct ast_hashtab tab,
void(*)(void *obj)  objdestroyfunc 
)

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

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

Definition at line 348 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(), and destroy_exten().

00349 {
00350    /* this func will free the hash table and all its memory. It
00351       doesn't touch the objects stored in it */
00352    if (tab) {
00353       
00354       if (tab->do_locking)
00355          ast_rwlock_wrlock(&tab->lock);
00356 
00357       if (tab->array) {
00358          /* go thru and destroy the buckets */
00359          struct ast_hashtab_bucket *t;
00360          int i;
00361          
00362          while (tab->tlist) {
00363             t = tab->tlist;
00364             if (t->object && objdestroyfunc)
00365                (*objdestroyfunc)((void *) t->object); /* I cast this because I'm not going to MOD it, I'm going to DESTROY it */
00366             
00367             tlist_del_item(&(tab->tlist), tab->tlist);
00368             free(t);
00369          }
00370          
00371          for (i = 0; i < tab->hash_tab_size; i++)
00372             tab->array[i] = NULL; /* not totally necc., but best to destroy old ptrs */
00373          
00374          free(tab->array);
00375       }
00376       if (tab->do_locking) {
00377          ast_rwlock_unlock(&tab->lock);
00378          ast_rwlock_destroy(&tab->lock);
00379       }
00380       free(tab);
00381    }
00382 }

void ast_hashtab_destroylock ( struct ast_hashtab tab  ) 

Call this before you destroy the table.

Definition at line 338 of file hashtab.c.

References ast_rwlock_destroy(), and ast_hashtab::lock.

00339 {
00340    ast_rwlock_destroy(&tab->lock);
00341 }

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

00252 {
00253    struct ast_hashtab *ht;
00254    unsigned int i;
00255 
00256    if (!(ht = ast_calloc(1, sizeof(*ht))))
00257       return NULL;
00258 
00259    if (!(ht->array = ast_calloc(tab->hash_tab_size, sizeof(*(ht->array))))) {
00260       free(ht);
00261       return NULL;
00262    }
00263 
00264    ht->hash_tab_size = tab->hash_tab_size;
00265    ht->compare = tab->compare;
00266    ht->resize = tab->resize;
00267    ht->newsize = tab->newsize;
00268    ht->hash = tab->hash;
00269    ht->do_locking = tab->do_locking;
00270 
00271    if (ht->do_locking)
00272       ast_rwlock_init(&ht->lock);
00273 
00274    /* now, dup the objects in the buckets and get them into the table */
00275    /* the fast way is to use the existing array index, and not have to hash
00276       the objects again */
00277    for (i = 0; i < ht->hash_tab_size; i++) {
00278       struct ast_hashtab_bucket *b = tab->array[i];
00279       while (b) {
00280          void *newobj = (*obj_dup_func)(b->object);
00281          if (newobj)
00282             ast_hashtab_insert_immediate_bucket(ht, newobj, i);
00283          b = b->next;
00284       }
00285    }
00286 
00287    return ht;
00288 }

void ast_hashtab_end_traversal ( struct ast_hashtab_iter it  ) 

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

Definition at line 648 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().

00649 {
00650    if (it->tab->do_locking)
00651       ast_rwlock_unlock(&it->tab->lock);
00652    free(it);
00653 }

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 540 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().

00541 {
00542    /* returns key stats for the table */
00543    if (tab->do_locking)
00544       ast_rwlock_rdlock(&tab->lock);
00545    *biggest_bucket_size = tab->largest_bucket_size;
00546    *resize_count = tab->resize_count;
00547    *num_objects = tab->hash_tab_elements;
00548    *num_buckets = tab->hash_tab_size;
00549    if (tab->do_locking)
00550       ast_rwlock_unlock(&tab->lock);
00551 }

unsigned int ast_hashtab_hash_int ( const int  num  ) 

Definition at line 201 of file hashtab.c.

Referenced by hashtab_hash_priority().

00202 {
00203    return x;
00204 }

unsigned int ast_hashtab_hash_short ( const short  num  ) 

Definition at line 206 of file hashtab.c.

00207 {
00208    /* hmmmm.... modulus is best < 65535 !! */
00209    return x;
00210 }

unsigned int ast_hashtab_hash_string ( const void *  obj  ) 

Hashes a string to a number.

Parameters:
obj 
Note:
A modulus is applied so it in the range 0 to mod-1

Definition at line 148 of file hashtab.c.

References str, and total.

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.

References str, and total.

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  ) 

Definition at line 166 of file hashtab.c.

References str, and total.

00167 {
00168    const unsigned char *str = obj;
00169    unsigned int total = 0, c = 0;
00170 
00171    while ((c = *str++))
00172       total ^= (total << 5) + (total >> 2) + (total << 10) + c;
00173 
00174    return total;
00175 }

void ast_hashtab_initlock ( struct ast_hashtab tab  ) 

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

Definition at line 333 of file hashtab.c.

References ast_rwlock_init(), and ast_hashtab::lock.

00334 {
00335    ast_rwlock_init(&tab->lock);
00336 }

int ast_hashtab_insert_immediate ( struct ast_hashtab tab,
const void *  obj 
)

Insert without checking.

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

Definition at line 384 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().

00385 {
00386    unsigned int h;
00387    int res=0;
00388    
00389    if (!tab || !obj)
00390       return res;
00391 
00392    if (tab->do_locking)
00393       ast_rwlock_wrlock(&tab->lock);
00394 
00395    h = (*tab->hash)(obj) % tab->hash_tab_size;
00396 
00397    res = ast_hashtab_insert_immediate_bucket(tab,obj,h);
00398 
00399    if (tab->do_locking)
00400       ast_rwlock_unlock(&tab->lock);
00401 
00402    return res;
00403 }

int ast_hashtab_insert_immediate_bucket ( struct ast_hashtab tab,
const void *  obj,
unsigned int  h 
)

Insert without checking, hashing or locking.

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

Definition at line 405 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().

00406 {
00407    int c;
00408    struct ast_hashtab_bucket *b;
00409    
00410    if (!tab || !obj)
00411       return 0;
00412    
00413    for (c = 0, b = tab->array[h]; b; b= b->next)
00414       c++;
00415 
00416    if (c + 1 > tab->largest_bucket_size)
00417       tab->largest_bucket_size = c + 1;
00418 
00419    if (!(b = ast_calloc(1, sizeof(*b))))
00420       return 0;
00421 
00422    b->object = obj;
00423    b->next = tab->array[h];
00424    tab->array[h] = b;
00425 
00426    if (b->next)
00427       b->next->prev = b;
00428 
00429    tlist_add_head(&(tab->tlist), b);
00430    tab->hash_tab_elements++;
00431 
00432    if ((*tab->resize)(tab))
00433       ast_hashtab_resize(tab);
00434 
00435    return 1;
00436 }

int ast_hashtab_insert_safe ( struct ast_hashtab tab,
const void *  obj 
)

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

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

Definition at line 438 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(), and ast_context_find_or_create().

00439 {
00440    /* check to see if the element is already there; insert only if
00441       it is not there. */
00442    /* will force a resize if the resize func returns 1 */
00443    /* returns 1 on success, 0 if there's a problem, or it's already there. */
00444    unsigned int bucket = 0;
00445 
00446    if (tab->do_locking)
00447       ast_rwlock_wrlock(&tab->lock);
00448 
00449    if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
00450       int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket);
00451 
00452       if (tab->do_locking)
00453          ast_rwlock_unlock(&tab->lock);
00454       
00455       return ret2;
00456    }
00457 
00458    if (tab->do_locking)
00459       ast_rwlock_unlock(&tab->lock);
00460       
00461    return 0;
00462 }

void* ast_hashtab_lookup ( struct ast_hashtab tab,
const void *  obj 
)

Lookup this object in the hash table.

Parameters:
tab 
obj 
Return values:
a ptr if found
NULL if not found

Definition at line 464 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(), context_merge(), find_context_locked(), new_find_extension(), and pbx_find_extension().

00465 {
00466    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00467    unsigned int h;
00468    void *ret;
00469 
00470    if (!tab || !obj)
00471       return 0;
00472    
00473    if (tab->do_locking)
00474       ast_rwlock_rdlock(&tab->lock);
00475 
00476    h = (*tab->hash)(obj) % tab->hash_tab_size;
00477 
00478    ret = ast_hashtab_lookup_internal(tab,obj,h);
00479 
00480    if (tab->do_locking)
00481       ast_rwlock_unlock(&tab->lock);
00482 
00483    return ret;
00484 }

void* ast_hashtab_lookup_bucket ( struct ast_hashtab tab,
const void *  obj,
unsigned int *  h 
)

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

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

Definition at line 509 of file hashtab.c.

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

Referenced by ast_hashtab_insert_safe().

00510 {
00511    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00512    unsigned int h;
00513    void *ret;
00514 
00515    if (!tab || !obj)
00516       return 0;
00517    
00518    h = (*tab->hash)(obj) % tab->hash_tab_size;
00519    
00520    ret = ast_hashtab_lookup_internal(tab,obj,h);
00521    
00522    *bucket = h; 
00523    
00524    return ret;
00525 }

void* ast_hashtab_lookup_with_hash ( struct ast_hashtab tab,
const void *  obj,
unsigned int  hashval 
)

Use this if have the hash val for the object.

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

Definition at line 487 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.

00488 {
00489    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00490    unsigned int h;
00491    void *ret;
00492 
00493    if (!tab || !obj)
00494       return 0;
00495    
00496    if (tab->do_locking)
00497       ast_rwlock_rdlock(&tab->lock);
00498       
00499    h = hashval % tab->hash_tab_size;
00500 
00501    ret = ast_hashtab_lookup_internal(tab,obj,h);
00502    
00503    if (tab->do_locking)
00504       ast_rwlock_unlock(&tab->lock);
00505 
00506    return ret;
00507 }

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(), and pbx_load_module().

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 655 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().

00656 {
00657    /* returns the next object in the list, advances iter one step */
00658    struct ast_hashtab_bucket *retval;
00659    
00660    if (it && it->next) { /* there's a next in the bucket list */
00661       retval = it->next;
00662       it->next = retval->tnext;
00663       return (void *) retval->object;
00664    }
00665 
00666    return NULL;
00667 }

void ast_hashtab_rdlock ( struct ast_hashtab tab  ) 

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

Definition at line 328 of file hashtab.c.

References ast_rwlock_rdlock(), and ast_hashtab::lock.

00329 {
00330    ast_rwlock_rdlock(&tab->lock);
00331 }

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

Looks up the object, removes the corresponding bucket.

Definition at line 718 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.

00719 {
00720    /* looks up the object; removes the corresponding bucket */
00721    const void *obj2;
00722 
00723    if (!tab || !obj)
00724       return 0;
00725 
00726    if (tab->do_locking)
00727       ast_rwlock_wrlock(&tab->lock);
00728 
00729    obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj);
00730 
00731    if (tab->do_locking)
00732       ast_rwlock_unlock(&tab->lock);
00733 
00734    return (void *)obj2;
00735 }

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 737 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().

00738 {
00739    /* looks up the object; removes the corresponding bucket */
00740    unsigned int h;
00741    struct ast_hashtab_bucket *b;
00742 
00743    if (!tab || !obj)
00744       return 0;
00745 
00746    h = (*tab->hash)(obj) % tab->hash_tab_size;
00747    for (b = tab->array[h]; b; b = b->next) {
00748       
00749       if (!(*tab->compare)(obj, b->object)) {
00750          const void *obj2;
00751 
00752          obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00753          
00754          return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00755       }
00756    }
00757 
00758    return 0;
00759 }

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 761 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(), and ast_context_remove_extension_callerid2().

00762 {
00763    /* looks up the object by hash and then comparing pts in bucket list instead of
00764       calling the compare routine; removes the bucket -- a slightly cheaper operation */
00765    /* looks up the object; removes the corresponding bucket */
00766    const void *obj2;
00767 
00768    if (!tab || !obj)
00769       return 0;
00770  
00771    if (tab->do_locking)
00772       ast_rwlock_wrlock(&tab->lock);
00773 
00774    obj2 = ast_hashtab_remove_this_object_nolock(tab,obj);
00775    
00776    if (tab->do_locking)
00777       ast_rwlock_unlock(&tab->lock);
00778 
00779    return (void *)obj2;
00780 }

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 782 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().

00783 {
00784    /* looks up the object by hash and then comparing pts in bucket list instead of
00785       calling the compare routine; removes the bucket -- a slightly cheaper operation */
00786    /* looks up the object; removes the corresponding bucket */
00787    unsigned int h;
00788    struct ast_hashtab_bucket *b;
00789 
00790    if (!tab || !obj)
00791       return 0;
00792  
00793    h = (*tab->hash)(obj) % tab->hash_tab_size;
00794    for (b = tab->array[h]; b; b = b->next) {
00795       
00796       if (obj == b->object) {
00797          const void *obj2;
00798          obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00799          
00800          return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00801       }
00802    }
00803 
00804    return 0;
00805 }

int ast_hashtab_resize_java ( struct ast_hashtab tab  ) 

determine if resize should occur

Returns:
1 if the table is 75% full or more

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(), and pbx_load_module().

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  ) 

no resizing; always return 0

Definition at line 90 of file hashtab.c.

00091 {
00092    return 0;
00093 }

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 554 of file hashtab.c.

References ast_hashtab::hash_tab_elements.

Referenced by ast_context_remove_extension_callerid2().

00555 {
00556    return tab->hash_tab_elements;
00557 }

struct ast_hashtab_iter* ast_hashtab_start_traversal ( struct ast_hashtab tab  ) 

Gives an iterator to hastable.

Definition at line 615 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().

00616 {
00617    /* returns an iterator */
00618    struct ast_hashtab_iter *it;
00619    
00620    if (!(it = ast_calloc(1, sizeof(*it))))
00621       return NULL;
00622 
00623    it->next = tab->tlist;
00624    it->tab = tab;
00625    if (tab->do_locking)
00626       ast_rwlock_rdlock(&tab->lock);
00627 
00628    return it;
00629 }

struct ast_hashtab_iter* ast_hashtab_start_write_traversal ( struct ast_hashtab tab  ) 

Gives an iterator to hastable.

Definition at line 632 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.

00633 {
00634    /* returns an iterator */
00635    struct ast_hashtab_iter *it;
00636    
00637    if (!(it = ast_calloc(1, sizeof(*it))))
00638       return NULL;
00639 
00640    it->next = tab->tlist;
00641    it->tab = tab;
00642    if (tab->do_locking)
00643       ast_rwlock_wrlock(&tab->lock);
00644 
00645    return it;
00646 }

void ast_hashtab_unlock ( struct ast_hashtab tab  ) 

release a read- or write- lock.

Definition at line 343 of file hashtab.c.

References ast_rwlock_unlock(), and ast_hashtab::lock.

00344 {
00345    ast_rwlock_unlock(&tab->lock);
00346 }

void ast_hashtab_wrlock ( struct ast_hashtab tab  ) 

Request a write-lock on the table.

Definition at line 323 of file hashtab.c.

References ast_rwlock_wrlock(), and ast_hashtab::lock.

00324 {
00325    ast_rwlock_wrlock(&tab->lock);
00326 }

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 }


Generated on Thu Jul 9 13:41:20 2009 for Asterisk - the Open Source PBX by  doxygen 1.4.7