Asterisk - The Open Source Telephony Project  18.5.0
Macros | Functions
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_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 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.

224 {
225  struct ast_hashtab *ht;
226 
227  ht = __ast_calloc(1, sizeof(*ht), file, lineno, function);
228  if (!ht) {
229  return NULL;
230  }
231 
232  while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
233  initial_buckets++;
234 
235  ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)),
236  file, lineno, function);
237  if (!ht->array) {
238  ast_free(ht);
239  return NULL;
240  }
241 
242  ht->hash_tab_size = initial_buckets;
243  ht->compare = compare;
244  ht->resize = resize;
245  ht->newsize = newsize;
246  ht->hash = hash;
247  ht->do_locking = do_locking;
248 
249  if (do_locking)
250  ast_rwlock_init(&ht->lock);
251 
252  if (!ht->resize)
254 
255  if (!ht->newsize)
257 
258  return ht;
259 }
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
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:84
#define NULL
Definition: resample.c:96
int do_locking
Definition: hashtab.h:99
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:101
int ast_hashtab_newsize_java(struct ast_hashtab *tab)
Create a prime number roughly 2x the current table size.
Definition: hashtab.c:127
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:222
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
#define ast_free(a)
Definition: astmm.h:182
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
static int compare(const char *text, const char *template)
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90

◆ _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.

262 {
263  struct ast_hashtab *ht;
264  unsigned int i;
265 
266  ht = __ast_calloc(1, sizeof(*ht), file, lineno, func);
267  if (!ht) {
268  return NULL;
269  }
270 
271  ht->array = __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)),
272  file, lineno, func);
273  if (!ht->array) {
274  ast_free(ht);
275  return NULL;
276  }
277 
278  ht->hash_tab_size = tab->hash_tab_size;
279  ht->compare = tab->compare;
280  ht->resize = tab->resize;
281  ht->newsize = tab->newsize;
282  ht->hash = tab->hash;
283  ht->do_locking = tab->do_locking;
284 
285  if (ht->do_locking)
286  ast_rwlock_init(&ht->lock);
287 
288  /* now, dup the objects in the buckets and get them into the table */
289  /* the fast way is to use the existing array index, and not have to hash
290  the objects again */
291  for (i = 0; i < ht->hash_tab_size; i++) {
292  struct ast_hashtab_bucket *b = tab->array[i];
293  while (b) {
294  void *newobj = (*obj_dup_func)(b->object);
295  if (newobj) {
296  _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func);
297  }
298  b = b->next;
299  }
300  }
301 
302  return ht;
303 }
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
#define NULL
Definition: resample.c:96
int do_locking
Definition: hashtab.h:99
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:222
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
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.
Definition: hashtab.c:425
#define ast_free(a)
Definition: astmm.h:182
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
static struct test_val b
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90

◆ _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
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 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.

405 {
406  unsigned int h;
407  int res=0;
408 
409  if (!tab || !obj)
410  return res;
411 
412  if (tab->do_locking)
413  ast_rwlock_wrlock(&tab->lock);
414 
415  h = (*tab->hash)(obj) % tab->hash_tab_size;
416 
417  res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func);
418 
419  if (tab->do_locking)
420  ast_rwlock_unlock(&tab->lock);
421 
422  return res;
423 }
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:232
int do_locking
Definition: hashtab.h:99
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.
Definition: hashtab.c:425
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
#define ast_rwlock_wrlock(a)
Definition: lock.h:234

◆ _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
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 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().

426 {
427  int c;
428  struct ast_hashtab_bucket *b;
429 
430  if (!tab || !obj)
431  return 0;
432 
433  for (c = 0, b = tab->array[h]; b; b= b->next)
434  c++;
435 
436  if (c + 1 > tab->largest_bucket_size)
437  tab->largest_bucket_size = c + 1;
438 
439  b = __ast_calloc(1, sizeof(*b), file, lineno, func);
440  if (!b) {
441  return 0;
442  }
443 
444  b->object = obj;
445  b->next = tab->array[h];
446  tab->array[h] = b;
447 
448  if (b->next)
449  b->next->prev = b;
450 
451  tlist_add_head(&(tab->tlist), b);
452  tab->hash_tab_elements++;
453 
454  if ((*tab->resize)(tab))
455  ast_hashtab_resize(tab);
456 
457  return 1;
458 }
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
int largest_bucket_size
Definition: hashtab.h:96
static struct test_val c
struct ast_hashtab_bucket * prev
Definition: hashtab.h:78
#define ast_hashtab_resize(tab)
Definition: hashtab.c:45
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:320
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
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
static struct test_val b
int hash_tab_elements
Definition: hashtab.h:95

◆ _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
1on success
0if 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.

461 {
462  /* check to see if the element is already there; insert only if
463  it is not there. */
464  /* will force a resize if the resize func returns 1 */
465  /* returns 1 on success, 0 if there's a problem, or it's already there. */
466  unsigned int bucket = 0;
467 
468  if (tab->do_locking)
469  ast_rwlock_wrlock(&tab->lock);
470 
471  if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
472  int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func);
473 
474  if (tab->do_locking)
475  ast_rwlock_unlock(&tab->lock);
476 
477  return ret2;
478  }
479 
480  if (tab->do_locking)
481  ast_rwlock_unlock(&tab->lock);
482 
483  return 0;
484 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:232
int do_locking
Definition: hashtab.h:99
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.
Definition: hashtab.c:425
#define ast_rwlock_wrlock(a)
Definition: lock.h:234
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.
Definition: hashtab.c:531

◆ _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.

592 {
593  /* this function is called either internally, when the resize func returns 1, or
594  externally by the user to force a resize of the hash table */
595  int newsize = (*tab->newsize)(tab), i, c;
596  unsigned int h;
597  struct ast_hashtab_bucket *b,*bn;
598 
599  /* Since we keep a DLL of all the buckets in tlist,
600  all we have to do is free the array, malloc a new one,
601  and then go thru the tlist array and reassign them into
602  the bucket arrayj.
603  */
604  for (i = 0; i < tab->hash_tab_size; i++) { /* don't absolutely have to do this, but
605  why leave ptrs laying around */
606  tab->array[i] = 0; /* erase old ptrs */
607  }
608  ast_free(tab->array);
609  tab->array = __ast_calloc(newsize, sizeof(*(tab->array)), file, lineno, func);
610  if (!tab->array) {
611  return;
612  }
613 
614  /* now sort the buckets into their rightful new slots */
615  tab->resize_count++;
616  tab->hash_tab_size = newsize;
617  tab->largest_bucket_size = 0;
618 
619  for (b = tab->tlist; b; b = bn) {
620  b->prev = 0;
621  bn = b->tnext;
622  h = (*tab->hash)(b->object) % tab->hash_tab_size;
623  b->next = tab->array[h];
624  if (b->next)
625  b->next->prev = b;
626  tab->array[h] = b;
627  }
628  /* recalc the largest bucket size */
629  for (i = 0; i < tab->hash_tab_size; i++) {
630  for (c = 0, b = tab->array[i]; b; b = b->next)
631  c++;
632  if (c > tab->largest_bucket_size)
633  tab->largest_bucket_size = c;
634  }
635 }
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
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
static struct test_val c
struct ast_hashtab_bucket * prev
Definition: hashtab.h:78
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
#define ast_free(a)
Definition: astmm.h:182
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
static struct test_val b
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90

◆ _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.

638 {
639  /* returns an iterator */
640  struct ast_hashtab_iter *it;
641 
642  it = __ast_calloc(1, sizeof(*it), file, lineno, func);
643  if (!it) {
644  return NULL;
645  }
646 
647  it->next = tab->tlist;
648  it->tab = tab;
649  if (tab->do_locking)
650  ast_rwlock_rdlock(&tab->lock);
651 
652  return it;
653 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:233
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
ast_rwlock_t lock
Definition: hashtab.h:101
#define NULL
Definition: resample.c:96
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

◆ _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.

657 {
658  /* returns an iterator */
659  struct ast_hashtab_iter *it;
660 
661  it = __ast_calloc(1, sizeof(*it), file, lineno, func);
662  if (!it) {
663  return NULL;
664  }
665 
666  it->next = tab->tlist;
667  it->tab = tab;
668  if (tab->do_locking)
669  ast_rwlock_wrlock(&tab->lock);
670 
671  return it;
672 }
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
ast_rwlock_t lock
Definition: hashtab.h:101
#define NULL
Definition: resample.c:96
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:234

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

584 {
585  return tab->hash_tab_size;
586 }
int hash_tab_size
Definition: hashtab.h:94

◆ ast_hashtab_compare_ints()

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

63 {
64  int ai = *((int *) a);
65  int bi = *((int *) b);
66 
67  if (ai < bi)
68  return -1;
69 
70  return !(ai == bi);
71 }
static struct test_val b
static struct test_val a

◆ ast_hashtab_compare_shorts()

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

References bs.

74 {
75  short as = *((short *) a);
76  short bs = *((short *) b);
77 
78  if (as < bs)
79  return -1;
80 
81  return !(as == bs);
82 }
char * bs
Definition: eagi_proxy.c:73
static struct test_val b
static struct test_val a

◆ ast_hashtab_compare_strings()

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

53 {
54  return strcmp(a, b);
55 }
static struct test_val b
static struct test_val a

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

Referenced by AST_TEST_DEFINE().

58 {
59  return strcasecmp(a, b);
60 }
static struct test_val b
static struct test_val a

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

364 {
365  /* this func will free the hash table and all its memory. It
366  doesn't touch the objects stored in it */
367  if (tab) {
368 
369  if (tab->do_locking)
370  ast_rwlock_wrlock(&tab->lock);
371 
372  if (tab->array) {
373  /* go thru and destroy the buckets */
374  struct ast_hashtab_bucket *t;
375  int i;
376 
377  while (tab->tlist) {
378  t = tab->tlist;
379  if (t->object && objdestroyfunc) {
380  /* I cast this because I'm not going to MOD it, I'm going to DESTROY
381  * it.
382  */
383  (*objdestroyfunc)((void *) t->object);
384  }
385 
386  tlist_del_item(&(tab->tlist), tab->tlist);
387  ast_free(t);
388  }
389 
390  for (i = 0; i < tab->hash_tab_size; i++) {
391  /* Not totally necessary, but best to destroy old pointers */
392  tab->array[i] = NULL;
393  }
394  ast_free(tab->array);
395  }
396  if (tab->do_locking) {
397  ast_rwlock_unlock(&tab->lock);
398  ast_rwlock_destroy(&tab->lock);
399  }
400  ast_free(tab);
401  }
402 }
int hash_tab_size
Definition: hashtab.h:94
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:231
ast_rwlock_t lock
Definition: hashtab.h:101
#define NULL
Definition: resample.c:96
#define ast_rwlock_unlock(a)
Definition: lock.h:232
int do_locking
Definition: hashtab.h:99
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:305
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
#define ast_free(a)
Definition: astmm.h:182
#define ast_rwlock_wrlock(a)
Definition: lock.h:234
const void * object
Definition: hashtab.h:76

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

354 {
355  ast_rwlock_destroy(&tab->lock);
356 }
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:231
ast_rwlock_t lock
Definition: hashtab.h:101

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

675 {
676  if (!it)
677  return;
678  if (it->tab->do_locking)
679  ast_rwlock_unlock(&it->tab->lock);
680  ast_free(it);
681 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:232
int do_locking
Definition: hashtab.h:99
struct ast_hashtab * tab
Definition: hashtab.h:107
#define ast_free(a)
Definition: astmm.h:182

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

564 {
565  /* returns key stats for the table */
566  if (tab->do_locking)
567  ast_rwlock_rdlock(&tab->lock);
568  *biggest_bucket_size = tab->largest_bucket_size;
569  *resize_count = tab->resize_count;
570  *num_objects = tab->hash_tab_elements;
571  *num_buckets = tab->hash_tab_size;
572  if (tab->do_locking)
573  ast_rwlock_unlock(&tab->lock);
574 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:233
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:232
int do_locking
Definition: hashtab.h:99
int hash_tab_elements
Definition: hashtab.h:95

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

206 {
207  return x;
208 }

◆ ast_hashtab_hash_short()

unsigned int ast_hashtab_hash_short ( const short  x)

Definition at line 210 of file hashtab.c.

211 {
212  /* hmmmm.... modulus is best < 65535 !! */
213  return x;
214 }

◆ ast_hashtab_hash_string()

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

154 {
155  unsigned char *str = (unsigned char *) obj;
156  unsigned int total;
157 
158  for (total = 0; *str; str++) {
159  unsigned int tmp = total;
160  total <<= 1; /* multiply by 2 */
161  total += tmp; /* multiply by 3 */
162  total <<= 2; /* multiply by 12 */
163  total += tmp; /* multiply by 13 */
164 
165  total += ((unsigned int)(*str));
166  }
167  return total;
168 }
static int tmp()
Definition: bt_open.c:389
const char * str
Definition: app_jack.c:147
static int total
Definition: res_adsi.c:968

◆ ast_hashtab_hash_string_nocase()

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

References str, tmp(), and total.

Referenced by AST_TEST_DEFINE(), and hash_string().

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

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

References c, str, and total.

171 {
172  const unsigned char *str = obj;
173  unsigned int total = 0, c = 0;
174 
175  while ((c = *str++))
176  total ^= (total << 5) + (total >> 2) + (total << 10) + c;
177 
178  return total;
179 }
static struct test_val c
const char * str
Definition: app_jack.c:147
static int total
Definition: res_adsi.c:968

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

349 {
350  ast_rwlock_init(&tab->lock);
351 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:222

◆ 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
aptr if found
NULLif 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().

487 {
488  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
489  unsigned int h;
490  void *ret;
491 
492  if (!tab || !obj)
493  return 0;
494 
495  if (tab->do_locking)
496  ast_rwlock_rdlock(&tab->lock);
497 
498  h = (*tab->hash)(obj) % tab->hash_tab_size;
499 
500  ret = ast_hashtab_lookup_internal(tab,obj,h);
501 
502  if (tab->do_locking)
503  ast_rwlock_unlock(&tab->lock);
504 
505  return ret;
506 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:233
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:232
static void * ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
Definition: hashtab.c:549
int do_locking
Definition: hashtab.h:99
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92

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

532 {
533  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
534  unsigned int h;
535  void *ret;
536 
537  if (!tab || !obj)
538  return 0;
539 
540  h = (*tab->hash)(obj) % tab->hash_tab_size;
541 
542  ret = ast_hashtab_lookup_internal(tab,obj,h);
543 
544  *bucket = h;
545 
546  return ret;
547 }
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:549
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92

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

550 {
551  struct ast_hashtab_bucket *b;
552 
553  for (b = tab->array[h]; b; b = b->next) {
554  if (!(*tab->compare)(obj,b->object)) {
555  /* I can't touch obj in this func, but the outside world is welcome to */
556  return (void*) b->object;
557  }
558  }
559 
560  return NULL;
561 }
#define NULL
Definition: resample.c:96
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
static struct test_val b

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

510 {
511  /* lookup this object in the hash table. return a ptr if found, or NULL if not */
512  unsigned int h;
513  void *ret;
514 
515  if (!tab || !obj)
516  return 0;
517 
518  if (tab->do_locking)
519  ast_rwlock_rdlock(&tab->lock);
520 
521  h = hashval % tab->hash_tab_size;
522 
523  ret = ast_hashtab_lookup_internal(tab,obj,h);
524 
525  if (tab->do_locking)
526  ast_rwlock_unlock(&tab->lock);
527 
528  return ret;
529 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:233
int hash_tab_size
Definition: hashtab.h:94
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:232
static void * ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
Definition: hashtab.c:549
int do_locking
Definition: hashtab.h:99

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

128 {
129  int i = (tab->hash_tab_size << 1); /* multiply by two */
130 
131  while (!ast_is_prime(i))
132  i++;
133 
134  return i;
135 }
int hash_tab_size
Definition: hashtab.h:94
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:101

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

149 {
150  return tab->hash_tab_size;
151 }
int hash_tab_size
Definition: hashtab.h:94

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

138 {
139  int x = (tab->hash_tab_size << 1);
140  int i = (tab->hash_tab_size + x);
141 
142  while (!ast_is_prime(i))
143  i++;
144 
145  return i;
146 }
int hash_tab_size
Definition: hashtab.h:94
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:101

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

684 {
685  /* returns the next object in the list, advances iter one step */
686  struct ast_hashtab_bucket *retval;
687 
688  if (it && it->next) { /* there's a next in the bucket list */
689  retval = it->next;
690  it->next = retval->tnext;
691  return (void *) retval->object;
692  }
693 
694  return NULL;
695 }
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
#define NULL
Definition: resample.c:96
struct ast_hashtab_bucket * next
Definition: hashtab.h:108
const void * object
Definition: hashtab.h:76
static ENTRY retval
Definition: hsearch.c:50

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

344 {
345  ast_rwlock_rdlock(&tab->lock);
346 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:233
ast_rwlock_t lock
Definition: hashtab.h:101

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

698 {
699  const void *obj2;
700 
701  if (b->prev)
702  b->prev->next = b->next;
703  else
704  tab->array[h] = b->next;
705 
706  if (b->next)
707  b->next->prev = b->prev;
708 
709  tlist_del_item(&(tab->tlist), b);
710 
711  obj2 = b->object;
712  b->object = b->next = (void*)2;
713  ast_free(b); /* free up the hashbucket */
714  tab->hash_tab_elements--;
715 #ifdef DEBUG
716  {
717  int c2;
718  struct ast_hashtab_bucket *b2;
719  /* do a little checking */
720  for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
721  c2++;
722  }
723  if (c2 != tab->hash_tab_elements) {
724  printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
725  c2, tab->hash_tab_elements);
726  }
727  for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
728  unsigned int obj3 = (unsigned long) obj2;
729  unsigned int b3 = (unsigned long) b;
730  if (b2->object == obj2)
731  printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
732  if (b2->next == b)
733  printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
734  if (b2->prev == b)
735  printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
736  if (b2->tprev == b)
737  printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
738  if (b2->tnext == b)
739  printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
740  }
741  }
742 #endif
743  return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
744 }
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
static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:305
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
#define ast_free(a)
Definition: astmm.h:182
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
int hash_tab_elements
Definition: hashtab.h:95

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

747 {
748  /* looks up the object; removes the corresponding bucket */
749  const void *obj2;
750 
751  if (!tab || !obj)
752  return 0;
753 
754  if (tab->do_locking)
755  ast_rwlock_wrlock(&tab->lock);
756 
758 
759  if (tab->do_locking)
760  ast_rwlock_unlock(&tab->lock);
761 
762  return (void *)obj2;
763 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:232
int do_locking
Definition: hashtab.h:99
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:765
#define ast_rwlock_wrlock(a)
Definition: lock.h:234

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

766 {
767  /* looks up the object; removes the corresponding bucket */
768  unsigned int h;
769  struct ast_hashtab_bucket *b;
770 
771  if (!tab || !obj)
772  return 0;
773 
774  h = (*tab->hash)(obj) % tab->hash_tab_size;
775  for (b = tab->array[h]; b; b = b->next) {
776 
777  if (!(*tab->compare)(obj, b->object)) {
778  const void *obj2;
779 
780  obj2 = ast_hashtab_remove_object_internal(tab, b, h);
781 
782  return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
783  }
784  }
785 
786  return 0;
787 }
int hash_tab_size
Definition: hashtab.h:94
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
static void * ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
Definition: hashtab.c:697
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
static struct test_val b

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

790 {
791  /* looks up the object by hash and then comparing pts in bucket list instead of
792  calling the compare routine; removes the bucket -- a slightly cheaper operation */
793  /* looks up the object; removes the corresponding bucket */
794  const void *obj2;
795 
796  if (!tab || !obj)
797  return 0;
798 
799  if (tab->do_locking)
800  ast_rwlock_wrlock(&tab->lock);
801 
803 
804  if (tab->do_locking)
805  ast_rwlock_unlock(&tab->lock);
806 
807  return (void *)obj2;
808 }
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:810
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:232
int do_locking
Definition: hashtab.h:99
#define ast_rwlock_wrlock(a)
Definition: lock.h:234

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

811 {
812  /* looks up the object by hash and then comparing pts in bucket list instead of
813  calling the compare routine; removes the bucket -- a slightly cheaper operation */
814  /* looks up the object; removes the corresponding bucket */
815  unsigned int h;
816  struct ast_hashtab_bucket *b;
817 
818  if (!tab || !obj)
819  return 0;
820 
821  h = (*tab->hash)(obj) % tab->hash_tab_size;
822  for (b = tab->array[h]; b; b = b->next) {
823 
824  if (obj == b->object) {
825  const void *obj2;
826  obj2 = ast_hashtab_remove_object_internal(tab, b, h);
827 
828  return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
829  }
830  }
831 
832  return 0;
833 }
int hash_tab_size
Definition: hashtab.h:94
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
static void * ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
Definition: hashtab.c:697
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
static struct test_val b

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

85 {
86  double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
87 
88  return (loadfactor > 0.75);
89 }
int hash_tab_size
Definition: hashtab.h:94
int hash_tab_elements
Definition: hashtab.h:95

◆ 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
tabthe hash table to operate on
Returns
0 is always returned

Definition at line 96 of file hashtab.c.

97 {
98  return 0;
99 }

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

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

92 {
93  return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
94 }
int hash_tab_size
Definition: hashtab.h:94
int hash_tab_elements
Definition: hashtab.h:95

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

578 {
579  return tab->hash_tab_elements;
580 }
int hash_tab_elements
Definition: hashtab.h:95

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

359 {
360  ast_rwlock_unlock(&tab->lock);
361 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_unlock(a)
Definition: lock.h:232

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

339 {
340  ast_rwlock_wrlock(&tab->lock);
341 }
ast_rwlock_t lock
Definition: hashtab.h:101
#define ast_rwlock_wrlock(a)
Definition: lock.h:234

◆ ast_is_prime()

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

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

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

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

321 {
322  if (*head) {
323  item->tnext = *head;
324  item->tprev = NULL;
325  (*head)->tprev = item;
326  *head = item;
327  } else {
328  /* the list is empty */
329  *head = item;
330  item->tprev = NULL;
331  item->tnext = NULL;
332  }
333 }
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
struct ast_hashtab_bucket * tprev
Definition: hashtab.h:80
static struct aco_type item
Definition: test_config.c:1463
#define NULL
Definition: resample.c:96

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

306 {
307  /* item had better be in the list! or suffer the weirdness that occurs, later! */
308  if (*head == item) { /* first item in the list */
309  *head = item->tnext;
310  if (item->tnext)
311  item->tnext->tprev = NULL;
312  } else {
313  /* short circuit stuff */
314  item->tprev->tnext = item->tnext;
315  if (item->tnext)
316  item->tnext->tprev = item->tprev;
317  }
318 }
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
struct ast_hashtab_bucket * tprev
Definition: hashtab.h:80
#define NULL
Definition: resample.c:96