44 static void _ast_hashtab_resize(
struct ast_hashtab *tab,
const char *file,
int lineno,
const char *func);
45 #define ast_hashtab_resize(tab) \
46 _ast_hashtab_resize(tab, __FILE__, __LINE__, __PRETTY_FUNCTION__)
48 static void *ast_hashtab_lookup_internal(
struct ast_hashtab *tab,
const void *obj,
unsigned int h);
59 return strcasecmp(a, b);
64 int ai = *((
int *) a);
65 int bi = *((
int *) b);
75 short as = *((
short *) a);
76 short bs = *((
short *) b);
88 return (loadfactor > 0.75);
112 while (tnum < limit) {
137 int ast_hashtab_newsize_tight(
struct ast_hashtab *tab)
155 unsigned char *str = (
unsigned char *) obj;
158 for (total = 0; *str; str++) {
159 unsigned int tmp = total;
165 total += ((
unsigned int)(*str));
172 const unsigned char *str = obj;
173 unsigned int total = 0, c = 0;
176 total ^= (total << 5) + (total >> 2) + (total << 10) + c;
183 const unsigned char *str = obj;
186 for (total = 0; *str; str++) {
187 unsigned int tmp = total;
188 unsigned int charval = toupper(*str);
205 unsigned int ast_hashtab_hash_int(
const int x)
210 unsigned int ast_hashtab_hash_short(
const short x)
216 struct ast_hashtab *_ast_hashtab_create(
int initial_buckets,
217 int (*
compare)(
const void *a,
const void *b),
220 unsigned int (*
hash)(
const void *obj),
222 const char *file,
int lineno,
const char *
function
227 ht = __ast_calloc(1,
sizeof(*ht), file, lineno,
function);
235 ht->array = __ast_calloc(initial_buckets,
sizeof(*(ht->array)),
236 file, lineno,
function);
266 ht = __ast_calloc(1,
sizeof(*ht), file, lineno, func);
271 ht->array = __ast_calloc(tab->
hash_tab_size,
sizeof(*(ht->array)),
294 void *newobj = (*obj_dup_func)(b->
object);
296 _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func);
325 (*head)->tprev = item;
340 ast_rwlock_wrlock(&tab->lock);
345 ast_rwlock_rdlock(&tab->lock);
355 ast_rwlock_destroy(&tab->lock);
360 ast_rwlock_unlock(&tab->lock);
370 ast_rwlock_wrlock(&tab->lock);
379 if (t->
object && objdestroyfunc) {
383 (*objdestroyfunc)((
void *) t->
object);
392 tab->array[i] = NULL;
394 ast_free(tab->array);
397 ast_rwlock_unlock(&tab->lock);
398 ast_rwlock_destroy(&tab->lock);
404 int _ast_hashtab_insert_immediate(
struct ast_hashtab *tab,
const void *obj,
const char *file,
int lineno,
const char *func)
413 ast_rwlock_wrlock(&tab->lock);
417 res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func);
420 ast_rwlock_unlock(&tab->lock);
425 int _ast_hashtab_insert_immediate_bucket(
struct ast_hashtab *tab,
const void *obj,
unsigned int h,
const char *file,
int lineno,
const char *func)
433 for (c = 0, b = tab->array[h]; b; b= b->
next)
439 b = __ast_calloc(1,
sizeof(*b), file, lineno, func);
445 b->
next = tab->array[h];
451 tlist_add_head(&(tab->
tlist), b);
455 ast_hashtab_resize(tab);
466 unsigned int bucket = 0;
469 ast_rwlock_wrlock(&tab->lock);
472 int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func);
475 ast_rwlock_unlock(&tab->lock);
481 ast_rwlock_unlock(&tab->lock);
496 ast_rwlock_rdlock(&tab->lock);
500 ret = ast_hashtab_lookup_internal(tab,obj,h);
503 ast_rwlock_unlock(&tab->lock);
519 ast_rwlock_rdlock(&tab->lock);
523 ret = ast_hashtab_lookup_internal(tab,obj,h);
526 ast_rwlock_unlock(&tab->lock);
542 ret = ast_hashtab_lookup_internal(tab,obj,h);
549 static void *ast_hashtab_lookup_internal(
struct ast_hashtab *tab,
const void *obj,
unsigned int h)
553 for (b = tab->array[h]; b; b = b->
next) {
567 ast_rwlock_rdlock(&tab->lock);
573 ast_rwlock_unlock(&tab->lock);
591 static void _ast_hashtab_resize(
struct ast_hashtab *tab,
const char *file,
int lineno,
const char *func)
595 int newsize = (*tab->
newsize)(tab), i, c;
608 ast_free(tab->array);
609 tab->array = __ast_calloc(newsize,
sizeof(*(tab->array)), file, lineno, func);
619 for (b = tab->
tlist; b; b = bn) {
623 b->
next = tab->array[h];
630 for (c = 0, b = tab->array[i]; b; b = b->
next)
642 it = __ast_calloc(1,
sizeof(*it), file, lineno, func);
647 it->next = tab->
tlist;
650 ast_rwlock_rdlock(&tab->lock);
661 it = __ast_calloc(1,
sizeof(*it), file, lineno, func);
666 it->next = tab->
tlist;
669 ast_rwlock_wrlock(&tab->lock);
679 ast_rwlock_unlock(&it->tab->lock);
688 if (it && it->next) {
690 it->next = retval->
tnext;
691 return (
void *) retval->
object;
704 tab->array[h] = b->
next;
709 tlist_del_item(&(tab->
tlist), b);
720 for (c2 = 0, b2 = tab->
tlist; b2; b2 = b2->
tnext) {
724 printf(
"Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
727 for (c2 = 0, b2 = tab->
tlist; b2; b2 = b2->
tnext) {
728 unsigned int obj3 = (
unsigned long) obj2;
729 unsigned int b3 = (
unsigned long) b;
731 printf(
"Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
733 printf(
"Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
735 printf(
"Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
737 printf(
"Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
739 printf(
"Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
743 return (
void *) obj2;
755 ast_rwlock_wrlock(&tab->lock);
760 ast_rwlock_unlock(&tab->lock);
775 for (b = tab->array[h]; b; b = b->
next) {
780 obj2 = ast_hashtab_remove_object_internal(tab, b, h);
782 return (
void *) obj2;
800 ast_rwlock_wrlock(&tab->lock);
805 ast_rwlock_unlock(&tab->lock);
822 for (b = tab->array[h]; b; b = b->
next) {
826 obj2 = ast_hashtab_remove_object_internal(tab, b, h);
828 return (
void *) obj2;
int ast_is_prime(int num)
Determines if the specified number is prime.
void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
end the traversal, free the iterator, unlock if necc.
struct ast_hashtab_bucket * tnext
Asterisk locking-related definitions:
Asterisk main include file. File version handling, generic pbx functions.
int ast_hashtab_compare_shorts(const void *a, const void *b)
Compares two shorts for equality.
void * ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
Looks up the object, removes the corresponding bucket.
unsigned int ast_hashtab_hash_string_nocase(const void *obj)
Hashes a string to a number ignoring case.
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
struct ast_hashtab_bucket * tprev
void ast_hashtab_rdlock(struct ast_hashtab *tab)
Request a read-lock on the table – don't change anything!
struct ast_hashtab_iter * _ast_hashtab_start_write_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
Gives an iterator to hastable.
Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk.
int ast_hashtab_newsize_java(struct ast_hashtab *tab)
Create a prime number roughly 2x the current table size.
int ast_hashtab_size(struct ast_hashtab *tab)
Returns the number of elements stored in the hashtab.
struct ast_hashtab_bucket * prev
Definitions to aid in the use of thread local storage.
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% o...
void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
Lookup this object in the hash table.
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.
unsigned int ast_hashtab_hash_string(const void *obj)
Hashes a string to a number.
void ast_hashtab_destroy(struct ast_hashtab *tab, void(*objdestroyfunc)(void *obj))
This func will free the hash table and all its memory.
General Asterisk PBX channel definitions.
int ast_hashtab_compare_ints(const void *a, const void *b)
Compares two integers for equality.
Asterisk internal frame definitions.
struct ast_hashtab * _ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj), const char *file, int lineno, const char *func)
Return a copy of the hash table.
A set of macros to manage forward-linked lists.
int ast_hashtab_capacity(struct ast_hashtab *tab)
Returns the size of the bucket array in the hashtab.
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...
struct ast_hashtab_iter * _ast_hashtab_start_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
Gives an iterator to hastable.
void ast_hashtab_unlock(struct ast_hashtab *tab)
release a read- or write- lock.
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 ...
int(* compare)(const void *a, const void *b)
void * ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
Looks up the object, removes the corresponding bucket.
int(* resize)(struct ast_hashtab *tab)
struct ast_hashtab_bucket * tlist
int ast_hashtab_compare_strings(const void *a, const void *b)
Compares two strings for equality.
an iterator for traversing the buckets
unsigned int(* hash)(const void *obj)
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.
Standard Command Line Interface.
struct ast_hashtab_bucket * next
void ast_hashtab_wrlock(struct ast_hashtab *tab)
Request a write-lock on the table.
void ast_hashtab_destroylock(struct ast_hashtab *tab)
Call this before you destroy the table.
Handy terminal functions for vt* terms.
int ast_hashtab_newsize_none(struct ast_hashtab *tab)
always return current size – no resizing
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.
int(* newsize)(struct ast_hashtab *tab)
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_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...
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.
int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
Compares two strings for equality, ignoring case.
int _ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
Check and insert new object only if it is not there.
void ast_hashtab_initlock(struct ast_hashtab *tab)
Call this after you create the table to init the lock.
int ast_hashtab_resize_none(struct ast_hashtab *tab)
Effectively disables resizing by always returning 0, regardless of of load factor.