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 util_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 #ifdef HAVE_CONFIG_H 42 #include "config.h" 43 #endif 44 45 #include "util_hash_table.h" 46 #include "util_hash.h" 47 48 #include <stdlib.h> 49 #include <assert.h> 50 51 struct util_hash_table 52 { 53 struct util_hash *head; 54 55 /** Hash function */ 56 unsigned (*make_hash)(void *key); 57 58 /** Compare two keys */ 59 int (*compare)(void *key1, void *key2); 60 }; 61 62 struct util_hash_table_item 63 { 64 void *key; 65 void *value; 66 }; 67 68 69 static struct util_hash_table_item * 70 util_hash_table_item(struct util_hash_iter iter) 71 { 72 return (struct util_hash_table_item *)util_hash_iter_data(iter); 73 } 74 75 drm_private struct util_hash_table * 76 util_hash_table_create(unsigned (*hash)(void *key), 77 int (*compare)(void *key1, void *key2)) 78 { 79 struct util_hash_table *ht; 80 81 ht = malloc(sizeof(struct util_hash_table)); 82 if(!ht) 83 return NULL; 84 85 ht->head = util_hash_create(); 86 if(!ht->head) { 87 free(ht); 88 return NULL; 89 } 90 91 ht->make_hash = hash; 92 ht->compare = compare; 93 94 return ht; 95 } 96 97 static struct util_hash_iter 98 util_hash_table_find_iter(struct util_hash_table *ht, 99 void *key, unsigned key_hash) 100 { 101 struct util_hash_iter iter; 102 struct util_hash_table_item *item; 103 104 iter = util_hash_find(ht->head, key_hash); 105 while (!util_hash_iter_is_null(iter)) { 106 item = (struct util_hash_table_item *)util_hash_iter_data(iter); 107 if (!ht->compare(item->key, key)) 108 break; 109 iter = util_hash_iter_next(iter); 110 } 111 112 return iter; 113 } 114 115 static struct util_hash_table_item * 116 util_hash_table_find_item(struct util_hash_table *ht, 117 void *key, unsigned key_hash) 118 { 119 struct util_hash_iter iter; 120 struct util_hash_table_item *item; 121 122 iter = util_hash_find(ht->head, key_hash); 123 while (!util_hash_iter_is_null(iter)) { 124 item = (struct util_hash_table_item *)util_hash_iter_data(iter); 125 if (!ht->compare(item->key, key)) 126 return item; 127 iter = util_hash_iter_next(iter); 128 } 129 130 return NULL; 131 } 132 133 drm_private void 134 util_hash_table_set(struct util_hash_table *ht, void *key, void *value) 135 { 136 unsigned key_hash; 137 struct util_hash_table_item *item; 138 struct util_hash_iter iter; 139 140 assert(ht); 141 if (!ht) 142 return; 143 144 key_hash = ht->make_hash(key); 145 146 item = util_hash_table_find_item(ht, key, key_hash); 147 if(item) { 148 /* TODO: key/value destruction? */ 149 item->value = value; 150 return; 151 } 152 153 item = malloc(sizeof(struct util_hash_table_item)); 154 if(!item) 155 return; 156 157 item->key = key; 158 item->value = value; 159 160 iter = util_hash_insert(ht->head, key_hash, item); 161 if(util_hash_iter_is_null(iter)) { 162 free(item); 163 return; 164 } 165 } 166 167 drm_private void *util_hash_table_get(struct util_hash_table *ht, void *key) 168 { 169 unsigned key_hash; 170 struct util_hash_table_item *item; 171 172 assert(ht); 173 if (!ht) 174 return NULL; 175 176 key_hash = ht->make_hash(key); 177 178 item = util_hash_table_find_item(ht, key, key_hash); 179 if(!item) 180 return NULL; 181 182 return item->value; 183 } 184 185 drm_private void util_hash_table_remove(struct util_hash_table *ht, void *key) 186 { 187 unsigned key_hash; 188 struct util_hash_iter iter; 189 struct util_hash_table_item *item; 190 191 assert(ht); 192 if (!ht) 193 return; 194 195 key_hash = ht->make_hash(key); 196 197 iter = util_hash_table_find_iter(ht, key, key_hash); 198 if(util_hash_iter_is_null(iter)) 199 return; 200 201 item = util_hash_table_item(iter); 202 assert(item); 203 free(item); 204 205 util_hash_erase(ht->head, iter); 206 } 207 208 drm_private void util_hash_table_clear(struct util_hash_table *ht) 209 { 210 struct util_hash_iter iter; 211 struct util_hash_table_item *item; 212 213 assert(ht); 214 if (!ht) 215 return; 216 217 iter = util_hash_first_node(ht->head); 218 while (!util_hash_iter_is_null(iter)) { 219 item = (struct util_hash_table_item *)util_hash_take(ht->head, util_hash_iter_key(iter)); 220 free(item); 221 iter = util_hash_first_node(ht->head); 222 } 223 } 224 225 drm_private void util_hash_table_foreach(struct util_hash_table *ht, 226 void (*callback)(void *key, void *value, void *data), 227 void *data) 228 { 229 struct util_hash_iter iter; 230 struct util_hash_table_item *item; 231 232 assert(ht); 233 if (!ht) 234 return; 235 236 iter = util_hash_first_node(ht->head); 237 while (!util_hash_iter_is_null(iter)) { 238 item = (struct util_hash_table_item *)util_hash_iter_data(iter); 239 callback(item->key, item->value, data); 240 iter = util_hash_iter_next(iter); 241 } 242 } 243 244 drm_private void util_hash_table_destroy(struct util_hash_table *ht) 245 { 246 struct util_hash_iter iter; 247 struct util_hash_table_item *item; 248 249 assert(ht); 250 if (!ht) 251 return; 252 253 iter = util_hash_first_node(ht->head); 254 while (!util_hash_iter_is_null(iter)) { 255 item = (struct util_hash_table_item *)util_hash_iter_data(iter); 256 free(item); 257 iter = util_hash_iter_next(iter); 258 } 259 260 util_hash_delete(ht->head); 261 free(ht); 262 } 263
