FreeSWITCH API Documentation  1.7.0
switch_hashtable.h
Go to the documentation of this file.
1 /*
2  * FreeSWITCH Modular Media Switching Software Library / Soft-Switch Application
3  *
4  * switch_hashtable.h -- Hashtable
5  *
6  */
7 
8 
9 /* hashtable.h Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
10 
11 #ifndef __HASHTABLE_CWC22_H__
12 #define __HASHTABLE_CWC22_H__
13 #ifdef _MSC_VER
14 #ifndef __inline__
15 #define __inline__ __inline
16 #endif
17 #endif
18 #include "switch.h"
19 
20 #ifdef __cplusplus
21 extern "C" {
22 #endif
23 
26 
27 
28 /* Example of use:
29  *
30  * switch_hashtable_t *h;
31  * struct some_key *k;
32  * struct some_value *v;
33  *
34  * static unsigned int hash_from_key_fn( void *k );
35  * static int keys_equal_fn ( void *key1, void *key2 );
36  *
37  * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
38  * k = (struct some_key *) malloc(sizeof(struct some_key));
39  * v = (struct some_value *) malloc(sizeof(struct some_value));
40  *
41  * (initialise k and v to suitable values)
42  *
43  * if (! hashtable_insert(h,k,v) )
44  * { exit(-1); }
45  *
46  * if (NULL == (found = hashtable_search(h,k) ))
47  * { printf("not found!"); }
48  *
49  * if (NULL == (found = hashtable_remove(h,k) ))
50  * { printf("Not found\n"); }
51  *
52  */
53 
54 /* Macros may be used to define type-safe(r) hashtable access functions, with
55  * methods specialized to take known key and value types as parameters.
56  *
57  * Example:
58  *
59  * Insert this at the start of your file:
60  *
61  * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
62  * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
63  * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
64  *
65  * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
66  * These operate just like hashtable_insert etc., with the same parameters,
67  * but their function signatures have 'struct some_key *' rather than
68  * 'void *', and hence can generate compile time errors if your program is
69  * supplying incorrect data as a key (and similarly for value).
70  *
71  * Note that the hash and key equality functions passed to create_hashtable
72  * still take 'void *' parameters instead of 'some key *'. This shouldn't be
73  * a difficult issue as they're only defined and passed once, and the other
74  * functions will ensure that only valid keys are supplied to them.
75  *
76  * The cost for this checking is increased code size and runtime overhead
77  * - if performance is important, it may be worth switching back to the
78  * unsafe methods once your program has been debugged with the safe methods.
79  * This just requires switching to some simple alternative defines - eg:
80  * #define insert_some hashtable_insert
81  *
82  */
83 
84 /*****************************************************************************
85  * create_hashtable
86 
87  * @name create_hashtable
88  * @param minsize minimum initial size of hashtable
89  * @param hashfunction function for hashing keys
90  * @param key_eq_fn function for determining key equality
91  * @return newly created hashtable or NULL on failure
92  */
93 
95 switch_create_hashtable(switch_hashtable_t **hp, unsigned int minsize,
96  unsigned int (*hashfunction) (void*),
97  int (*key_eq_fn) (void*,void*));
98 
99 /*****************************************************************************
100  * hashtable_insert
101 
102  * @name hashtable_insert
103  * @param h the hashtable to insert into
104  * @param k the key - hashtable claims ownership and will free on removal
105  * @param v the value - does not claim ownership
106  * @return non-zero for successful insertion
107  *
108  * This function will cause the table to expand if the insertion would take
109  * the ratio of entries to table size over the maximum load factor.
110  *
111  * This function does not check for repeated insertions with a duplicate key.
112  * The value returned when using a duplicate key is undefined -- when
113  * the hashtable changes size, the order of retrieval of duplicate key
114  * entries is reversed.
115  * If in doubt, remove before insert.
116  */
117 
118 
119 typedef enum {
125 
126 SWITCH_DECLARE(int)
128 #define switch_hashtable_insert(_h, _k, _v, _f) switch_hashtable_insert_destructor(_h, _k, _v, _f, NULL)
129 
130 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
131  int fnname (switch_hashtable_t *h, keytype *k, valuetype *v) \
132  { \
133  return hashtable_insert(h,k,v); \
134  }
135 
136 /*****************************************************************************
137  * hashtable_search
138 
139  * @name hashtable_search
140  * @param h the hashtable to search
141  * @param k the key to search for - does not claim ownership
142  * @return the value associated with the key, or NULL if none found
143  */
144 
145 SWITCH_DECLARE(void *)
147 
148 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
149  valuetype * fnname (switch_hashtable_t *h, keytype *k) \
150  { \
151  return (valuetype *) (hashtable_search(h,k)); \
152  }
153 
154 /*****************************************************************************
155  * hashtable_remove
156 
157  * @name hashtable_remove
158  * @param h the hashtable to remove the item from
159  * @param k the key to search for - does not claim ownership
160  * @return the value associated with the key, or NULL if none found
161  */
162 
163 SWITCH_DECLARE(void *) /* returns value */
165 
166 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
167  valuetype * fnname (switch_hashtable_t *h, keytype *k) \
168  { \
169  return (valuetype *) (hashtable_remove(h,k)); \
170  }
171 
172 
173 /*****************************************************************************
174  * hashtable_count
175 
176  * @name hashtable_count
177  * @param h the hashtable
178  * @return the number of items stored in the hashtable
179  */
180 SWITCH_DECLARE(unsigned int)
182 
183 
184 /*****************************************************************************
185  * hashtable_destroy
186 
187  * @name hashtable_destroy
188  * @param h the hashtable
189  * @param free_values whether to call 'free' on the remaining values
190  */
191 
192 SWITCH_DECLARE(void)
194 
196 #define switch_hashtable_first(_h) switch_hashtable_first_iter(_h, NULL)
198 SWITCH_DECLARE(void) switch_hashtable_this(switch_hashtable_iterator_t *i, const void **key, switch_ssize_t *klen, void **val);
200 
201 static inline uint32_t switch_hash_default_int(void *ky) {
202  uint32_t x = *((uint32_t *)ky);
203  x = ((x >> 16) ^ x) * 0x45d9f3b;
204  x = ((x >> 16) ^ x) * 0x45d9f3b;
205  x = ((x >> 16) ^ x);
206  return x;
207 }
208 
209 static inline int switch_hash_equalkeys_int(void *k1, void *k2)
210 {
211  return *(uint32_t *)k1 == *(uint32_t *)k2;
212 }
213 
214 static inline int switch_hash_equalkeys(void *k1, void *k2)
215 {
216  return strcmp((char *) k1, (char *) k2) ? 0 : 1;
217 }
218 
219 static inline int switch_hash_equalkeys_ci(void *k1, void *k2)
220 {
221  return strcasecmp((char *) k1, (char *) k2) ? 0 : 1;
222 }
223 
224 static inline uint32_t switch_hash_default(void *ky)
225 {
226  unsigned char *str = (unsigned char *) ky;
227  uint32_t hash = 0;
228  int c;
229 
230  while ((c = *str)) {
231  str++;
232  hash = c + (hash << 6) + (hash << 16) - hash;
233  }
234 
235  return hash;
236 }
237 
238 static inline uint32_t switch_hash_default_ci(void *ky)
239 {
240  unsigned char *str = (unsigned char *) ky;
241  uint32_t hash = 0;
242  int c;
243 
244  while ((c = switch_tolower(*str))) {
245  str++;
246  hash = c + (hash << 6) + (hash << 16) - hash;
247  }
248 
249  return hash;
250 }
251 
252 
253 
254 
255 #ifdef __cplusplus
256 } /* extern C */
257 #endif
258 
259 #endif /* __HASHTABLE_CWC22_H__ */
260 
261 /*
262  * Copyright (c) 2002, Christopher Clark
263  * All rights reserved.
264  *
265  * Redistribution and use in source and binary forms, with or without
266  * modification, are permitted provided that the following conditions
267  * are met:
268  *
269  * * Redistributions of source code must retain the above copyright
270  * notice, this list of conditions and the following disclaimer.
271  *
272  * * Redistributions in binary form must reproduce the above copyright
273  * notice, this list of conditions and the following disclaimer in the
274  * documentation and/or other materials provided with the distribution.
275  *
276  * * Neither the name of the original author; nor the names of any contributors
277  * may be used to endorse or promote products derived from this software
278  * without specific prior written permission.
279  *
280  *
281  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
282  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
283  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
284  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
285  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
286  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
287  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
288  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
289  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
290  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
291  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
292  */
293 
294 /* For Emacs:
295  * Local Variables:
296  * mode:c
297  * indent-tabs-mode:t
298  * tab-width:4
299  * c-basic-offset:4
300  * End:
301  * For VIM:
302  * vim:set softtabstop=4 shiftwidth=4 tabstop=4 noet:
303  */
struct switch_hashtable * h
void * switch_hashtable_search(switch_hashtable_t *h, void *k)
switch_hash_t * hash
Definition: switch_event.c:74
static int switch_hash_equalkeys_ci(void *k1, void *k2)
static uint32_t switch_hash_default_ci(void *ky)
intptr_t switch_ssize_t
switch_hashtable_iterator_t * switch_hashtable_first_iter(switch_hashtable_t *h, switch_hashtable_iterator_t *it)
int switch_hashtable_insert_destructor(switch_hashtable_t *h, void *k, void *v, hashtable_flag_t flags, hashtable_destructor_t destructor)
hashtable_flag_t
static uint32_t switch_hash_default_int(void *ky)
void switch_hashtable_this_val(switch_hashtable_iterator_t *i, void *val)
switch_status_t
Common return values.
switch_hashtable_iterator_t * switch_hashtable_next(switch_hashtable_iterator_t **iP)
void switch_hashtable_destroy(switch_hashtable_t **h)
Main Library Header.
#define SWITCH_DECLARE(type)
switch_status_t switch_create_hashtable(switch_hashtable_t **hp, unsigned int minsize, unsigned int(*hashfunction)(void *), int(*key_eq_fn)(void *, void *))
void * switch_hashtable_remove(switch_hashtable_t *h, void *k)
static int switch_hash_equalkeys(void *k1, void *k2)
unsigned int switch_hashtable_count(switch_hashtable_t *h)
static uint32_t switch_hash_default(void *ky)
static uint32_t switch_tolower(uint32_t eax)
Definition: switch_utils.h:81
void switch_hashtable_this(switch_hashtable_iterator_t *i, const void **key, switch_ssize_t *klen, void **val)
static int switch_hash_equalkeys_int(void *k1, void *k2)
void(* hashtable_destructor_t)(void *ptr)