This is the perhaps the biggest, boldest, most daring change I've ever committed...
[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 /* generic (perhaps overly so) hashtable implementation */
23
24 /* notes:
25
26 A hash table is a structure that allows for an exact-match search
27 in O(1) (or close to that) time.
28
29 The method: given: a set of {key,val} pairs. (at a minimum).
30             given: a hash function, which, given a key,
31             will return an integer. Ideally, each key in the
32             set will have its own unique associated hash value.
33                         This hash number will index into an array. "buckets"
34             are what the elements of this array are called. To
35             handle possible collisions in hash values, buckets can form a list.
36
37 The key for a value must be contained in the value, or we won't
38 be able to find it in the bucket list.
39
40 This implementation is pretty generic, because:
41  1. The value and key are expected to be in a structure
42     (along with other data, perhaps) and it's address is a "void *".
43  2. The pointer to a compare function must be passed in at the
44     time of creation, and is stored in the hashtable.
45  3. The pointer to a resize function, which returns 1 if the
46     hash table is to be grown. A default routine is provided
47     if the pointer is NULL, and uses the java hashtable metric
48     of a 75% load factor.
49  4. The pointer to a "new size" function, which returns a preferable
50     new size for the hash table bucket array. By default, a function
51     is supplied which roughly doubles the size of the array, is provided.
52     This size should ideally be a prime number.
53  5. The hashing function pointer must also be supplied. This function
54     must be written by the user to access the keys in the objects being
55     stored. Some helper functions that use a simple "mult by prime, add
56     the next char", sort of string hash, or a simple modulus of the hash
57     table size for ints, is provided; the user can use these simple
58     algorithms to generate a hash, or implement any other algorithms they
59     wish.
60  6. Recently updated the hash routines to use Doubly-linked lists for buckets,
61     and added a doubly-linked list that threads thru every bucket in the table.
62     The list of all buckets is on the HashTab struct. The Traversal was modified
63     to go thru this list instead of searching the bucket array for buckets.
64     This also should make it safe to remove a bucket during the traversal.
65     Removal and destruction routines will work faster.
66 */
67
68 struct ast_hashtab_bucket
69 {
70         const void *object;                    /* whatever it is we are storing in this table */
71         struct ast_hashtab_bucket *next;       /* a DLL of buckets in hash collision */
72         struct ast_hashtab_bucket *prev;       /* a DLL of buckets in hash collision */
73         struct ast_hashtab_bucket *tnext;      /* a DLL of all the hash buckets for traversal */
74         struct ast_hashtab_bucket *tprev;      /* a DLL of all the hash buckets for traversal */
75 };
76
77 struct ast_hashtab
78 {
79         struct ast_hashtab_bucket **array;
80         struct ast_hashtab_bucket *tlist; /* the head of a DLList of all the hashbuckets in the table (for traversal). */
81         
82         int (*compare) (const void *a, const void *b);            /* a ptr to func that returns int, and take two void* ptrs, compares them, 
83                                                                                                          rets -1 if a < b; rets 0 if a==b; rets 1 if a>b */
84         int (*newsize) (struct ast_hashtab *tab);     /* a ptr to func that returns int, a new size for hash tab, based on curr_size */
85         int (*resize) (struct ast_hashtab *tab);      /* a function to decide whether this hashtable should be resized now */
86         unsigned int (*hash) (const void *obj);         /* a hash func ptr for this table. Given a raw ptr to an obj, 
87                                                                                                          it calcs a hash.*/
88         int hash_tab_size;                            /* the size of the bucket array */
89         int hash_tab_elements;                        /* the number of objects currently stored in the table */
90         int largest_bucket_size;                      /* a stat on the health of the table */
91         int resize_count;                             /* a count of the number of times this table has been
92                                                                                                          resized */
93         int do_locking;                               /* if 1, use locks to guarantee safety of insertions/deletions */
94         /* this spot reserved for the proper lock storage */
95         ast_rwlock_t lock;                                /* is this as good as it sounds? */
96 };
97
98 struct ast_hashtab_iter              /* an iterator for traversing the buckets */
99 {
100         struct ast_hashtab *tab;
101         struct ast_hashtab_bucket *next;
102 };
103
104
105 /* some standard, default routines for general use */
106
107 int isPrime(int num); /* this one is handy for sizing the hash table, tells if num is prime or not */
108
109 int ast_hashtab_compare_strings(const void *a, const void *b); /* assumes a and b are char * and returns 0 if they match */
110
111
112 int ast_hashtab_compare_strings_nocase(const void *a, const void *b); /* assumes a & b are strings, returns 0 if they match (strcasecmp) */
113
114
115 int ast_hashtab_compare_ints(const void *a, const void *b);  /* assumes a & b are int *, returns a != b */
116
117
118 int ast_hashtab_compare_shorts(const void *a, const void *b);  /* assumes a & b are short *, returns a != b */
119
120
121 int ast_hashtab_resize_java(struct ast_hashtab *tab); /* returns 1 if the table is 75% full or more */
122
123
124 int ast_hashtab_resize_tight(struct ast_hashtab *tab); /* not yet specified; probably will return 1 if table is 100% full */
125
126
127 int ast_hashtab_resize_none(struct ast_hashtab *tab); /* no resizing; always return 0 */
128
129
130 int ast_hashtab_newsize_java(struct ast_hashtab *tab);  /* returns a prime number roughly 2x the current table size */
131
132
133 int ast_hashtab_newsize_tight(struct ast_hashtab *tab); /* not yet specified, probably will return 1.5x the current table size */
134
135
136 int ast_hashtab_newsize_none(struct ast_hashtab *tab); /* always return current size -- no resizing */
137
138
139 unsigned int ast_hashtab_hash_string(const void *obj); /* hashes a string to a number, mod is applied so it in the range 0 to mod-1 */
140
141
142 unsigned int ast_hashtab_hash_string_nocase(const void *obj);  /* upcases each char before using them for a hash */
143
144
145 unsigned int ast_hashtab_hash_string_sax(const void *obj); /* from Josh */
146
147
148 unsigned int ast_hashtab_hash_int(const int num);  /* right now, both these funcs are just result = num%modulus; */
149
150
151 unsigned int ast_hashtab_hash_short(const short num);
152
153
154 struct ast_hashtab * ast_hashtab_create(int initial_buckets,
155                                         int (*compare)(const void *a, const void *b),        /* a func to compare two elements in the hash -- cannot be null  */
156                                         int (*resize)(struct ast_hashtab *),     /* a func to decide if the table needs to be resized, 
157                                                                                 a NULL ptr here will cause a default to be used */
158                                         int (*newsize)(struct ast_hashtab *tab), /* a ptr to func that returns a new size of the array. 
159                                                                                 A NULL will cause a default to be used */
160                                         unsigned int (*hash)(const void *obj),     /* a func to do the hashing */
161                                         int do_locking );                        /* use locks to guarantee safety of iterators/insertion/deletion */
162
163
164         /* this func will free the hash table and all its memory. It
165            doesn't touch the objects stored in it */
166 void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj));
167
168
169         /* normally, you'd insert "safely" by checking to see if the element is
170            already there; in this case, you must already have checked. If an element
171            is already in the hashtable, that matches this one, most likely this one
172            will be found first. */
173         /* will force a resize if the resize func returns 1 */
174         /* returns 1 on success, 0 if there's a problem */
175 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj);
176
177         /* same as the above, but h is the hash index; won't hash to find the index */
178 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, int h);
179
180
181         /* check to see if the element is already there; insert only if
182            it is not there.*/
183         /* will force a resize if the resize func returns 1 */
184         /* returns 1 on success, 0 if there's a problem, or it's already there. */
185 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj);
186
187
188         /* lookup this object in the hash table. return a ptr if found, or NULL if not */
189 void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj);
190
191     /* if you know the hash val for the object, then use this and avoid the recalc
192            of the hash (the modulus (table_size) is not applied) */
193 void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval);
194
195         /* same as the above lookup, but sets h to the key hash value if the lookup fails -- this has the modulus 
196        applied, and will not be useful for long term storage if the table is resizable */
197 void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, int *h);
198
199         /* returns key stats for the table */
200 void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets);
201
202         /* this function returns the number of elements stored in the hashtab */
203 int  ast_hashtab_size( struct ast_hashtab *tab);
204
205         /* this function returns the size of the bucket array in the hashtab */
206 int  ast_hashtab_capacity( struct ast_hashtab *tab);
207
208     /* this function will return a copy of the table */
209 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj));
210
211         /* returns an iterator */
212 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab);
213
214         /* end the traversal, free the iterator, unlock if necc. */
215 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it);
216
217         /* returns the next object in the list, advances iter one step, returns null on end of traversal */
218 void *ast_hashtab_next(struct ast_hashtab_iter *it);
219
220
221         /* looks up the object; removes the corresponding bucket */
222 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj);
223
224
225         /* looks up the object by hash and then comparing pts in bucket list instead of
226            calling the compare routine; removes the bucket */
227 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj);
228
229 /* ------------------ */
230 /* for lock-enabled traversals with ability to remove an object during the traversal*/
231 /* ------------------ */
232
233         /* returns an iterator */
234 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab);
235
236         /* looks up the object; removes the corresponding bucket */
237 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj);
238
239
240         /* looks up the object by hash and then comparing pts in bucket list instead of
241            calling the compare routine; removes the bucket */
242 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj);
243
244 /* ------------------ */
245 /* ------------------ */
246
247 /* user-controlled hashtab locking. Create a hashtab without locking, then call the
248    following locking routines yourself to lock the table between threads. */
249
250 void ast_hashtab_initlock(struct ast_hashtab *tab); /* call this after you create the table to init the lock */
251 void ast_hashtab_wrlock(struct ast_hashtab *tab); /* request a write-lock on the  table. */
252 void ast_hashtab_rdlock(struct ast_hashtab *tab); /* request a read-lock on the table-- don't change anything! */
253 void ast_hashtab_unlock(struct ast_hashtab *tab);      /* release a read- or write- lock. */
254 void ast_hashtab_destroylock(struct ast_hashtab *tab); /* call this before you destroy the table. */
255
256
257 #endif