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 /*! 00112 * \brief Determines if the specified number is prime. 00113 * 00114 * \param num the number to test 00115 * \retval 0 if the number is not prime 00116 * \retval 1 if the number is prime 00117 */ 00118 int ast_is_prime(int num); 00119 00120 /*! 00121 * \brief Compares two strings for equality. 00122 * 00123 * \param a a character string 00124 * \param b a character string 00125 * \retval 0 if the strings match 00126 * \retval <0 if string a is less than string b 00127 * \retval >0 if string a is greather than string b 00128 */ 00129 int ast_hashtab_compare_strings(const void *a, const void *b); 00130 00131 /*! 00132 * \brief Compares two strings for equality, ignoring case. 00133 * 00134 * \param a a character string 00135 * \param b a character string 00136 * \retval 0 if the strings match 00137 * \retval <0 if string a is less than string b 00138 * \retval >0 if string a is greather than string b 00139 */ 00140 int ast_hashtab_compare_strings_nocase(const void *a, const void *b); 00141 00142 /*! 00143 * \brief Compares two integers for equality. 00144 * 00145 * \param a an integer pointer (int *) 00146 * \param b an integer pointer (int *) 00147 * \retval 0 if the integers pointed to are equal 00148 * \retval 1 if a is greater than b 00149 * \retval -1 if a is less than b 00150 */ 00151 int ast_hashtab_compare_ints(const void *a, const void *b); 00152 00153 /*! 00154 * \brief Compares two shorts for equality. 00155 * 00156 * \param a a short pointer (short *) 00157 * \param b a short pointer (short *) 00158 * \retval 0 if the shorts pointed to are equal 00159 * \retval 1 if a is greater than b 00160 * \retval -1 if a is less than b 00161 */ 00162 int ast_hashtab_compare_shorts(const void *a, const void *b); 00163 00164 /*! 00165 * \brief Determines if a table resize should occur using the Java algorithm 00166 * (if the table load factor is 75% or higher). 00167 * 00168 * \param tab the hash table to operate on 00169 * \retval 0 if the table load factor is less than or equal to 75% 00170 * \retval 1 if the table load factor is greater than 75% 00171 */ 00172 int ast_hashtab_resize_java(struct ast_hashtab *tab); 00173 00174 /*! \brief Causes a resize whenever the number of elements stored in the table 00175 * exceeds the number of buckets in the table. 00176 * 00177 * \param tab the hash table to operate on 00178 * \retval 0 if the number of elements in the table is less than or equal to 00179 * the number of buckets 00180 * \retval 1 if the number of elements in the table exceeds the number of 00181 * buckets 00182 */ 00183 int ast_hashtab_resize_tight(struct ast_hashtab *tab); 00184 00185 /*! 00186 * \brief Effectively disables resizing by always returning 0, regardless of 00187 * of load factor. 00188 * 00189 * \param tab the hash table to operate on 00190 * \return 0 is always returned 00191 */ 00192 int ast_hashtab_resize_none(struct ast_hashtab *tab); 00193 00194 /*! \brief Create a prime number roughly 2x the current table size */ 00195 int ast_hashtab_newsize_java(struct ast_hashtab *tab); 00196 00197 /* not yet specified, probably will return 1.5x the current table size */ 00198 int ast_hashtab_newsize_tight(struct ast_hashtab *tab); 00199 00200 /*! \brief always return current size -- no resizing */ 00201 int ast_hashtab_newsize_none(struct ast_hashtab *tab); 00202 00203 /*! 00204 * \brief Hashes a string to a number 00205 * 00206 * \param obj the string to hash 00207 * \return Integer hash of the specified string 00208 * \sa ast_hashtable_hash_string_nocase 00209 * \sa ast_hashtab_hash_string_sax 00210 * \note A modulus will be applied to the return value of this function 00211 */ 00212 unsigned int ast_hashtab_hash_string(const void *obj); 00213 00214 /*! 00215 * \brief Hashes a string to a number ignoring case 00216 * 00217 * \param obj the string to hash 00218 * \return Integer hash of the specified string 00219 * \sa ast_hashtable_hash_string 00220 * \sa ast_hashtab_hash_string_sax 00221 * \note A modulus will be applied to the return value of this function 00222 */ 00223 unsigned int ast_hashtab_hash_string_nocase(const void *obj); 00224 00225 /*! 00226 * \brief Hashes a string to a number using a modified Shift-And-XOR algorithm 00227 * 00228 * \param obj the string to hash 00229 * \return Integer has of the specified string 00230 * \sa ast_hastable_hash_string 00231 * \sa ast_hastable_hash_string_nocase 00232 */ 00233 unsigned int ast_hashtab_hash_string_sax(const void *obj); 00234 00235 00236 unsigned int ast_hashtab_hash_int(const int num); /* right now, both these funcs are just result = num%modulus; */ 00237 00238 00239 unsigned int ast_hashtab_hash_short(const short num); 00240 00241 00242 /*! 00243 * \brief Create the hashtable list 00244 * \param initial_buckets starting number of buckets 00245 * \param compare a func ptr to compare two elements in the hash -- cannot be null 00246 * \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 00247 * \param newsize a func ptr that returns a new size of the array. A NULL will cause a default to be used 00248 * \param hash a func ptr to do the hashing 00249 * \param do_locking use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now 00250 */ 00251 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00252 struct ast_hashtab * _ast_hashtab_create(int initial_buckets, 00253 int (*compare)(const void *a, const void *b), 00254 int (*resize)(struct ast_hashtab *), 00255 int (*newsize)(struct ast_hashtab *tab), 00256 unsigned int (*hash)(const void *obj), 00257 int do_locking, const char *file, int lineno, const char *function); 00258 #define ast_hashtab_create(a,b,c,d,e,f) _ast_hashtab_create(a,b,c,d,e,f,__FILE__,__LINE__,__PRETTY_FUNCTION__) 00259 #else 00260 struct ast_hashtab * ast_hashtab_create(int initial_buckets, 00261 int (*compare)(const void *a, const void *b), 00262 int (*resize)(struct ast_hashtab *), 00263 int (*newsize)(struct ast_hashtab *tab), 00264 unsigned int (*hash)(const void *obj), 00265 int do_locking ); 00266 #endif 00267 00268 /*! 00269 * \brief This func will free the hash table and all its memory. 00270 * \note It doesn't touch the objects stored in it, unless you 00271 * specify a destroy func; it will call that func for each 00272 * object in the hashtab, remove all the objects, and then 00273 * free the hashtab itself. If no destroyfunc is specified 00274 * then the routine will assume you will free it yourself. 00275 * \param tab 00276 * \param objdestroyfunc 00277 */ 00278 void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj)); 00279 00280 00281 /*! 00282 * \brief Insert without checking 00283 * \param tab 00284 * \param obj 00285 * 00286 * Normally, you'd insert "safely" by checking to see if the element is 00287 * already there; in this case, you must already have checked. If an element 00288 * is already in the hashtable, that matches this one, most likely this one 00289 * will be found first. 00290 * \note will force a resize if the resize func returns 1 00291 * \retval 1 on success 00292 * \retval 0 if there's a problem 00293 */ 00294 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00295 int _ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func); 00296 #define ast_hashtab_insert_immediate(a,b) _ast_hashtab_insert_immediate(a, b, __FILE__, __LINE__, __PRETTY_FUNCTION__) 00297 #else 00298 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj); 00299 #endif 00300 00301 /*! 00302 * \brief Insert without checking, hashing or locking 00303 * \param tab 00304 * \param obj 00305 * \param h hashed index value 00306 * 00307 * \note Will force a resize if the resize func returns 1 00308 * \retval 1 on success 00309 * \retval 0 if there's a problem 00310 */ 00311 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00312 int _ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func); 00313 #define ast_hashtab_insert_immediate_bucket(a,b,c) _ast_hashtab_insert_immediate_bucket(a, b, c, __FILE__, __LINE__, __PRETTY_FUNCTION__) 00314 #else 00315 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h); 00316 #endif 00317 00318 /*! 00319 * \brief Check and insert new object only if it is not there. 00320 * \note Will force a resize if the resize func returns 1 00321 * \retval 1 on success 00322 * \retval 0 if there's a problem, or it's already there. 00323 */ 00324 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00325 int _ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func); 00326 #define ast_hashtab_insert_safe(a,b) _ast_hashtab_insert_safe(a,b,__FILE__, __LINE__, __PRETTY_FUNCTION__) 00327 #else 00328 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj); 00329 #endif 00330 00331 /*! 00332 * \brief Lookup this object in the hash table. 00333 * \param tab 00334 * \param obj 00335 * \retval a ptr if found 00336 * \retval NULL if not found 00337 */ 00338 void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj); 00339 00340 /*! 00341 * \brief Use this if have the hash val for the object 00342 * \note This and avoid the recalc of the hash (the modulus (table_size) is not applied) 00343 */ 00344 void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval); 00345 00346 /*! 00347 * \brief Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails. 00348 * \note This has the modulus applied, and will not be useful for long term storage if the table is resizable. 00349 */ 00350 void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *h); 00351 00352 /*! \brief Returns key stats for the table */ 00353 void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets); 00354 00355 /*! \brief Returns the number of elements stored in the hashtab */ 00356 int ast_hashtab_size( struct ast_hashtab *tab); 00357 00358 /*! \brief Returns the size of the bucket array in the hashtab */ 00359 int ast_hashtab_capacity( struct ast_hashtab *tab); 00360 00361 /*! \brief Return a copy of the hash table */ 00362 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00363 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); 00364 #define ast_hashtab_dup(a,b) _ast_hashtab_dup(a,b,__FILE__,__LINE__,__PRETTY_FUNCTION__) 00365 #else 00366 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj)); 00367 #endif 00368 00369 /*! \brief Gives an iterator to hastable */ 00370 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00371 struct ast_hashtab_iter *_ast_hashtab_start_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func); 00372 #define ast_hashtab_start_traversal(a) _ast_hashtab_start_traversal(a,__FILE__,__LINE__,__PRETTY_FUNCTION__) 00373 #else 00374 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab); 00375 #endif 00376 00377 /*! \brief end the traversal, free the iterator, unlock if necc. */ 00378 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it); 00379 00380 /*! \brief Gets the next object in the list, advances iter one step returns null on end of traversal */ 00381 void *ast_hashtab_next(struct ast_hashtab_iter *it); 00382 00383 /*! \brief Looks up the object, removes the corresponding bucket */ 00384 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj); 00385 00386 /*! \brief Hash the object and then compare ptrs in bucket list instead of 00387 calling the compare routine, will remove the bucket */ 00388 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj); 00389 00390 /* ------------------ */ 00391 /* for lock-enabled traversals with ability to remove an object during the traversal*/ 00392 /* ------------------ */ 00393 00394 /*! \brief Gives an iterator to hastable */ 00395 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE)) 00396 struct ast_hashtab_iter *_ast_hashtab_start_write_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func); 00397 #define ast_hashtab_start_write_traversal(a) _ast_hashtab_start_write_traversal(a,__FILE__,__LINE__,__PRETTY_FUNCTION__) 00398 #else 00399 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab); 00400 #endif 00401 00402 /*! \brief Looks up the object, removes the corresponding bucket */ 00403 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj); 00404 00405 /*! \brief Hash the object and then compare ptrs in bucket list instead of 00406 calling the compare routine, will remove the bucket */ 00407 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj); 00408 00409 /* ------------------ */ 00410 /* ------------------ */ 00411 00412 /* user-controlled hashtab locking. Create a hashtab without locking, then call the 00413 following locking routines yourself to lock the table between threads. */ 00414 00415 /*! \brief Call this after you create the table to init the lock */ 00416 void ast_hashtab_initlock(struct ast_hashtab *tab); 00417 /*! \brief Request a write-lock on the table. */ 00418 void ast_hashtab_wrlock(struct ast_hashtab *tab); 00419 /*! \brief Request a read-lock on the table -- don't change anything! */ 00420 void ast_hashtab_rdlock(struct ast_hashtab *tab); 00421 /*! \brief release a read- or write- lock. */ 00422 void ast_hashtab_unlock(struct ast_hashtab *tab); 00423 /*! \brief Call this before you destroy the table. */ 00424 void ast_hashtab_destroylock(struct ast_hashtab *tab); 00425 00426 00427 #endif