1 /* 2 * Copyright 2009-2012 Intel Corporation 3 * Copyright 1988-2004 Keith Packard and Bart Massey. 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the "Software"), 7 * to deal in the Software without restriction, including without limitation 8 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 * and/or sell copies of the Software, and to permit persons to whom the 10 * Software is furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice (including the next 13 * paragraph) shall be included in all copies or substantial portions of the 14 * Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 22 * IN THE SOFTWARE. 23 * 24 * Except as contained in this notice, the names of the authors 25 * or their institutions shall not be used in advertising or 26 * otherwise to promote the sale, use or other dealings in this 27 * Software without prior written authorization from the 28 * authors. 29 * 30 * Authors: 31 * Eric Anholt <eric (at) anholt.net> 32 * Keith Packard <keithp (at) keithp.com> 33 */ 34 35 #include <stdlib.h> 36 #include <assert.h> 37 38 #include "macros.h" 39 #include "ralloc.h" 40 #include "set.h" 41 42 /* 43 * From Knuth -- a good choice for hash/rehash values is p, p-2 where 44 * p and p-2 are both prime. These tables are sized to have an extra 10% 45 * free to avoid exponential performance degradation as the hash table fills 46 */ 47 48 static const uint32_t deleted_key_value; 49 static const void *deleted_key = &deleted_key_value; 50 51 static const struct { 52 uint32_t max_entries, size, rehash; 53 } hash_sizes[] = { 54 { 2, 5, 3 }, 55 { 4, 7, 5 }, 56 { 8, 13, 11 }, 57 { 16, 19, 17 }, 58 { 32, 43, 41 }, 59 { 64, 73, 71 }, 60 { 128, 151, 149 }, 61 { 256, 283, 281 }, 62 { 512, 571, 569 }, 63 { 1024, 1153, 1151 }, 64 { 2048, 2269, 2267 }, 65 { 4096, 4519, 4517 }, 66 { 8192, 9013, 9011 }, 67 { 16384, 18043, 18041 }, 68 { 32768, 36109, 36107 }, 69 { 65536, 72091, 72089 }, 70 { 131072, 144409, 144407 }, 71 { 262144, 288361, 288359 }, 72 { 524288, 576883, 576881 }, 73 { 1048576, 1153459, 1153457 }, 74 { 2097152, 2307163, 2307161 }, 75 { 4194304, 4613893, 4613891 }, 76 { 8388608, 9227641, 9227639 }, 77 { 16777216, 18455029, 18455027 }, 78 { 33554432, 36911011, 36911009 }, 79 { 67108864, 73819861, 73819859 }, 80 { 134217728, 147639589, 147639587 }, 81 { 268435456, 295279081, 295279079 }, 82 { 536870912, 590559793, 590559791 }, 83 { 1073741824, 1181116273, 1181116271 }, 84 { 2147483648ul, 2362232233ul, 2362232231ul } 85 }; 86 87 static int 88 entry_is_free(struct set_entry *entry) 89 { 90 return entry->key == NULL; 91 } 92 93 static int 94 entry_is_deleted(struct set_entry *entry) 95 { 96 return entry->key == deleted_key; 97 } 98 99 static int 100 entry_is_present(struct set_entry *entry) 101 { 102 return entry->key != NULL && entry->key != deleted_key; 103 } 104 105 struct set * 106 _mesa_set_create(void *mem_ctx, 107 uint32_t (*key_hash_function)(const void *key), 108 bool (*key_equals_function)(const void *a, 109 const void *b)) 110 { 111 struct set *ht; 112 113 ht = ralloc(mem_ctx, struct set); 114 if (ht == NULL) 115 return NULL; 116 117 ht->size_index = 0; 118 ht->size = hash_sizes[ht->size_index].size; 119 ht->rehash = hash_sizes[ht->size_index].rehash; 120 ht->max_entries = hash_sizes[ht->size_index].max_entries; 121 ht->key_hash_function = key_hash_function; 122 ht->key_equals_function = key_equals_function; 123 ht->table = rzalloc_array(ht, struct set_entry, ht->size); 124 ht->entries = 0; 125 ht->deleted_entries = 0; 126 127 if (ht->table == NULL) { 128 ralloc_free(ht); 129 return NULL; 130 } 131 132 return ht; 133 } 134 135 /** 136 * Frees the given set. 137 * 138 * If delete_function is passed, it gets called on each entry present before 139 * freeing. 140 */ 141 void 142 _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry)) 143 { 144 if (!ht) 145 return; 146 147 if (delete_function) { 148 struct set_entry *entry; 149 150 set_foreach (ht, entry) { 151 delete_function(entry); 152 } 153 } 154 ralloc_free(ht->table); 155 ralloc_free(ht); 156 } 157 158 /** 159 * Finds a set entry with the given key and hash of that key. 160 * 161 * Returns NULL if no entry is found. 162 */ 163 static struct set_entry * 164 set_search(const struct set *ht, uint32_t hash, const void *key) 165 { 166 uint32_t hash_address; 167 168 hash_address = hash % ht->size; 169 do { 170 uint32_t double_hash; 171 172 struct set_entry *entry = ht->table + hash_address; 173 174 if (entry_is_free(entry)) { 175 return NULL; 176 } else if (entry_is_present(entry) && entry->hash == hash) { 177 if (ht->key_equals_function(key, entry->key)) { 178 return entry; 179 } 180 } 181 182 double_hash = 1 + hash % ht->rehash; 183 184 hash_address = (hash_address + double_hash) % ht->size; 185 } while (hash_address != hash % ht->size); 186 187 return NULL; 188 } 189 190 struct set_entry * 191 _mesa_set_search(const struct set *set, const void *key) 192 { 193 assert(set->key_hash_function); 194 return set_search(set, set->key_hash_function(key), key); 195 } 196 197 struct set_entry * 198 _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash, 199 const void *key) 200 { 201 assert(set->key_hash_function == NULL || 202 hash == set->key_hash_function(key)); 203 return set_search(set, hash, key); 204 } 205 206 static struct set_entry * 207 set_add(struct set *ht, uint32_t hash, const void *key); 208 209 static void 210 set_rehash(struct set *ht, unsigned new_size_index) 211 { 212 struct set old_ht; 213 struct set_entry *table, *entry; 214 215 if (new_size_index >= ARRAY_SIZE(hash_sizes)) 216 return; 217 218 table = rzalloc_array(ht, struct set_entry, 219 hash_sizes[new_size_index].size); 220 if (table == NULL) 221 return; 222 223 old_ht = *ht; 224 225 ht->table = table; 226 ht->size_index = new_size_index; 227 ht->size = hash_sizes[ht->size_index].size; 228 ht->rehash = hash_sizes[ht->size_index].rehash; 229 ht->max_entries = hash_sizes[ht->size_index].max_entries; 230 ht->entries = 0; 231 ht->deleted_entries = 0; 232 233 for (entry = old_ht.table; 234 entry != old_ht.table + old_ht.size; 235 entry++) { 236 if (entry_is_present(entry)) { 237 set_add(ht, entry->hash, entry->key); 238 } 239 } 240 241 ralloc_free(old_ht.table); 242 } 243 244 /** 245 * Inserts the key with the given hash into the table. 246 * 247 * Note that insertion may rearrange the table on a resize or rehash, 248 * so previously found hash_entries are no longer valid after this function. 249 */ 250 static struct set_entry * 251 set_add(struct set *ht, uint32_t hash, const void *key) 252 { 253 uint32_t hash_address; 254 struct set_entry *available_entry = NULL; 255 256 if (ht->entries >= ht->max_entries) { 257 set_rehash(ht, ht->size_index + 1); 258 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { 259 set_rehash(ht, ht->size_index); 260 } 261 262 hash_address = hash % ht->size; 263 do { 264 struct set_entry *entry = ht->table + hash_address; 265 uint32_t double_hash; 266 267 if (!entry_is_present(entry)) { 268 /* Stash the first available entry we find */ 269 if (available_entry == NULL) 270 available_entry = entry; 271 if (entry_is_free(entry)) 272 break; 273 } 274 275 /* Implement replacement when another insert happens 276 * with a matching key. This is a relatively common 277 * feature of hash tables, with the alternative 278 * generally being "insert the new value as well, and 279 * return it first when the key is searched for". 280 * 281 * Note that the hash table doesn't have a delete callback. 282 * If freeing of old keys is required to avoid memory leaks, 283 * perform a search before inserting. 284 */ 285 if (!entry_is_deleted(entry) && 286 entry->hash == hash && 287 ht->key_equals_function(key, entry->key)) { 288 entry->key = key; 289 return entry; 290 } 291 292 double_hash = 1 + hash % ht->rehash; 293 294 hash_address = (hash_address + double_hash) % ht->size; 295 } while (hash_address != hash % ht->size); 296 297 if (available_entry) { 298 if (entry_is_deleted(available_entry)) 299 ht->deleted_entries--; 300 available_entry->hash = hash; 301 available_entry->key = key; 302 ht->entries++; 303 return available_entry; 304 } 305 306 /* We could hit here if a required resize failed. An unchecked-malloc 307 * application could ignore this result. 308 */ 309 return NULL; 310 } 311 312 struct set_entry * 313 _mesa_set_add(struct set *set, const void *key) 314 { 315 assert(set->key_hash_function); 316 return set_add(set, set->key_hash_function(key), key); 317 } 318 319 struct set_entry * 320 _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key) 321 { 322 assert(set->key_hash_function == NULL || 323 hash == set->key_hash_function(key)); 324 return set_add(set, hash, key); 325 } 326 327 /** 328 * This function deletes the given hash table entry. 329 * 330 * Note that deletion doesn't otherwise modify the table, so an iteration over 331 * the table deleting entries is safe. 332 */ 333 void 334 _mesa_set_remove(struct set *ht, struct set_entry *entry) 335 { 336 if (!entry) 337 return; 338 339 entry->key = deleted_key; 340 ht->entries--; 341 ht->deleted_entries++; 342 } 343 344 /** 345 * This function is an iterator over the hash table. 346 * 347 * Pass in NULL for the first entry, as in the start of a for loop. Note that 348 * an iteration over the table is O(table_size) not O(entries). 349 */ 350 struct set_entry * 351 _mesa_set_next_entry(const struct set *ht, struct set_entry *entry) 352 { 353 if (entry == NULL) 354 entry = ht->table; 355 else 356 entry = entry + 1; 357 358 for (; entry != ht->table + ht->size; entry++) { 359 if (entry_is_present(entry)) { 360 return entry; 361 } 362 } 363 364 return NULL; 365 } 366 367 struct set_entry * 368 _mesa_set_random_entry(struct set *ht, 369 int (*predicate)(struct set_entry *entry)) 370 { 371 struct set_entry *entry; 372 uint32_t i = rand() % ht->size; 373 374 if (ht->entries == 0) 375 return NULL; 376 377 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) { 378 if (entry_is_present(entry) && 379 (!predicate || predicate(entry))) { 380 return entry; 381 } 382 } 383 384 for (entry = ht->table; entry != ht->table + i; entry++) { 385 if (entry_is_present(entry) && 386 (!predicate || predicate(entry))) { 387 return entry; 388 } 389 } 390 391 return NULL; 392 } 393
