include/asterisk/hashtab.h

   1 /*
   2  * Asterisk -- An open source telephony toolkit.
   3  *
   4  * Copyright (C) 2006, Digium, Inc.
   5  *
   6  * Steve Murphy <murf@digium.com>
   7  *
   8  * See http://www.asterisk.org for more information about
   9  * the Asterisk project. Please do not directly contact
  10  * any of the maintainers of this project for assistance;
  11  * the project provides a web site, mailing lists and IRC
  12  * channels for your use.
  13  *
  14  * This program is free software, distributed under the terms of
  15  * the GNU General Public License Version 2. See the LICENSE file
  16  * at the top of the source tree.
  17  */
  18 #ifndef _ASTERISK_HASHTAB_H_
  19 #define _ASTERISK_HASHTAB_H_
  20 #define __USE_UNIX98 1          /* to get the MUTEX_RECURSIVE stuff */
  21
  22 /*! \file
  23  * \brief Generic (perhaps overly so) hashtable implementation
  24  * \ref AstHash
  25  */
  26 /*! \page AstHash Hash Table support in Asterisk
  27
  28 A hash table is a structure that allows for an exact-match search
  29 in O(1) (or close to that) time.
  30
  31 The method: given: a set of {key,val} pairs. (at a minimum).
  32             given: a hash function, which, given a key,
  33             will return an integer. Ideally, each key in the
  34             set will have its own unique associated hash value.
  35                         This hash number will index into an array. "buckets"
  36             are what the elements of this array are called. To
  37             handle possible collisions in hash values, buckets can form a list.
  38
  39 The key for a value must be contained in the value, or we won't
  40 be able to find it in the bucket list.
  41
  42 This implementation is pretty generic, because:
  43
  44  1. The value and key are expected to be in a structure
  45     (along with other data, perhaps) and it's address is a "void *".
  46  2. The pointer to a compare function must be passed in at the
  47     time of creation, and is stored in the hashtable.
  48  3. The pointer to a resize function, which returns 1 if the
  49     hash table is to be grown. A default routine is provided
  50     if the pointer is NULL, and uses the java hashtable metric
  51     of a 75% load factor.
  52  4. The pointer to a "new size" function, which returns a preferable
  53     new size for the hash table bucket array. By default, a function
  54     is supplied which roughly doubles the size of the array, is provided.
  55     This size should ideally be a prime number.
  56  5. The hashing function pointer must also be supplied. This function
  57     must be written by the user to access the keys in the objects being
  58     stored. Some helper functions that use a simple "mult by prime, add
  59     the next char", sort of string hash, or a simple modulus of the hash
  60     table size for ints, is provided; the user can use these simple
  61     algorithms to generate a hash, or implement any other algorithms they
  62     wish.
  63  6. Recently updated the hash routines to use Doubly-linked lists for buckets,
  64     and added a doubly-linked list that threads thru every bucket in the table.
  65     The list of all buckets is on the HashTab struct. The Traversal was modified
  66     to go thru this list instead of searching the bucket array for buckets.
  67     This also should make it safe to remove a bucket during the traversal.
  68     Removal and destruction routines will work faster.
  69 */
  70
  71 struct ast_hashtab_bucket
  72 {
  73         const void *object;                    /*!< whatever it is we are storing in this table */
  74         struct ast_hashtab_bucket *next;       /*!< a DLL of buckets in hash collision */
  75         struct ast_hashtab_bucket *prev;       /*!< a DLL of buckets in hash collision */
  76         struct ast_hashtab_bucket *tnext;      /*!< a DLL of all the hash buckets for traversal */
  77         struct ast_hashtab_bucket *tprev;      /*!< a DLL of all the hash buckets for traversal */
  78 };
  79
  80 struct ast_hashtab
  81 {
  82         struct ast_hashtab_bucket **array;
  83         struct ast_hashtab_bucket *tlist;               /*!< the head of a DLList of all the hashbuckets in the table (for traversal). */
  84
  85         int (*compare) (const void *a, const void *b);  /*!< a ptr to func that returns int, and take two void* ptrs, compares them,
  86                                                                                                          rets -1 if a < b; rets 0 if a==b; rets 1 if a>b */
  87         int (*newsize) (struct ast_hashtab *tab);       /*!< a ptr to func that returns int, a new size for hash tab, based on curr_size */
  88         int (*resize) (struct ast_hashtab *tab);        /*!< a function to decide whether this hashtable should be resized now */
  89         unsigned int (*hash) (const void *obj);         /*!< a hash func ptr for this table. Given a raw ptr to an obj,
  90                                                                                                          it calcs a hash.*/
  91         int hash_tab_size;                            /*!< the size of the bucket array */
  92         int hash_tab_elements;                        /*!< the number of objects currently stored in the table */
  93         int largest_bucket_size;                      /*!< a stat on the health of the table */
  94         int resize_count;                             /*!< a count of the number of times this table has been
  95                                                                                                          resized */
  96         int do_locking;                               /*!< if 1 use locks to guarantee safety of insertions/deletions */
  97         /* this spot reserved for the proper lock storage */
  98         ast_rwlock_t lock;                                /* is this as good as it sounds? */
  99 };
 100
 101 /*! \brief an iterator for traversing the buckets */
 102 struct ast_hashtab_iter
 103 {
 104         struct ast_hashtab *tab;
 105         struct ast_hashtab_bucket *next;
 106 };
 107
 108
 109 /* some standard, default routines for general use */
 110
 111 /*!
 112  * \brief Determines if the specified number is prime.
 113  *
 114  * \param num the number to test
 115  * \retval 0 if the number is not prime
 116  * \retval 1 if the number is prime
 117  */
 118 int ast_is_prime(int num);
 119
 120 /*!
 121  * \brief Compares two strings for equality.
 122  *
 123  * \param a a character string
 124  * \param b a character string
 125  * \retval 0 if the strings match
 126  * \retval <0 if string a is less than string b
 127  * \retval >0 if string a is greather than string b
 128  */
 129 int ast_hashtab_compare_strings(const void *a, const void *b);
 130
 131 /*!
 132  * \brief Compares two strings for equality, ignoring case.
 133  *
 134  * \param a a character string
 135  * \param b a character string
 136  * \retval 0 if the strings match
 137  * \retval <0 if string a is less than string b
 138  * \retval >0 if string a is greather than string b
 139  */
 140 int ast_hashtab_compare_strings_nocase(const void *a, const void *b);
 141
 142 /*!
 143  * \brief Compares two integers for equality.
 144  *
 145  * \param a an integer pointer (int *)
 146  * \param b an integer pointer (int *)
 147  * \retval 0 if the integers pointed to are equal
 148  * \retval 1 if a is greater than b
 149  * \retval -1 if a is less than b
 150  */
 151 int ast_hashtab_compare_ints(const void *a, const void *b);
 152
 153 /*!
 154  * \brief Compares two shorts for equality.
 155  *
 156  * \param a a short pointer (short *)
 157  * \param b a short pointer (short *)
 158  * \retval 0 if the shorts pointed to are equal
 159  * \retval 1 if a is greater than b
 160  * \retval -1 if a is less than b
 161  */
 162 int ast_hashtab_compare_shorts(const void *a, const void *b);
 163
 164 /*!
 165  * \brief Determines if a table resize should occur using the Java algorithm
 166  *        (if the table load factor is 75% or higher).
 167  *
 168  * \param tab the hash table to operate on
 169  * \retval 0 if the table load factor is less than or equal to 75%
 170  * \retval 1 if the table load factor is greater than 75%
 171  */
 172 int ast_hashtab_resize_java(struct ast_hashtab *tab);
 173
 174 /*! \brief Causes a resize whenever the number of elements stored in the table
 175  *         exceeds the number of buckets in the table.
 176  *
 177  * \param tab the hash table to operate on
 178  * \retval 0 if the number of elements in the table is less than or equal to
 179  *           the number of buckets
 180  * \retval 1 if the number of elements in the table exceeds the number of
 181  *           buckets
 182  */
 183 int ast_hashtab_resize_tight(struct ast_hashtab *tab);
 184
 185 /*!
 186  * \brief Effectively disables resizing by always returning 0, regardless of
 187  *        of load factor.
 188  *
 189  * \param tab the hash table to operate on
 190  * \return 0 is always returned
 191  */
 192 int ast_hashtab_resize_none(struct ast_hashtab *tab);
 193
 194 /*! \brief Create a prime number roughly 2x the current table size */
 195 int ast_hashtab_newsize_java(struct ast_hashtab *tab);
 196
 197 /* not yet specified, probably will return 1.5x the current table size */
 198 int ast_hashtab_newsize_tight(struct ast_hashtab *tab);
 199
 200 /*! \brief always return current size -- no resizing */
 201 int ast_hashtab_newsize_none(struct ast_hashtab *tab);
 202
 203 /*!
 204  * \brief Hashes a string to a number
 205  *
 206  * \param obj the string to hash
 207  * \return Integer hash of the specified string
 208  * \sa ast_hashtable_hash_string_nocase
 209  * \sa ast_hashtab_hash_string_sax
 210  * \note A modulus will be applied to the return value of this function
 211  */
 212 unsigned int ast_hashtab_hash_string(const void *obj);
 213
 214 /*!
 215  * \brief Hashes a string to a number ignoring case
 216  *
 217  * \param obj the string to hash
 218  * \return Integer hash of the specified string
 219  * \sa ast_hashtable_hash_string
 220  * \sa ast_hashtab_hash_string_sax
 221  * \note A modulus will be applied to the return value of this function
 222  */
 223 unsigned int ast_hashtab_hash_string_nocase(const void *obj);
 224
 225 /*!
 226  * \brief Hashes a string to a number using a modified Shift-And-XOR algorithm
 227  *
 228  * \param obj the string to hash
 229  * \return Integer has of the specified string
 230  * \sa ast_hastable_hash_string
 231  * \sa ast_hastable_hash_string_nocase
 232  */
 233 unsigned int ast_hashtab_hash_string_sax(const void *obj);
 234
 235
 236 unsigned int ast_hashtab_hash_int(const int num);  /* right now, both these funcs are just result = num%modulus; */
 237
 238
 239 unsigned int ast_hashtab_hash_short(const short num);
 240
 241
 242 /*!
 243  * \brief Create the hashtable list
 244  * \param initial_buckets starting number of buckets
 245  * \param compare a func ptr to compare two elements in the hash -- cannot be null
 246  * \param resize a func ptr to decide if the table needs to be resized, a NULL ptr here will cause a default to be used
 247  * \param newsize a func ptr that returns a new size of the array. A NULL will cause a default to be used
 248  * \param hash a func ptr to do the hashing
 249  * \param do_locking use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now
 250 */
 251 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
 252 struct ast_hashtab * _ast_hashtab_create(int initial_buckets,
 253                                         int (*compare)(const void *a, const void *b),
 254                                         int (*resize)(struct ast_hashtab *),
 255                                         int (*newsize)(struct ast_hashtab *tab),
 256                                         unsigned int (*hash)(const void *obj),
 257                                         int do_locking, const char *file, int lineno, const char *function);
 258 #define ast_hashtab_create(a,b,c,d,e,f) _ast_hashtab_create(a,b,c,d,e,f,__FILE__,__LINE__,__PRETTY_FUNCTION__)
 259 #else
 260 struct ast_hashtab * ast_hashtab_create(int initial_buckets,
 261                                         int (*compare)(const void *a, const void *b),
 262                                         int (*resize)(struct ast_hashtab *),
 263                                         int (*newsize)(struct ast_hashtab *tab),
 264                                         unsigned int (*hash)(const void *obj),
 265                                         int do_locking );
 266 #endif
 267
 268 /*!
 269  * \brief This func will free the hash table and all its memory.
 270  * \note It doesn't touch the objects stored in it, unless you
 271  *       specify a destroy func; it will call that func for each
 272  *       object in the hashtab, remove all the objects, and then
 273  *       free the hashtab itself. If no destroyfunc is specified
 274  *       then the routine will assume you will free it yourself.
 275  * \param tab
 276  * \param objdestroyfunc
 277 */
 278 void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj));
 279
 280
 281 /*!
 282  * \brief Insert without checking
 283  * \param tab
 284  * \param obj
 285  *
 286  * Normally, you'd insert "safely" by checking to see if the element is
 287  * already there; in this case, you must already have checked. If an element
 288  * is already in the hashtable, that matches this one, most likely this one
 289  * will be found first.
 290  * \note will force a resize if the resize func returns 1
 291  * \retval 1 on success
 292  * \retval 0 if there's a problem
 293 */
 294 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
 295 int _ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func);
 296 #define ast_hashtab_insert_immediate(a,b)       _ast_hashtab_insert_immediate(a, b, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 297 #else
 298 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj);
 299 #endif
 300
 301 /*!
 302  * \brief Insert without checking, hashing or locking
 303  * \param tab
 304  * \param obj
 305  * \param h hashed index value
 306  *
 307  * \note Will force a resize if the resize func returns 1
 308  * \retval 1 on success
 309  * \retval 0 if there's a problem
 310 */
 311 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
 312 int _ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func);
 313 #define ast_hashtab_insert_immediate_bucket(a,b,c)      _ast_hashtab_insert_immediate_bucket(a, b, c, __FILE__, __LINE__, __PRETTY_FUNCTION__)
 314 #else
 315 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h);
 316 #endif
 317
 318 /*!
 319  * \brief Check and insert new object only if it is not there.
 320  * \note Will force a resize if the resize func returns 1
 321  * \retval 1 on success
 322  * \retval  0 if there's a problem, or it's already there.
 323 */
 324 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
 325 int _ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func);
 326 #define ast_hashtab_insert_safe(a,b)    _ast_hashtab_insert_safe(a,b,__FILE__, __LINE__, __PRETTY_FUNCTION__)
 327 #else
 328 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj);
 329 #endif
 330
 331 /*!
 332  * \brief Lookup this object in the hash table.
 333  * \param tab
 334  * \param obj
 335  * \retval a ptr if found
 336  * \retval NULL if not found
 337 */
 338 void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj);
 339
 340 /*!
 341  * \brief  Use this if have the hash val for the object
 342  * \note This and avoid the recalc of the hash (the modulus (table_size) is not applied)
 343 */
 344 void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval);
 345
 346 /*!
 347  * \brief Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.
 348  * \note This has the modulus applied, and will not be useful for long term storage if the table is resizable.
 349 */
 350 void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *h);
 351
 352 /*! \brief Returns key stats for the table */
 353 void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets);
 354
 355 /*! \brief Returns the number of elements stored in the hashtab */
 356 int ast_hashtab_size( struct ast_hashtab *tab);
 357
 358 /*! \brief Returns the size of the bucket array in the hashtab */
 359 int ast_hashtab_capacity( struct ast_hashtab *tab);
 360
 361 /*! \brief Return a copy of the hash table */
 362 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
 363 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);
 364 #define ast_hashtab_dup(a,b)    _ast_hashtab_dup(a,b,__FILE__,__LINE__,__PRETTY_FUNCTION__)
 365 #else
 366 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj));
 367 #endif
 368
 369 /*! \brief Gives an iterator to hastable */
 370 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
 371 struct ast_hashtab_iter *_ast_hashtab_start_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func);
 372 #define ast_hashtab_start_traversal(a)  _ast_hashtab_start_traversal(a,__FILE__,__LINE__,__PRETTY_FUNCTION__)
 373 #else
 374 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab);
 375 #endif
 376
 377 /*! \brief end the traversal, free the iterator, unlock if necc. */
 378 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it);
 379
 380 /*! \brief Gets the next object in the list, advances iter one step returns null on end of traversal */
 381 void *ast_hashtab_next(struct ast_hashtab_iter *it);
 382
 383 /*! \brief Looks up the object, removes the corresponding bucket */
 384 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj);
 385
 386 /*! \brief Hash the object and then compare ptrs in bucket list instead of
 387            calling the compare routine, will remove the bucket */
 388 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj);
 389
 390 /* ------------------ */
 391 /* for lock-enabled traversals with ability to remove an object during the traversal*/
 392 /* ------------------ */
 393
 394 /*! \brief Gives an iterator to hastable */
 395 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
 396 struct ast_hashtab_iter *_ast_hashtab_start_write_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func);
 397 #define ast_hashtab_start_write_traversal(a)    _ast_hashtab_start_write_traversal(a,__FILE__,__LINE__,__PRETTY_FUNCTION__)
 398 #else
 399 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab);
 400 #endif
 401
 402 /*! \brief Looks up the object, removes the corresponding bucket */
 403 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj);
 404
 405 /*! \brief Hash the object and then compare ptrs in bucket list instead of
 406            calling the compare routine, will remove the bucket */
 407 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj);
 408
 409 /* ------------------ */
 410 /* ------------------ */
 411
 412 /* user-controlled hashtab locking. Create a hashtab without locking, then call the
 413    following locking routines yourself to lock the table between threads. */
 414
 415 /*! \brief Call this after you create the table to init the lock */
 416 void ast_hashtab_initlock(struct ast_hashtab *tab);
 417 /*! \brief Request a write-lock on the table. */
 418 void ast_hashtab_wrlock(struct ast_hashtab *tab);
 419 /*! \brief Request a read-lock on the table -- don't change anything! */
 420 void ast_hashtab_rdlock(struct ast_hashtab *tab);
 421 /*! \brief release a read- or write- lock. */
 422 void ast_hashtab_unlock(struct ast_hashtab *tab);
 423 /*! \brief Call this before you destroy the table. */
 424 void ast_hashtab_destroylock(struct ast_hashtab *tab);
 425
 426
 427 #endif