Lines Matching +defs:hash +defs:table
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
61 * was deleted from the table, along with NULL for the "never allocated in the
62 * table" marker. Legacy GL allows any GLuint to be used as a GL object name,
65 * struct hash_table. We tell the hash table to use "1" as the deleted key
66 * value, so that we test the deleted-key-in-the-table path as best we can.
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
163 ht->table = rzalloc_array(mem_ctx, struct hash_entry, ht->size);
168 return ht->table != NULL;
179 /* mem_ctx is used to allocate the hash table, but the hash table is used
225 ht->table = ralloc_array(ht, struct hash_entry, ht->size);
226 if (ht->table == NULL) {
231 memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry));
237 * Frees the given hash table.
260 memset(ht->table, 0, sizeof(struct hash_entry) * hash_sizes[ht->size_index].size);
265 * Deletes all entries of the given hash table without deleting the table
280 for (entry = ht->table; entry != ht->table + ht->size; entry++) {
292 /** Sets the value of the key pointer used for deleted entries in the table.
297 * table, like a uint32_t, in which case that pointer may conflict with one of
300 * This must be called before any keys are actually deleted from 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,
320 struct hash_entry *entry = ht->table + hash_address;
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,
373 struct hash_entry *entry = ht->table + hash_address;
376 entry->hash = hash;
392 struct hash_entry *table;
403 table = rzalloc_array(ralloc_parent(ht->table), struct hash_entry,
405 if (table == NULL)
410 ht->table = table;
421 hash_table_insert_rehash(ht, entry->hash, entry->key, entry->data);
426 ralloc_free(old_ht.table);
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,
449 struct hash_entry *entry = ht->table + hash_address;
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.
502 * Note that insertion may rearrange the table on a resize or rehash,
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.
523 * Note that deletion doesn't otherwise modify the table, so an iteration over
524 * the table deleting entries is safe.
559 entry = ht->table;
562 if (entry != ht->table + ht->size)
569 * This function is an iterator over the hash table.
572 * an iteration over the table is O(table_size) not O(entries).
579 entry = ht->table;
583 for (; entry != ht->table + ht->size; entry++) {
593 * Returns a random entry from the hash table.
596 * to just removing everything) in caches based on this hash table
610 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
617 for (entry = ht->table; entry != ht->table + i; entry++) {
658 /** FNV-1a string hash implementation */
662 uint32_t hash = 0;
666 hash = (uint32_t)XXH64(key, len, hash);
668 hash = XXH32(key, len, hash);
670 return hash;
716 * Helper to create a hash table with pointer keys.
741 * Hash table wrapper which supports 64-bit keys.
743 * TODO: unify all hash table implementations.
778 ht->table = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
781 ht->table = _mesa_hash_table_create(mem_ctx, key_u64_hash,
785 if (ht->table)
786 _mesa_hash_table_set_deleted_key(ht->table, uint_key(DELETED_KEY_VALUE));
809 _mesa_hash_table_clear(ht->table, _mesa_hash_table_u64_delete_key);
821 _mesa_hash_table_destroy(ht->table, NULL);
840 _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data);
848 _mesa_hash_table_insert(ht->table, _key, data);
856 return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key);
859 return _mesa_hash_table_search(ht->table, &_key);
901 _mesa_hash_table_remove(ht->table, entry);
905 _mesa_hash_table_remove(ht->table, entry);