x-hash.c (8360B)
1 /* x-hash.c - basic hash tables 2 * 3 * Copyright (c) 2002-2012 Apple Inc. All rights reserved. 4 * 5 * Permission is hereby granted, free of charge, to any person 6 * obtaining a copy of this software and associated documentation files 7 * (the "Software"), to deal in the Software without restriction, 8 * including without limitation the rights to use, copy, modify, merge, 9 * publish, distribute, sublicense, and/or sell copies of the Software, 10 * and to permit persons to whom the Software is furnished to do so, 11 * subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be 14 * included in all copies or substantial portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 19 * NONINFRINGEMENT. IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT 20 * HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 23 * DEALINGS IN THE SOFTWARE. 24 * 25 * Except as contained in this notice, the name(s) of the above 26 * copyright holders shall not be used in advertising or otherwise to 27 * promote the sale, use or other dealings in this Software without 28 * prior written authorization. 29 */ 30 31 #ifdef HAVE_DIX_CONFIG_H 32 #include <dix-config.h> 33 #endif 34 35 #include "x-hash.h" 36 #include "x-list.h" 37 #include <stdlib.h> 38 #include <assert.h> 39 40 #define ARRAY_SIZE(a) (sizeof((a)) / sizeof((a)[0])) 41 42 struct x_hash_table_struct { 43 unsigned int bucket_index; 44 unsigned int total_keys; 45 x_list **buckets; 46 47 x_hash_fun *hash_key; 48 x_compare_fun *compare_keys; 49 x_destroy_fun *destroy_key; 50 x_destroy_fun *destroy_value; 51 }; 52 53 #define ITEM_NEW(k, v) X_PFX(list_prepend) ((x_list *)(k), v) 54 #define ITEM_FREE(i) X_PFX(list_free_1) (i) 55 #define ITEM_KEY(i) ((void *)(i)->next) 56 #define ITEM_VALUE(i) ((i)->data) 57 58 #define SPLIT_THRESHOLD_FACTOR 2 59 60 /* http://planetmath.org/?op=getobj&from=objects&name=GoodHashTablePrimes */ 61 static const unsigned int bucket_sizes[] = { 62 29, 53, 97, 193, 389, 769, 1543, 63 3079, 6151, 12289, 24593, 49157, 64 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 65 12582917, 66 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 67 1610612741 68 }; 69 70 static inline unsigned int 71 hash_table_total_buckets(x_hash_table *h) 72 { 73 return bucket_sizes[h->bucket_index]; 74 } 75 76 static inline void 77 hash_table_destroy_item(x_hash_table *h, void *k, void *v) 78 { 79 if (h->destroy_key != 0) 80 (*h->destroy_key)(k); 81 82 if (h->destroy_value != 0) 83 (*h->destroy_value)(v); 84 } 85 86 static inline size_t 87 hash_table_hash_key(x_hash_table *h, void *k) 88 { 89 if (h->hash_key != 0) 90 return (*h->hash_key)(k); 91 else 92 return (size_t)k; 93 } 94 95 static inline int 96 hash_table_compare_keys(x_hash_table *h, void *k1, void *k2) 97 { 98 if (h->compare_keys == 0) 99 return k1 == k2; 100 else 101 return (*h->compare_keys)(k1, k2) == 0; 102 } 103 104 static void 105 hash_table_split(x_hash_table *h) 106 { 107 x_list **new, **old; 108 x_list *node, *item, *next; 109 int new_size, old_size; 110 size_t b; 111 int i; 112 113 if (h->bucket_index == ARRAY_SIZE(bucket_sizes) - 1) 114 return; 115 116 old_size = hash_table_total_buckets(h); 117 old = h->buckets; 118 119 h->bucket_index++; 120 121 new_size = hash_table_total_buckets(h); 122 new = calloc(new_size, sizeof(x_list *)); 123 124 if (new == 0) { 125 h->bucket_index--; 126 return; 127 } 128 129 for (i = 0; i < old_size; i++) { 130 for (node = old[i]; node != 0; node = next) { 131 next = node->next; 132 item = node->data; 133 134 b = hash_table_hash_key(h, ITEM_KEY(item)) % new_size; 135 136 node->next = new[b]; 137 new[b] = node; 138 } 139 } 140 141 h->buckets = new; 142 free(old); 143 } 144 145 X_EXTERN x_hash_table * 146 X_PFX(hash_table_new) (x_hash_fun * hash, 147 x_compare_fun * compare, 148 x_destroy_fun * key_destroy, 149 x_destroy_fun * value_destroy) { 150 x_hash_table *h; 151 152 h = calloc(1, sizeof(x_hash_table)); 153 if (h == 0) 154 return 0; 155 156 h->bucket_index = 0; 157 h->buckets = calloc(hash_table_total_buckets(h), sizeof(x_list *)); 158 159 if (h->buckets == 0) { 160 free(h); 161 return 0; 162 } 163 164 h->hash_key = hash; 165 h->compare_keys = compare; 166 h->destroy_key = key_destroy; 167 h->destroy_value = value_destroy; 168 169 return h; 170 } 171 172 X_EXTERN void 173 X_PFX(hash_table_free) (x_hash_table * h) { 174 int n, i; 175 x_list *node, *item; 176 177 assert(h != NULL); 178 179 n = hash_table_total_buckets(h); 180 181 for (i = 0; i < n; i++) { 182 for (node = h->buckets[i]; node != 0; node = node->next) { 183 item = node->data; 184 hash_table_destroy_item(h, ITEM_KEY(item), ITEM_VALUE(item)); 185 ITEM_FREE(item); 186 } 187 X_PFX(list_free) (h->buckets[i]); 188 } 189 190 free(h->buckets); 191 free(h); 192 } 193 194 X_EXTERN unsigned int 195 X_PFX(hash_table_size) (x_hash_table * h) { 196 assert(h != NULL); 197 198 return h->total_keys; 199 } 200 201 static void 202 hash_table_modify(x_hash_table *h, void *k, void *v, int replace) 203 { 204 size_t hash_value; 205 x_list *node, *item; 206 207 assert(h != NULL); 208 209 hash_value = hash_table_hash_key(h, k); 210 211 for (node = h->buckets[hash_value % hash_table_total_buckets(h)]; 212 node != 0; node = node->next) { 213 item = node->data; 214 215 if (hash_table_compare_keys(h, ITEM_KEY(item), k)) { 216 if (replace) { 217 hash_table_destroy_item(h, ITEM_KEY(item), 218 ITEM_VALUE(item)); 219 item->next = k; 220 ITEM_VALUE(item) = v; 221 } 222 else { 223 hash_table_destroy_item(h, k, ITEM_VALUE(item)); 224 ITEM_VALUE(item) = v; 225 } 226 return; 227 } 228 } 229 230 /* Key isn't already in the table. Insert it. */ 231 232 if (h->total_keys + 1 233 > hash_table_total_buckets(h) * SPLIT_THRESHOLD_FACTOR) { 234 hash_table_split(h); 235 } 236 237 hash_value = hash_value % hash_table_total_buckets(h); 238 h->buckets[hash_value] = X_PFX(list_prepend) (h->buckets[hash_value], 239 ITEM_NEW(k, v)); 240 h->total_keys++; 241 } 242 243 X_EXTERN void 244 X_PFX(hash_table_insert) (x_hash_table * h, void *k, void *v) { 245 hash_table_modify(h, k, v, 0); 246 } 247 248 X_EXTERN void 249 X_PFX(hash_table_replace) (x_hash_table * h, void *k, void *v) { 250 hash_table_modify(h, k, v, 1); 251 } 252 253 X_EXTERN void 254 X_PFX(hash_table_remove) (x_hash_table * h, void *k) { 255 size_t hash_value; 256 x_list **ptr, *item; 257 258 assert(h != NULL); 259 260 hash_value = hash_table_hash_key(h, k); 261 262 for (ptr = &h->buckets[hash_value % hash_table_total_buckets(h)]; 263 *ptr != 0; ptr = &((*ptr)->next)) { 264 item = (*ptr)->data; 265 266 if (hash_table_compare_keys(h, ITEM_KEY(item), k)) { 267 hash_table_destroy_item(h, ITEM_KEY(item), ITEM_VALUE(item)); 268 ITEM_FREE(item); 269 item = *ptr; 270 *ptr = item->next; 271 X_PFX(list_free_1) (item); 272 h->total_keys--; 273 return; 274 } 275 } 276 } 277 278 X_EXTERN void * 279 X_PFX(hash_table_lookup) (x_hash_table * h, void *k, void **k_ret) { 280 size_t hash_value; 281 x_list *node, *item; 282 283 assert(h != NULL); 284 285 hash_value = hash_table_hash_key(h, k); 286 287 for (node = h->buckets[hash_value % hash_table_total_buckets(h)]; 288 node != 0; node = node->next) { 289 item = node->data; 290 291 if (hash_table_compare_keys(h, ITEM_KEY(item), k)) { 292 if (k_ret != 0) 293 *k_ret = ITEM_KEY(item); 294 295 return ITEM_VALUE(item); 296 } 297 } 298 299 if (k_ret != 0) 300 *k_ret = 0; 301 302 return 0; 303 } 304 305 X_EXTERN void 306 X_PFX(hash_table_foreach) (x_hash_table * h, 307 x_hash_foreach_fun * fun, void *data) { 308 int i, n; 309 x_list *node, *item; 310 311 assert(h != NULL); 312 313 n = hash_table_total_buckets(h); 314 315 for (i = 0; i < n; i++) { 316 for (node = h->buckets[i]; node != 0; node = node->next) { 317 item = node->data; 318 (*fun)(ITEM_KEY(item), ITEM_VALUE(item), data); 319 } 320 } 321 }