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 */
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;
}
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 */
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;
}
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);
total += (charval);
}
+
return total;
}
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;
}
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
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);
}
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;
}
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;
}
/* 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;
}
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);
/* 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;
}
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;
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;
}
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;
}
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;
}
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;
}
{
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);
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)
}
}
#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)
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;
}
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;
}
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;
}
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 */
}
}
projects / asterisk/asterisk.git / commitdiff