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"

Include dependency graph for hashtab.c:

Go to the source code of this file.

Macros
#define	ast_hashtab_resize(tab)   _ast_hashtab_resize(tab, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Functions
struct ast_hashtab *	_ast_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, const char *file, int lineno, const char *function)
	Create the hashtable list. More...
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. More...
int	_ast_hashtab_insert_immediate (struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
	Insert without checking. More...
int	_ast_hashtab_insert_immediate_bucket (struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func)
	Insert without checking, hashing or locking. More...
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. More...
static void	_ast_hashtab_resize (struct ast_hashtab *tab, const char *file, int lineno, const char *func)
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. More...
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. More...
int	ast_hashtab_capacity (struct ast_hashtab *tab)
	Returns the size of the bucket array in the hashtab. More...
int	ast_hashtab_compare_ints (const void *a, const void *b)
	Compares two integers for equality. More...
int	ast_hashtab_compare_shorts (const void *a, const void *b)
	Compares two shorts for equality. More...
int	ast_hashtab_compare_strings (const void *a, const void *b)
	Compares two strings for equality. More...
int	ast_hashtab_compare_strings_nocase (const void *a, const void *b)
	Compares two strings for equality, ignoring case. More...
void	ast_hashtab_destroy (struct ast_hashtab *tab, void(*objdestroyfunc)(void *obj))
	This func will free the hash table and all its memory. More...
void	ast_hashtab_destroylock (struct ast_hashtab *tab)
	Call this before you destroy the table. More...
void	ast_hashtab_end_traversal (struct ast_hashtab_iter *it)
	end the traversal, free the iterator, unlock if necc. More...
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. More...
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. More...
unsigned int	ast_hashtab_hash_string_nocase (const void *obj)
	Hashes a string to a number ignoring case. More...
unsigned int	ast_hashtab_hash_string_sax (const void *obj)
	Hashes a string to a number using a modified Shift-And-XOR algorithm. More...
void	ast_hashtab_initlock (struct ast_hashtab *tab)
	Call this after you create the table to init the lock. More...
void *	ast_hashtab_lookup (struct ast_hashtab *tab, const void *obj)
	Lookup this object in the hash table. More...
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. More...
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. More...
int	ast_hashtab_newsize_java (struct ast_hashtab *tab)
	Create a prime number roughly 2x the current table size. More...
int	ast_hashtab_newsize_none (struct ast_hashtab *tab)
	always return current size – no resizing More...
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. More...
void	ast_hashtab_rdlock (struct ast_hashtab *tab)
	Request a read-lock on the table – don't change anything! More...
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. More...
void *	ast_hashtab_remove_object_via_lookup_nolock (struct ast_hashtab *tab, void *obj)
	Looks up the object, removes the corresponding bucket. More...
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. More...
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. More...
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). More...
int	ast_hashtab_resize_none (struct ast_hashtab *tab)
	Effectively disables resizing by always returning 0, regardless of of load factor. More...
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. More...
int	ast_hashtab_size (struct ast_hashtab *tab)
	Returns the number of elements stored in the hashtab. More...
void	ast_hashtab_unlock (struct ast_hashtab *tab)
	release a read- or write- lock. More...
void	ast_hashtab_wrlock (struct ast_hashtab *tab)
	Request a write-lock on the table. More...
int	ast_is_prime (int num)
	Determines if the specified number is prime. More...
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@.nosp@m.digi.nosp@m.um.co.nosp@m.m

Definition in file hashtab.c.

Macro Definition Documentation

ast_hashtab_resize

#define ast_hashtab_resize

(

tab

)

_ast_hashtab_resize(tab, __FILE__, __LINE__, __PRETTY_FUNCTION__)

Definition at line 45 of file hashtab.c.

Referenced by _ast_hashtab_insert_immediate_bucket().

Function Documentation

_ast_hashtab_create()

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,
		const char *	file,
		int	lineno,
		const char *	function
	)

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

References __ast_calloc(), ast_hashtab::array, ast_free, ast_hashtab_newsize_java(), ast_hashtab_resize_java(), ast_is_prime(), ast_rwlock_init, ast_hashtab::compare, compare(), ast_hashtab::do_locking, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab::newsize, NULL, and ast_hashtab::resize.

{
   struct ast_hashtab *ht;

   ht = __ast_calloc(1, sizeof(*ht), file, lineno, function);
   if (!ht) {
      return NULL;
   }

   while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
      initial_buckets++;

   ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)),
      file, lineno, function);
   if (!ht->array) {
      ast_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;
}

_ast_hashtab_dup()

struct ast_hashtab* _ast_hashtab_dup	(	struct ast_hashtab *	tab,
		void *(*)(const void *obj)	obj_dup_func,
		const char *	file,
		int	lineno,
		const char *	func
	)

Return a copy of the hash table.

Definition at line 261 of file hashtab.c.

References __ast_calloc(), _ast_hashtab_insert_immediate_bucket(), ast_hashtab::array, ast_free, ast_rwlock_init, ast_hashtab::compare, ast_hashtab::do_locking, ast_hashtab::hash, ast_hashtab::hash_tab_size, ast_hashtab::lock, ast_hashtab::newsize, ast_hashtab_bucket::next, NULL, ast_hashtab_bucket::object, and ast_hashtab::resize.

{
   struct ast_hashtab *ht;
   unsigned int i;

   ht = __ast_calloc(1, sizeof(*ht), file, lineno, func);
   if (!ht) {
      return NULL;
   }

   ht->array = __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)),
      file, lineno, func);
   if (!ht->array) {
      ast_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++) {
      struct ast_hashtab_bucket *b = tab->array[i];
      while (b) {
         void *newobj = (*obj_dup_func)(b->object);
         if (newobj) {
            _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func);
         }
         b = b->next;
      }
   }

   return ht;
}

_ast_hashtab_insert_immediate()

int _ast_hashtab_insert_immediate	(	struct ast_hashtab *	tab,
		const void *	obj,
		const char *	file,
		int	lineno,
		const char *	func
	)

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 404 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.

{
   unsigned int h;
   int res=0;

   if (!tab || !obj)
      return res;

   if (tab->do_locking)
      ast_rwlock_wrlock(&tab->lock);

   h = (*tab->hash)(obj) % tab->hash_tab_size;

   res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func);

   if (tab->do_locking)
      ast_rwlock_unlock(&tab->lock);

   return res;
}

_ast_hashtab_insert_immediate_bucket()

int _ast_hashtab_insert_immediate_bucket	(	struct ast_hashtab *	tab,
		const void *	obj,
		unsigned int	h,
		const char *	file,
		int	lineno,
		const char *	func
	)

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

References __ast_calloc(), ast_hashtab::array, ast_hashtab_resize, b, c, ast_hashtab::hash_tab_elements, ast_hashtab::largest_bucket_size, ast_hashtab_bucket::next, ast_hashtab_bucket::object, 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().

{
   int c;
   struct ast_hashtab_bucket *b;

   if (!tab || !obj)
      return 0;

   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_calloc(1, sizeof(*b), file, lineno, func);
   if (!b) {
      return 0;
   }

   b->object = obj;
   b->next = tab->array[h];
   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;
}

_ast_hashtab_insert_safe()

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.

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 460 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.

{
   /* check to see if the element is already there; insert only if
      it is not there. */
   /* 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)) {
      int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func);

      if (tab->do_locking)
         ast_rwlock_unlock(&tab->lock);

      return ret2;
   }

   if (tab->do_locking)
      ast_rwlock_unlock(&tab->lock);

   return 0;
}

_ast_hashtab_resize()

static void _ast_hashtab_resize ( struct ast_hashtab *  tab, const char *  file, int  lineno, const char *  func  )

static

Definition at line 591 of file hashtab.c.

References __ast_calloc(), ast_hashtab::array, ast_free, b, c, 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.

{
   /* this function is called either internally, when the resize func returns 1, or
      externally by the user to force a resize of the hash table */
   int newsize = (*tab->newsize)(tab), i, c;
   unsigned int h;
   struct ast_hashtab_bucket *b,*bn;

   /* Since we keep a DLL of all the buckets in tlist,
      all we have to do is free the array, malloc a new one,
      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
                                 why leave ptrs laying around */
      tab->array[i] = 0; /* erase old ptrs */
   }
   ast_free(tab->array);
   tab->array = __ast_calloc(newsize, sizeof(*(tab->array)), file, lineno, func);
   if (!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) {
      b->prev = 0;
      bn = b->tnext;
      h = (*tab->hash)(b->object) % tab->hash_tab_size;
      b->next = tab->array[h];
      if (b->next)
         b->next->prev = b;
      tab->array[h] = b;
   }
   /* recalc the largest bucket size */
   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;
   }
}

_ast_hashtab_start_traversal()

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.

Definition at line 637 of file hashtab.c.

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

{
   /* returns an iterator */
   struct ast_hashtab_iter *it;

   it = __ast_calloc(1, sizeof(*it), file, lineno, func);
   if (!it) {
      return NULL;
   }

   it->next = tab->tlist;
   it->tab = tab;
   if (tab->do_locking)
      ast_rwlock_rdlock(&tab->lock);

   return it;
}

_ast_hashtab_start_write_traversal()

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.

Definition at line 656 of file hashtab.c.

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

{
   /* returns an iterator */
   struct ast_hashtab_iter *it;

   it = __ast_calloc(1, sizeof(*it), file, lineno, func);
   if (!it) {
      return NULL;
   }

   it->next = tab->tlist;
   it->tab = tab;
   if (tab->do_locking)
      ast_rwlock_wrlock(&tab->lock);

   return it;
}

ast_hashtab_capacity()

int ast_hashtab_capacity

(

struct ast_hashtab *

tab

)

Returns the size of the bucket array in the hashtab.

Definition at line 583 of file hashtab.c.

References ast_hashtab::hash_tab_size.

{
   return tab->hash_tab_size;
}

ast_hashtab_compare_ints()

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

{
   int ai = *((int *) a);
   int bi = *((int *) b);

   if (ai < bi)
      return -1;

   return !(ai == bi);
}

ast_hashtab_compare_shorts()

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

References bs.

{
   short as = *((short *) a);
   short bs = *((short *) b);

   if (as < bs)
      return -1;

   return !(as == bs);
}

ast_hashtab_compare_strings()

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

{
   return strcmp(a, b);
}

ast_hashtab_compare_strings_nocase()

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

Referenced by AST_TEST_DEFINE().

{
   return strcasecmp(a, b);
}

ast_hashtab_destroy()

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

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

Referenced by __ast_internal_context_destroy(), ast_merge_contexts_and_delete(), AST_TEST_DEFINE(), destroy_exten(), pbx_load_module(), and pbx_shutdown().

{
   /* this func will free the hash table and all its memory. It
      doesn't touch the objects stored in it */
   if (tab) {

      if (tab->do_locking)
         ast_rwlock_wrlock(&tab->lock);

      if (tab->array) {
         /* go thru and destroy the buckets */
         struct ast_hashtab_bucket *t;
         int i;

         while (tab->tlist) {
            t = tab->tlist;
            if (t->object && objdestroyfunc) {
               /* I cast this because I'm not going to MOD it, I'm going to DESTROY
                * it.
                */
               (*objdestroyfunc)((void *) t->object);
            }

            tlist_del_item(&(tab->tlist), tab->tlist);
            ast_free(t);
         }

         for (i = 0; i < tab->hash_tab_size; i++) {
            /* Not totally necessary, but best to destroy old pointers */
            tab->array[i] = NULL;
         }
         ast_free(tab->array);
      }
      if (tab->do_locking) {
         ast_rwlock_unlock(&tab->lock);
         ast_rwlock_destroy(&tab->lock);
      }
      ast_free(tab);
   }
}

ast_hashtab_destroylock()

void ast_hashtab_destroylock

(

struct ast_hashtab *

tab

)

Call this before you destroy the table.

Definition at line 353 of file hashtab.c.

References ast_rwlock_destroy, and ast_hashtab::lock.

{
   ast_rwlock_destroy(&tab->lock);
}

ast_hashtab_end_traversal()

void ast_hashtab_end_traversal

(

struct ast_hashtab_iter *

it

)

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

Definition at line 674 of file hashtab.c.

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

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

{
   if (!it)
      return;
   if (it->tab->do_locking)
      ast_rwlock_unlock(&it->tab->lock);
   ast_free(it);
}

ast_hashtab_get_stats()

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

{
   /* returns key stats for the table */
   if (tab->do_locking)
      ast_rwlock_rdlock(&tab->lock);
   *biggest_bucket_size = tab->largest_bucket_size;
   *resize_count = tab->resize_count;
   *num_objects = tab->hash_tab_elements;
   *num_buckets = tab->hash_tab_size;
   if (tab->do_locking)
      ast_rwlock_unlock(&tab->lock);
}

ast_hashtab_hash_int()

unsigned int ast_hashtab_hash_int

(

const int

x

)

Definition at line 205 of file hashtab.c.

Referenced by hashtab_hash_priority().

{
   return x;
}

ast_hashtab_hash_short()

unsigned int ast_hashtab_hash_short

(

const short

x

)

Definition at line 210 of file hashtab.c.

{
   /* hmmmm.... modulus is best < 65535 !! */
   return x;
}

ast_hashtab_hash_string()

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

References str, tmp(), and total.

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

{
   unsigned char *str = (unsigned char *) obj;
   unsigned int total;

   for (total = 0; *str; str++) {
      unsigned int tmp = total;
      total <<= 1; /* multiply by 2 */
      total += tmp; /* multiply by 3 */
      total <<= 2; /* multiply by 12 */
      total += tmp; /* multiply by 13 */

      total += ((unsigned int)(*str));
   }
   return total;
}

ast_hashtab_hash_string_nocase()

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

References str, tmp(), and total.

Referenced by AST_TEST_DEFINE(), and hash_string().

{
   const unsigned char *str = obj;
   unsigned int total;

   for (total = 0; *str; str++) {
      unsigned int tmp = total;
      unsigned int charval = toupper(*str);

      /* hopefully, the following is faster than multiplication by 7 */
      /* why do I go to this bother? A good compiler will do this
         anyway, if I say total *= 13 */
      /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */
      total <<= 1; /* multiply by 2 */
      total += tmp; /* multiply by 3 */
      total <<= 2; /* multiply by 12 */
      total += tmp; /* multiply by 13 */

      total += (charval);
   }

   return total;
}

ast_hashtab_hash_string_sax()

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

References c, str, and total.

{
   const unsigned char *str = obj;
   unsigned int total = 0, c = 0;

   while ((c = *str++))
      total ^= (total << 5) + (total >> 2) + (total << 10) + c;

   return total;
}

ast_hashtab_initlock()

void ast_hashtab_initlock

(

struct ast_hashtab *

tab

)

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

Definition at line 348 of file hashtab.c.

References ast_rwlock_init, and ast_hashtab::lock.

{
   ast_rwlock_init(&tab->lock);
}

ast_hashtab_lookup()

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 486 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(), context_merge(), find_context(), find_context_locked(), hash_test_lookup(), and pbx_find_extension().

{
   /* lookup this object in the hash table. return a ptr if found, or NULL if not */
   unsigned int h;
   void *ret;

   if (!tab || !obj)
      return 0;

   if (tab->do_locking)
      ast_rwlock_rdlock(&tab->lock);

   h = (*tab->hash)(obj) % tab->hash_tab_size;

   ret = ast_hashtab_lookup_internal(tab,obj,h);

   if (tab->do_locking)
      ast_rwlock_unlock(&tab->lock);

   return ret;
}

ast_hashtab_lookup_bucket()

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

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

Referenced by _ast_hashtab_insert_safe().

{
   /* lookup this object in the hash table. return a ptr if found, or NULL if not */
   unsigned int h;
   void *ret;

   if (!tab || !obj)
      return 0;

   h = (*tab->hash)(obj) % tab->hash_tab_size;

   ret = ast_hashtab_lookup_internal(tab,obj,h);

   *bucket = h;

   return ret;
}

ast_hashtab_lookup_internal()

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

static

Definition at line 549 of file hashtab.c.

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

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

{
   struct ast_hashtab_bucket *b;

   for (b = tab->array[h]; b; b = b->next) {
      if (!(*tab->compare)(obj,b->object)) {
         /* I can't touch obj in this func, but the outside world is welcome to */
         return (void*) b->object;
      }
   }

   return NULL;
}

ast_hashtab_lookup_with_hash()

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 509 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.

{
   /* lookup this object in the hash table. return a ptr if found, or NULL if not */
   unsigned int h;
   void *ret;

   if (!tab || !obj)
      return 0;

   if (tab->do_locking)
      ast_rwlock_rdlock(&tab->lock);

   h = hashval % tab->hash_tab_size;

   ret = ast_hashtab_lookup_internal(tab,obj,h);

   if (tab->do_locking)
      ast_rwlock_unlock(&tab->lock);

   return ret;
}

ast_hashtab_newsize_java()

int ast_hashtab_newsize_java

(

struct ast_hashtab *

tab

)

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

Definition at line 127 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

Referenced by _ast_hashtab_create(), ast_add_extension2_lockopt(), ast_context_find_or_create(), AST_TEST_DEFINE(), lua_register_hints(), lua_register_switches(), and pbx_load_module().

{
   int i = (tab->hash_tab_size << 1); /* multiply by two */

   while (!ast_is_prime(i))
      i++;

   return i;
}

ast_hashtab_newsize_none()

int ast_hashtab_newsize_none

(

struct ast_hashtab *

tab

)

always return current size – no resizing

Definition at line 148 of file hashtab.c.

References ast_hashtab::hash_tab_size.

{
   return tab->hash_tab_size;
}

ast_hashtab_newsize_tight()

int ast_hashtab_newsize_tight

(

struct ast_hashtab *

tab

)

Definition at line 137 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

{
   int x = (tab->hash_tab_size << 1);
   int i = (tab->hash_tab_size + x);

   while (!ast_is_prime(i))
      i++;

   return i;
}

ast_hashtab_next()

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

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

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

{
   /* returns the next object in the list, advances iter one step */
   struct ast_hashtab_bucket *retval;

   if (it && it->next) { /* there's a next in the bucket list */
      retval = it->next;
      it->next = retval->tnext;
      return (void *) retval->object;
   }

   return NULL;
}

ast_hashtab_rdlock()

void ast_hashtab_rdlock

(

struct ast_hashtab *

tab

)

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

Definition at line 343 of file hashtab.c.

References ast_rwlock_rdlock, and ast_hashtab::lock.

{
   ast_rwlock_rdlock(&tab->lock);
}

ast_hashtab_remove_object_internal()

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

static

Definition at line 697 of file hashtab.c.

References ast_hashtab::array, ast_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().

{
   const void *obj2;

   if (b->prev)
      b->prev->next = b->next;
   else
      tab->array[h] = b->next;

   if (b->next)
      b->next->prev = b->prev;

   tlist_del_item(&(tab->tlist), b);

   obj2 = b->object;
   b->object = b->next = (void*)2;
   ast_free(b); /* free up the hashbucket */
   tab->hash_tab_elements--;
#ifdef DEBUG
   {
      int c2;
      struct ast_hashtab_bucket *b2;
      /* do a little checking */
      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;
         if (b2->object == obj2)
            printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
         if (b2->next == b)
            printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
         if (b2->prev == b)
            printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
         if (b2->tprev == b)
            printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
         if (b2->tnext == b)
            printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
      }
   }
#endif
   return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
}

ast_hashtab_remove_object_via_lookup()

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

Looks up the object, removes the corresponding bucket.

Definition at line 746 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.

Referenced by add_priority(), and hash_test_shrink().

{
   /* looks up the object; removes the corresponding bucket */
   const void *obj2;

   if (!tab || !obj)
      return 0;

   if (tab->do_locking)
      ast_rwlock_wrlock(&tab->lock);

   obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj);

   if (tab->do_locking)
      ast_rwlock_unlock(&tab->lock);

   return (void *)obj2;
}

ast_hashtab_remove_object_via_lookup_nolock()

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

References ast_hashtab::array, ast_hashtab_remove_object_internal(), b, 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().

{
   /* looks up the object; removes the corresponding bucket */
   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)) {
         const void *obj2;

         obj2 = ast_hashtab_remove_object_internal(tab, b, h);

         return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
      }
   }

   return 0;
}

ast_hashtab_remove_this_object()

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 789 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_add_extension2_lockopt(), and ast_context_remove_extension_callerid2().

{
   /* looks up the object by hash and then comparing pts in bucket list instead of
      calling the compare routine; removes the bucket -- a slightly cheaper operation */
   /* looks up the object; removes the corresponding bucket */
   const void *obj2;

   if (!tab || !obj)
      return 0;

   if (tab->do_locking)
      ast_rwlock_wrlock(&tab->lock);

   obj2 = ast_hashtab_remove_this_object_nolock(tab,obj);

   if (tab->do_locking)
      ast_rwlock_unlock(&tab->lock);

   return (void *)obj2;
}

ast_hashtab_remove_this_object_nolock()

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

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

Referenced by ast_hashtab_remove_this_object().

{
   /* looks up the object by hash and then comparing pts in bucket list instead of
      calling the compare routine; removes the bucket -- a slightly cheaper operation */
   /* looks up the object; removes the corresponding bucket */
   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 (obj == b->object) {
         const void *obj2;
         obj2 = ast_hashtab_remove_object_internal(tab, b, h);

         return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
      }
   }

   return 0;
}

ast_hashtab_resize_java()

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

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

Referenced by _ast_hashtab_create(), ast_add_extension2_lockopt(), ast_context_find_or_create(), AST_TEST_DEFINE(), lua_register_hints(), lua_register_switches(), and pbx_load_module().

{
   double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;

   return (loadfactor > 0.75);
}

ast_hashtab_resize_none()

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

{
   return 0;
}

ast_hashtab_resize_tight()

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

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

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

ast_hashtab_size()

int ast_hashtab_size

(

struct ast_hashtab *

tab

)

Returns the number of elements stored in the hashtab.

Definition at line 577 of file hashtab.c.

References ast_hashtab::hash_tab_elements.

Referenced by ast_context_remove_extension_callerid2(), and AST_TEST_DEFINE().

{
   return tab->hash_tab_elements;
}

ast_hashtab_unlock()

void ast_hashtab_unlock

(

struct ast_hashtab *

tab

)

release a read- or write- lock.

Definition at line 358 of file hashtab.c.

References ast_rwlock_unlock, and ast_hashtab::lock.

{
   ast_rwlock_unlock(&tab->lock);
}

ast_hashtab_wrlock()

void ast_hashtab_wrlock

(

struct ast_hashtab *

tab

)

Request a write-lock on the table.

Definition at line 338 of file hashtab.c.

References ast_rwlock_wrlock, and ast_hashtab::lock.

{
   ast_rwlock_wrlock(&tab->lock);
}

ast_is_prime()

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

Referenced by _ast_hashtab_create(), ast_hashtab_newsize_java(), ast_hashtab_newsize_tight(), and sorcery_config_internal_load().

{
   int tnum, limit;

   if (!(num & 0x1)) /* even number -- not prime */
      return 0;

   /* Loop through ODD numbers starting with 3 */

   tnum = 3;
   limit = num;
   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;
   }

   /* if we made it through the loop, the number is a prime */
   return 1;
}

tlist_add_head()

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

static

Definition at line 320 of file hashtab.c.

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

Referenced by _ast_hashtab_insert_immediate_bucket().

{
   if (*head) {
      item->tnext = *head;
      item->tprev = NULL;
      (*head)->tprev = item;
      *head = item;
   } else {
      /* the list is empty */
      *head = item;
      item->tprev = NULL;
      item->tnext = NULL;
   }
}

tlist_del_item()

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

static

Definition at line 305 of file hashtab.c.

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

Referenced by ast_hashtab_destroy(), and ast_hashtab_remove_object_internal().

{
   /* item had better be in the list! or suffer the weirdness that occurs, later! */
   if (*head == item) { /* first item in the list */
      *head = item->tnext;
      if (item->tnext)
         item->tnext->tprev = NULL;
   } else {
      /* short circuit stuff */
      item->tprev->tnext = item->tnext;
      if (item->tnext)
         item->tnext->tprev = item->tprev;
   }
}