I added a little verbage to hashtab for the hashtab_destroy func.
[asterisk/asterisk.git] / 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 /*! \brief For sizing the hash table, tells if num is prime or not */
112 int ast_is_prime(int num);
113
114 /*! 
115  * \brief assumes a and b are char * 
116  * \return 0 if they match 
117 */
118 int ast_hashtab_compare_strings(const void *a, const void *b);
119
120 /*!
121  * \brief assumes a & b are strings
122  * \return 0 if they match (strcasecmp) 
123 */
124 int ast_hashtab_compare_strings_nocase(const void *a, const void *b);
125
126 /*!
127  * \brief assumes a & b are int *
128  * \retval 0 if match
129  * \retval 1 a > b
130  * \retval -1 a < b
131 */
132 int ast_hashtab_compare_ints(const void *a, const void *b);
133
134 /*!
135  * \brief assumes a & b are short *
136  * \retval 0 if match
137  * \retval 1 a > b
138  * \retval -1 a < b
139 */
140 int ast_hashtab_compare_shorts(const void *a, const void *b);
141
142 /*!
143  * \brief determine if resize should occur
144  * \returns 1 if the table is 75% full or more
145 */
146 int ast_hashtab_resize_java(struct ast_hashtab *tab);
147
148 /*! \brief no resizing; always return 0 */
149 int ast_hashtab_resize_tight(struct ast_hashtab *tab);
150
151 /*! \brief no resizing; always return 0 */
152 int ast_hashtab_resize_none(struct ast_hashtab *tab);
153
154 /*! \brief Create a prime number roughly 2x the current table size */
155 int ast_hashtab_newsize_java(struct ast_hashtab *tab);
156
157 /* not yet specified, probably will return 1.5x the current table size */
158 int ast_hashtab_newsize_tight(struct ast_hashtab *tab);
159
160 /*! \brief always return current size -- no resizing */
161 int ast_hashtab_newsize_none(struct ast_hashtab *tab);
162
163 /*! 
164  * \brief Hashes a string to a number
165  * \param obj
166  * \note A modulus is applied so it in the range 0 to mod-1 
167 */
168 unsigned int ast_hashtab_hash_string(const void *obj);
169
170 /*! \brief Upperases each char before using them for a hash */
171 unsigned int ast_hashtab_hash_string_nocase(const void *obj);
172
173
174 unsigned int ast_hashtab_hash_string_sax(const void *obj); /* from Josh */
175
176
177 unsigned int ast_hashtab_hash_int(const int num);  /* right now, both these funcs are just result = num%modulus; */
178
179
180 unsigned int ast_hashtab_hash_short(const short num);
181
182
183 /*!
184  * \brief Create the hashtable list
185  * \param initial_buckets starting number of buckets
186  * \param compare a func ptr to compare two elements in the hash -- cannot be null 
187  * \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
188  * \param newsize a func ptr that returns a new size of the array. A NULL will cause a default to be used
189  * \param hash a func ptr to do the hashing
190  * \param do_locking use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now
191 */
192 struct ast_hashtab * ast_hashtab_create(int initial_buckets,
193                                         int (*compare)(const void *a, const void *b), 
194                                         int (*resize)(struct ast_hashtab *),    
195                                         int (*newsize)(struct ast_hashtab *tab),
196                                         unsigned int (*hash)(const void *obj), 
197                                         int do_locking );
198
199 /*!
200  * \brief This func will free the hash table and all its memory. 
201  * \note It doesn't touch the objects stored in it, unless you
202  *       specify a destroy func; it will call that func for each
203  *       object in the hashtab, remove all the objects, and then
204  *       free the hashtab itself. If no destroyfunc is specified
205  *       then the routine will assume you will free it yourself.
206  * \param tab
207  * \param objdestroyfunc
208 */
209 void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj));
210
211
212 /*!
213  * \brief Insert without checking 
214  * \param tab
215  * \param obj
216  *
217  * Normally, you'd insert "safely" by checking to see if the element is
218  * already there; in this case, you must already have checked. If an element
219  * is already in the hashtable, that matches this one, most likely this one
220  * will be found first. 
221  * \note will force a resize if the resize func returns 1
222  * \retval 1 on success
223  * \retval 0 if there's a problem
224 */
225 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj);
226
227 /*!
228  * \brief Insert without checking, hashing or locking
229  * \param tab
230  * \param obj
231  * \param h hashed index value
232  * 
233  * \note Will force a resize if the resize func returns 1
234  * \retval 1 on success
235  * \retval 0 if there's a problem
236 */
237 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h);
238
239 /*!
240  * \brief Check and insert new object only if it is not there.
241  * \note Will force a resize if the resize func returns 1
242  * \retval 1 on success
243  * \retval  0 if there's a problem, or it's already there. 
244 */
245 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj);
246
247 /*!
248  * \brief Lookup this object in the hash table. 
249  * \param tab 
250  * \param obj 
251  * \retval a ptr if found
252  * \retval NULL if not found
253 */
254 void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj);
255
256 /*!
257  * \brief  Use this if have the hash val for the object
258  * \note This and avoid the recalc of the hash (the modulus (table_size) is not applied)
259 */
260 void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval);
261
262 /*!
263  * \brief Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.
264  * \note This has the modulus applied, and will not be useful for long term storage if the table is resizable.
265 */
266 void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *h);
267
268 /*! \brief Returns key stats for the table */
269 void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets);
270
271 /*! \brief Returns the number of elements stored in the hashtab */
272 int ast_hashtab_size( struct ast_hashtab *tab);
273
274 /*! \brief Returns the size of the bucket array in the hashtab */
275 int ast_hashtab_capacity( struct ast_hashtab *tab);
276
277 /*! \brief Return a copy of the hash table */
278 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj));
279
280 /*! \brief Gives an iterator to hastable */
281 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab);
282
283 /*! \brief end the traversal, free the iterator, unlock if necc. */
284 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it);
285
286 /*! \brief Gets the next object in the list, advances iter one step returns null on end of traversal */
287 void *ast_hashtab_next(struct ast_hashtab_iter *it);
288
289 /*! \brief Looks up the object, removes the corresponding bucket */
290 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj);
291
292 /*! \brief Hash the object and then compare ptrs in bucket list instead of
293            calling the compare routine, will remove the bucket */
294 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj);
295
296 /* ------------------ */
297 /* for lock-enabled traversals with ability to remove an object during the traversal*/
298 /* ------------------ */
299
300 /*! \brief Gives an iterator to hastable */
301 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab);
302
303 /*! \brief Looks up the object, removes the corresponding bucket */
304 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj);
305
306 /*! \brief Hash the object and then compare ptrs in bucket list instead of
307            calling the compare routine, will remove the bucket */
308 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj);
309
310 /* ------------------ */
311 /* ------------------ */
312
313 /* user-controlled hashtab locking. Create a hashtab without locking, then call the
314    following locking routines yourself to lock the table between threads. */
315
316 /*! \brief Call this after you create the table to init the lock */
317 void ast_hashtab_initlock(struct ast_hashtab *tab); 
318 /*! \brief Request a write-lock on the table. */
319 void ast_hashtab_wrlock(struct ast_hashtab *tab); 
320 /*! \brief Request a read-lock on the table -- don't change anything! */
321 void ast_hashtab_rdlock(struct ast_hashtab *tab); 
322 /*! \brief release a read- or write- lock. */
323 void ast_hashtab_unlock(struct ast_hashtab *tab); 
324 /*! \brief Call this before you destroy the table. */
325 void ast_hashtab_destroylock(struct ast_hashtab *tab); 
326
327
328 #endif