Thu Oct 11 06:49:09 2012

Asterisk developer's documentation


hashtab.h File Reference

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

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  ast_hashtab
struct  ast_hashtab_bucket
struct  ast_hashtab_iter
 an iterator for traversing the buckets More...

Defines

#define __USE_UNIX98   1

Functions

int ast_hashtab_capacity (struct ast_hashtab *tab)
 Returns the size of the bucket array in the hashtab.
int ast_hashtab_compare_ints (const void *a, const void *b)
 Compares two integers for equality.
int ast_hashtab_compare_shorts (const void *a, const void *b)
 Compares two shorts for equality.
int ast_hashtab_compare_strings (const void *a, const void *b)
 Compares two strings for equality.
int ast_hashtab_compare_strings_nocase (const void *a, const void *b)
 Compares two strings for equality, ignoring case.
struct ast_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.
struct 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)
 Hashes a string to a number ignoring case.
unsigned int ast_hashtab_hash_string_sax (const void *obj)
 Hashes a string to a number using a modified Shift-And-XOR algorithm.
void ast_hashtab_initlock (struct ast_hashtab *tab)
 Call this after you create the table to init the lock.
int ast_hashtab_insert_immediate (struct ast_hashtab *tab, const void *obj)
 Insert without checking.
int ast_hashtab_insert_immediate_bucket (struct ast_hashtab *tab, const void *obj, unsigned int h)
 Insert without checking, hashing or locking.
int ast_hashtab_insert_safe (struct ast_hashtab *tab, const void *obj)
 Check and insert new object only if it is not there.
void * ast_hashtab_lookup (struct ast_hashtab *tab, const void *obj)
 Lookup this object in the hash table.
void * ast_hashtab_lookup_bucket (struct ast_hashtab *tab, const void *obj, unsigned int *h)
 Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.
void * ast_hashtab_lookup_with_hash (struct ast_hashtab *tab, const void *obj, unsigned int hashval)
 Use this if have the hash val for the object.
int ast_hashtab_newsize_java (struct ast_hashtab *tab)
 Create a prime number roughly 2x the current table size.
int ast_hashtab_newsize_none (struct ast_hashtab *tab)
 always return current size -- no resizing
int ast_hashtab_newsize_tight (struct ast_hashtab *tab)
void * ast_hashtab_next (struct ast_hashtab_iter *it)
 Gets the next object in the list, advances iter one step returns null on end of traversal.
void ast_hashtab_rdlock (struct ast_hashtab *tab)
 Request a read-lock on the table -- don't change anything!
void * ast_hashtab_remove_object_via_lookup (struct ast_hashtab *tab, void *obj)
 Looks up the object, removes the corresponding bucket.
void * ast_hashtab_remove_object_via_lookup_nolock (struct ast_hashtab *tab, void *obj)
 Looks up the object, removes the corresponding bucket.
void * ast_hashtab_remove_this_object (struct ast_hashtab *tab, void *obj)
 Hash the object and then compare ptrs in bucket list instead of calling the compare routine, will remove the bucket.
void * ast_hashtab_remove_this_object_nolock (struct ast_hashtab *tab, void *obj)
 Hash the object and then compare ptrs in bucket list instead of calling the compare routine, will remove the bucket.
int ast_hashtab_resize_java (struct ast_hashtab *tab)
 Determines if a table resize should occur using the Java algorithm (if the table load factor is 75% or higher).
int ast_hashtab_resize_none (struct ast_hashtab *tab)
 Effectively disables resizing by always returning 0, regardless of of load factor.
int ast_hashtab_resize_tight (struct ast_hashtab *tab)
 Causes a resize whenever the number of elements stored in the table exceeds the number of buckets in the table.
int ast_hashtab_size (struct ast_hashtab *tab)
 Returns the number of elements stored in the hashtab.
struct ast_hashtab_iterast_hashtab_start_traversal (struct ast_hashtab *tab)
 Gives an iterator to hastable.
struct 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)
 Determines if the specified number is prime.


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

References ast_hashtab::hash_tab_size.

00628 {
00629    return tab->hash_tab_size;
00630 }

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

Compares two integers for equality.

Parameters:
a an integer pointer (int *)
b an integer pointer (int *)
Return values:
0 if the integers pointed to are equal
1 if a is greater than b
-1 if a is less than b

Definition at line 62 of file hashtab.c.

00063 {
00064    int ai = *((int *) a);
00065    int bi = *((int *) b);
00066 
00067    if (ai < bi)
00068       return -1;
00069 
00070    return !(ai == bi);
00071 }

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

Compares two shorts for equality.

Parameters:
a a short pointer (short *)
b a short pointer (short *)
Return values:
0 if the shorts pointed to are equal
1 if a is greater than b
-1 if a is less than b

Definition at line 73 of file hashtab.c.

00074 {
00075    short as = *((short *) a);
00076    short bs = *((short *) b);
00077 
00078    if (as < bs)
00079       return -1;
00080 
00081    return !(as == bs);
00082 }

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

Compares two strings for equality.

Parameters:
a a character string
b a character string
Return values:
0 if the strings match
<0 if string a is less than string b
>0 if string a is greather than string b

Definition at line 52 of file hashtab.c.

00053 {
00054    return strcmp(a, b);
00055 }

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

Compares two strings for equality, ignoring case.

Parameters:
a a character string
b a character string
Return values:
0 if the strings match
<0 if string a is less than string b
>0 if string a is greather than string b

Definition at line 57 of file hashtab.c.

00058 {
00059    return strcasecmp(a, b);
00060 }

struct ast_hashtab* ast_hashtab_create ( int  initial_buckets,
int(*)(const void *a, const void *b)  compare,
int(*)(struct ast_hashtab *)  resize,
int(*)(struct ast_hashtab *tab)  newsize,
unsigned int(*)(const void *obj)  hash,
int  do_locking 
) [read]

Create the hashtable list.

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

References __ast_calloc(), ast_hashtab::array, ast_calloc, ast_hashtab_newsize_java(), ast_hashtab_resize_java(), ast_is_prime(), ast_rwlock_init(), compare(), ast_hashtab::compare, ast_hashtab::do_locking, free, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab::newsize, and ast_hashtab::resize.

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

00232 {
00233    struct ast_hashtab *ht;
00234 
00235 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00236    if (!(ht = __ast_calloc(1, sizeof(*ht), file, lineno, function)))
00237 #else
00238    if (!(ht = ast_calloc(1, sizeof(*ht))))
00239 #endif
00240       return NULL;
00241 
00242    while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
00243       initial_buckets++;
00244 
00245 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00246    if (!(ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)), file, lineno, function))) {
00247 #else
00248    if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) {
00249 #endif
00250       free(ht);
00251       return NULL;
00252    }
00253 
00254    ht->hash_tab_size = initial_buckets;
00255    ht->compare = compare;
00256    ht->resize = resize;
00257    ht->newsize = newsize;
00258    ht->hash = hash;
00259    ht->do_locking = do_locking;
00260 
00261    if (do_locking)
00262       ast_rwlock_init(&ht->lock);
00263 
00264    if (!ht->resize)
00265       ht->resize = ast_hashtab_resize_java;
00266 
00267    if (!ht->newsize)
00268       ht->newsize = ast_hashtab_newsize_java;
00269 
00270    return ht;
00271 }

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

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

Referenced by __ast_internal_context_destroy(), ast_merge_contexts_and_delete(), destroy_exten(), and sched_context_destroy().

00385 {
00386    /* this func will free the hash table and all its memory. It
00387       doesn't touch the objects stored in it */
00388    if (tab) {
00389 
00390       if (tab->do_locking)
00391          ast_rwlock_wrlock(&tab->lock);
00392 
00393       if (tab->array) {
00394          /* go thru and destroy the buckets */
00395          struct ast_hashtab_bucket *t;
00396          int i;
00397 
00398          while (tab->tlist) {
00399             t = tab->tlist;
00400             if (t->object && objdestroyfunc) {
00401                /* I cast this because I'm not going to MOD it, I'm going to DESTROY
00402                 * it.
00403                 */
00404                (*objdestroyfunc)((void *) t->object);
00405             }
00406 
00407             tlist_del_item(&(tab->tlist), tab->tlist);
00408             free(t);
00409          }
00410 
00411          for (i = 0; i < tab->hash_tab_size; i++) {
00412             /* Not totally necessary, but best to destroy old pointers */
00413             tab->array[i] = NULL;
00414          }
00415          free(tab->array);
00416       }
00417       if (tab->do_locking) {
00418          ast_rwlock_unlock(&tab->lock);
00419          ast_rwlock_destroy(&tab->lock);
00420       }
00421       free(tab);
00422    }
00423 }

void ast_hashtab_destroylock ( struct ast_hashtab tab  ) 

Call this before you destroy the table.

Definition at line 374 of file hashtab.c.

References ast_rwlock_destroy(), and ast_hashtab::lock.

00375 {
00376    ast_rwlock_destroy(&tab->lock);
00377 }

struct ast_hashtab* ast_hashtab_dup ( struct ast_hashtab tab,
void *(*)(const void *obj)  obj_dup_func 
) [read]

Return a copy of the hash table.

Definition at line 276 of file hashtab.c.

References __ast_calloc(), ast_hashtab::array, ast_calloc, ast_hashtab_insert_immediate_bucket(), ast_rwlock_init(), ast_hashtab::compare, ast_hashtab::do_locking, free, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab::newsize, ast_hashtab_bucket::next, ast_hashtab_bucket::object, and ast_hashtab::resize.

00278 {
00279    struct ast_hashtab *ht;
00280    unsigned int i;
00281 
00282    if (!(ht = ast_calloc(1, sizeof(*ht))))
00283       return NULL;
00284 
00285    if (!(ht->array =
00286 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00287       __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)), file, lineno, func)
00288 #else
00289       ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)))
00290 #endif
00291       )) {
00292       free(ht);
00293       return NULL;
00294    }
00295 
00296    ht->hash_tab_size = tab->hash_tab_size;
00297    ht->compare = tab->compare;
00298    ht->resize = tab->resize;
00299    ht->newsize = tab->newsize;
00300    ht->hash = tab->hash;
00301    ht->do_locking = tab->do_locking;
00302 
00303    if (ht->do_locking)
00304       ast_rwlock_init(&ht->lock);
00305 
00306    /* now, dup the objects in the buckets and get them into the table */
00307    /* the fast way is to use the existing array index, and not have to hash
00308       the objects again */
00309    for (i = 0; i < ht->hash_tab_size; i++) {
00310       struct ast_hashtab_bucket *b = tab->array[i];
00311       while (b) {
00312          void *newobj = (*obj_dup_func)(b->object);
00313          if (newobj)
00314 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00315             _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func);
00316 #else
00317             ast_hashtab_insert_immediate_bucket(ht, newobj, i);
00318 #endif
00319          b = b->next;
00320       }
00321    }
00322 
00323    return ht;
00324 }

void ast_hashtab_end_traversal ( struct ast_hashtab_iter it  ) 

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

Definition at line 742 of file hashtab.c.

References ast_rwlock_unlock(), ast_hashtab::do_locking, free, ast_hashtab::lock, and ast_hashtab_iter::tab.

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

00743 {
00744    if (it->tab->do_locking)
00745       ast_rwlock_unlock(&it->tab->lock);
00746    free(it);
00747 }

void ast_hashtab_get_stats ( struct ast_hashtab tab,
int *  biggest_bucket_size,
int *  resize_count,
int *  num_objects,
int *  num_buckets 
)

Returns key stats for the table.

Definition at line 607 of file hashtab.c.

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

Referenced by create_match_char_tree().

00608 {
00609    /* returns key stats for the table */
00610    if (tab->do_locking)
00611       ast_rwlock_rdlock(&tab->lock);
00612    *biggest_bucket_size = tab->largest_bucket_size;
00613    *resize_count = tab->resize_count;
00614    *num_objects = tab->hash_tab_elements;
00615    *num_buckets = tab->hash_tab_size;
00616    if (tab->do_locking)
00617       ast_rwlock_unlock(&tab->lock);
00618 }

unsigned int ast_hashtab_hash_int ( const int  num  ) 

Definition at line 205 of file hashtab.c.

Referenced by hashtab_hash_priority().

00206 {
00207    return x;
00208 }

unsigned int ast_hashtab_hash_short ( const short  num  ) 

Definition at line 210 of file hashtab.c.

00211 {
00212    /* hmmmm.... modulus is best < 65535 !! */
00213    return x;
00214 }

unsigned int ast_hashtab_hash_string ( const void *  obj  ) 

Hashes a string to a number.

Parameters:
obj the string to hash
Returns:
Integer hash of the specified string
See also:
ast_hashtable_hash_string_nocase

ast_hashtab_hash_string_sax

Note:
A modulus will be applied to the return value of this function

Definition at line 153 of file hashtab.c.

References str, and total.

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

00154 {
00155    unsigned char *str = (unsigned char *) obj;
00156    unsigned int total;
00157 
00158    for (total = 0; *str; str++) {
00159       unsigned int tmp = total;
00160       total <<= 1; /* multiply by 2 */
00161       total += tmp; /* multiply by 3 */
00162       total <<= 2; /* multiply by 12 */
00163       total += tmp; /* multiply by 13 */
00164 
00165       total += ((unsigned int)(*str));
00166    }
00167    return total;
00168 }

unsigned int ast_hashtab_hash_string_nocase ( const void *  obj  ) 

Hashes a string to a number ignoring case.

Parameters:
obj the string to hash
Returns:
Integer hash of the specified string
See also:
ast_hashtable_hash_string

ast_hashtab_hash_string_sax

Note:
A modulus will be applied to the return value of this function

Definition at line 181 of file hashtab.c.

References str, and total.

00182 {
00183    const unsigned char *str = obj;
00184    unsigned int total;
00185 
00186    for (total = 0; *str; str++) {
00187       unsigned int tmp = total;
00188       unsigned int charval = toupper(*str);
00189 
00190       /* hopefully, the following is faster than multiplication by 7 */
00191       /* why do I go to this bother? A good compiler will do this
00192          anyway, if I say total *= 13 */
00193       /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */
00194       total <<= 1; /* multiply by 2 */
00195       total += tmp; /* multiply by 3 */
00196       total <<= 2; /* multiply by 12 */
00197       total += tmp; /* multiply by 13 */
00198 
00199       total += (charval);
00200    }
00201 
00202    return total;
00203 }

unsigned int ast_hashtab_hash_string_sax ( const void *  obj  ) 

Hashes a string to a number using a modified Shift-And-XOR algorithm.

Parameters:
obj the string to hash
Returns:
Integer has of the specified string
See also:
ast_hastable_hash_string

ast_hastable_hash_string_nocase

Definition at line 170 of file hashtab.c.

References str, and total.

00171 {
00172    const unsigned char *str = obj;
00173    unsigned int total = 0, c = 0;
00174 
00175    while ((c = *str++))
00176       total ^= (total << 5) + (total >> 2) + (total << 10) + c;
00177 
00178    return total;
00179 }

void ast_hashtab_initlock ( struct ast_hashtab tab  ) 

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

Definition at line 369 of file hashtab.c.

References ast_rwlock_init(), and ast_hashtab::lock.

00370 {
00371    ast_rwlock_init(&tab->lock);
00372 }

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

References ast_hashtab_insert_immediate_bucket(), ast_rwlock_unlock(), ast_rwlock_wrlock(), ast_hashtab::do_locking, ast_hashtab::hash, ast_hashtab::hash_tab_size, and ast_hashtab::lock.

Referenced by ast_context_find_or_create(), and ast_context_remove_extension_callerid2().

00430 {
00431    unsigned int h;
00432    int res=0;
00433 
00434    if (!tab || !obj)
00435       return res;
00436 
00437    if (tab->do_locking)
00438       ast_rwlock_wrlock(&tab->lock);
00439 
00440    h = (*tab->hash)(obj) % tab->hash_tab_size;
00441 
00442 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00443    res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func);
00444 #else
00445    res = ast_hashtab_insert_immediate_bucket(tab, obj, h);
00446 #endif
00447 
00448    if (tab->do_locking)
00449       ast_rwlock_unlock(&tab->lock);
00450 
00451    return res;
00452 }

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

References __ast_calloc(), ast_hashtab::array, ast_calloc, ast_hashtab_resize(), ast_hashtab::hash_tab_elements, ast_hashtab::largest_bucket_size, ast_hashtab_bucket::next, ast_hashtab_bucket::object, ast_hashtab_bucket::prev, ast_hashtab::resize, ast_hashtab::tlist, and tlist_add_head().

Referenced by ast_hashtab_dup(), ast_hashtab_insert_immediate(), and ast_hashtab_insert_safe().

00459 {
00460    int c;
00461    struct ast_hashtab_bucket *b;
00462 
00463    if (!tab || !obj)
00464       return 0;
00465 
00466    for (c = 0, b = tab->array[h]; b; b= b->next)
00467       c++;
00468 
00469    if (c + 1 > tab->largest_bucket_size)
00470       tab->largest_bucket_size = c + 1;
00471 
00472    if (!(b =
00473 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00474          __ast_calloc(1, sizeof(*b), file, lineno, func)
00475 #else
00476          ast_calloc(1, sizeof(*b))
00477 #endif
00478       )) return 0;
00479 
00480    b->object = obj;
00481    b->next = tab->array[h];
00482    tab->array[h] = b;
00483 
00484    if (b->next)
00485       b->next->prev = b;
00486 
00487    tlist_add_head(&(tab->tlist), b);
00488    tab->hash_tab_elements++;
00489 
00490    if ((*tab->resize)(tab))
00491       ast_hashtab_resize(tab);
00492 
00493    return 1;
00494 }

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

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

Referenced by add_pri_lockopt(), ast_add_extension2_lockopt(), ast_context_find_or_create(), and schedule().

00501 {
00502    /* check to see if the element is already there; insert only if
00503       it is not there. */
00504    /* will force a resize if the resize func returns 1 */
00505    /* returns 1 on success, 0 if there's a problem, or it's already there. */
00506    unsigned int bucket = 0;
00507 
00508    if (tab->do_locking)
00509       ast_rwlock_wrlock(&tab->lock);
00510 
00511    if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
00512 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00513       int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func);
00514 #else
00515       int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket);
00516 #endif
00517 
00518       if (tab->do_locking)
00519          ast_rwlock_unlock(&tab->lock);
00520 
00521       return ret2;
00522    }
00523 
00524    if (tab->do_locking)
00525       ast_rwlock_unlock(&tab->lock);
00526 
00527    return 0;
00528 }

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

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

Referenced by ast_add_extension2_lockopt(), ast_context_find(), ast_context_find_or_create(), ast_context_lockmacro(), ast_context_remove_extension_callerid2(), ast_context_unlockmacro(), ast_sched_del(), ast_sched_find_data(), ast_sched_when(), context_merge(), find_context(), find_context_locked(), and pbx_find_extension().

00531 {
00532    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00533    unsigned int h;
00534    void *ret;
00535 
00536    if (!tab || !obj)
00537       return 0;
00538 
00539    if (tab->do_locking)
00540       ast_rwlock_rdlock(&tab->lock);
00541 
00542    h = (*tab->hash)(obj) % tab->hash_tab_size;
00543 
00544    ret = ast_hashtab_lookup_internal(tab,obj,h);
00545 
00546    if (tab->do_locking)
00547       ast_rwlock_unlock(&tab->lock);
00548 
00549    return ret;
00550 }

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

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

Referenced by ast_hashtab_insert_safe().

00576 {
00577    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00578    unsigned int h;
00579    void *ret;
00580 
00581    if (!tab || !obj)
00582       return 0;
00583 
00584    h = (*tab->hash)(obj) % tab->hash_tab_size;
00585 
00586    ret = ast_hashtab_lookup_internal(tab,obj,h);
00587 
00588    *bucket = h;
00589 
00590    return ret;
00591 }

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

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

00554 {
00555    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00556    unsigned int h;
00557    void *ret;
00558 
00559    if (!tab || !obj)
00560       return 0;
00561 
00562    if (tab->do_locking)
00563       ast_rwlock_rdlock(&tab->lock);
00564 
00565    h = hashval % tab->hash_tab_size;
00566 
00567    ret = ast_hashtab_lookup_internal(tab,obj,h);
00568 
00569    if (tab->do_locking)
00570       ast_rwlock_unlock(&tab->lock);
00571 
00572    return ret;
00573 }

int ast_hashtab_newsize_java ( struct ast_hashtab tab  ) 

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

Definition at line 127 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

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

00128 {
00129    int i = (tab->hash_tab_size << 1); /* multiply by two */
00130 
00131    while (!ast_is_prime(i))
00132       i++;
00133 
00134    return i;
00135 }

int ast_hashtab_newsize_none ( struct ast_hashtab tab  ) 

always return current size -- no resizing

Definition at line 148 of file hashtab.c.

References ast_hashtab::hash_tab_size.

00149 {
00150    return tab->hash_tab_size;
00151 }

int ast_hashtab_newsize_tight ( struct ast_hashtab tab  ) 

Definition at line 137 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

00138 {
00139    int x = (tab->hash_tab_size << 1);
00140    int i = (tab->hash_tab_size + x);
00141 
00142    while (!ast_is_prime(i))
00143       i++;
00144 
00145    return i;
00146 }

void* ast_hashtab_next ( struct ast_hashtab_iter it  ) 

Gets the next object in the list, advances iter one step returns null on end of traversal.

Definition at line 749 of file hashtab.c.

References ast_hashtab_iter::next, ast_hashtab_bucket::object, and ast_hashtab_bucket::tnext.

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

00750 {
00751    /* returns the next object in the list, advances iter one step */
00752    struct ast_hashtab_bucket *retval;
00753 
00754    if (it && it->next) { /* there's a next in the bucket list */
00755       retval = it->next;
00756       it->next = retval->tnext;
00757       return (void *) retval->object;
00758    }
00759 
00760    return NULL;
00761 }

void ast_hashtab_rdlock ( struct ast_hashtab tab  ) 

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

Definition at line 364 of file hashtab.c.

References ast_rwlock_rdlock(), and ast_hashtab::lock.

00365 {
00366    ast_rwlock_rdlock(&tab->lock);
00367 }

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

Looks up the object, removes the corresponding bucket.

Definition at line 812 of file hashtab.c.

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

Referenced by add_pri_lockopt().

00813 {
00814    /* looks up the object; removes the corresponding bucket */
00815    const void *obj2;
00816 
00817    if (!tab || !obj)
00818       return 0;
00819 
00820    if (tab->do_locking)
00821       ast_rwlock_wrlock(&tab->lock);
00822 
00823    obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj);
00824 
00825    if (tab->do_locking)
00826       ast_rwlock_unlock(&tab->lock);
00827 
00828    return (void *)obj2;
00829 }

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

Looks up the object, removes the corresponding bucket.

Definition at line 831 of file hashtab.c.

References ast_hashtab::array, ast_hashtab_remove_object_internal(), ast_hashtab::compare, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab_bucket::next, and ast_hashtab_bucket::object.

Referenced by ast_hashtab_remove_object_via_lookup().

00832 {
00833    /* looks up the object; removes the corresponding bucket */
00834    unsigned int h;
00835    struct ast_hashtab_bucket *b;
00836 
00837    if (!tab || !obj)
00838       return 0;
00839 
00840    h = (*tab->hash)(obj) % tab->hash_tab_size;
00841    for (b = tab->array[h]; b; b = b->next) {
00842 
00843       if (!(*tab->compare)(obj, b->object)) {
00844          const void *obj2;
00845 
00846          obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00847 
00848          return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00849       }
00850    }
00851 
00852    return 0;
00853 }

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

Hash the object and then compare ptrs in bucket list instead of calling the compare routine, will remove the bucket.

Definition at line 855 of file hashtab.c.

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

Referenced by __ast_context_destroy(), ast_context_remove_extension_callerid2(), ast_sched_del(), and ast_sched_runq().

00856 {
00857    /* looks up the object by hash and then comparing pts in bucket list instead of
00858       calling the compare routine; removes the bucket -- a slightly cheaper operation */
00859    /* looks up the object; removes the corresponding bucket */
00860    const void *obj2;
00861 
00862    if (!tab || !obj)
00863       return 0;
00864 
00865    if (tab->do_locking)
00866       ast_rwlock_wrlock(&tab->lock);
00867 
00868    obj2 = ast_hashtab_remove_this_object_nolock(tab,obj);
00869 
00870    if (tab->do_locking)
00871       ast_rwlock_unlock(&tab->lock);
00872 
00873    return (void *)obj2;
00874 }

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

Hash the object and then compare ptrs in bucket list instead of calling the compare routine, will remove the bucket.

Definition at line 876 of file hashtab.c.

References ast_hashtab::array, ast_hashtab_remove_object_internal(), ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab_bucket::next, and ast_hashtab_bucket::object.

Referenced by ast_hashtab_remove_this_object().

00877 {
00878    /* looks up the object by hash and then comparing pts in bucket list instead of
00879       calling the compare routine; removes the bucket -- a slightly cheaper operation */
00880    /* looks up the object; removes the corresponding bucket */
00881    unsigned int h;
00882    struct ast_hashtab_bucket *b;
00883 
00884    if (!tab || !obj)
00885       return 0;
00886 
00887    h = (*tab->hash)(obj) % tab->hash_tab_size;
00888    for (b = tab->array[h]; b; b = b->next) {
00889 
00890       if (obj == b->object) {
00891          const void *obj2;
00892          obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00893 
00894          return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00895       }
00896    }
00897 
00898    return 0;
00899 }

int ast_hashtab_resize_java ( struct ast_hashtab tab  ) 

Determines if a table resize should occur using the Java algorithm (if the table load factor is 75% or higher).

Parameters:
tab the hash table to operate on
Return values:
0 if the table load factor is less than or equal to 75%
1 if the table load factor is greater than 75%

Definition at line 84 of file hashtab.c.

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

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

00085 {
00086    double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
00087 
00088    return (loadfactor > 0.75);
00089 }

int ast_hashtab_resize_none ( struct ast_hashtab tab  ) 

Effectively disables resizing by always returning 0, regardless of of load factor.

Parameters:
tab the hash table to operate on
Returns:
0 is always returned

Definition at line 96 of file hashtab.c.

00097 {
00098    return 0;
00099 }

int ast_hashtab_resize_tight ( struct ast_hashtab tab  ) 

Causes a resize whenever the number of elements stored in the table exceeds the number of buckets in the table.

Parameters:
tab the hash table to operate on
Return values:
0 if the number of elements in the table is less than or equal to the number of buckets
1 if the number of elements in the table exceeds the number of buckets

Definition at line 91 of file hashtab.c.

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

00092 {
00093    return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
00094 }

int ast_hashtab_size ( struct ast_hashtab tab  ) 

Returns the number of elements stored in the hashtab.

Definition at line 621 of file hashtab.c.

References ast_hashtab::hash_tab_elements.

Referenced by ast_context_remove_extension_callerid2().

00622 {
00623    return tab->hash_tab_elements;
00624 }

struct ast_hashtab_iter* ast_hashtab_start_traversal ( struct ast_hashtab tab  )  [read]

Gives an iterator to hastable.

Definition at line 692 of file hashtab.c.

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

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

00694 {
00695    /* returns an iterator */
00696    struct ast_hashtab_iter *it;
00697 
00698    if (!(it =
00699 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00700          __ast_calloc(1, sizeof(*it), file, lineno, func)
00701 #else
00702          ast_calloc(1, sizeof(*it))
00703 #endif
00704       ))
00705       return NULL;
00706 
00707    it->next = tab->tlist;
00708    it->tab = tab;
00709    if (tab->do_locking)
00710       ast_rwlock_rdlock(&tab->lock);
00711 
00712    return it;
00713 }

struct ast_hashtab_iter* ast_hashtab_start_write_traversal ( struct ast_hashtab tab  )  [read]

Gives an iterator to hastable.

Definition at line 719 of file hashtab.c.

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

00721 {
00722    /* returns an iterator */
00723    struct ast_hashtab_iter *it;
00724 
00725    if (!(it =
00726 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00727          __ast_calloc(1, sizeof(*it), file, lineno, func)
00728 #else
00729          ast_calloc(1, sizeof(*it))
00730 #endif
00731       ))
00732       return NULL;
00733 
00734    it->next = tab->tlist;
00735    it->tab = tab;
00736    if (tab->do_locking)
00737       ast_rwlock_wrlock(&tab->lock);
00738 
00739    return it;
00740 }

void ast_hashtab_unlock ( struct ast_hashtab tab  ) 

release a read- or write- lock.

Definition at line 379 of file hashtab.c.

References ast_rwlock_unlock(), and ast_hashtab::lock.

00380 {
00381    ast_rwlock_unlock(&tab->lock);
00382 }

void ast_hashtab_wrlock ( struct ast_hashtab tab  ) 

Request a write-lock on the table.

Definition at line 359 of file hashtab.c.

References ast_rwlock_wrlock(), and ast_hashtab::lock.

00360 {
00361    ast_rwlock_wrlock(&tab->lock);
00362 }

int ast_is_prime ( int  num  ) 

Determines if the specified number is prime.

Parameters:
num the number to test
Return values:
0 if the number is not prime
1 if the number is prime

Definition at line 101 of file hashtab.c.

Referenced by ast_hashtab_create(), ast_hashtab_newsize_java(), and ast_hashtab_newsize_tight().

00102 {
00103    int tnum, limit;
00104 
00105    if (!(num & 0x1)) /* even number -- not prime */
00106       return 0;
00107 
00108    /* Loop through ODD numbers starting with 3 */
00109 
00110    tnum = 3;
00111    limit = num;
00112    while (tnum < limit) {
00113       if (!(num % tnum))
00114          return 0;
00115 
00116       /* really, we only need to check sqrt(num) numbers */
00117       limit = num / tnum;
00118 
00119       /* we only check odd numbers */
00120       tnum = tnum + 2;
00121    }
00122 
00123    /* if we made it through the loop, the number is a prime */
00124    return 1;
00125 }


Generated on Thu Oct 11 06:49:09 2012 for Asterisk - the Open Source PBX by  doxygen 1.5.6