Lines Matching defs:hash
36 * Implements an open-addressing, linear-reprobing hash table.
60 * The hash table needs a particular pointer to be the marker for a key that
65 * struct hash_table. We tell the hash table to use "1" as the deleted key
79 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
81 * free to avoid exponential performance degradation as the hash table fills
179 /* mem_ctx is used to allocate the hash table, but the hash table is used
237 * Frees the given hash table.
265 * Deletes all entries of the given hash table without deleting the table
309 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
314 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
315 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
324 } else if (entry_is_present(ht, entry) && entry->hash == hash) {
339 * Finds a hash table entry with the given key and hash of that key.
352 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
355 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
356 return hash_table_search(ht, hash, key);
360 hash_table_insert(struct hash_table *ht, uint32_t hash,
364 hash_table_insert_rehash(struct hash_table *ht, uint32_t hash,
368 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
369 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
376 entry->hash = hash;
421 hash_table_insert_rehash(ht, entry->hash, entry->key, entry->data);
430 hash_table_insert(struct hash_table *ht, uint32_t hash,
444 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
445 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
461 * feature of hash tables, with the alternative
465 * Note that the hash table doesn't have a delete
471 entry->hash == hash &&
486 available_entry->hash = hash;
500 * Inserts the key with the given hash into the table.
513 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
516 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
517 return hash_table_insert(ht, hash, key, data);
521 * This function deletes the given hash table entry.
569 * This function is an iterator over the hash table.
593 * Returns a random entry from the hash table.
596 * to just removing everything) in caches based on this hash table
658 /** FNV-1a string hash implementation */
668 uint32_t hash = 0;
671 hash = (uint32_t)XXH64(key, length, hash);
673 hash = XXH32(key, length, hash);
675 return hash;
721 * Helper to create a hash table with pointer keys.
748 * TODO: unify all hash table implementations.