Mon Oct 8 12:39:23 2012

Asterisk developer's documentation


hashtab.c File Reference

code to implement generic hash tables More...

#include "asterisk.h"
#include <ctype.h>
#include "asterisk/lock.h"
#include "asterisk/frame.h"
#include "asterisk/channel.h"
#include "asterisk/cli.h"
#include "asterisk/term.h"
#include "asterisk/utils.h"
#include "asterisk/threadstorage.h"
#include "asterisk/linkedlists.h"
#include "asterisk/hashtab.h"

Go to the source code of this file.

Functions

int ast_hashtab_capacity (struct ast_hashtab *tab)
 Returns the size of the bucket array in the hashtab.
int ast_hashtab_compare_ints (const void *a, const void *b)
 Compares two integers for equality.
int ast_hashtab_compare_shorts (const void *a, const void *b)
 Compares two shorts for equality.
int ast_hashtab_compare_strings (const void *a, const void *b)
 Compares two strings for equality.
int ast_hashtab_compare_strings_nocase (const void *a, const void *b)
 Compares two strings for equality, ignoring case.
ast_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 x)
unsigned int ast_hashtab_hash_short (const short x)
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 *bucket)
 Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.
static void * ast_hashtab_lookup_internal (struct ast_hashtab *tab, const void *obj, unsigned int h)
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!
static void * ast_hashtab_remove_object_internal (struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
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.
static void ast_hashtab_resize (struct ast_hashtab *tab)
int ast_hashtab_resize_java (struct ast_hashtab *tab)
 Determines if a table resize should occur using the Java algorithm (if the table load factor is 75% or higher).
int ast_hashtab_resize_none (struct ast_hashtab *tab)
 Effectively disables resizing by always returning 0, regardless of of load factor.
int ast_hashtab_resize_tight (struct ast_hashtab *tab)
 Causes a resize whenever the number of elements stored in the table exceeds the number of buckets in the table.
int ast_hashtab_size (struct ast_hashtab *tab)
 Returns the number of elements stored in the hashtab.
ast_hashtab_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)
 Determines if the specified number is prime.
static void tlist_add_head (struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
static void tlist_del_item (struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)


Detailed Description

code to implement generic hash tables

Author:
Steve Murphy <murf@digium.com>

Definition in file hashtab.c.


Function Documentation

int ast_hashtab_capacity ( struct ast_hashtab tab  ) 

Returns the size of the bucket array in the hashtab.

Definition at line 631 of file hashtab.c.

References ast_hashtab::hash_tab_size.

00632 {
00633    return tab->hash_tab_size;
00634 }

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

Compares two integers for equality.

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

00067 {
00068    int ai = *((int *) a);
00069    int bi = *((int *) b);
00070 
00071    if (ai < bi)
00072       return -1;
00073 
00074    return !(ai == bi);
00075 }

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

Compares two shorts for equality.

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

00078 {
00079    short as = *((short *) a);
00080    short bs = *((short *) b);
00081 
00082    if (as < bs)
00083       return -1;
00084 
00085    return !(as == bs);
00086 }

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

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

00057 {
00058    return strcmp(a, b);
00059 }

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

00062 {
00063    return strcasecmp(a, b);
00064 }

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

References __ast_calloc(), ast_calloc, ast_hashtab_newsize_java(), ast_hashtab_resize_java(), ast_is_prime(), ast_rwlock_init, compare(), ast_hashtab::do_locking, and free.

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

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

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

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

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

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

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

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

void ast_hashtab_destroylock ( struct ast_hashtab tab  ) 

Call this before you destroy the table.

Definition at line 378 of file hashtab.c.

References ast_rwlock_destroy, and ast_hashtab::lock.

00379 {
00380    ast_rwlock_destroy(&tab->lock);
00381 }

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

Return a copy of the hash table.

Definition at line 280 of file hashtab.c.

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

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

void ast_hashtab_end_traversal ( struct ast_hashtab_iter it  ) 

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

Definition at line 746 of file hashtab.c.

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

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

00747 {
00748    if (it->tab->do_locking)
00749       ast_rwlock_unlock(&it->tab->lock);
00750    free(it);
00751 }

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

Returns key stats for the table.

Definition at line 611 of file hashtab.c.

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

Referenced by create_match_char_tree().

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

unsigned int ast_hashtab_hash_int ( const int  x  ) 

Definition at line 209 of file hashtab.c.

Referenced by hashtab_hash_priority().

00210 {
00211    return x;
00212 }

unsigned int ast_hashtab_hash_short ( const short  x  ) 

Definition at line 214 of file hashtab.c.

00215 {
00216    /* hmmmm.... modulus is best < 65535 !! */
00217    return x;
00218 }

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

References str, and total.

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

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

unsigned int ast_hashtab_hash_string_nocase ( const void *  obj  ) 

Hashes a string to a number ignoring case.

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

References str, and total.

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

unsigned int ast_hashtab_hash_string_sax ( const void *  obj  ) 

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

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

References str, and total.

00175 {
00176    const unsigned char *str = obj;
00177    unsigned int total = 0, c = 0;
00178 
00179    while ((c = *str++))
00180       total ^= (total << 5) + (total >> 2) + (total << 10) + c;
00181 
00182    return total;
00183 }

void ast_hashtab_initlock ( struct ast_hashtab tab  ) 

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

Definition at line 373 of file hashtab.c.

References ast_rwlock_init, and ast_hashtab::lock.

00374 {
00375    ast_rwlock_init(&tab->lock);
00376 }

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

Insert without checking.

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

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

Referenced by ast_context_find_or_create(), and ast_context_remove_extension_callerid2().

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

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

Insert without checking, hashing or locking.

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

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

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

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

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

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

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

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

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

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

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

Lookup this object in the hash table.

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

Definition at line 534 of file hashtab.c.

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

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

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

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

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

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

Definition at line 579 of file hashtab.c.

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

Referenced by ast_hashtab_insert_safe().

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

static void * ast_hashtab_lookup_internal ( struct ast_hashtab tab,
const void *  obj,
unsigned int  h 
) [static]

Definition at line 597 of file hashtab.c.

References ast_hashtab::array, ast_hashtab::compare, ast_hashtab_bucket::next, and ast_hashtab_bucket::object.

Referenced by ast_hashtab_lookup(), ast_hashtab_lookup_bucket(), and ast_hashtab_lookup_with_hash().

00598 {
00599    struct ast_hashtab_bucket *b;
00600 
00601    for (b = tab->array[h]; b; b = b->next) {
00602       if (!(*tab->compare)(obj,b->object)) {
00603          /* I can't touch obj in this func, but the outside world is welcome to */
00604          return (void*) b->object;
00605       }
00606    }
00607 
00608    return NULL;
00609 }

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

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

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

int ast_hashtab_newsize_java ( struct ast_hashtab tab  ) 

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

Definition at line 131 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

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

00132 {
00133    int i = (tab->hash_tab_size << 1); /* multiply by two */
00134 
00135    while (!ast_is_prime(i))
00136       i++;
00137 
00138    return i;
00139 }

int ast_hashtab_newsize_none ( struct ast_hashtab tab  ) 

always return current size -- no resizing

Definition at line 152 of file hashtab.c.

References ast_hashtab::hash_tab_size.

00153 {
00154    return tab->hash_tab_size;
00155 }

int ast_hashtab_newsize_tight ( struct ast_hashtab tab  ) 

Definition at line 141 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

00142 {
00143    int x = (tab->hash_tab_size << 1);
00144    int i = (tab->hash_tab_size + x);
00145 
00146    while (!ast_is_prime(i))
00147       i++;
00148 
00149    return i;
00150 }

void* ast_hashtab_next ( struct ast_hashtab_iter it  ) 

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

Definition at line 753 of file hashtab.c.

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

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

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

void ast_hashtab_rdlock ( struct ast_hashtab tab  ) 

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

Definition at line 368 of file hashtab.c.

References ast_rwlock_rdlock, and ast_hashtab::lock.

00369 {
00370    ast_rwlock_rdlock(&tab->lock);
00371 }

static void* ast_hashtab_remove_object_internal ( struct ast_hashtab tab,
struct ast_hashtab_bucket b,
int  h 
) [static]

Definition at line 767 of file hashtab.c.

References ast_hashtab::array, free, ast_hashtab::hash_tab_elements, ast_hashtab_bucket::next, ast_hashtab_bucket::object, ast_hashtab_bucket::prev, ast_hashtab::tlist, tlist_del_item(), ast_hashtab_bucket::tnext, and ast_hashtab_bucket::tprev.

Referenced by ast_hashtab_remove_object_via_lookup_nolock(), and ast_hashtab_remove_this_object_nolock().

00768 {
00769    const void *obj2;
00770 
00771    if (b->prev)
00772       b->prev->next = b->next;
00773    else
00774       tab->array[h] = b->next;
00775 
00776    if (b->next)
00777       b->next->prev = b->prev;
00778 
00779    tlist_del_item(&(tab->tlist), b);
00780 
00781    obj2 = b->object;
00782    b->object = b->next = (void*)2;
00783    free(b); /* free up the hashbucket */
00784    tab->hash_tab_elements--;
00785 #ifdef DEBUG
00786    {
00787       int c2;
00788       struct ast_hashtab_bucket *b2;
00789       /* do a little checking */
00790       for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
00791          c2++;
00792       }
00793       if (c2 != tab->hash_tab_elements) {
00794          printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
00795                c2, tab->hash_tab_elements);
00796       }
00797       for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
00798          unsigned int obj3 = (unsigned long) obj2;
00799          unsigned int b3 = (unsigned long) b;
00800          if (b2->object == obj2)
00801             printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
00802          if (b2->next == b)
00803             printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
00804          if (b2->prev == b)
00805             printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
00806          if (b2->tprev == b)
00807             printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
00808          if (b2->tnext == b)
00809             printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
00810       }
00811    }
00812 #endif
00813    return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00814 }

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

Looks up the object, removes the corresponding bucket.

Definition at line 816 of file hashtab.c.

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

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

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

Looks up the object, removes the corresponding bucket.

Definition at line 835 of file hashtab.c.

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

Referenced by ast_hashtab_remove_object_via_lookup().

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

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

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

Definition at line 859 of file hashtab.c.

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

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

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

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

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

Definition at line 880 of file hashtab.c.

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

Referenced by ast_hashtab_remove_this_object().

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

static void ast_hashtab_resize ( struct ast_hashtab tab  )  [static]

Definition at line 642 of file hashtab.c.

References __ast_calloc(), ast_hashtab::array, ast_calloc, free, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::largest_bucket_size, ast_hashtab::newsize, ast_hashtab_bucket::next, ast_hashtab_bucket::object, ast_hashtab_bucket::prev, ast_hashtab::resize_count, ast_hashtab::tlist, and ast_hashtab_bucket::tnext.

Referenced by ast_hashtab_insert_immediate_bucket().

00644 {
00645    /* this function is called either internally, when the resize func returns 1, or
00646       externally by the user to force a resize of the hash table */
00647    int newsize = (*tab->newsize)(tab), i, c;
00648    unsigned int h;
00649    struct ast_hashtab_bucket *b,*bn;
00650 
00651    /* Since we keep a DLL of all the buckets in tlist,
00652       all we have to do is free the array, malloc a new one,
00653       and then go thru the tlist array and reassign them into
00654       the bucket arrayj.
00655    */
00656    for (i = 0; i < tab->hash_tab_size; i++) { /* don't absolutely have to do this, but
00657                                  why leave ptrs laying around */
00658       tab->array[i] = 0; /* erase old ptrs */
00659    }
00660    free(tab->array);
00661    if (!(tab->array =
00662 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00663       __ast_calloc(newsize, sizeof(*(tab->array)), file, lineno, func)
00664 #else
00665       ast_calloc(newsize, sizeof(*(tab->array)))
00666 #endif
00667       ))
00668       return;
00669 
00670    /* now sort the buckets into their rightful new slots */
00671    tab->resize_count++;
00672    tab->hash_tab_size = newsize;
00673    tab->largest_bucket_size = 0;
00674 
00675    for (b = tab->tlist; b; b = bn) {
00676       b->prev = 0;
00677       bn = b->tnext;
00678       h = (*tab->hash)(b->object) % tab->hash_tab_size;
00679       b->next = tab->array[h];
00680       if (b->next)
00681          b->next->prev = b;
00682       tab->array[h] = b;
00683    }
00684    /* recalc the largest bucket size */
00685    for (i = 0; i < tab->hash_tab_size; i++) {
00686       for (c = 0, b = tab->array[i]; b; b = b->next)
00687          c++;
00688       if (c > tab->largest_bucket_size)
00689          tab->largest_bucket_size = c;
00690    }
00691 }

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

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

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

00089 {
00090    double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
00091 
00092    return (loadfactor > 0.75);
00093 }

int ast_hashtab_resize_none ( struct ast_hashtab tab  ) 

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

00101 {
00102    return 0;
00103 }

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

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

00096 {
00097    return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
00098 }

int ast_hashtab_size ( struct ast_hashtab tab  ) 

Returns the number of elements stored in the hashtab.

Definition at line 625 of file hashtab.c.

References ast_hashtab::hash_tab_elements.

Referenced by ast_context_remove_extension_callerid2().

00626 {
00627    return tab->hash_tab_elements;
00628 }

struct ast_hashtab_iter* ast_hashtab_start_traversal ( struct ast_hashtab tab  ) 

Gives an iterator to hastable.

Definition at line 696 of file hashtab.c.

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

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

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

struct ast_hashtab_iter* ast_hashtab_start_write_traversal ( struct ast_hashtab tab  ) 

Gives an iterator to hastable.

Definition at line 723 of file hashtab.c.

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

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

void ast_hashtab_unlock ( struct ast_hashtab tab  ) 

release a read- or write- lock.

Definition at line 383 of file hashtab.c.

References ast_rwlock_unlock, and ast_hashtab::lock.

00384 {
00385    ast_rwlock_unlock(&tab->lock);
00386 }

void ast_hashtab_wrlock ( struct ast_hashtab tab  ) 

Request a write-lock on the table.

Definition at line 363 of file hashtab.c.

References ast_rwlock_wrlock, and ast_hashtab::lock.

00364 {
00365    ast_rwlock_wrlock(&tab->lock);
00366 }

int ast_is_prime ( int  num  ) 

Determines if the specified number is prime.

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

Definition at line 105 of file hashtab.c.

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

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

static void tlist_add_head ( struct ast_hashtab_bucket **  head,
struct ast_hashtab_bucket item 
) [static]

Definition at line 345 of file hashtab.c.

References ast_hashtab_bucket::tnext, and ast_hashtab_bucket::tprev.

Referenced by ast_hashtab_insert_immediate_bucket().

00346 {
00347    if (*head) {
00348       item->tnext = *head;
00349       item->tprev = NULL;
00350       (*head)->tprev = item;
00351       *head = item;
00352    } else {
00353       /* the list is empty */
00354       *head = item;
00355       item->tprev = NULL;
00356       item->tnext = NULL;
00357    }
00358 }

static void tlist_del_item ( struct ast_hashtab_bucket **  head,
struct ast_hashtab_bucket item 
) [static]

Definition at line 330 of file hashtab.c.

References ast_hashtab_bucket::tnext, and ast_hashtab_bucket::tprev.

Referenced by ast_hashtab_destroy(), and ast_hashtab_remove_object_internal().

00331 {
00332    /* item had better be in the list! or suffer the weirdness that occurs, later! */
00333    if (*head == item) { /* first item in the list */
00334       *head = item->tnext;
00335       if (item->tnext)
00336          item->tnext->tprev = NULL;
00337    } else {
00338       /* short circuit stuff */
00339       item->tprev->tnext = item->tnext;
00340       if (item->tnext)
00341          item->tnext->tprev = item->tprev;
00342    }
00343 }


Generated on Mon Oct 8 12:39:23 2012 for Asterisk - The Open Source Telephony Project by  doxygen 1.4.7