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