Wed Jan 8 2020 09:50:13

Asterisk developer's documentation


hashtab.c File Reference

code to implement generic hash tables More...

#include "asterisk.h"
#include <ctype.h>
#include "asterisk/lock.h"
#include "asterisk/frame.h"
#include "asterisk/channel.h"
#include "asterisk/cli.h"
#include "asterisk/term.h"
#include "asterisk/utils.h"
#include "asterisk/threadstorage.h"
#include "asterisk/linkedlists.h"
#include "asterisk/hashtab.h"

Go to the source code of this file.

Functions

int ast_hashtab_capacity (struct ast_hashtab *tab)
 Returns the size of the bucket array in the hashtab. 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...
 
struct ast_hashtabast_hashtab_create (int initial_buckets, int(*compare)(const void *a, const void *b), int(*resize)(struct ast_hashtab *), int(*newsize)(struct ast_hashtab *tab), unsigned int(*hash)(const void *obj), int do_locking)
 Create the hashtable list. 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...
 
struct ast_hashtabast_hashtab_dup (struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj))
 Return a copy of the hash 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...
 
int ast_hashtab_insert_immediate (struct ast_hashtab *tab, const void *obj)
 Insert without checking. More...
 
int ast_hashtab_insert_immediate_bucket (struct ast_hashtab *tab, const void *obj, unsigned int h)
 Insert without checking, hashing or locking. More...
 
int ast_hashtab_insert_safe (struct ast_hashtab *tab, const void *obj)
 Check and insert new object only if it is not there. 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...
 
static void ast_hashtab_resize (struct ast_hashtab *tab)
 
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...
 
struct ast_hashtab_iterast_hashtab_start_traversal (struct ast_hashtab *tab)
 Gives an iterator to hastable. More...
 
struct ast_hashtab_iterast_hashtab_start_write_traversal (struct ast_hashtab *tab)
 Gives an iterator to hastable. 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.

Function Documentation

int ast_hashtab_capacity ( struct ast_hashtab tab)

Returns the size of the bucket array in the hashtab.

Definition at line 631 of file hashtab.c.

References ast_hashtab::hash_tab_size.

632 {
633  return tab->hash_tab_size;
634 }
int hash_tab_size
Definition: hashtab.h:94
int ast_hashtab_compare_ints ( const void *  a,
const void *  b 
)

Compares two integers for equality.

Parameters
aan integer pointer (int *)
ban integer pointer (int *)
Return values
0if the integers pointed to are equal
1if a is greater than b
-1if a is less than b

Definition at line 66 of file hashtab.c.

67 {
68  int ai = *((int *) a);
69  int bi = *((int *) b);
70 
71  if (ai < bi)
72  return -1;
73 
74  return !(ai == bi);
75 }
int ast_hashtab_compare_shorts ( const void *  a,
const void *  b 
)

Compares two shorts for equality.

Parameters
aa short pointer (short *)
ba short pointer (short *)
Return values
0if the shorts pointed to are equal
1if a is greater than b
-1if a is less than b

Definition at line 77 of file hashtab.c.

78 {
79  short as = *((short *) a);
80  short bs = *((short *) b);
81 
82  if (as < bs)
83  return -1;
84 
85  return !(as == bs);
86 }
int ast_hashtab_compare_strings ( const void *  a,
const void *  b 
)

Compares two strings for equality.

Parameters
aa character string
ba character string
Return values
0if the strings match
<0if string a is less than string b
>0if string a is greather than string b

Definition at line 56 of file hashtab.c.

57 {
58  return strcmp(a, b);
59 }
int ast_hashtab_compare_strings_nocase ( const void *  a,
const void *  b 
)

Compares two strings for equality, ignoring case.

Parameters
aa character string
ba character string
Return values
0if the strings match
<0if string a is less than string b
>0if string a is greather than string b

Definition at line 61 of file hashtab.c.

62 {
63  return strcasecmp(a, b);
64 }
struct ast_hashtab* ast_hashtab_create ( int  initial_buckets,
int(*)(const void *a, const void *b)  compare,
int(*)(struct ast_hashtab *)  resize,
int(*)(struct ast_hashtab *tab)  newsize,
unsigned int(*)(const void *obj)  hash,
int  do_locking 
)

Create the hashtable list.

Parameters
initial_bucketsstarting number of buckets
comparea func ptr to compare two elements in the hash – cannot be null
resizea func ptr to decide if the table needs to be resized, a NULL ptr here will cause a default to be used
newsizea func ptr that returns a new size of the array. A NULL will cause a default to be used
hasha func ptr to do the hashing
do_lockinguse locks to guarantee safety of iterators/insertion/deletion – real simpleminded right now

Definition at line 226 of file hashtab.c.

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

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

236 {
237  struct ast_hashtab *ht;
238 
239 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
240  if (!(ht = __ast_calloc(1, sizeof(*ht), file, lineno, function)))
241 #else
242  if (!(ht = ast_calloc(1, sizeof(*ht))))
243 #endif
244  return NULL;
245 
246  while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
247  initial_buckets++;
248 
249 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
250  if (!(ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)), file, lineno, function))) {
251 #else
252  if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) {
253 #endif
254  free(ht);
255  return NULL;
256  }
257 
258  ht->hash_tab_size = initial_buckets;
259  ht->compare = compare;
260  ht->resize = resize;
261  ht->newsize = newsize;
262  ht->hash = hash;
263  ht->do_locking = do_locking;
264 
265  if (do_locking)
266  ast_rwlock_init(&ht->lock);
267 
268  if (!ht->resize)
270 
271  if (!ht->newsize)
273 
274  return ht;
275 }
int ast_hashtab_newsize_java(struct ast_hashtab *tab)
Create a prime number roughly 2x the current table size.
Definition: hashtab.c:131
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func)
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...
Definition: hashtab.c:88
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
int do_locking
Definition: hashtab.h:99
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90
#define free(a)
Definition: astmm.h:94
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:190
#define ast_calloc(a, b)
Definition: astmm.h:82
static int compare(const char *text, const char *template)
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:105
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 388 of file hashtab.c.

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

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

389 {
390  /* this func will free the hash table and all its memory. It
391  doesn't touch the objects stored in it */
392  if (tab) {
393 
394  if (tab->do_locking)
395  ast_rwlock_wrlock(&tab->lock);
396 
397  if (tab->array) {
398  /* go thru and destroy the buckets */
399  struct ast_hashtab_bucket *t;
400  int i;
401 
402  while (tab->tlist) {
403  t = tab->tlist;
404  if (t->object && objdestroyfunc) {
405  /* I cast this because I'm not going to MOD it, I'm going to DESTROY
406  * it.
407  */
408  (*objdestroyfunc)((void *) t->object);
409  }
410 
411  tlist_del_item(&(tab->tlist), tab->tlist);
412  free(t);
413  }
414 
415  for (i = 0; i < tab->hash_tab_size; i++) {
416  /* Not totally necessary, but best to destroy old pointers */
417  tab->array[i] = NULL;
418  }
419  free(tab->array);
420  }
421  if (tab->do_locking) {
422  ast_rwlock_unlock(&tab->lock);
423  ast_rwlock_destroy(&tab->lock);
424  }
425  free(tab);
426  }
427 }
int hash_tab_size
Definition: hashtab.h:94
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:199
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:200
int do_locking
Definition: hashtab.h:99
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
#define free(a)
Definition: astmm.h:94
static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:330
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
#define ast_rwlock_wrlock(a)
Definition: lock.h:202
const void * object
Definition: hashtab.h:76
void ast_hashtab_destroylock ( struct ast_hashtab tab)

Call this before you destroy the table.

Definition at line 378 of file hashtab.c.

References ast_rwlock_destroy, and ast_hashtab::lock.

379 {
380  ast_rwlock_destroy(&tab->lock);
381 }
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:199
ast_rwlock_t lock
Definition: hashtab.h:101
struct ast_hashtab* ast_hashtab_dup ( struct ast_hashtab tab,
void *(*)(const void *obj)  obj_dup_func 
)

Return a copy of the hash table.

Definition at line 280 of file hashtab.c.

References __ast_calloc(), ast_hashtab::array, ast_calloc, ast_hashtab_insert_immediate_bucket(), ast_rwlock_init, ast_hashtab::compare, ast_hashtab::do_locking, free, ast_hashtab::hash, ast_hashtab::hash_tab_size, if(), ast_hashtab::lock, ast_hashtab::newsize, ast_hashtab_bucket::next, ast_hashtab_bucket::object, and ast_hashtab::resize.

282 {
283  struct ast_hashtab *ht;
284  unsigned int i;
285 
286  if (!(ht = ast_calloc(1, sizeof(*ht))))
287  return NULL;
288 
289  if (!(ht->array =
290 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
291  __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)), file, lineno, func)
292 #else
293  ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)))
294 #endif
295  )) {
296  free(ht);
297  return NULL;
298  }
299 
300  ht->hash_tab_size = tab->hash_tab_size;
301  ht->compare = tab->compare;
302  ht->resize = tab->resize;
303  ht->newsize = tab->newsize;
304  ht->hash = tab->hash;
305  ht->do_locking = tab->do_locking;
306 
307  if (ht->do_locking)
308  ast_rwlock_init(&ht->lock);
309 
310  /* now, dup the objects in the buckets and get them into the table */
311  /* the fast way is to use the existing array index, and not have to hash
312  the objects again */
313  for (i = 0; i < ht->hash_tab_size; i++) {
314  struct ast_hashtab_bucket *b = tab->array[i];
315  while (b) {
316  void *newobj = (*obj_dup_func)(b->object);
317  if (newobj)
318 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
319  _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func);
320 #else
322 #endif
323  b = b->next;
324  }
325  }
326 
327  return ht;
328 }
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func)
int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h)
Insert without checking, hashing or locking.
Definition: hashtab.c:461
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
int do_locking
Definition: hashtab.h:99
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90
#define free(a)
Definition: astmm.h:94
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:190
if(yyss+yystacksize-1<=yyssp)
Definition: ast_expr2.c:1874
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
#define ast_calloc(a, b)
Definition: astmm.h:82
void ast_hashtab_end_traversal ( struct ast_hashtab_iter it)

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

Definition at line 746 of file hashtab.c.

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

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

747 {
748  if (it->tab->do_locking)
749  ast_rwlock_unlock(&it->tab->lock);
750  free(it);
751 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:200
int do_locking
Definition: hashtab.h:99
struct ast_hashtab * tab
Definition: hashtab.h:107
#define free(a)
Definition: astmm.h:94
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 611 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().

612 {
613  /* returns key stats for the table */
614  if (tab->do_locking)
615  ast_rwlock_rdlock(&tab->lock);
616  *biggest_bucket_size = tab->largest_bucket_size;
617  *resize_count = tab->resize_count;
618  *num_objects = tab->hash_tab_elements;
619  *num_buckets = tab->hash_tab_size;
620  if (tab->do_locking)
621  ast_rwlock_unlock(&tab->lock);
622 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:201
int hash_tab_size
Definition: hashtab.h:94
int largest_bucket_size
Definition: hashtab.h:96
ast_rwlock_t lock
Definition: hashtab.h:101
int resize_count
Definition: hashtab.h:97
#define ast_rwlock_unlock(a)
Definition: lock.h:200
int do_locking
Definition: hashtab.h:99
int hash_tab_elements
Definition: hashtab.h:95
unsigned int ast_hashtab_hash_int ( const int  x)

Definition at line 209 of file hashtab.c.

Referenced by hashtab_hash_priority().

210 {
211  return x;
212 }
unsigned int ast_hashtab_hash_short ( const short  x)

Definition at line 214 of file hashtab.c.

215 {
216  /* hmmmm.... modulus is best < 65535 !! */
217  return x;
218 }
unsigned int ast_hashtab_hash_string ( const void *  obj)

Hashes a string to a number.

Parameters
objthe 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 157 of file hashtab.c.

References str, and total.

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

158 {
159  unsigned char *str = (unsigned char *) obj;
160  unsigned int total;
161 
162  for (total = 0; *str; str++) {
163  unsigned int tmp = total;
164  total <<= 1; /* multiply by 2 */
165  total += tmp; /* multiply by 3 */
166  total <<= 2; /* multiply by 12 */
167  total += tmp; /* multiply by 13 */
168 
169  total += ((unsigned int)(*str));
170  }
171  return total;
172 }
const char * str
Definition: app_jack.c:144
static int total
Definition: res_adsi.c:967
unsigned int ast_hashtab_hash_string_nocase ( const void *  obj)

Hashes a string to a number ignoring case.

Parameters
objthe 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 185 of file hashtab.c.

References str, and total.

186 {
187  const unsigned char *str = obj;
188  unsigned int total;
189 
190  for (total = 0; *str; str++) {
191  unsigned int tmp = total;
192  unsigned int charval = toupper(*str);
193 
194  /* hopefully, the following is faster than multiplication by 7 */
195  /* why do I go to this bother? A good compiler will do this
196  anyway, if I say total *= 13 */
197  /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */
198  total <<= 1; /* multiply by 2 */
199  total += tmp; /* multiply by 3 */
200  total <<= 2; /* multiply by 12 */
201  total += tmp; /* multiply by 13 */
202 
203  total += (charval);
204  }
205 
206  return total;
207 }
const char * str
Definition: app_jack.c:144
static int total
Definition: res_adsi.c:967
unsigned int ast_hashtab_hash_string_sax ( const void *  obj)

Hashes a string to a number using a modified Shift-And-XOR algorithm.

Parameters
objthe string to hash
Returns
Integer has of the specified string
See Also
ast_hastable_hash_string
ast_hastable_hash_string_nocase

Definition at line 174 of file hashtab.c.

References str, and total.

175 {
176  const unsigned char *str = obj;
177  unsigned int total = 0, c = 0;
178 
179  while ((c = *str++))
180  total ^= (total << 5) + (total >> 2) + (total << 10) + c;
181 
182  return total;
183 }
const char * str
Definition: app_jack.c:144
static int total
Definition: res_adsi.c:967
void ast_hashtab_initlock ( struct ast_hashtab tab)

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

Definition at line 373 of file hashtab.c.

References ast_rwlock_init, and ast_hashtab::lock.

374 {
375  ast_rwlock_init(&tab->lock);
376 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:190
int ast_hashtab_insert_immediate ( struct ast_hashtab tab,
const void *  obj 
)

Insert without checking.

Parameters
tab
objNormally, 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
1on success
0if there's a problem

Definition at line 432 of file hashtab.c.

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

Referenced by ast_context_find_or_create(), and ast_context_remove_extension_callerid2().

434 {
435  unsigned int h;
436  int res=0;
437 
438  if (!tab || !obj)
439  return res;
440 
441  if (tab->do_locking)
442  ast_rwlock_wrlock(&tab->lock);
443 
444  h = (*tab->hash)(obj) % tab->hash_tab_size;
445 
446 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
447  res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func);
448 #else
449  res = ast_hashtab_insert_immediate_bucket(tab, obj, h);
450 #endif
451 
452  if (tab->do_locking)
453  ast_rwlock_unlock(&tab->lock);
454 
455  return res;
456 }
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h)
Insert without checking, hashing or locking.
Definition: hashtab.c:461
#define ast_rwlock_unlock(a)
Definition: lock.h:200
int do_locking
Definition: hashtab.h:99
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
#define ast_rwlock_wrlock(a)
Definition: lock.h:202
int ast_hashtab_insert_immediate_bucket ( struct ast_hashtab tab,
const void *  obj,
unsigned int  h 
)

Insert without checking, hashing or locking.

Parameters
tab
obj
hhashed index value
Note
Will force a resize if the resize func returns 1
Return values
1on success
0if there's a problem

Definition at line 461 of file hashtab.c.

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

463 {
464  int c;
465  struct ast_hashtab_bucket *b;
466 
467  if (!tab || !obj)
468  return 0;
469 
470  for (c = 0, b = tab->array[h]; b; b= b->next)
471  c++;
472 
473  if (c + 1 > tab->largest_bucket_size)
474  tab->largest_bucket_size = c + 1;
475 
476  if (!(b =
477 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
478  __ast_calloc(1, sizeof(*b), file, lineno, func)
479 #else
480  ast_calloc(1, sizeof(*b))
481 #endif
482  )) return 0;
483 
484  b->object = obj;
485  b->next = tab->array[h];
486  tab->array[h] = b;
487 
488  if (b->next)
489  b->next->prev = b;
490 
491  tlist_add_head(&(tab->tlist), b);
492  tab->hash_tab_elements++;
493 
494  if ((*tab->resize)(tab))
495  ast_hashtab_resize(tab);
496 
497  return 1;
498 }
int largest_bucket_size
Definition: hashtab.h:96
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func)
struct ast_hashtab_bucket * prev
Definition: hashtab.h:78
static void ast_hashtab_resize(struct ast_hashtab *tab)
Definition: hashtab.c:642
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:345
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
#define ast_calloc(a, b)
Definition: astmm.h:82
int hash_tab_elements
Definition: hashtab.h:95
int ast_hashtab_insert_safe ( struct ast_hashtab tab,
const void *  obj 
)

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

Note
Will force a resize if the resize func returns 1
Return values
1on success
0if there's a problem, or it's already there.

Definition at line 503 of file hashtab.c.

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

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

505 {
506  /* check to see if the element is already there; insert only if
507  it is not there. */
508  /* will force a resize if the resize func returns 1 */
509  /* returns 1 on success, 0 if there's a problem, or it's already there. */
510  unsigned int bucket = 0;
511 
512  if (tab->do_locking)
513  ast_rwlock_wrlock(&tab->lock);
514 
515  if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
516 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
517  int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func);
518 #else
519  int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket);
520 #endif
521 
522  if (tab->do_locking)
523  ast_rwlock_unlock(&tab->lock);
524 
525  return ret2;
526  }
527 
528  if (tab->do_locking)
529  ast_rwlock_unlock(&tab->lock);
530 
531  return 0;
532 }
ast_rwlock_t lock
Definition: hashtab.h:101
int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h)
Insert without checking, hashing or locking.
Definition: hashtab.c:461
#define ast_rwlock_unlock(a)
Definition: lock.h:200
int do_locking
Definition: hashtab.h:99
#define ast_rwlock_wrlock(a)
Definition: lock.h:202
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.
Definition: hashtab.c:579
void* ast_hashtab_lookup ( struct ast_hashtab tab,
const void *  obj 
)

Lookup this object in the hash table.

Parameters
tab
obj
Return values
aptr if found
NULLif not found

Definition at line 534 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(), ast_sched_del(), ast_sched_find_data(), ast_sched_when(), context_merge(), find_context(), find_context_locked(), and pbx_find_extension().

535 {
536  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
537  unsigned int h;
538  void *ret;
539 
540  if (!tab || !obj)
541  return 0;
542 
543  if (tab->do_locking)
544  ast_rwlock_rdlock(&tab->lock);
545 
546  h = (*tab->hash)(obj) % tab->hash_tab_size;
547 
548  ret = ast_hashtab_lookup_internal(tab,obj,h);
549 
550  if (tab->do_locking)
551  ast_rwlock_unlock(&tab->lock);
552 
553  return ret;
554 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:201
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:200
static void * ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
Definition: hashtab.c:597
int do_locking
Definition: hashtab.h:99
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
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 579 of file hashtab.c.

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

Referenced by ast_hashtab_insert_safe().

580 {
581  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
582  unsigned int h;
583  void *ret;
584 
585  if (!tab || !obj)
586  return 0;
587 
588  h = (*tab->hash)(obj) % tab->hash_tab_size;
589 
590  ret = ast_hashtab_lookup_internal(tab,obj,h);
591 
592  *bucket = h;
593 
594  return ret;
595 }
int hash_tab_size
Definition: hashtab.h:94
static void * ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
Definition: hashtab.c:597
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
static void * ast_hashtab_lookup_internal ( struct ast_hashtab tab,
const void *  obj,
unsigned int  h 
)
static

Definition at line 597 of file hashtab.c.

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

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

598 {
599  struct ast_hashtab_bucket *b;
600 
601  for (b = tab->array[h]; b; b = b->next) {
602  if (!(*tab->compare)(obj,b->object)) {
603  /* I can't touch obj in this func, but the outside world is welcome to */
604  return (void*) b->object;
605  }
606  }
607 
608  return NULL;
609 }
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
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 557 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.

558 {
559  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
560  unsigned int h;
561  void *ret;
562 
563  if (!tab || !obj)
564  return 0;
565 
566  if (tab->do_locking)
567  ast_rwlock_rdlock(&tab->lock);
568 
569  h = hashval % tab->hash_tab_size;
570 
571  ret = ast_hashtab_lookup_internal(tab,obj,h);
572 
573  if (tab->do_locking)
574  ast_rwlock_unlock(&tab->lock);
575 
576  return ret;
577 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:201
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:200
static void * ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
Definition: hashtab.c:597
int do_locking
Definition: hashtab.h:99
int ast_hashtab_newsize_java ( struct ast_hashtab tab)

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

Definition at line 131 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

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

132 {
133  int i = (tab->hash_tab_size << 1); /* multiply by two */
134 
135  while (!ast_is_prime(i))
136  i++;
137 
138  return i;
139 }
int hash_tab_size
Definition: hashtab.h:94
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:105
int ast_hashtab_newsize_none ( struct ast_hashtab tab)

always return current size – no resizing

Definition at line 152 of file hashtab.c.

References ast_hashtab::hash_tab_size.

153 {
154  return tab->hash_tab_size;
155 }
int hash_tab_size
Definition: hashtab.h:94
int ast_hashtab_newsize_tight ( struct ast_hashtab tab)

Definition at line 141 of file hashtab.c.

References ast_is_prime(), and ast_hashtab::hash_tab_size.

142 {
143  int x = (tab->hash_tab_size << 1);
144  int i = (tab->hash_tab_size + x);
145 
146  while (!ast_is_prime(i))
147  i++;
148 
149  return i;
150 }
int hash_tab_size
Definition: hashtab.h:94
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:105
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 753 of file hashtab.c.

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

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

754 {
755  /* returns the next object in the list, advances iter one step */
756  struct ast_hashtab_bucket *retval;
757 
758  if (it && it->next) { /* there's a next in the bucket list */
759  retval = it->next;
760  it->next = retval->tnext;
761  return (void *) retval->object;
762  }
763 
764  return NULL;
765 }
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
struct ast_hashtab_bucket * next
Definition: hashtab.h:108
const void * object
Definition: hashtab.h:76
void ast_hashtab_rdlock ( struct ast_hashtab tab)

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

Definition at line 368 of file hashtab.c.

References ast_rwlock_rdlock, and ast_hashtab::lock.

369 {
370  ast_rwlock_rdlock(&tab->lock);
371 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:201
ast_rwlock_t lock
Definition: hashtab.h:101
static void* ast_hashtab_remove_object_internal ( struct ast_hashtab tab,
struct ast_hashtab_bucket b,
int  h 
)
static

Definition at line 767 of file hashtab.c.

References ast_hashtab::array, free, ast_hashtab::hash_tab_elements, ast_hashtab_bucket::next, ast_hashtab_bucket::object, ast_hashtab_bucket::prev, ast_hashtab::tlist, tlist_del_item(), ast_hashtab_bucket::tnext, and ast_hashtab_bucket::tprev.

Referenced by ast_hashtab_remove_object_via_lookup_nolock(), and ast_hashtab_remove_this_object_nolock().

768 {
769  const void *obj2;
770 
771  if (b->prev)
772  b->prev->next = b->next;
773  else
774  tab->array[h] = b->next;
775 
776  if (b->next)
777  b->next->prev = b->prev;
778 
779  tlist_del_item(&(tab->tlist), b);
780 
781  obj2 = b->object;
782  b->object = b->next = (void*)2;
783  free(b); /* free up the hashbucket */
784  tab->hash_tab_elements--;
785 #ifdef DEBUG
786  {
787  int c2;
788  struct ast_hashtab_bucket *b2;
789  /* do a little checking */
790  for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
791  c2++;
792  }
793  if (c2 != tab->hash_tab_elements) {
794  printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
795  c2, tab->hash_tab_elements);
796  }
797  for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
798  unsigned int obj3 = (unsigned long) obj2;
799  unsigned int b3 = (unsigned long) b;
800  if (b2->object == obj2)
801  printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
802  if (b2->next == b)
803  printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
804  if (b2->prev == b)
805  printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
806  if (b2->tprev == b)
807  printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
808  if (b2->tnext == b)
809  printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
810  }
811  }
812 #endif
813  return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
814 }
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
struct ast_hashtab_bucket * tprev
Definition: hashtab.h:80
struct ast_hashtab_bucket * prev
Definition: hashtab.h:78
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
#define free(a)
Definition: astmm.h:94
static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:330
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
int hash_tab_elements
Definition: hashtab.h:95
void* ast_hashtab_remove_object_via_lookup ( struct ast_hashtab tab,
void *  obj 
)

Looks up the object, removes the corresponding bucket.

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

817 {
818  /* looks up the object; removes the corresponding bucket */
819  const void *obj2;
820 
821  if (!tab || !obj)
822  return 0;
823 
824  if (tab->do_locking)
825  ast_rwlock_wrlock(&tab->lock);
826 
828 
829  if (tab->do_locking)
830  ast_rwlock_unlock(&tab->lock);
831 
832  return (void *)obj2;
833 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:200
void * ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
Looks up the object, removes the corresponding bucket.
Definition: hashtab.c:835
int do_locking
Definition: hashtab.h:99
#define ast_rwlock_wrlock(a)
Definition: lock.h:202
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 835 of file hashtab.c.

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

Referenced by ast_hashtab_remove_object_via_lookup().

836 {
837  /* looks up the object; removes the corresponding bucket */
838  unsigned int h;
839  struct ast_hashtab_bucket *b;
840 
841  if (!tab || !obj)
842  return 0;
843 
844  h = (*tab->hash)(obj) % tab->hash_tab_size;
845  for (b = tab->array[h]; b; b = b->next) {
846 
847  if (!(*tab->compare)(obj, b->object)) {
848  const void *obj2;
849 
850  obj2 = ast_hashtab_remove_object_internal(tab, b, h);
851 
852  return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
853  }
854  }
855 
856  return 0;
857 }
int hash_tab_size
Definition: hashtab.h:94
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
static void * ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
Definition: hashtab.c:767
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
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 859 of file hashtab.c.

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

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

860 {
861  /* looks up the object by hash and then comparing pts in bucket list instead of
862  calling the compare routine; removes the bucket -- a slightly cheaper operation */
863  /* looks up the object; removes the corresponding bucket */
864  const void *obj2;
865 
866  if (!tab || !obj)
867  return 0;
868 
869  if (tab->do_locking)
870  ast_rwlock_wrlock(&tab->lock);
871 
873 
874  if (tab->do_locking)
875  ast_rwlock_unlock(&tab->lock);
876 
877  return (void *)obj2;
878 }
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...
Definition: hashtab.c:880
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:200
int do_locking
Definition: hashtab.h:99
#define ast_rwlock_wrlock(a)
Definition: lock.h:202
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 880 of file hashtab.c.

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

Referenced by ast_hashtab_remove_this_object().

881 {
882  /* looks up the object by hash and then comparing pts in bucket list instead of
883  calling the compare routine; removes the bucket -- a slightly cheaper operation */
884  /* looks up the object; removes the corresponding bucket */
885  unsigned int h;
886  struct ast_hashtab_bucket *b;
887 
888  if (!tab || !obj)
889  return 0;
890 
891  h = (*tab->hash)(obj) % tab->hash_tab_size;
892  for (b = tab->array[h]; b; b = b->next) {
893 
894  if (obj == b->object) {
895  const void *obj2;
896  obj2 = ast_hashtab_remove_object_internal(tab, b, h);
897 
898  return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
899  }
900  }
901 
902  return 0;
903 }
int hash_tab_size
Definition: hashtab.h:94
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
static void * ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
Definition: hashtab.c:767
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
static void ast_hashtab_resize ( struct ast_hashtab tab)
static

Definition at line 642 of file hashtab.c.

References __ast_calloc(), ast_hashtab::array, ast_calloc, free, ast_hashtab::hash, ast_hashtab::hash_tab_size, if(), ast_hashtab::largest_bucket_size, ast_hashtab::newsize, ast_hashtab_bucket::next, ast_hashtab_bucket::object, ast_hashtab_bucket::prev, ast_hashtab::resize_count, ast_hashtab::tlist, and ast_hashtab_bucket::tnext.

Referenced by ast_hashtab_insert_immediate_bucket().

644 {
645  /* this function is called either internally, when the resize func returns 1, or
646  externally by the user to force a resize of the hash table */
647  int newsize = (*tab->newsize)(tab), i, c;
648  unsigned int h;
649  struct ast_hashtab_bucket *b,*bn;
650 
651  /* Since we keep a DLL of all the buckets in tlist,
652  all we have to do is free the array, malloc a new one,
653  and then go thru the tlist array and reassign them into
654  the bucket arrayj.
655  */
656  for (i = 0; i < tab->hash_tab_size; i++) { /* don't absolutely have to do this, but
657  why leave ptrs laying around */
658  tab->array[i] = 0; /* erase old ptrs */
659  }
660  free(tab->array);
661  if (!(tab->array =
662 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
663  __ast_calloc(newsize, sizeof(*(tab->array)), file, lineno, func)
664 #else
665  ast_calloc(newsize, sizeof(*(tab->array)))
666 #endif
667  ))
668  return;
669 
670  /* now sort the buckets into their rightful new slots */
671  tab->resize_count++;
672  tab->hash_tab_size = newsize;
673  tab->largest_bucket_size = 0;
674 
675  for (b = tab->tlist; b; b = bn) {
676  b->prev = 0;
677  bn = b->tnext;
678  h = (*tab->hash)(b->object) % tab->hash_tab_size;
679  b->next = tab->array[h];
680  if (b->next)
681  b->next->prev = b;
682  tab->array[h] = b;
683  }
684  /* recalc the largest bucket size */
685  for (i = 0; i < tab->hash_tab_size; i++) {
686  for (c = 0, b = tab->array[i]; b; b = b->next)
687  c++;
688  if (c > tab->largest_bucket_size)
689  tab->largest_bucket_size = c;
690  }
691 }
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
int hash_tab_size
Definition: hashtab.h:94
int largest_bucket_size
Definition: hashtab.h:96
int resize_count
Definition: hashtab.h:97
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func)
struct ast_hashtab_bucket * prev
Definition: hashtab.h:78
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90
#define free(a)
Definition: astmm.h:94
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
if(yyss+yystacksize-1<=yyssp)
Definition: ast_expr2.c:1874
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
#define ast_calloc(a, b)
Definition: astmm.h:82
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
tabthe hash table to operate on
Return values
0if the table load factor is less than or equal to 75%
1if the table load factor is greater than 75%

Definition at line 88 of file hashtab.c.

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

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

89 {
90  double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
91 
92  return (loadfactor > 0.75);
93 }
int hash_tab_size
Definition: hashtab.h:94
int hash_tab_elements
Definition: hashtab.h:95
int ast_hashtab_resize_none ( struct ast_hashtab tab)

Effectively disables resizing by always returning 0, regardless of of load factor.

Parameters
tabthe hash table to operate on
Returns
0 is always returned

Definition at line 100 of file hashtab.c.

101 {
102  return 0;
103 }
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
tabthe hash table to operate on
Return values
0if the number of elements in the table is less than or equal to the number of buckets
1if the number of elements in the table exceeds the number of buckets

Definition at line 95 of file hashtab.c.

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

96 {
97  return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
98 }
int hash_tab_size
Definition: hashtab.h:94
int hash_tab_elements
Definition: hashtab.h:95
int ast_hashtab_size ( struct ast_hashtab tab)

Returns the number of elements stored in the hashtab.

Definition at line 625 of file hashtab.c.

References ast_hashtab::hash_tab_elements.

Referenced by ast_context_remove_extension_callerid2().

626 {
627  return tab->hash_tab_elements;
628 }
int hash_tab_elements
Definition: hashtab.h:95
struct ast_hashtab_iter* ast_hashtab_start_traversal ( struct ast_hashtab tab)

Gives an iterator to hastable.

Definition at line 696 of file hashtab.c.

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

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

698 {
699  /* returns an iterator */
700  struct ast_hashtab_iter *it;
701 
702  if (!(it =
703 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
704  __ast_calloc(1, sizeof(*it), file, lineno, func)
705 #else
706  ast_calloc(1, sizeof(*it))
707 #endif
708  ))
709  return NULL;
710 
711  it->next = tab->tlist;
712  it->tab = tab;
713  if (tab->do_locking)
714  ast_rwlock_rdlock(&tab->lock);
715 
716  return it;
717 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:201
ast_rwlock_t lock
Definition: hashtab.h:101
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func)
struct ast_hashtab_bucket * next
Definition: hashtab.h:108
int do_locking
Definition: hashtab.h:99
struct ast_hashtab * tab
Definition: hashtab.h:107
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
an iterator for traversing the buckets
Definition: hashtab.h:105
#define ast_calloc(a, b)
Definition: astmm.h:82
struct ast_hashtab_iter* ast_hashtab_start_write_traversal ( struct ast_hashtab tab)

Gives an iterator to hastable.

Definition at line 723 of file hashtab.c.

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

725 {
726  /* returns an iterator */
727  struct ast_hashtab_iter *it;
728 
729  if (!(it =
730 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
731  __ast_calloc(1, sizeof(*it), file, lineno, func)
732 #else
733  ast_calloc(1, sizeof(*it))
734 #endif
735  ))
736  return NULL;
737 
738  it->next = tab->tlist;
739  it->tab = tab;
740  if (tab->do_locking)
741  ast_rwlock_wrlock(&tab->lock);
742 
743  return it;
744 }
ast_rwlock_t lock
Definition: hashtab.h:101
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func)
struct ast_hashtab_bucket * next
Definition: hashtab.h:108
int do_locking
Definition: hashtab.h:99
struct ast_hashtab * tab
Definition: hashtab.h:107
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
an iterator for traversing the buckets
Definition: hashtab.h:105
#define ast_rwlock_wrlock(a)
Definition: lock.h:202
#define ast_calloc(a, b)
Definition: astmm.h:82
void ast_hashtab_unlock ( struct ast_hashtab tab)

release a read- or write- lock.

Definition at line 383 of file hashtab.c.

References ast_rwlock_unlock, and ast_hashtab::lock.

384 {
385  ast_rwlock_unlock(&tab->lock);
386 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:200
void ast_hashtab_wrlock ( struct ast_hashtab tab)

Request a write-lock on the table.

Definition at line 363 of file hashtab.c.

References ast_rwlock_wrlock, and ast_hashtab::lock.

364 {
365  ast_rwlock_wrlock(&tab->lock);
366 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_wrlock(a)
Definition: lock.h:202
int ast_is_prime ( int  num)

Determines if the specified number is prime.

Parameters
numthe number to test
Return values
0if the number is not prime
1if the number is prime

Definition at line 105 of file hashtab.c.

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

106 {
107  int tnum, limit;
108 
109  if (!(num & 0x1)) /* even number -- not prime */
110  return 0;
111 
112  /* Loop through ODD numbers starting with 3 */
113 
114  tnum = 3;
115  limit = num;
116  while (tnum < limit) {
117  if (!(num % tnum))
118  return 0;
119 
120  /* really, we only need to check sqrt(num) numbers */
121  limit = num / tnum;
122 
123  /* we only check odd numbers */
124  tnum = tnum + 2;
125  }
126 
127  /* if we made it through the loop, the number is a prime */
128  return 1;
129 }
static void tlist_add_head ( struct ast_hashtab_bucket **  head,
struct ast_hashtab_bucket item 
)
static

Definition at line 345 of file hashtab.c.

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

Referenced by ast_hashtab_insert_immediate_bucket().

346 {
347  if (*head) {
348  item->tnext = *head;
349  item->tprev = NULL;
350  (*head)->tprev = item;
351  *head = item;
352  } else {
353  /* the list is empty */
354  *head = item;
355  item->tprev = NULL;
356  item->tnext = NULL;
357  }
358 }
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
struct ast_hashtab_bucket * tprev
Definition: hashtab.h:80
static void tlist_del_item ( struct ast_hashtab_bucket **  head,
struct ast_hashtab_bucket item 
)
static

Definition at line 330 of file hashtab.c.

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

Referenced by ast_hashtab_destroy(), and ast_hashtab_remove_object_internal().

331 {
332  /* item had better be in the list! or suffer the weirdness that occurs, later! */
333  if (*head == item) { /* first item in the list */
334  *head = item->tnext;
335  if (item->tnext)
336  item->tnext->tprev = NULL;
337  } else {
338  /* short circuit stuff */
339  item->tprev->tnext = item->tnext;
340  if (item->tnext)
341  item->tnext->tprev = item->tprev;
342  }
343 }
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
struct ast_hashtab_bucket * tprev
Definition: hashtab.h:80