Lines Matching refs:ht
120 _mesa_set_init(struct set *ht, void *mem_ctx,
125 ht->size_index = 0;
126 ht->size = hash_sizes[ht->size_index].size;
127 ht->rehash = hash_sizes[ht->size_index].rehash;
128 ht->size_magic = hash_sizes[ht->size_index].size_magic;
129 ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
130 ht->max_entries = hash_sizes[ht->size_index].max_entries;
131 ht->key_hash_function = key_hash_function;
132 ht->key_equals_function = key_equals_function;
133 ht->table = rzalloc_array(mem_ctx, struct set_entry, ht->size);
134 ht->entries = 0;
135 ht->deleted_entries = 0;
137 return ht->table != NULL;
146 struct set *ht;
148 ht = ralloc(mem_ctx, struct set);
149 if (ht == NULL)
152 if (!_mesa_set_init(ht, ht, key_hash_function, key_equals_function)) {
153 ralloc_free(ht);
157 return ht;
209 _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
211 if (!ht)
215 set_foreach (ht, entry) {
219 ralloc_free(ht->table);
220 ralloc_free(ht);
225 set_clear_fast(struct set *ht)
227 memset(ht->table, 0, sizeof(struct set_entry) * hash_sizes[ht->size_index].size);
228 ht->entries = ht->deleted_entries = 0;
264 set_search(const struct set *ht, uint32_t hash, const void *key)
268 uint32_t size = ht->size;
269 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
270 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
271 ht->rehash_magic) + 1;
274 struct set_entry *entry = ht->table + hash_address;
279 if (ht->key_equals_function(key, entry->key)) {
309 set_add_rehash(struct set *ht, uint32_t hash, const void *key)
311 uint32_t size = ht->size;
312 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
313 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
314 ht->rehash_magic) + 1;
317 struct set_entry *entry = ht->table + hash_address;
331 set_rehash(struct set *ht, unsigned new_size_index)
336 if (ht->size_index == new_size_index && ht->deleted_entries == ht->max_entries) {
337 set_clear_fast(ht);
338 assert(!ht->entries);
345 table = rzalloc_array(ralloc_parent(ht->table), struct set_entry,
350 old_ht = *ht;
352 ht->table = table;
353 ht->size_index = new_size_index;
354 ht->size = hash_sizes[ht->size_index].size;
355 ht->rehash = hash_sizes[ht->size_index].rehash;
356 ht->size_magic = hash_sizes[ht->size_index].size_magic;
357 ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
358 ht->max_entries = hash_sizes[ht->size_index].max_entries;
359 ht->entries = 0;
360 ht->deleted_entries = 0;
363 set_add_rehash(ht, entry->hash, entry->key);
366 ht->entries = old_ht.entries;
393 set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found)
399 if (ht->entries >= ht->max_entries) {
400 set_rehash(ht, ht->size_index + 1);
401 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
402 set_rehash(ht, ht->size_index);
405 uint32_t size = ht->size;
406 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
407 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
408 ht->rehash_magic) + 1;
411 struct set_entry *entry = ht->table + hash_address;
423 ht->key_equals_function(key, entry->key)) {
437 ht->deleted_entries--;
440 ht->entries++;
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);
544 _mesa_set_remove(struct set *ht, struct set_entry *entry)
550 ht->entries--;
551 ht->deleted_entries++;
569 _mesa_set_next_entry_unsafe(const struct set *ht, struct set_entry *entry)
571 assert(!ht->deleted_entries);
572 if (!ht->entries)
575 entry = ht->table;
578 if (entry != ht->table + ht->size)
579 return entry->key ? entry : _mesa_set_next_entry_unsafe(ht, entry);
591 _mesa_set_next_entry(const struct set *ht, struct set_entry *entry)
594 entry = ht->table;
598 for (; entry != ht->table + ht->size; entry++) {
608 _mesa_set_random_entry(struct set *ht,
612 uint32_t i = rand() % ht->size;
614 if (ht->entries == 0)
617 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
624 for (entry = ht->table; entry != ht->table + i; entry++) {