]>
Commit | Line | Data |
---|---|---|
e53af1a6 JR |
1 | /* |
2 | Copyright (c) 2002, 2004, Christopher Clark | |
3 | All rights reserved. | |
4 | ||
5 | Redistribution and use in source and binary forms, with or without | |
6 | modification, are permitted provided that the following conditions are met: | |
7 | ||
8 | * Redistributions of source code must retain the above copyright notice, | |
9 | this list of conditions and the following disclaimer. | |
10 | ||
11 | * Redistributions in binary form must reproduce the above copyright notice, | |
12 | this list of conditions and the following disclaimer in the documentation | |
13 | and/or other materials provided with the distribution. | |
14 | ||
15 | * Neither the name of the original author; nor the names of any | |
16 | contributors may be used to endorse or promote products derived from this | |
17 | software without specific prior written permission. | |
18 | ||
19 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
20 | AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
21 | IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
22 | ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE | |
23 | LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
24 | CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
25 | SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
26 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
27 | CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
28 | ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
29 | POSSIBILITY OF SUCH DAMAGE. | |
30 | */ | |
31 | ||
32 | #ifndef __HASHTABLE_CWC22_H__ | |
33 | #define __HASHTABLE_CWC22_H__ | |
34 | ||
6256d04b JR |
35 | #include "config.h" |
36 | ||
e53af1a6 JR |
37 | struct hashtable; |
38 | ||
39 | /* Example of use: | |
40 | * | |
41 | * struct hashtable *h; | |
42 | * struct some_key *k; | |
43 | * struct some_value *v; | |
44 | * | |
45 | * static unsigned int hash_from_key_fn( void *k ); | |
46 | * static int keys_equal_fn ( void *key1, void *key2 ); | |
47 | * | |
48 | * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn); | |
49 | * k = (struct some_key *) malloc(sizeof(struct some_key)); | |
50 | * v = (struct some_value *) malloc(sizeof(struct some_value)); | |
51 | * | |
52 | * (initialise k and v to suitable values) | |
53 | * | |
54 | * if (! hashtable_insert(h,k,v) ) | |
55 | * { exit(-1); } | |
56 | * | |
57 | * if (NULL == (found = hashtable_search(h,k) )) | |
58 | * { printf("not found!"); } | |
59 | * | |
60 | * if (NULL == (found = hashtable_remove(h,k) )) | |
61 | * { printf("Not found\n"); } | |
62 | * | |
63 | */ | |
64 | ||
65 | /* Macros may be used to define type-safe(r) hashtable access functions, with | |
66 | * methods specialized to take known key and value types as parameters. | |
67 | * | |
68 | * Example: | |
69 | * | |
70 | * Insert this at the start of your file: | |
71 | * | |
72 | * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value); | |
73 | * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value); | |
74 | * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value); | |
75 | * | |
76 | * This defines the functions 'insert_some', 'search_some' and 'remove_some'. | |
77 | * These operate just like hashtable_insert etc., with the same parameters, | |
78 | * but their function signatures have 'struct some_key *' rather than | |
79 | * 'void *', and hence can generate compile time errors if your program is | |
80 | * supplying incorrect data as a key (and similarly for value). | |
81 | * | |
82 | * Note that the hash and key equality functions passed to create_hashtable | |
83 | * still take 'void *' parameters instead of 'some key *'. This shouldn't be | |
84 | * a difficult issue as they're only defined and passed once, and the other | |
85 | * functions will ensure that only valid keys are supplied to them. | |
86 | * | |
87 | * The cost for this checking is increased code size and runtime overhead | |
88 | * - if performance is important, it may be worth switching back to the | |
89 | * unsafe methods once your program has been debugged with the safe methods. | |
90 | * This just requires switching to some simple alternative defines - eg: | |
91 | * #define insert_some hashtable_insert | |
92 | * | |
93 | */ | |
94 | ||
95 | /***************************************************************************** | |
96 | * create_hashtable | |
97 | ||
98 | * @name create_hashtable | |
99 | * @param minsize minimum initial size of hashtable | |
100 | * @param hashfunction function for hashing keys | |
101 | * @param key_eq_fn function for determining key equality | |
102 | * @return newly created hashtable or NULL on failure | |
103 | */ | |
104 | ||
105 | struct hashtable * | |
106 | create_hashtable(unsigned int minsize, | |
107 | unsigned int (*hashfunction) (void*), | |
108 | int (*key_eq_fn) (void*,void*)); | |
109 | ||
110 | /***************************************************************************** | |
111 | * hashtable_insert | |
112 | ||
113 | * @name hashtable_insert | |
114 | * @param h the hashtable to insert into | |
115 | * @param k the key - hashtable claims ownership and will free on removal | |
116 | * @param v the value - does not claim ownership | |
117 | * @return non-zero for successful insertion | |
118 | * | |
119 | * This function will cause the table to expand if the insertion would take | |
120 | * the ratio of entries to table size over the maximum load factor. | |
121 | * | |
122 | * This function does not check for repeated insertions with a duplicate key. | |
123 | * The value returned when using a duplicate key is undefined -- when | |
124 | * the hashtable changes size, the order of retrieval of duplicate key | |
125 | * entries is reversed. | |
126 | * If in doubt, remove before insert. | |
127 | */ | |
128 | ||
129 | int | |
130 | hashtable_insert(struct hashtable *h, void *k, void *v); | |
131 | ||
132 | #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ | |
133 | int fnname (struct hashtable *h, keytype *k, valuetype *v) \ | |
134 | { \ | |
135 | return hashtable_insert(h,k,v); \ | |
136 | } | |
137 | ||
138 | /***************************************************************************** | |
139 | * hashtable_search | |
140 | ||
141 | * @name hashtable_search | |
142 | * @param h the hashtable to search | |
143 | * @param k the key to search for - does not claim ownership | |
144 | * @return the value associated with the key, or NULL if none found | |
145 | */ | |
146 | ||
147 | void * | |
148 | hashtable_search(struct hashtable *h, void *k); | |
149 | ||
150 | #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \ | |
151 | valuetype * fnname (struct hashtable *h, keytype *k) \ | |
152 | { \ | |
153 | return (valuetype *) (hashtable_search(h,k)); \ | |
154 | } | |
155 | ||
156 | /***************************************************************************** | |
157 | * hashtable_remove | |
158 | ||
159 | * @name hashtable_remove | |
160 | * @param h the hashtable to remove the item from | |
161 | * @param k the key to search for - does not claim ownership | |
162 | * @return the value associated with the key, or NULL if none found | |
163 | */ | |
164 | ||
165 | void * /* returns value */ | |
166 | hashtable_remove(struct hashtable *h, void *k); | |
167 | ||
168 | #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ | |
169 | valuetype * fnname (struct hashtable *h, keytype *k) \ | |
170 | { \ | |
171 | return (valuetype *) (hashtable_remove(h,k)); \ | |
172 | } | |
173 | ||
174 | ||
175 | /***************************************************************************** | |
176 | * hashtable_count | |
177 | ||
178 | * @name hashtable_count | |
179 | * @param h the hashtable | |
180 | * @return the number of items stored in the hashtable | |
181 | */ | |
182 | unsigned int | |
183 | hashtable_count(struct hashtable *h); | |
184 | ||
185 | ||
186 | /***************************************************************************** | |
187 | * hashtable_destroy | |
188 | ||
189 | * @name hashtable_destroy | |
190 | * @param h the hashtable | |
191 | * @param free_values whether to call 'free' on the remaining values | |
192 | */ | |
193 | ||
194 | void | |
195 | hashtable_destroy(struct hashtable *h, int free_values); | |
196 | ||
197 | #endif /* __HASHTABLE_CWC22_H__ */ | |
198 | ||
199 | /* | |
200 | * Copyright (c) 2002, Christopher Clark | |
201 | * All rights reserved. | |
202 | * | |
203 | * Redistribution and use in source and binary forms, with or without | |
204 | * modification, are permitted provided that the following conditions | |
205 | * are met: | |
206 | * | |
207 | * * Redistributions of source code must retain the above copyright | |
208 | * notice, this list of conditions and the following disclaimer. | |
209 | * | |
210 | * * Redistributions in binary form must reproduce the above copyright | |
211 | * notice, this list of conditions and the following disclaimer in the | |
212 | * documentation and/or other materials provided with the distribution. | |
213 | * | |
214 | * * Neither the name of the original author; nor the names of any contributors | |
215 | * may be used to endorse or promote products derived from this software | |
216 | * without specific prior written permission. | |
217 | * | |
218 | * | |
219 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
220 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
221 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
222 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER | |
223 | * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
224 | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
225 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | |
226 | * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF | |
227 | * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING | |
228 | * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | |
229 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
230 | */ |