Tue Aug 20 16:34:34 2013

Asterisk developer's documentation


hashtab.h

Go to the documentation of this file.
00001 /*
00002  * Asterisk -- An open source telephony toolkit.
00003  *
00004  * Copyright (C) 2006, Digium, Inc.
00005  *
00006  * Steve Murphy <murf@digium.com>
00007  *
00008  * See http://www.asterisk.org for more information about
00009  * the Asterisk project. Please do not directly contact
00010  * any of the maintainers of this project for assistance;
00011  * the project provides a web site, mailing lists and IRC
00012  * channels for your use.
00013  *
00014  * This program is free software, distributed under the terms of
00015  * the GNU General Public License Version 2. See the LICENSE file
00016  * at the top of the source tree.
00017  */
00018 #ifndef _ASTERISK_HASHTAB_H_
00019 #define _ASTERISK_HASHTAB_H_
00020 #define __USE_UNIX98 1          /* to get the MUTEX_RECURSIVE stuff */
00021 
00022 /*! \file
00023  * \brief Generic (perhaps overly so) hashtable implementation
00024  * \ref AstHash
00025  */
00026 
00027 #include "asterisk/lock.h"
00028 
00029 /*! \page AstHash Hash Table support in Asterisk
00030 
00031 A hash table is a structure that allows for an exact-match search
00032 in O(1) (or close to that) time.
00033 
00034 The method: given: a set of {key,val} pairs. (at a minimum).
00035             given: a hash function, which, given a key,
00036             will return an integer. Ideally, each key in the
00037             set will have its own unique associated hash value.
00038          This hash number will index into an array. "buckets"
00039             are what the elements of this array are called. To
00040             handle possible collisions in hash values, buckets can form a list.
00041 
00042 The key for a value must be contained in the value, or we won't
00043 be able to find it in the bucket list.
00044 
00045 This implementation is pretty generic, because:
00046 
00047  1. The value and key are expected to be in a structure
00048     (along with other data, perhaps) and it's address is a "void *".
00049  2. The pointer to a compare function must be passed in at the
00050     time of creation, and is stored in the hashtable.
00051  3. The pointer to a resize function, which returns 1 if the
00052     hash table is to be grown. A default routine is provided
00053     if the pointer is NULL, and uses the java hashtable metric
00054     of a 75% load factor.
00055  4. The pointer to a "new size" function, which returns a preferable
00056     new size for the hash table bucket array. By default, a function
00057     is supplied which roughly doubles the size of the array, is provided.
00058     This size should ideally be a prime number.
00059  5. The hashing function pointer must also be supplied. This function
00060     must be written by the user to access the keys in the objects being
00061     stored. Some helper functions that use a simple "mult by prime, add
00062     the next char", sort of string hash, or a simple modulus of the hash
00063     table size for ints, is provided; the user can use these simple
00064     algorithms to generate a hash, or implement any other algorithms they
00065     wish.
00066  6. Recently updated the hash routines to use Doubly-linked lists for buckets,
00067     and added a doubly-linked list that threads thru every bucket in the table.
00068     The list of all buckets is on the HashTab struct. The Traversal was modified
00069     to go thru this list instead of searching the bucket array for buckets.
00070     This also should make it safe to remove a bucket during the traversal.
00071     Removal and destruction routines will work faster.
00072 */
00073 
00074 struct ast_hashtab_bucket
00075 {
00076    const void *object;                    /*!< whatever it is we are storing in this table */
00077    struct ast_hashtab_bucket *next;       /*!< a DLL of buckets in hash collision */
00078    struct ast_hashtab_bucket *prev;       /*!< a DLL of buckets in hash collision */
00079    struct ast_hashtab_bucket *tnext;      /*!< a DLL of all the hash buckets for traversal */
00080    struct ast_hashtab_bucket *tprev;      /*!< a DLL of all the hash buckets for traversal */
00081 };
00082 
00083 struct ast_hashtab
00084 {
00085    struct ast_hashtab_bucket **array;
00086    struct ast_hashtab_bucket *tlist;      /*!< the head of a DLList of all the hashbuckets in the table (for traversal). */
00087 
00088    int (*compare) (const void *a, const void *b);  /*!< a ptr to func that returns int, and take two void* ptrs, compares them,
00089                                         rets -1 if a < b; rets 0 if a==b; rets 1 if a>b */
00090    int (*newsize) (struct ast_hashtab *tab); /*!< a ptr to func that returns int, a new size for hash tab, based on curr_size */
00091    int (*resize) (struct ast_hashtab *tab);  /*!< a function to decide whether this hashtable should be resized now */
00092    unsigned int (*hash) (const void *obj);         /*!< a hash func ptr for this table. Given a raw ptr to an obj,
00093                                         it calcs a hash.*/
00094    int hash_tab_size;                            /*!< the size of the bucket array */
00095    int hash_tab_elements;                        /*!< the number of objects currently stored in the table */
00096    int largest_bucket_size;                      /*!< a stat on the health of the table */
00097    int resize_count;                             /*!< a count of the number of times this table has been
00098                                         resized */
00099    int do_locking;                               /*!< if 1 use locks to guarantee safety of insertions/deletions */
00100    /* this spot reserved for the proper lock storage */
00101    ast_rwlock_t lock;                                /* is this as good as it sounds? */
00102 };
00103 
00104 /*! \brief an iterator for traversing the buckets */
00105 struct ast_hashtab_iter
00106 {
00107    struct ast_hashtab *tab;
00108    struct ast_hashtab_bucket *next;
00109 };
00110 
00111 
00112 /* some standard, default routines for general use */
00113 
00114 /*!
00115  * \brief Determines if the specified number is prime.
00116  *
00117  * \param num the number to test
00118  * \retval 0 if the number is not prime
00119  * \retval 1 if the number is prime
00120  */
00121 int ast_is_prime(int num);
00122 
00123 /*!
00124  * \brief Compares two strings for equality.
00125  *
00126  * \param a a character string
00127  * \param b a character string
00128  * \retval 0 if the strings match
00129  * \retval <0 if string a is less than string b
00130  * \retval >0 if string a is greather than string b
00131  */
00132 int ast_hashtab_compare_strings(const void *a, const void *b);
00133 
00134 /*!
00135  * \brief Compares two strings for equality, ignoring case.
00136  *
00137  * \param a a character string
00138  * \param b a character string
00139  * \retval 0 if the strings match
00140  * \retval <0 if string a is less than string b
00141  * \retval >0 if string a is greather than string b
00142  */
00143 int ast_hashtab_compare_strings_nocase(const void *a, const void *b);
00144 
00145 /*!
00146  * \brief Compares two integers for equality.
00147  *
00148  * \param a an integer pointer (int *)
00149  * \param b an integer pointer (int *)
00150  * \retval 0 if the integers pointed to are equal
00151  * \retval 1 if a is greater than b
00152  * \retval -1 if a is less than b
00153  */
00154 int ast_hashtab_compare_ints(const void *a, const void *b);
00155 
00156 /*!
00157  * \brief Compares two shorts for equality.
00158  *
00159  * \param a a short pointer (short *)
00160  * \param b a short pointer (short *)
00161  * \retval 0 if the shorts pointed to are equal
00162  * \retval 1 if a is greater than b
00163  * \retval -1 if a is less than b
00164  */
00165 int ast_hashtab_compare_shorts(const void *a, const void *b);
00166 
00167 /*!
00168  * \brief Determines if a table resize should occur using the Java algorithm
00169  *        (if the table load factor is 75% or higher).
00170  *
00171  * \param tab the hash table to operate on
00172  * \retval 0 if the table load factor is less than or equal to 75%
00173  * \retval 1 if the table load factor is greater than 75%
00174  */
00175 int ast_hashtab_resize_java(struct ast_hashtab *tab);
00176 
00177 /*! \brief Causes a resize whenever the number of elements stored in the table
00178  *         exceeds the number of buckets in the table.
00179  *
00180  * \param tab the hash table to operate on
00181  * \retval 0 if the number of elements in the table is less than or equal to
00182  *           the number of buckets
00183  * \retval 1 if the number of elements in the table exceeds the number of
00184  *           buckets
00185  */
00186 int ast_hashtab_resize_tight(struct ast_hashtab *tab);
00187 
00188 /*!
00189  * \brief Effectively disables resizing by always returning 0, regardless of
00190  *        of load factor.
00191  *
00192  * \param tab the hash table to operate on
00193  * \return 0 is always returned
00194  */
00195 int ast_hashtab_resize_none(struct ast_hashtab *tab);
00196 
00197 /*! \brief Create a prime number roughly 2x the current table size */
00198 int ast_hashtab_newsize_java(struct ast_hashtab *tab);
00199 
00200 /* not yet specified, probably will return 1.5x the current table size */
00201 int ast_hashtab_newsize_tight(struct ast_hashtab *tab);
00202 
00203 /*! \brief always return current size -- no resizing */
00204 int ast_hashtab_newsize_none(struct ast_hashtab *tab);
00205 
00206 /*!
00207  * \brief Hashes a string to a number
00208  *
00209  * \param obj the string to hash
00210  * \return Integer hash of the specified string
00211  * \sa ast_hashtable_hash_string_nocase
00212  * \sa ast_hashtab_hash_string_sax
00213  * \note A modulus will be applied to the return value of this function
00214  */
00215 unsigned int ast_hashtab_hash_string(const void *obj);
00216 
00217 /*!
00218  * \brief Hashes a string to a number ignoring case
00219  *
00220  * \param obj the string to hash
00221  * \return Integer hash of the specified string
00222  * \sa ast_hashtable_hash_string
00223  * \sa ast_hashtab_hash_string_sax
00224  * \note A modulus will be applied to the return value of this function
00225  */
00226 unsigned int ast_hashtab_hash_string_nocase(const void *obj);
00227 
00228 /*!
00229  * \brief Hashes a string to a number using a modified Shift-And-XOR algorithm
00230  *
00231  * \param obj the string to hash
00232  * \return Integer has of the specified string
00233  * \sa ast_hastable_hash_string
00234  * \sa ast_hastable_hash_string_nocase
00235  */
00236 unsigned int ast_hashtab_hash_string_sax(const void *obj);
00237 
00238 
00239 unsigned int ast_hashtab_hash_int(const int num);  /* right now, both these funcs are just result = num%modulus; */
00240 
00241 
00242 unsigned int ast_hashtab_hash_short(const short num);
00243 
00244 
00245 /*!
00246  * \brief Create the hashtable list
00247  * \param initial_buckets starting number of buckets
00248  * \param compare a func ptr to compare two elements in the hash -- cannot be null
00249  * \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
00250  * \param newsize a func ptr that returns a new size of the array. A NULL will cause a default to be used
00251  * \param hash a func ptr to do the hashing
00252  * \param do_locking use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now
00253 */
00254 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00255 struct ast_hashtab * _ast_hashtab_create(int initial_buckets,
00256                int (*compare)(const void *a, const void *b),
00257                int (*resize)(struct ast_hashtab *),
00258                int (*newsize)(struct ast_hashtab *tab),
00259                unsigned int (*hash)(const void *obj),
00260                int do_locking, const char *file, int lineno, const char *function);
00261 #define ast_hashtab_create(a,b,c,d,e,f)   _ast_hashtab_create(a,b,c,d,e,f,__FILE__,__LINE__,__PRETTY_FUNCTION__)
00262 #else
00263 struct ast_hashtab * ast_hashtab_create(int initial_buckets,
00264                int (*compare)(const void *a, const void *b),
00265                int (*resize)(struct ast_hashtab *),
00266                int (*newsize)(struct ast_hashtab *tab),
00267                unsigned int (*hash)(const void *obj),
00268                int do_locking );
00269 #endif
00270 
00271 /*!
00272  * \brief This func will free the hash table and all its memory.
00273  * \note It doesn't touch the objects stored in it, unless you
00274  *       specify a destroy func; it will call that func for each
00275  *       object in the hashtab, remove all the objects, and then
00276  *       free the hashtab itself. If no destroyfunc is specified
00277  *       then the routine will assume you will free it yourself.
00278  * \param tab
00279  * \param objdestroyfunc
00280 */
00281 void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj));
00282 
00283 
00284 /*!
00285  * \brief Insert without checking
00286  * \param tab
00287  * \param obj
00288  *
00289  * Normally, you'd insert "safely" by checking to see if the element is
00290  * already there; in this case, you must already have checked. If an element
00291  * is already in the hashtable, that matches this one, most likely this one
00292  * will be found first.
00293  * \note will force a resize if the resize func returns 1
00294  * \retval 1 on success
00295  * \retval 0 if there's a problem
00296 */
00297 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00298 int _ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func);
00299 #define  ast_hashtab_insert_immediate(a,b)   _ast_hashtab_insert_immediate(a, b, __FILE__, __LINE__, __PRETTY_FUNCTION__)
00300 #else
00301 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj);
00302 #endif
00303 
00304 /*!
00305  * \brief Insert without checking, hashing or locking
00306  * \param tab
00307  * \param obj
00308  * \param h hashed index value
00309  *
00310  * \note Will force a resize if the resize func returns 1
00311  * \retval 1 on success
00312  * \retval 0 if there's a problem
00313 */
00314 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00315 int _ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func);
00316 #define  ast_hashtab_insert_immediate_bucket(a,b,c)   _ast_hashtab_insert_immediate_bucket(a, b, c, __FILE__, __LINE__, __PRETTY_FUNCTION__)
00317 #else
00318 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h);
00319 #endif
00320 
00321 /*!
00322  * \brief Check and insert new object only if it is not there.
00323  * \note Will force a resize if the resize func returns 1
00324  * \retval 1 on success
00325  * \retval  0 if there's a problem, or it's already there.
00326 */
00327 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00328 int _ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func);
00329 #define  ast_hashtab_insert_safe(a,b)  _ast_hashtab_insert_safe(a,b,__FILE__, __LINE__, __PRETTY_FUNCTION__)
00330 #else
00331 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj);
00332 #endif
00333 
00334 /*!
00335  * \brief Lookup this object in the hash table.
00336  * \param tab
00337  * \param obj
00338  * \retval a ptr if found
00339  * \retval NULL if not found
00340 */
00341 void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj);
00342 
00343 /*!
00344  * \brief  Use this if have the hash val for the object
00345  * \note This and avoid the recalc of the hash (the modulus (table_size) is not applied)
00346 */
00347 void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval);
00348 
00349 /*!
00350  * \brief Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.
00351  * \note This has the modulus applied, and will not be useful for long term storage if the table is resizable.
00352 */
00353 void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *h);
00354 
00355 /*! \brief Returns key stats for the table */
00356 void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets);
00357 
00358 /*! \brief Returns the number of elements stored in the hashtab */
00359 int ast_hashtab_size( struct ast_hashtab *tab);
00360 
00361 /*! \brief Returns the size of the bucket array in the hashtab */
00362 int ast_hashtab_capacity( struct ast_hashtab *tab);
00363 
00364 /*! \brief Return a copy of the hash table */
00365 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00366 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);
00367 #define  ast_hashtab_dup(a,b) _ast_hashtab_dup(a,b,__FILE__,__LINE__,__PRETTY_FUNCTION__)
00368 #else
00369 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj));
00370 #endif
00371 
00372 /*! \brief Gives an iterator to hastable */
00373 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00374 struct ast_hashtab_iter *_ast_hashtab_start_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func);
00375 #define  ast_hashtab_start_traversal(a)   _ast_hashtab_start_traversal(a,__FILE__,__LINE__,__PRETTY_FUNCTION__)
00376 #else
00377 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab);
00378 #endif
00379 
00380 /*! \brief end the traversal, free the iterator, unlock if necc. */
00381 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it);
00382 
00383 /*! \brief Gets the next object in the list, advances iter one step returns null on end of traversal */
00384 void *ast_hashtab_next(struct ast_hashtab_iter *it);
00385 
00386 /*! \brief Looks up the object, removes the corresponding bucket */
00387 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj);
00388 
00389 /*! \brief Hash the object and then compare ptrs in bucket list instead of
00390       calling the compare routine, will remove the bucket */
00391 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj);
00392 
00393 /* ------------------ */
00394 /* for lock-enabled traversals with ability to remove an object during the traversal*/
00395 /* ------------------ */
00396 
00397 /*! \brief Gives an iterator to hastable */
00398 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00399 struct ast_hashtab_iter *_ast_hashtab_start_write_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func);
00400 #define  ast_hashtab_start_write_traversal(a)   _ast_hashtab_start_write_traversal(a,__FILE__,__LINE__,__PRETTY_FUNCTION__)
00401 #else
00402 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab);
00403 #endif
00404 
00405 /*! \brief Looks up the object, removes the corresponding bucket */
00406 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj);
00407 
00408 /*! \brief Hash the object and then compare ptrs in bucket list instead of
00409       calling the compare routine, will remove the bucket */
00410 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj);
00411 
00412 /* ------------------ */
00413 /* ------------------ */
00414 
00415 /* user-controlled hashtab locking. Create a hashtab without locking, then call the
00416    following locking routines yourself to lock the table between threads. */
00417 
00418 /*! \brief Call this after you create the table to init the lock */
00419 void ast_hashtab_initlock(struct ast_hashtab *tab);
00420 /*! \brief Request a write-lock on the table. */
00421 void ast_hashtab_wrlock(struct ast_hashtab *tab);
00422 /*! \brief Request a read-lock on the table -- don't change anything! */
00423 void ast_hashtab_rdlock(struct ast_hashtab *tab);
00424 /*! \brief release a read- or write- lock. */
00425 void ast_hashtab_unlock(struct ast_hashtab *tab);
00426 /*! \brief Call this before you destroy the table. */
00427 void ast_hashtab_destroylock(struct ast_hashtab *tab);
00428 
00429 
00430 #endif

Generated on 20 Aug 2013 for Asterisk - The Open Source Telephony Project by  doxygen 1.6.1