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