1 /************************************************************************** 2 * 3 * Copyright 2008 VMware, Inc. 4 * All Rights Reserved. 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a 7 * copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sub license, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice (including the 15 * next paragraph) shall be included in all copies or substantial portions 16 * of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR 22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 * 26 **************************************************************************/ 27 28 /** 29 * @file 30 * General purpose hash table implementation. 31 * 32 * Just uses the cso_hash for now, but it might be better switch to a linear 33 * probing hash table implementation at some point -- as it is said they have 34 * better lookup and cache performance and it appears to be possible to write 35 * a lock-free implementation of such hash tables . 36 * 37 * @author Jos Fonseca <jfonseca (at) vmware.com> 38 */ 39 40 41 #include "pipe/p_compiler.h" 42 #include "util/u_debug.h" 43 44 #include "cso_cache/cso_hash.h" 45 46 #include "util/u_memory.h" 47 #include "util/u_hash_table.h" 48 49 50 struct util_hash_table 51 { 52 struct cso_hash *cso; 53 54 /** Hash function */ 55 unsigned (*hash)(void *key); 56 57 /** Compare two keys */ 58 int (*compare)(void *key1, void *key2); 59 60 /** free value */ 61 void (*destroy)(void *value); 62 }; 63 64 65 struct util_hash_table_item 66 { 67 void *key; 68 void *value; 69 }; 70 71 72 static inline struct util_hash_table_item * 73 util_hash_table_item(struct cso_hash_iter iter) 74 { 75 return (struct util_hash_table_item *)cso_hash_iter_data(iter); 76 } 77 78 79 struct util_hash_table * 80 util_hash_table_create(unsigned (*hash)(void *key), 81 int (*compare)(void *key1, void *key2), 82 void (*destroy)(void *value)) 83 { 84 struct util_hash_table *ht; 85 86 ht = MALLOC_STRUCT(util_hash_table); 87 if(!ht) 88 return NULL; 89 90 ht->cso = cso_hash_create(); 91 if(!ht->cso) { 92 FREE(ht); 93 return NULL; 94 } 95 96 ht->hash = hash; 97 ht->compare = compare; 98 ht->destroy = destroy; 99 100 return ht; 101 } 102 103 104 static inline struct cso_hash_iter 105 util_hash_table_find_iter(struct util_hash_table *ht, 106 void *key, 107 unsigned key_hash) 108 { 109 struct cso_hash_iter iter; 110 struct util_hash_table_item *item; 111 112 iter = cso_hash_find(ht->cso, key_hash); 113 while (!cso_hash_iter_is_null(iter)) { 114 item = (struct util_hash_table_item *)cso_hash_iter_data(iter); 115 if (!ht->compare(item->key, key)) 116 break; 117 iter = cso_hash_iter_next(iter); 118 } 119 120 return iter; 121 } 122 123 124 static inline struct util_hash_table_item * 125 util_hash_table_find_item(struct util_hash_table *ht, 126 void *key, 127 unsigned key_hash) 128 { 129 struct cso_hash_iter iter; 130 struct util_hash_table_item *item; 131 132 iter = cso_hash_find(ht->cso, key_hash); 133 while (!cso_hash_iter_is_null(iter)) { 134 item = (struct util_hash_table_item *)cso_hash_iter_data(iter); 135 if (!ht->compare(item->key, key)) 136 return item; 137 iter = cso_hash_iter_next(iter); 138 } 139 140 return NULL; 141 } 142 143 144 enum pipe_error 145 util_hash_table_set(struct util_hash_table *ht, 146 void *key, 147 void *value) 148 { 149 unsigned key_hash; 150 struct util_hash_table_item *item; 151 struct cso_hash_iter iter; 152 153 assert(ht); 154 if (!ht) 155 return PIPE_ERROR_BAD_INPUT; 156 157 key_hash = ht->hash(key); 158 159 item = util_hash_table_find_item(ht, key, key_hash); 160 if(item) { 161 ht->destroy(item->value); 162 item->value = value; 163 return PIPE_OK; 164 } 165 166 item = MALLOC_STRUCT(util_hash_table_item); 167 if(!item) 168 return PIPE_ERROR_OUT_OF_MEMORY; 169 170 item->key = key; 171 item->value = value; 172 173 iter = cso_hash_insert(ht->cso, key_hash, item); 174 if(cso_hash_iter_is_null(iter)) { 175 FREE(item); 176 return PIPE_ERROR_OUT_OF_MEMORY; 177 } 178 179 return PIPE_OK; 180 } 181 182 183 void * 184 util_hash_table_get(struct util_hash_table *ht, 185 void *key) 186 { 187 unsigned key_hash; 188 struct util_hash_table_item *item; 189 190 assert(ht); 191 if (!ht) 192 return NULL; 193 194 key_hash = ht->hash(key); 195 196 item = util_hash_table_find_item(ht, key, key_hash); 197 if(!item) 198 return NULL; 199 200 return item->value; 201 } 202 203 204 void 205 util_hash_table_remove(struct util_hash_table *ht, 206 void *key) 207 { 208 unsigned key_hash; 209 struct cso_hash_iter iter; 210 struct util_hash_table_item *item; 211 212 assert(ht); 213 if (!ht) 214 return; 215 216 key_hash = ht->hash(key); 217 218 iter = util_hash_table_find_iter(ht, key, key_hash); 219 if(cso_hash_iter_is_null(iter)) 220 return; 221 222 item = util_hash_table_item(iter); 223 assert(item); 224 ht->destroy(item->value); 225 FREE(item); 226 227 cso_hash_erase(ht->cso, iter); 228 } 229 230 231 void 232 util_hash_table_clear(struct util_hash_table *ht) 233 { 234 struct cso_hash_iter iter; 235 struct util_hash_table_item *item; 236 237 assert(ht); 238 if (!ht) 239 return; 240 241 iter = cso_hash_first_node(ht->cso); 242 while (!cso_hash_iter_is_null(iter)) { 243 item = (struct util_hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter)); 244 ht->destroy(item->value); 245 FREE(item); 246 iter = cso_hash_first_node(ht->cso); 247 } 248 } 249 250 251 enum pipe_error 252 util_hash_table_foreach(struct util_hash_table *ht, 253 enum pipe_error (*callback) 254 (void *key, void *value, void *data), 255 void *data) 256 { 257 struct cso_hash_iter iter; 258 struct util_hash_table_item *item; 259 enum pipe_error result; 260 261 assert(ht); 262 if (!ht) 263 return PIPE_ERROR_BAD_INPUT; 264 265 iter = cso_hash_first_node(ht->cso); 266 while (!cso_hash_iter_is_null(iter)) { 267 item = (struct util_hash_table_item *)cso_hash_iter_data(iter); 268 result = callback(item->key, item->value, data); 269 if(result != PIPE_OK) 270 return result; 271 iter = cso_hash_iter_next(iter); 272 } 273 274 return PIPE_OK; 275 } 276 277 278 void 279 util_hash_table_destroy(struct util_hash_table *ht) 280 { 281 struct cso_hash_iter iter; 282 struct util_hash_table_item *item; 283 284 assert(ht); 285 if (!ht) 286 return; 287 288 iter = cso_hash_first_node(ht->cso); 289 while (!cso_hash_iter_is_null(iter)) { 290 item = (struct util_hash_table_item *)cso_hash_iter_data(iter); 291 ht->destroy(item->value); 292 FREE(item); 293 iter = cso_hash_iter_next(iter); 294 } 295 296 cso_hash_delete(ht->cso); 297 298 FREE(ht); 299 } 300
