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