Fri Jul 24 00:40:57 2009

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 /*! \page AstHash Hash Table support in Asterisk
00027 
00028 A hash table is a structure that allows for an exact-match search
00029 in O(1) (or close to that) time.
00030 
00031 The method: given: a set of {key,val} pairs. (at a minimum).
00032             given: a hash function, which, given a key,
00033             will return an integer. Ideally, each key in the
00034             set will have its own unique associated hash value.
00035          This hash number will index into an array. "buckets"
00036             are what the elements of this array are called. To
00037             handle possible collisions in hash values, buckets can form a list.
00038 
00039 The key for a value must be contained in the value, or we won't
00040 be able to find it in the bucket list.
00041 
00042 This implementation is pretty generic, because:
00043 
00044  1. The value and key are expected to be in a structure
00045     (along with other data, perhaps) and it's address is a "void *".
00046  2. The pointer to a compare function must be passed in at the
00047     time of creation, and is stored in the hashtable.
00048  3. The pointer to a resize function, which returns 1 if the
00049     hash table is to be grown. A default routine is provided
00050     if the pointer is NULL, and uses the java hashtable metric
00051     of a 75% load factor.
00052  4. The pointer to a "new size" function, which returns a preferable
00053     new size for the hash table bucket array. By default, a function
00054     is supplied which roughly doubles the size of the array, is provided.
00055     This size should ideally be a prime number.
00056  5. The hashing function pointer must also be supplied. This function
00057     must be written by the user to access the keys in the objects being
00058     stored. Some helper functions that use a simple "mult by prime, add
00059     the next char", sort of string hash, or a simple modulus of the hash
00060     table size for ints, is provided; the user can use these simple
00061     algorithms to generate a hash, or implement any other algorithms they
00062     wish.
00063  6. Recently updated the hash routines to use Doubly-linked lists for buckets,
00064     and added a doubly-linked list that threads thru every bucket in the table.
00065     The list of all buckets is on the HashTab struct. The Traversal was modified
00066     to go thru this list instead of searching the bucket array for buckets.
00067     This also should make it safe to remove a bucket during the traversal.
00068     Removal and destruction routines will work faster.
00069 */
00070 
00071 struct ast_hashtab_bucket
00072 {
00073    const void *object;                    /*!< whatever it is we are storing in this table */
00074    struct ast_hashtab_bucket *next;       /*!< a DLL of buckets in hash collision */
00075    struct ast_hashtab_bucket *prev;       /*!< a DLL of buckets in hash collision */
00076    struct ast_hashtab_bucket *tnext;      /*!< a DLL of all the hash buckets for traversal */
00077    struct ast_hashtab_bucket *tprev;      /*!< a DLL of all the hash buckets for traversal */
00078 };
00079 
00080 struct ast_hashtab
00081 {
00082    struct ast_hashtab_bucket **array;
00083    struct ast_hashtab_bucket *tlist;      /*!< the head of a DLList of all the hashbuckets in the table (for traversal). */
00084    
00085    int (*compare) (const void *a, const void *b);  /*!< a ptr to func that returns int, and take two void* ptrs, compares them, 
00086                                         rets -1 if a < b; rets 0 if a==b; rets 1 if a>b */
00087    int (*newsize) (struct ast_hashtab *tab); /*!< a ptr to func that returns int, a new size for hash tab, based on curr_size */
00088    int (*resize) (struct ast_hashtab *tab);  /*!< a function to decide whether this hashtable should be resized now */
00089    unsigned int (*hash) (const void *obj);         /*!< a hash func ptr for this table. Given a raw ptr to an obj, 
00090                                         it calcs a hash.*/
00091    int hash_tab_size;                            /*!< the size of the bucket array */
00092    int hash_tab_elements;                        /*!< the number of objects currently stored in the table */
00093    int largest_bucket_size;                      /*!< a stat on the health of the table */
00094    int resize_count;                             /*!< a count of the number of times this table has been
00095                                         resized */
00096    int do_locking;                               /*!< if 1 use locks to guarantee safety of insertions/deletions */
00097    /* this spot reserved for the proper lock storage */
00098    ast_rwlock_t lock;                                /* is this as good as it sounds? */
00099 };
00100 
00101 /*! \brief an iterator for traversing the buckets */
00102 struct ast_hashtab_iter
00103 {
00104    struct ast_hashtab *tab;
00105    struct ast_hashtab_bucket *next;
00106 };
00107 
00108 
00109 /* some standard, default routines for general use */
00110 
00111 /*! \brief For sizing the hash table, tells if num is prime or not */
00112 int ast_is_prime(int num);
00113 
00114 /*! 
00115  * \brief assumes a and b are char * 
00116  * \return 0 if they match 
00117 */
00118 int ast_hashtab_compare_strings(const void *a, const void *b);
00119 
00120 /*!
00121  * \brief assumes a & b are strings
00122  * \return 0 if they match (strcasecmp) 
00123 */
00124 int ast_hashtab_compare_strings_nocase(const void *a, const void *b);
00125 
00126 /*!
00127  * \brief assumes a & b are int *
00128  * \retval 0 if match
00129  * \retval 1 a > b
00130  * \retval -1 a < b
00131 */
00132 int ast_hashtab_compare_ints(const void *a, const void *b);
00133 
00134 /*!
00135  * \brief assumes a & b are short *
00136  * \retval 0 if match
00137  * \retval 1 a > b
00138  * \retval -1 a < b
00139 */
00140 int ast_hashtab_compare_shorts(const void *a, const void *b);
00141 
00142 /*!
00143  * \brief determine if resize should occur
00144  * \returns 1 if the table is 75% full or more
00145 */
00146 int ast_hashtab_resize_java(struct ast_hashtab *tab);
00147 
00148 /*! \brief no resizing; always return 0 */
00149 int ast_hashtab_resize_tight(struct ast_hashtab *tab);
00150 
00151 /*! \brief no resizing; always return 0 */
00152 int ast_hashtab_resize_none(struct ast_hashtab *tab);
00153 
00154 /*! \brief Create a prime number roughly 2x the current table size */
00155 int ast_hashtab_newsize_java(struct ast_hashtab *tab);
00156 
00157 /* not yet specified, probably will return 1.5x the current table size */
00158 int ast_hashtab_newsize_tight(struct ast_hashtab *tab);
00159 
00160 /*! \brief always return current size -- no resizing */
00161 int ast_hashtab_newsize_none(struct ast_hashtab *tab);
00162 
00163 /*! 
00164  * \brief Hashes a string to a number
00165  * \param obj
00166  * \note A modulus is applied so it in the range 0 to mod-1 
00167 */
00168 unsigned int ast_hashtab_hash_string(const void *obj);
00169 
00170 /*! \brief Upperases each char before using them for a hash */
00171 unsigned int ast_hashtab_hash_string_nocase(const void *obj);
00172 
00173 
00174 unsigned int ast_hashtab_hash_string_sax(const void *obj); /* from Josh */
00175 
00176 
00177 unsigned int ast_hashtab_hash_int(const int num);  /* right now, both these funcs are just result = num%modulus; */
00178 
00179 
00180 unsigned int ast_hashtab_hash_short(const short num);
00181 
00182 
00183 /*!
00184  * \brief Create the hashtable list
00185  * \param initial_buckets starting number of buckets
00186  * \param compare a func ptr to compare two elements in the hash -- cannot be null 
00187  * \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
00188  * \param newsize a func ptr that returns a new size of the array. A NULL will cause a default to be used
00189  * \param hash a func ptr to do the hashing
00190  * \param do_locking use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now
00191 */
00192 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00193 struct ast_hashtab * _ast_hashtab_create(int initial_buckets,
00194                int (*compare)(const void *a, const void *b), 
00195                int (*resize)(struct ast_hashtab *),   
00196                int (*newsize)(struct ast_hashtab *tab),
00197                unsigned int (*hash)(const void *obj), 
00198                int do_locking, const char *file, int lineno, const char *function);
00199 #define ast_hashtab_create(a,b,c,d,e,f)   _ast_hashtab_create(a,b,c,d,e,f,__FILE__,__LINE__,__PRETTY_FUNCTION__)
00200 #else
00201 struct ast_hashtab * ast_hashtab_create(int initial_buckets,
00202                int (*compare)(const void *a, const void *b), 
00203                int (*resize)(struct ast_hashtab *),   
00204                int (*newsize)(struct ast_hashtab *tab),
00205                unsigned int (*hash)(const void *obj), 
00206                int do_locking );
00207 #endif
00208 
00209 /*!
00210  * \brief This func will free the hash table and all its memory. 
00211  * \note It doesn't touch the objects stored in it, unless you
00212  *       specify a destroy func; it will call that func for each
00213  *       object in the hashtab, remove all the objects, and then
00214  *       free the hashtab itself. If no destroyfunc is specified
00215  *       then the routine will assume you will free it yourself.
00216  * \param tab
00217  * \param objdestroyfunc
00218 */
00219 void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj));
00220 
00221 
00222 /*!
00223  * \brief Insert without checking 
00224  * \param tab
00225  * \param obj
00226  *
00227  * Normally, you'd insert "safely" by checking to see if the element is
00228  * already there; in this case, you must already have checked. If an element
00229  * is already in the hashtable, that matches this one, most likely this one
00230  * will be found first. 
00231  * \note will force a resize if the resize func returns 1
00232  * \retval 1 on success
00233  * \retval 0 if there's a problem
00234 */
00235 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj);
00236 
00237 /*!
00238  * \brief Insert without checking, hashing or locking
00239  * \param tab
00240  * \param obj
00241  * \param h hashed index value
00242  * 
00243  * \note Will force a resize if the resize func returns 1
00244  * \retval 1 on success
00245  * \retval 0 if there's a problem
00246 */
00247 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h);
00248 
00249 /*!
00250  * \brief Check and insert new object only if it is not there.
00251  * \note Will force a resize if the resize func returns 1
00252  * \retval 1 on success
00253  * \retval  0 if there's a problem, or it's already there. 
00254 */
00255 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj);
00256 
00257 /*!
00258  * \brief Lookup this object in the hash table. 
00259  * \param tab 
00260  * \param obj 
00261  * \retval a ptr if found
00262  * \retval NULL if not found
00263 */
00264 void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj);
00265 
00266 /*!
00267  * \brief  Use this if have the hash val for the object
00268  * \note This and avoid the recalc of the hash (the modulus (table_size) is not applied)
00269 */
00270 void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval);
00271 
00272 /*!
00273  * \brief Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.
00274  * \note This has the modulus applied, and will not be useful for long term storage if the table is resizable.
00275 */
00276 void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *h);
00277 
00278 /*! \brief Returns key stats for the table */
00279 void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets);
00280 
00281 /*! \brief Returns the number of elements stored in the hashtab */
00282 int ast_hashtab_size( struct ast_hashtab *tab);
00283 
00284 /*! \brief Returns the size of the bucket array in the hashtab */
00285 int ast_hashtab_capacity( struct ast_hashtab *tab);
00286 
00287 /*! \brief Return a copy of the hash table */
00288 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj));
00289 
00290 /*! \brief Gives an iterator to hastable */
00291 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab);
00292 
00293 /*! \brief end the traversal, free the iterator, unlock if necc. */
00294 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it);
00295 
00296 /*! \brief Gets the next object in the list, advances iter one step returns null on end of traversal */
00297 void *ast_hashtab_next(struct ast_hashtab_iter *it);
00298 
00299 /*! \brief Looks up the object, removes the corresponding bucket */
00300 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj);
00301 
00302 /*! \brief Hash the object and then compare ptrs in bucket list instead of
00303       calling the compare routine, will remove the bucket */
00304 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj);
00305 
00306 /* ------------------ */
00307 /* for lock-enabled traversals with ability to remove an object during the traversal*/
00308 /* ------------------ */
00309 
00310 /*! \brief Gives an iterator to hastable */
00311 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab);
00312 
00313 /*! \brief Looks up the object, removes the corresponding bucket */
00314 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj);
00315 
00316 /*! \brief Hash the object and then compare ptrs in bucket list instead of
00317       calling the compare routine, will remove the bucket */
00318 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj);
00319 
00320 /* ------------------ */
00321 /* ------------------ */
00322 
00323 /* user-controlled hashtab locking. Create a hashtab without locking, then call the
00324    following locking routines yourself to lock the table between threads. */
00325 
00326 /*! \brief Call this after you create the table to init the lock */
00327 void ast_hashtab_initlock(struct ast_hashtab *tab); 
00328 /*! \brief Request a write-lock on the table. */
00329 void ast_hashtab_wrlock(struct ast_hashtab *tab); 
00330 /*! \brief Request a read-lock on the table -- don't change anything! */
00331 void ast_hashtab_rdlock(struct ast_hashtab *tab); 
00332 /*! \brief release a read- or write- lock. */
00333 void ast_hashtab_unlock(struct ast_hashtab *tab); 
00334 /*! \brief Call this before you destroy the table. */
00335 void ast_hashtab_destroylock(struct ast_hashtab *tab); 
00336 
00337 
00338 #endif

Generated on Fri Jul 24 00:40:57 2009 for Asterisk - the Open Source PBX by  doxygen 1.4.7