Lines Matching +defs:hash +defs:table
36 * Implements an open-addressing, linear-reprobing hash table.
50 #include "main/hash.h"
55 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
57 * free to avoid exponential performance degradation as the hash table fills
126 ht->table = rzalloc_array(mem_ctx, struct hash_entry, ht->size);
131 return ht->table != NULL;
142 /* mem_ctx is used to allocate the hash table, but the hash table is used
168 ht->table = ralloc_array(ht, struct hash_entry, ht->size);
169 if (ht->table == NULL) {
174 memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry));
180 * Frees the given hash table.
201 * Deletes all entries of the given hash table without deleting the table
212 for (entry = ht->table; entry != ht->table + ht->size; entry++) {
226 /** Sets the value of the key pointer used for deleted entries in the table.
231 * table, like a uint32_t, in which case that pointer may conflict with one of
234 * This must be called before any keys are actually deleted from the table.
243 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
245 uint32_t start_hash_address = hash % ht->size;
251 struct hash_entry *entry = ht->table + hash_address;
255 } else if (entry_is_present(ht, entry) && entry->hash == hash) {
261 double_hash = 1 + hash % ht->rehash;
270 * Finds a hash table entry with the given key and hash of that key.
283 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
286 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
287 return hash_table_search(ht, hash, key);
291 hash_table_insert(struct hash_table *ht, uint32_t hash,
298 struct hash_entry *table;
303 table = rzalloc_array(ralloc_parent(ht->table), struct hash_entry,
305 if (table == NULL)
310 ht->table = table;
319 hash_table_insert(ht, entry->hash, entry->key, entry->data);
322 ralloc_free(old_ht.table);
326 hash_table_insert(struct hash_table *ht, uint32_t hash,
340 start_hash_address = hash % ht->size;
343 struct hash_entry *entry = ht->table + hash_address;
356 * feature of hash tables, with the alternative
360 * Note that the hash table doesn't have a delete
366 entry->hash == hash &&
374 double_hash = 1 + hash % ht->rehash;
382 available_entry->hash = hash;
396 * Inserts the key with the given hash into the table.
398 * Note that insertion may rearrange the table on a resize or rehash,
409 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
412 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
413 return hash_table_insert(ht, hash, key, data);
417 * This function deletes the given hash table entry.
419 * Note that deletion doesn't otherwise modify the table, so an iteration over
420 * the table deleting entries is safe.
444 * This function is an iterator over the hash table.
447 * an iteration over the table is O(table_size) not O(entries).
454 entry = ht->table;
458 for (; entry != ht->table + ht->size; entry++) {
468 * Returns a random entry from the hash table.
471 * to just removing everything) in caches based on this hash table
485 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
492 for (entry = ht->table; entry != ht->table + i; entry++) {
504 * Quick FNV-1a hash implementation based on:
507 * FNV-1a is not be the best hash out there -- Jenkins's lookup3 is supposed
510 * Hsieh's http://www.azillionmonkeys.com/qed/hash.html
519 /** FNV-1a string hash implementation */
523 uint32_t hash = _mesa_fnv32_1a_offset_bias;
527 hash = _mesa_fnv32_1a_accumulate(hash, *key);
531 return hash;
551 * Helper to create a hash table with pointer keys.
561 * Hash table wrapper which supports 64-bit keys.
563 * TODO: unify all hash table implementations.
595 ht->table = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
598 ht->table = _mesa_hash_table_create(mem_ctx, key_u64_hash,
602 if (ht->table)
603 _mesa_hash_table_set_deleted_key(ht->table, uint_key(DELETED_KEY_VALUE));
617 struct hash_table *table = ht->table;
621 deleted_entry.hash = table->key_hash_function(table->deleted_key);
622 deleted_entry.key = table->deleted_key;
630 _mesa_hash_table_destroy(ht->table, delete_function);
644 _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data);
652 _mesa_hash_table_insert(ht->table, _key, data);
660 return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key);
663 return _mesa_hash_table_search(ht->table, &_key);
697 _mesa_hash_table_remove(ht->table, entry);
701 _mesa_hash_table_remove(ht->table, entry);