Wed Aug 18 22:34:24 2010

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)
 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 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)
 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 *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)
 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.
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 578 of file hashtab.c.

References ast_hashtab::hash_tab_size.

00579 {
00580    return tab->hash_tab_size;
00581 }

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

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

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

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

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

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

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

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

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

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

00367 {
00368    /* this func will free the hash table and all its memory. It
00369       doesn't touch the objects stored in it */
00370    if (tab) {
00371       
00372       if (tab->do_locking)
00373          ast_rwlock_wrlock(&tab->lock);
00374 
00375       if (tab->array) {
00376          /* go thru and destroy the buckets */
00377          struct ast_hashtab_bucket *t;
00378          int i;
00379          
00380          while (tab->tlist) {
00381             t = tab->tlist;
00382             if (t->object && objdestroyfunc)
00383                (*objdestroyfunc)((void *) t->object); /* I cast this because I'm not going to MOD it, I'm going to DESTROY it */
00384             
00385             tlist_del_item(&(tab->tlist), tab->tlist);
00386             free(t);
00387          }
00388          
00389          for (i = 0; i < tab->hash_tab_size; i++)
00390             tab->array[i] = NULL; /* not totally necc., but best to destroy old ptrs */
00391          
00392          free(tab->array);
00393       }
00394       if (tab->do_locking) {
00395          ast_rwlock_unlock(&tab->lock);
00396          ast_rwlock_destroy(&tab->lock);
00397       }
00398       free(tab);
00399    }
00400 }

void ast_hashtab_destroylock ( struct ast_hashtab tab  ) 

Call this before you destroy the table.

Definition at line 356 of file hashtab.c.

References ast_rwlock_destroy(), and ast_hashtab::lock.

00357 {
00358    ast_rwlock_destroy(&tab->lock);
00359 }

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

Return a copy of the hash table.

Definition at line 269 of file hashtab.c.

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

00270 {
00271    struct ast_hashtab *ht;
00272    unsigned int i;
00273 
00274    if (!(ht = ast_calloc(1, sizeof(*ht))))
00275       return NULL;
00276 
00277    if (!(ht->array = ast_calloc(tab->hash_tab_size, sizeof(*(ht->array))))) {
00278       free(ht);
00279       return NULL;
00280    }
00281 
00282    ht->hash_tab_size = tab->hash_tab_size;
00283    ht->compare = tab->compare;
00284    ht->resize = tab->resize;
00285    ht->newsize = tab->newsize;
00286    ht->hash = tab->hash;
00287    ht->do_locking = tab->do_locking;
00288 
00289    if (ht->do_locking)
00290       ast_rwlock_init(&ht->lock);
00291 
00292    /* now, dup the objects in the buckets and get them into the table */
00293    /* the fast way is to use the existing array index, and not have to hash
00294       the objects again */
00295    for (i = 0; i < ht->hash_tab_size; i++) {
00296       struct ast_hashtab_bucket *b = tab->array[i];
00297       while (b) {
00298          void *newobj = (*obj_dup_func)(b->object);
00299          if (newobj)
00300             ast_hashtab_insert_immediate_bucket(ht, newobj, i);
00301          b = b->next;
00302       }
00303    }
00304 
00305    return ht;
00306 }

void ast_hashtab_end_traversal ( struct ast_hashtab_iter it  ) 

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

Definition at line 666 of file hashtab.c.

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

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

00667 {
00668    if (it->tab->do_locking)
00669       ast_rwlock_unlock(&it->tab->lock);
00670    free(it);
00671 }

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

Returns key stats for the table.

Definition at line 558 of file hashtab.c.

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

Referenced by create_match_char_tree().

00559 {
00560    /* returns key stats for the table */
00561    if (tab->do_locking)
00562       ast_rwlock_rdlock(&tab->lock);
00563    *biggest_bucket_size = tab->largest_bucket_size;
00564    *resize_count = tab->resize_count;
00565    *num_objects = tab->hash_tab_elements;
00566    *num_buckets = tab->hash_tab_size;
00567    if (tab->do_locking)
00568       ast_rwlock_unlock(&tab->lock);
00569 }

unsigned int ast_hashtab_hash_int ( const int  x  ) 

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  x  ) 

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

References ast_rwlock_init(), and ast_hashtab::lock.

00352 {
00353    ast_rwlock_init(&tab->lock);
00354 }

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

Insert without checking.

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

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

Referenced by ast_context_find_or_create(), and ast_context_remove_extension_callerid2().

00403 {
00404    unsigned int h;
00405    int res=0;
00406    
00407    if (!tab || !obj)
00408       return res;
00409 
00410    if (tab->do_locking)
00411       ast_rwlock_wrlock(&tab->lock);
00412 
00413    h = (*tab->hash)(obj) % tab->hash_tab_size;
00414 
00415    res = ast_hashtab_insert_immediate_bucket(tab,obj,h);
00416 
00417    if (tab->do_locking)
00418       ast_rwlock_unlock(&tab->lock);
00419 
00420    return res;
00421 }

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

Insert without checking, hashing or locking.

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

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

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

00424 {
00425    int c;
00426    struct ast_hashtab_bucket *b;
00427    
00428    if (!tab || !obj)
00429       return 0;
00430    
00431    for (c = 0, b = tab->array[h]; b; b= b->next)
00432       c++;
00433 
00434    if (c + 1 > tab->largest_bucket_size)
00435       tab->largest_bucket_size = c + 1;
00436 
00437    if (!(b = ast_calloc(1, sizeof(*b))))
00438       return 0;
00439 
00440    b->object = obj;
00441    b->next = tab->array[h];
00442    tab->array[h] = b;
00443 
00444    if (b->next)
00445       b->next->prev = b;
00446 
00447    tlist_add_head(&(tab->tlist), b);
00448    tab->hash_tab_elements++;
00449 
00450    if ((*tab->resize)(tab))
00451       ast_hashtab_resize(tab);
00452 
00453    return 1;
00454 }

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

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

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

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

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

00457 {
00458    /* check to see if the element is already there; insert only if
00459       it is not there. */
00460    /* will force a resize if the resize func returns 1 */
00461    /* returns 1 on success, 0 if there's a problem, or it's already there. */
00462    unsigned int bucket = 0;
00463 
00464    if (tab->do_locking)
00465       ast_rwlock_wrlock(&tab->lock);
00466 
00467    if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
00468       int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket);
00469 
00470       if (tab->do_locking)
00471          ast_rwlock_unlock(&tab->lock);
00472       
00473       return ret2;
00474    }
00475 
00476    if (tab->do_locking)
00477       ast_rwlock_unlock(&tab->lock);
00478       
00479    return 0;
00480 }

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

Lookup this object in the hash table.

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

Definition at line 482 of file hashtab.c.

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

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

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

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

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

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

Definition at line 527 of file hashtab.c.

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

Referenced by ast_hashtab_insert_safe().

00528 {
00529    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00530    unsigned int h;
00531    void *ret;
00532 
00533    if (!tab || !obj)
00534       return 0;
00535    
00536    h = (*tab->hash)(obj) % tab->hash_tab_size;
00537    
00538    ret = ast_hashtab_lookup_internal(tab,obj,h);
00539    
00540    *bucket = h; 
00541    
00542    return ret;
00543 }

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

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

00546 {
00547    struct ast_hashtab_bucket *b;
00548 
00549    for (b = tab->array[h]; b; b = b->next) {
00550       if (!(*tab->compare)(obj,b->object)) {
00551          return (void*) b->object; /* I can't touch obj in this func, but the outside world is welcome to */
00552       }
00553    }
00554 
00555    return NULL;
00556 }

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

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

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

int ast_hashtab_newsize_java ( struct ast_hashtab tab  ) 

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

Definition at line 122 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

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

00123 {
00124    int i = (tab->hash_tab_size << 1); /* multiply by two */
00125    
00126    while (!ast_is_prime(i))
00127       i++;
00128 
00129    return i;
00130 }

int ast_hashtab_newsize_none ( struct ast_hashtab tab  ) 

always return current size -- no resizing

Definition at line 143 of file hashtab.c.

References ast_hashtab::hash_tab_size.

00144 {
00145    return tab->hash_tab_size;
00146 }

int ast_hashtab_newsize_tight ( struct ast_hashtab tab  ) 

Definition at line 132 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

00133 {
00134    int x = (tab->hash_tab_size << 1);
00135    int i = (tab->hash_tab_size + x);
00136    
00137    while (!ast_is_prime(i))
00138       i++;
00139 
00140    return i;
00141 }

void* ast_hashtab_next ( struct ast_hashtab_iter it  ) 

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

Definition at line 673 of file hashtab.c.

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

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

00674 {
00675    /* returns the next object in the list, advances iter one step */
00676    struct ast_hashtab_bucket *retval;
00677    
00678    if (it && it->next) { /* there's a next in the bucket list */
00679       retval = it->next;
00680       it->next = retval->tnext;
00681       return (void *) retval->object;
00682    }
00683 
00684    return NULL;
00685 }

void ast_hashtab_rdlock ( struct ast_hashtab tab  ) 

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

Definition at line 346 of file hashtab.c.

References ast_rwlock_rdlock(), and ast_hashtab::lock.

00347 {
00348    ast_rwlock_rdlock(&tab->lock);
00349 }

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

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

00688 {
00689    const void *obj2;
00690    
00691    if (b->prev)
00692       b->prev->next = b->next;
00693    else
00694       tab->array[h] = b->next;
00695    
00696    if (b->next)
00697       b->next->prev = b->prev;
00698    
00699    tlist_del_item(&(tab->tlist), b);
00700    
00701    obj2 = b->object;
00702    b->object = b->next = (void*)2;
00703    free(b); /* free up the hashbucket */
00704    tab->hash_tab_elements--;
00705 #ifdef DEBUG
00706    {
00707       int c2;
00708       struct ast_hashtab_bucket *b2;
00709       /* do a little checking */
00710       for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
00711          c2++;
00712       }
00713       if (c2 != tab->hash_tab_elements) {
00714          printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
00715                c2, tab->hash_tab_elements);
00716       }
00717       for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
00718          unsigned int obj3 = (unsigned long) obj2;
00719          unsigned int b3 = (unsigned long) b;
00720          if (b2->object == obj2)
00721             printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
00722          if (b2->next == b)
00723             printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
00724          if (b2->prev == b)
00725             printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
00726          if (b2->tprev == b)
00727             printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
00728          if (b2->tnext == b)
00729             printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
00730       }
00731    }
00732 #endif
00733    return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00734 }

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

Looks up the object, removes the corresponding bucket.

Definition at line 736 of file hashtab.c.

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

00737 {
00738    /* looks up the object; removes the corresponding bucket */
00739    const void *obj2;
00740 
00741    if (!tab || !obj)
00742       return 0;
00743 
00744    if (tab->do_locking)
00745       ast_rwlock_wrlock(&tab->lock);
00746 
00747    obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj);
00748 
00749    if (tab->do_locking)
00750       ast_rwlock_unlock(&tab->lock);
00751 
00752    return (void *)obj2;
00753 }

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

Looks up the object, removes the corresponding bucket.

Definition at line 755 of file hashtab.c.

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

Referenced by ast_hashtab_remove_object_via_lookup().

00756 {
00757    /* looks up the object; removes the corresponding bucket */
00758    unsigned int h;
00759    struct ast_hashtab_bucket *b;
00760 
00761    if (!tab || !obj)
00762       return 0;
00763 
00764    h = (*tab->hash)(obj) % tab->hash_tab_size;
00765    for (b = tab->array[h]; b; b = b->next) {
00766       
00767       if (!(*tab->compare)(obj, b->object)) {
00768          const void *obj2;
00769 
00770          obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00771          
00772          return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00773       }
00774    }
00775 
00776    return 0;
00777 }

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

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

Definition at line 779 of file hashtab.c.

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

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

00780 {
00781    /* looks up the object by hash and then comparing pts in bucket list instead of
00782       calling the compare routine; removes the bucket -- a slightly cheaper operation */
00783    /* looks up the object; removes the corresponding bucket */
00784    const void *obj2;
00785 
00786    if (!tab || !obj)
00787       return 0;
00788  
00789    if (tab->do_locking)
00790       ast_rwlock_wrlock(&tab->lock);
00791 
00792    obj2 = ast_hashtab_remove_this_object_nolock(tab,obj);
00793    
00794    if (tab->do_locking)
00795       ast_rwlock_unlock(&tab->lock);
00796 
00797    return (void *)obj2;
00798 }

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

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

Definition at line 800 of file hashtab.c.

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

Referenced by ast_hashtab_remove_this_object().

00801 {
00802    /* looks up the object by hash and then comparing pts in bucket list instead of
00803       calling the compare routine; removes the bucket -- a slightly cheaper operation */
00804    /* looks up the object; removes the corresponding bucket */
00805    unsigned int h;
00806    struct ast_hashtab_bucket *b;
00807 
00808    if (!tab || !obj)
00809       return 0;
00810  
00811    h = (*tab->hash)(obj) % tab->hash_tab_size;
00812    for (b = tab->array[h]; b; b = b->next) {
00813       
00814       if (obj == b->object) {
00815          const void *obj2;
00816          obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00817          
00818          return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00819       }
00820    }
00821 
00822    return 0;
00823 }

static void ast_hashtab_resize ( struct ast_hashtab tab  )  [static]

Definition at line 589 of file hashtab.c.

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

00590 {
00591    /* this function is called either internally, when the resize func returns 1, or
00592       externally by the user to force a resize of the hash table */
00593    int newsize = (*tab->newsize)(tab), i, c;
00594    unsigned int h;
00595    struct ast_hashtab_bucket *b,*bn;
00596    
00597    /* Since we keep a DLL of all the buckets in tlist,
00598       all we have to do is free the array, malloc a new one,
00599       and then go thru the tlist array and reassign them into 
00600       the bucket arrayj.
00601    */
00602    for (i = 0; i < tab->hash_tab_size; i++) { /* don't absolutely have to do this, but
00603                                  why leave ptrs laying around */
00604       tab->array[i] = 0; /* erase old ptrs */
00605    }
00606    free(tab->array);
00607    if (!(tab->array = ast_calloc(newsize, sizeof(*(tab->array)))))
00608       return;
00609 
00610    /* now sort the buckets into their rightful new slots */
00611    tab->resize_count++;
00612    tab->hash_tab_size = newsize;
00613    tab->largest_bucket_size = 0;
00614 
00615    for (b = tab->tlist; b; b = bn) {
00616       b->prev = 0;
00617       bn = b->tnext;
00618       h = (*tab->hash)(b->object) % tab->hash_tab_size;
00619       b->next = tab->array[h];
00620       if (b->next)
00621          b->next->prev = b;
00622       tab->array[h] = b;
00623    }
00624    /* recalc the largest bucket size */
00625    for (i = 0; i < tab->hash_tab_size; i++) {
00626       for (c = 0, b = tab->array[i]; b; b = b->next)
00627          c++;
00628       if (c > tab->largest_bucket_size)
00629          tab->largest_bucket_size = c;
00630    }
00631 }

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

00079 {
00080    double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
00081 
00082    return (loadfactor > 0.75);
00083 }

int ast_hashtab_resize_none ( struct ast_hashtab tab  ) 

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

References ast_hashtab::hash_tab_elements.

Referenced by ast_context_remove_extension_callerid2().

00573 {
00574    return tab->hash_tab_elements;
00575 }

struct ast_hashtab_iter* ast_hashtab_start_traversal ( struct ast_hashtab tab  ) 

Gives an iterator to hastable.

Definition at line 633 of file hashtab.c.

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

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

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

struct ast_hashtab_iter* ast_hashtab_start_write_traversal ( struct ast_hashtab tab  ) 

Gives an iterator to hastable.

Definition at line 650 of file hashtab.c.

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

00651 {
00652    /* returns an iterator */
00653    struct ast_hashtab_iter *it;
00654    
00655    if (!(it = ast_calloc(1, sizeof(*it))))
00656       return NULL;
00657 
00658    it->next = tab->tlist;
00659    it->tab = tab;
00660    if (tab->do_locking)
00661       ast_rwlock_wrlock(&tab->lock);
00662 
00663    return it;
00664 }

void ast_hashtab_unlock ( struct ast_hashtab tab  ) 

release a read- or write- lock.

Definition at line 361 of file hashtab.c.

References ast_rwlock_unlock(), and ast_hashtab::lock.

00362 {
00363    ast_rwlock_unlock(&tab->lock);
00364 }

void ast_hashtab_wrlock ( struct ast_hashtab tab  ) 

Request a write-lock on the table.

Definition at line 341 of file hashtab.c.

References ast_rwlock_wrlock(), and ast_hashtab::lock.

00342 {
00343    ast_rwlock_wrlock(&tab->lock);
00344 }

int ast_is_prime ( int  num  ) 

For sizing the hash table, tells if num is prime or not.

Definition at line 95 of file hashtab.c.

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

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

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

Definition at line 323 of file hashtab.c.

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

Referenced by ast_hashtab_insert_immediate_bucket().

00324 {
00325    if (*head) {
00326       item->tnext = *head;
00327       item->tprev = NULL;
00328       (*head)->tprev = item;
00329       *head = item;
00330    } else {
00331       /* the list is empty */
00332       *head = item;
00333       item->tprev = NULL;
00334       item->tnext = NULL;
00335    }
00336 }

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

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

00309 {
00310    /* item had better be in the list! or suffer the weirdness that occurs, later! */
00311    if (*head == item) { /* first item in the list */
00312       *head = item->tnext;
00313       if (item->tnext)
00314          item->tnext->tprev = NULL;
00315    } else {
00316       /* short circuit stuff */
00317       item->tprev->tnext = item->tnext;
00318       if (item->tnext)
00319          item->tnext->tprev = item->tprev;
00320    }
00321 }


Generated on Wed Aug 18 22:34:24 2010 for Asterisk - the Open Source PBX by  doxygen 1.4.7