Lines Matching +defs:hash +defs:table
46 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
48 * free to avoid exponential performance degradation as the hash table fills
133 ht->table = rzalloc_array(mem_ctx, struct set_entry, ht->size);
137 return ht->table != NULL;
191 clone->table = ralloc_array(clone, struct set_entry, clone->size);
192 if (clone->table == NULL) {
197 memcpy(clone->table, set->table, clone->size * sizeof(struct set_entry));
219 ralloc_free(ht->table);
227 memset(ht->table, 0, sizeof(struct set_entry) * hash_sizes[ht->size_index].size);
246 for (entry = set->table; entry != set->table + set->size; entry++) {
259 * Finds a set entry with the given key and hash of that key.
264 set_search(const struct set *ht, uint32_t hash, const void *key)
269 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
270 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
274 struct set_entry *entry = ht->table + hash_address;
278 } else if (entry_is_present(entry) && entry->hash == hash) {
300 _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
304 hash == set->key_hash_function(key));
305 return set_search(set, hash, key);
309 set_add_rehash(struct set *ht, uint32_t hash, const void *key)
312 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
313 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
317 struct set_entry *entry = ht->table + hash_address;
319 entry->hash = hash;
334 struct set_entry *table;
345 table = rzalloc_array(ralloc_parent(ht->table), struct set_entry,
347 if (table == NULL)
352 ht->table = table;
363 set_add_rehash(ht, entry->hash, entry->key);
368 ralloc_free(old_ht.table);
389 * Note that insertion may rearrange the table on a resize or rehash,
393 set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found)
406 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
407 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
411 struct set_entry *entry = ht->table + hash_address;
422 entry->hash == hash &&
438 available_entry->hash = hash;
453 * Inserts the key with the given hash into the table.
455 * Note that insertion may rearrange the table on a resize or rehash,
459 set_add(struct set *ht, uint32_t hash, const void *key)
461 struct set_entry *entry = set_search_or_add(ht, hash, key, NULL);
467 * a relatively common feature of hash tables, with the alternative
471 * Note that the hash table doesn't have a delete callback. If freeing of
487 _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
490 hash == set->key_hash_function(key));
491 return set_add(set, hash, key);
504 _mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash,
508 hash == set->key_hash_function(key));
509 struct set_entry *entry = set_search_or_add(set, hash, key, replaced);
529 _mesa_set_search_or_add_pre_hashed(struct set *set, uint32_t hash,
533 hash == set->key_hash_function(key));
534 return set_search_or_add(set, hash, key, NULL);
538 * This function deletes the given hash table entry.
540 * Note that deletion doesn't otherwise modify the table, so an iteration over
541 * the table deleting entries is safe.
575 entry = ht->table;
578 if (entry != ht->table + ht->size)
585 * This function is an iterator over the hash table.
588 * an iteration over the table is O(table_size) not O(entries).
594 entry = ht->table;
598 for (; entry != ht->table + ht->size; entry++) {
617 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
624 for (entry = ht->table; entry != ht->table + i; entry++) {
658 if (_mesa_set_search_pre_hashed(b, entry->hash, entry->key))