Cross Reference: /xsrc/external/mit/MesaLib.old/dist/src/util/set.c

Lines Matching +defs:hash +defs:table
45  * From Knuth -- a good choice for hash/rehash values is p, p-2 where
47  * free to avoid exponential performance degradation as the hash table fills
125    ht->table = rzalloc_array(ht, struct set_entry, ht->size);
129    if (ht->table == NULL) {
148    clone->table = ralloc_array(clone, struct set_entry, clone->size);
149    if (clone->table == NULL) {
154    memcpy(clone->table, set->table, clone->size * sizeof(struct set_entry));
176    ralloc_free(ht->table);
202  * Finds a set entry with the given key and hash of that key.
207 set_search(const struct set *ht, uint32_t hash, const void *key)
211    hash_address = hash % ht->size;
215       struct set_entry *entry = ht->table + hash_address;
219       } else if (entry_is_present(entry) && entry->hash == hash) {
225       double_hash = 1 + hash % ht->rehash;
228    } while (hash_address != hash % ht->size);
241 _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
245           hash == set->key_hash_function(key));
246    return set_search(set, hash, key);
250 set_add(struct set *ht, uint32_t hash, const void *key);
256    struct set_entry *table;
261    table = rzalloc_array(ht, struct set_entry,
263    if (table == NULL)
268    ht->table = table;
277       set_add(ht, entry->hash, entry->key);
280    ralloc_free(old_ht.table);
284  * Inserts the key with the given hash into the table.
286  * Note that insertion may rearrange the table on a resize or rehash,
290 set_add(struct set *ht, uint32_t hash, const void *key)
301    hash_address = hash % ht->size;
303       struct set_entry *entry = ht->table + hash_address;
316        * feature of hash tables, with the alternative
320        * Note that the hash table doesn't have a delete callback.
325           entry->hash == hash &&
331       double_hash = 1 + hash % ht->rehash;
334    } while (hash_address != hash % ht->size);
339       available_entry->hash = hash;
359 _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
362           hash == set->key_hash_function(key));
363    return set_add(set, hash, key);
367  * This function deletes the given hash table entry.
369  * Note that deletion doesn't otherwise modify the table, so an iteration over
370  * the table deleting entries is safe.
393  * This function is an iterator over the hash table.
396  * an iteration over the table is O(table_size) not O(entries).
402       entry = ht->table;
406    for (; entry != ht->table + ht->size; entry++) {
425    for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
432    for (entry = ht->table; entry != ht->table + i; entry++) {