diff options
author | russell <russell@f38db490-d61c-443f-a65b-d21fe96a405b> | 2007-11-14 03:22:09 +0000 |
---|---|---|
committer | russell <russell@f38db490-d61c-443f-a65b-d21fe96a405b> | 2007-11-14 03:22:09 +0000 |
commit | 2e70fd87205ec4f9c775075b807c65e3703145e3 (patch) | |
tree | 6014218b3fa6812e6c3c5b552f2906650bfe2393 /main/hashtab.c | |
parent | a0ad3a06ca404ffd0c75c2c8586fc8295afe0aa7 (diff) |
Fix up various coding guidelines issues ...
- handle memory allocation failures
- add an ast_ prefix to a publicly exported function
- put curly braces in the right places
- add a bunch of spaces where they should be be used
git-svn-id: http://svn.digium.com/svn/asterisk/trunk@89266 f38db490-d61c-443f-a65b-d21fe96a405b
Diffstat (limited to 'main/hashtab.c')
-rw-r--r-- | main/hashtab.c | 327 |
1 files changed, 188 insertions, 139 deletions
diff --git a/main/hashtab.c b/main/hashtab.c index 1e4685761..19d642ebe 100644 --- a/main/hashtab.c +++ b/main/hashtab.c @@ -62,42 +62,36 @@ int ast_hashtab_compare_strings_nocase(const void *a, const void *b) int ast_hashtab_compare_ints(const void *a, const void *b) { - int ai = *((int*)a); - int bi = *((int*)b); + int ai = *((int *) a); + int bi = *((int *) b); + if (ai < bi) return -1; - else if (ai==bi) - return 0; - else - return 1; + + return !(ai == bi); } int ast_hashtab_compare_shorts(const void *a, const void *b) { - short as = *((short*)a); - short bs = *((short*)b); + short as = *((short *) a); + short bs = *((short *) b); + if (as < bs) return -1; - else if (as==bs) - return 0; - else - return 1; + + return !(as == bs); } int ast_hashtab_resize_java(struct ast_hashtab *tab) { - double loadfactor = (double)tab->hash_tab_elements / (double)tab->hash_tab_size; - if (loadfactor > 0.75) - return 1; - return 0; + double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size; + + return (loadfactor > 0.75); } int ast_hashtab_resize_tight(struct ast_hashtab *tab) { - - if (tab->hash_tab_elements > tab->hash_tab_size) /* this is quicker than division */ - return 1; - return 0; + return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */ } int ast_hashtab_resize_none(struct ast_hashtab *tab) /* always return 0 -- no resizing */ @@ -105,46 +99,51 @@ int ast_hashtab_resize_none(struct ast_hashtab *tab) /* always return 0 -- no re return 0; } - -int isPrime(int num) +int ast_is_prime(int num) { - int tnum,limit; + int tnum, limit; - if ((num & 0x1) == 0) /* even number -- not prime */ + if (!(num & 0x1)) /* even number -- not prime */ return 0; - /* Loop through ODD numbers starting with 3 */ + /* Loop through ODD numbers starting with 3 */ tnum = 3; limit = num; - while (tnum < limit) - { - if ((num%tnum) == 0) { + while (tnum < limit) { + if (!(num % tnum)) return 0; - } + /* really, we only need to check sqrt(num) numbers */ limit = num / tnum; + /* we only check odd numbers */ - tnum = tnum+2; + tnum = tnum + 2; } - /* if we made it thru the loop, the number is a prime */ + + /* if we made it through the loop, the number is a prime */ + return 1; } int ast_hashtab_newsize_java(struct ast_hashtab *tab) { - int i = (tab->hash_tab_size<<1); /* multiply by two */ - while (!isPrime(i)) + int i = (tab->hash_tab_size << 1); /* multiply by two */ + + while (!ast_is_prime(i)) i++; + return i; } int ast_hashtab_newsize_tight(struct ast_hashtab *tab) { - int x = (tab->hash_tab_size<<1); - int i = (tab->hash_tab_size+x); - while (!isPrime(i)) + int x = (tab->hash_tab_size << 1); + int i = (tab->hash_tab_size + x); + + while (!ast_is_prime(i)) i++; + return i; } @@ -155,10 +154,10 @@ int ast_hashtab_newsize_none(struct ast_hashtab *tab) /* always return current s unsigned int ast_hashtab_hash_string(const void *obj) { - unsigned char *str = (unsigned char*)obj; + unsigned char *str = (unsigned char *) obj; unsigned int total; - for (total=0; *str; str++) + for (total = 0; *str; str++) { unsigned int tmp = total; total <<= 1; /* multiply by 2 */ @@ -173,11 +172,11 @@ unsigned int ast_hashtab_hash_string(const void *obj) unsigned int ast_hashtab_hash_string_sax(const void *obj) /* from Josh */ { - unsigned char *str = (unsigned char*)obj; + unsigned char *str = (unsigned char *) obj; unsigned int total = 0, c = 0; while ((c = *str++)) - total ^= ( total << 5 ) + ( total >> 2 ) + ( total << 10) + c; + total ^= (total << 5) + (total >> 2) + (total << 10) + c; return total; } @@ -187,8 +186,7 @@ unsigned int ast_hashtab_hash_string_nocase(const void *obj) unsigned char *str = (unsigned char*)obj; unsigned int total; - for (total=0; *str; str++) - { + for (total = 0; *str; str++) { unsigned int tmp = total; unsigned int charval = toupper(*str); @@ -203,6 +201,7 @@ unsigned int ast_hashtab_hash_string_nocase(const void *obj) total += (charval); } + return total; } @@ -217,61 +216,81 @@ unsigned int ast_hashtab_hash_short(const short x) return x; } -struct ast_hashtab * ast_hashtab_create(int initial_buckets, - int (*compare)(const void *a, const void *b), /* a func to compare two elements in the hash -- cannot be null */ - int (*resize)(struct ast_hashtab *), /* a func to decide if the table needs to be resized, a NULL ptr here will cause a default to be used */ - int (*newsize)(struct ast_hashtab *tab), /* a ptr to func that returns a new size of the array. A NULL will cause a default to be used */ - unsigned int (*hash)(const void *obj), /* a func to do the hashing */ - int do_locking ) /* use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now */ +struct ast_hashtab *ast_hashtab_create(int initial_buckets, + int (*compare)(const void *a, const void *b), /* a func to compare two elements in the hash -- cannot be null */ + int (*resize)(struct ast_hashtab *), /* a func to decide if the table needs to be resized, a NULL ptr here will cause a default to be used */ + int (*newsize)(struct ast_hashtab *tab), /* a ptr to func that returns a new size of the array. A NULL will cause a default to be used */ + unsigned int (*hash)(const void *obj), /* a func to do the hashing */ + int do_locking ) /* use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now */ { - struct ast_hashtab *ht = ast_calloc(1,sizeof(struct ast_hashtab)); - while (!isPrime(initial_buckets)) /* make sure this is prime */ + struct ast_hashtab *ht; + + if (!(ht = ast_calloc(1, sizeof(*ht)))) + return NULL; + + while (!ast_is_prime(initial_buckets)) /* make sure this is prime */ initial_buckets++; - ht->array = ast_calloc(initial_buckets,sizeof(struct ast_hashtab_bucket*)); + + if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) { + free(ht); + return NULL; + } + ht->hash_tab_size = initial_buckets; ht->compare = compare; ht->resize = resize; ht->newsize = newsize; ht->hash = hash; ht->do_locking = do_locking; + if (do_locking) ast_rwlock_init(&ht->lock); + if (!ht->resize) ht->resize = ast_hashtab_resize_java; + if (!ht->newsize) ht->newsize = ast_hashtab_newsize_java; + return ht; } struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj)) { - struct ast_hashtab *ht = ast_calloc(1,sizeof(struct ast_hashtab)); + struct ast_hashtab *ht; unsigned int i; - - ht->array = ast_calloc(tab->hash_tab_size,sizeof(struct ast_hashtab_bucket*)); + + if (!(ht = ast_calloc(1, sizeof(*ht)))) + return NULL; + + if (!(ht->array = ast_calloc(tab->hash_tab_size, sizeof(*(ht->array))))) { + free(ht); + return NULL; + } + ht->hash_tab_size = tab->hash_tab_size; ht->compare = tab->compare; ht->resize = tab->resize; ht->newsize = tab->newsize; ht->hash = tab->hash; ht->do_locking = tab->do_locking; + if (ht->do_locking) ast_rwlock_init(&ht->lock); + /* now, dup the objects in the buckets and get them into the table */ /* the fast way is to use the existing array index, and not have to hash the objects again */ - for (i=0;i<ht->hash_tab_size;i++) - { + for (i = 0; i < ht->hash_tab_size; i++) { struct ast_hashtab_bucket *b = tab->array[i]; - while( b ) - { + while (b) { void *newobj = (*obj_dup_func)(b->object); - if (newobj) { + if (newobj) ast_hashtab_insert_immediate_bucket(ht, newobj, i); - } b = b->next; } } + return ht; } @@ -333,7 +352,6 @@ void ast_hashtab_unlock(struct ast_hashtab *tab) ast_rwlock_unlock(&tab->lock); } - void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj)) { /* this func will free the hash table and all its memory. It @@ -350,17 +368,15 @@ void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void * while (tab->tlist) { t = tab->tlist; - if (t->object && objdestroyfunc) { - (*objdestroyfunc)((void*)t->object); /* I cast this because I'm not going to MOD it, I'm going to DESTROY it */ - } + if (t->object && objdestroyfunc) + (*objdestroyfunc)((void *) t->object); /* I cast this because I'm not going to MOD it, I'm going to DESTROY it */ tlist_del_item(&(tab->tlist), tab->tlist); free(t); } - for (i=0;i<tab->hash_tab_size;i++) { + for (i = 0; i < tab->hash_tab_size; i++) tab->array[i] = NULL; /* not totally necc., but best to destroy old ptrs */ - } free(tab->array); } @@ -385,34 +401,43 @@ int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj) int c; struct ast_hashtab_bucket *b; - if (!tab) { + if (!tab) return 0; - } - if (!obj) { + + if (!obj) return 0; - } + if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); + h = (*tab->hash)(obj) % tab->hash_tab_size; - for (c=0,b=tab->array[h];b;b=b->next) { + + for (c = 0, b = tab->array[h]; b; b = b->next) c++; - } - if (c+1 > tab->largest_bucket_size) - tab->largest_bucket_size = c+1; - b = ast_malloc(sizeof(struct ast_hashtab_bucket)); + + if (c + 1 > tab->largest_bucket_size) + tab->largest_bucket_size = c + 1; + + if (!(b = ast_calloc(1, sizeof(*b)))) + return 0; + b->object = obj; b->next = tab->array[h]; - b->prev = NULL; + if (b->next) b->next->prev = b; - tlist_add_head(&(tab->tlist),b); + + tlist_add_head(&(tab->tlist), b); tab->array[h] = b; tab->hash_tab_elements++; + if ((*tab->resize)(tab)) ast_hashtab_resize(tab); + if (tab->do_locking) ast_rwlock_unlock(&tab->lock); + return 1; } @@ -431,22 +456,28 @@ int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj if (!tab || !obj) return 0; - for (c=0,b=tab->array[h];b;b=b->next) { + for (c = 0, b = tab->array[h]; b; b= b->next) c++; - } - if (c+1 > tab->largest_bucket_size) - tab->largest_bucket_size = c+1; - b = ast_malloc(sizeof(struct ast_hashtab_bucket)); + + if (c + 1 > tab->largest_bucket_size) + tab->largest_bucket_size = c + 1; + + if (!(b = ast_calloc(1, sizeof(*b)))) + return 0; + b->object = obj; b->next = tab->array[h]; - b->prev = NULL; tab->array[h] = b; + if (b->next) b->next->prev = b; + tlist_add_head(&(tab->tlist), b); tab->hash_tab_elements++; + if ((*tab->resize)(tab)) ast_hashtab_resize(tab); + return 1; } @@ -457,19 +488,22 @@ int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj) /* will force a resize if the resize func returns 1 */ /* returns 1 on success, 0 if there's a problem, or it's already there. */ unsigned int bucket = 0; + if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); - if (ast_hashtab_lookup_bucket(tab,obj,&bucket) == 0) - { - int ret2 = ast_hashtab_insert_immediate_bucket(tab,obj,bucket); + if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) { + int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket); + if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return ret2; } + if (tab->do_locking) ast_rwlock_unlock(&tab->lock); + return 0; } @@ -479,46 +513,52 @@ void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj) unsigned int h; const void *ret; struct ast_hashtab_bucket *b; + if (!tab || !obj) return 0; if (tab->do_locking) ast_rwlock_rdlock(&tab->lock); + h = (*tab->hash)(obj) % tab->hash_tab_size; - for (b=tab->array[h]; b; b=b->next) { - if ((*tab->compare)(obj,b->object) == 0) { + for (b = tab->array[h]; b; b = b->next) { + if (!(*tab->compare)(obj,b->object)) { ret = b->object; if (tab->do_locking) ast_rwlock_unlock(&tab->lock); - return (void*)ret; /* I can't touch obj in this func, but the outside world is welcome to */ + return (void*) ret; /* I can't touch obj in this func, but the outside world is welcome to */ } } + if (tab->do_locking) ast_rwlock_unlock(&tab->lock); return 0; } -void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval) +void *ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval) { /* lookup this object in the hash table. return a ptr if found, or NULL if not */ unsigned int h; const void *ret; struct ast_hashtab_bucket *b; + if (!tab || !obj) return 0; if (tab->do_locking) ast_rwlock_rdlock(&tab->lock); + h = hashval % tab->hash_tab_size; - for (b=tab->array[h]; b; b=b->next) { - if ((*tab->compare)(obj,b->object) == 0) { + for (b = tab->array[h]; b; b = b->next) { + if (!(*tab->compare)(obj,b->object)) { ret = b->object; if (tab->do_locking) ast_rwlock_unlock(&tab->lock); - return (void*)ret; /* I can't touch obj in this func, but the outside world is welcome to */ + return (void*) ret; /* I can't touch obj in this func, but the outside world is welcome to */ } } + if (tab->do_locking) ast_rwlock_unlock(&tab->lock); @@ -530,16 +570,18 @@ void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsig /* lookup this object in the hash table. return a ptr if found, or NULL if not */ unsigned int h; struct ast_hashtab_bucket *b; + if (!tab || !obj) return 0; h = (*tab->hash)(obj) % tab->hash_tab_size; - for (b=tab->array[h]; b; b=b->next) { - if ((*tab->compare)(obj,b->object) == 0) { - return (void*)b->object; /* I can't touch obj in this func, but the outside world is welcome to */ - } + for (b = tab->array[h]; b; b = b->next) { + if (!(*tab->compare)(obj,b->object)) + return (void*) b->object; /* I can't touch obj in this func, but the outside world is welcome to */ } + *bucket = h; + return 0; } @@ -587,19 +629,20 @@ static void ast_hashtab_resize( struct ast_hashtab *tab) and then go thru the tlist array and reassign them into the bucket arrayj. */ - for (i=0;i<tab->hash_tab_size;i++) { /* don't absolutely have to do this, but + for (i = 0; i < tab->hash_tab_size; i++) { /* don't absolutely have to do this, but why leave ptrs laying around */ tab->array[i] = 0; /* erase old ptrs */ } free(tab->array); - tab->array = ast_calloc(newsize,sizeof(struct ast_hashtab_bucket *)); + if (!(tab->array = ast_calloc(newsize, sizeof(*(tab->array))))) + return; + /* now sort the buckets into their rightful new slots */ tab->resize_count++; tab->hash_tab_size = newsize; tab->largest_bucket_size = 0; - for (b=tab->tlist;b;b=bn) - { + for (b = tab->tlist; b; b = bn) { b->prev = 0; bn = b->tnext; h = (*tab->hash)(b->object) % tab->hash_tab_size; @@ -609,11 +652,9 @@ static void ast_hashtab_resize( struct ast_hashtab *tab) tab->array[h] = b; } /* recalc the largest bucket size */ - for (i=0;i<tab->hash_tab_size;i++) { - c=0; - for (b=tab->array[i]; b; b=b->next) { + for (i = 0; i < tab->hash_tab_size; i++) { + for (c = 0, b = tab->array[i]; b; b = b->next) c++; - } if (c > tab->largest_bucket_size) tab->largest_bucket_size = c; } @@ -622,11 +663,16 @@ static void ast_hashtab_resize( struct ast_hashtab *tab) struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab) { /* returns an iterator */ - struct ast_hashtab_iter *it = ast_malloc(sizeof(struct ast_hashtab_iter)); + struct ast_hashtab_iter *it; + + if (!(it = ast_calloc(1, sizeof(*it)))) + return NULL; + it->next = tab->tlist; it->tab = tab; if (tab->do_locking) ast_rwlock_rdlock(&tab->lock); + return it; } @@ -634,11 +680,16 @@ struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab) struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab) { /* returns an iterator */ - struct ast_hashtab_iter *it = ast_malloc(sizeof(struct ast_hashtab_iter)); + struct ast_hashtab_iter *it; + + if (!(it = ast_calloc(1, sizeof(*it)))) + return NULL; + it->next = tab->tlist; it->tab = tab; if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); + return it; } @@ -657,8 +708,9 @@ void *ast_hashtab_next(struct ast_hashtab_iter *it) if (it && it->next) { /* there's a next in the bucket list */ retval = it->next; it->next = retval->tnext; - return (void*)retval->object; + return (void *) retval->object; } + return NULL; } @@ -666,15 +718,13 @@ static void *ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct { const void *obj2; - if (b->prev) { + if (b->prev) b->prev->next = b->next; - } else { + else tab->array[h] = b->next; - } - if (b->next) { + if (b->next) b->next->prev = b->prev; - } tlist_del_item(&(tab->tlist), b); @@ -687,16 +737,16 @@ static void *ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct int c2; struct ast_hashtab_bucket *b2; /* do a little checking */ - for (c2 = 0, b2 = tab->tlist;b2;b2=b2->tnext) { + for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) { c2++; } if (c2 != tab->hash_tab_elements) { printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n", c2, tab->hash_tab_elements); } - for (c2 = 0, b2 = tab->tlist;b2;b2=b2->tnext) { - unsigned int obj3 = (unsigned long)obj2; - unsigned int b3 = (unsigned long)b; + for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) { + unsigned int obj3 = (unsigned long) obj2; + unsigned int b3 = (unsigned long) b; if (b2->object == obj2) printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3); if (b2->next == b) @@ -710,7 +760,7 @@ static void *ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct } } #endif - return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ + return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ } void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj) @@ -721,25 +771,27 @@ void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj) if (!tab || !obj) return 0; + if (tab->do_locking) ast_rwlock_wrlock(&tab->lock); + h = (*tab->hash)(obj) % tab->hash_tab_size; - for (b=tab->array[h]; b; b=b->next) - { + for (b = tab->array[h]; b; b = b->next) { void *obj2; - if ((*tab->compare)(obj,b->object) == 0) { - + if (!(*tab->compare)(obj,b->object)) { obj2 = ast_hashtab_remove_object_internal(tab,b,h); if (tab->do_locking) ast_rwlock_unlock(&tab->lock); - return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ + return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ } } + if (tab->do_locking) ast_rwlock_unlock(&tab->lock); + return 0; } @@ -751,21 +803,22 @@ void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void if (!tab || !obj) return 0; + h = (*tab->hash)(obj) % tab->hash_tab_size; - for (b=tab->array[h]; b; b=b->next) - { + for (b = tab->array[h]; b; b = b->next) { void *obj2; - if ((*tab->compare)(obj,b->object) == 0) { + if (!(*tab->compare)(obj, b->object)) { - obj2 = ast_hashtab_remove_object_internal(tab,b,h); + obj2 = ast_hashtab_remove_object_internal(tab, b, h); if (tab->do_locking) ast_rwlock_unlock(&tab->lock); - return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ + return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ } } + return 0; } @@ -784,23 +837,21 @@ void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj) ast_rwlock_wrlock(&tab->lock); h = (*tab->hash)(obj) % tab->hash_tab_size; - for (b=tab->array[h]; b; b=b->next) - { + for (b = tab->array[h]; b; b = b->next) { const void *obj2; if (obj == b->object) { - - obj2 = ast_hashtab_remove_object_internal(tab,b,h); - + obj2 = ast_hashtab_remove_object_internal(tab, b, h); if (tab->do_locking) ast_rwlock_unlock(&tab->lock); - return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ + return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ } } if (tab->do_locking) ast_rwlock_unlock(&tab->lock); + return 0; } @@ -816,18 +867,16 @@ void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj) return 0; h = (*tab->hash)(obj) % tab->hash_tab_size; - for (b=tab->array[h]; b; b=b->next) - { + for (b = tab->array[h]; b; b = b->next) { const void *obj2; if (obj == b->object) { - - obj2 = ast_hashtab_remove_object_internal(tab,b,h); + obj2 = ast_hashtab_remove_object_internal(tab, b, h); if (tab->do_locking) ast_rwlock_unlock(&tab->lock); - return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ + return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */ } } |