Lines Matching refs:ht
101 entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry) in entry_is_deleted() argument
103 return entry->key == ht->deleted_key; in entry_is_deleted()
107 entry_is_present(const struct hash_table *ht, struct hash_entry *entry) in entry_is_present() argument
109 return entry->key != NULL && entry->key != ht->deleted_key; in entry_is_present()
118 struct hash_table *ht; in _mesa_hash_table_create() local
120 ht = ralloc(mem_ctx, struct hash_table); in _mesa_hash_table_create()
121 if (ht == NULL) in _mesa_hash_table_create()
124 ht->size_index = 0; in _mesa_hash_table_create()
125 ht->size = hash_sizes[ht->size_index].size; in _mesa_hash_table_create()
126 ht->rehash = hash_sizes[ht->size_index].rehash; in _mesa_hash_table_create()
127 ht->max_entries = hash_sizes[ht->size_index].max_entries; in _mesa_hash_table_create()
128 ht->key_hash_function = key_hash_function; in _mesa_hash_table_create()
129 ht->key_equals_function = key_equals_function; in _mesa_hash_table_create()
130 ht->table = rzalloc_array(ht, struct hash_entry, ht->size); in _mesa_hash_table_create()
131 ht->entries = 0; in _mesa_hash_table_create()
132 ht->deleted_entries = 0; in _mesa_hash_table_create()
133 ht->deleted_key = &deleted_key_value; in _mesa_hash_table_create()
135 if (ht->table == NULL) { in _mesa_hash_table_create()
136 ralloc_free(ht); in _mesa_hash_table_create()
140 return ht; in _mesa_hash_table_create()
150 _mesa_hash_table_destroy(struct hash_table *ht, in _mesa_hash_table_destroy() argument
153 if (!ht) in _mesa_hash_table_destroy()
159 hash_table_foreach(ht, entry) { in _mesa_hash_table_destroy()
163 ralloc_free(ht); in _mesa_hash_table_destroy()
173 _mesa_hash_table_clear(struct hash_table *ht, in _mesa_hash_table_clear() argument
178 for (entry = ht->table; entry != ht->table + ht->size; entry++) { in _mesa_hash_table_clear()
182 if (delete_function != NULL && entry->key != ht->deleted_key) in _mesa_hash_table_clear()
188 ht->entries = 0; in _mesa_hash_table_clear()
189 ht->deleted_entries = 0; in _mesa_hash_table_clear()
203 _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key) in _mesa_hash_table_set_deleted_key() argument
205 ht->deleted_key = deleted_key; in _mesa_hash_table_set_deleted_key()
209 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) in hash_table_search() argument
211 uint32_t start_hash_address = hash % ht->size; in hash_table_search()
217 struct hash_entry *entry = ht->table + hash_address; in hash_table_search()
221 } else if (entry_is_present(ht, entry) && entry->hash == hash) { in hash_table_search()
222 if (ht->key_equals_function(key, entry->key)) { in hash_table_search()
227 double_hash = 1 + hash % ht->rehash; in hash_table_search()
229 hash_address = (hash_address + double_hash) % ht->size; in hash_table_search()
242 _mesa_hash_table_search(struct hash_table *ht, const void *key) in _mesa_hash_table_search() argument
244 assert(ht->key_hash_function); in _mesa_hash_table_search()
245 return hash_table_search(ht, ht->key_hash_function(key), key); in _mesa_hash_table_search()
249 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash, in _mesa_hash_table_search_pre_hashed() argument
252 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); in _mesa_hash_table_search_pre_hashed()
253 return hash_table_search(ht, hash, key); in _mesa_hash_table_search_pre_hashed()
257 hash_table_insert(struct hash_table *ht, uint32_t hash,
261 _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index) in _mesa_hash_table_rehash() argument
269 table = rzalloc_array(ht, struct hash_entry, in _mesa_hash_table_rehash()
274 old_ht = *ht; in _mesa_hash_table_rehash()
276 ht->table = table; in _mesa_hash_table_rehash()
277 ht->size_index = new_size_index; in _mesa_hash_table_rehash()
278 ht->size = hash_sizes[ht->size_index].size; in _mesa_hash_table_rehash()
279 ht->rehash = hash_sizes[ht->size_index].rehash; in _mesa_hash_table_rehash()
280 ht->max_entries = hash_sizes[ht->size_index].max_entries; in _mesa_hash_table_rehash()
281 ht->entries = 0; in _mesa_hash_table_rehash()
282 ht->deleted_entries = 0; in _mesa_hash_table_rehash()
285 hash_table_insert(ht, entry->hash, entry->key, entry->data); in _mesa_hash_table_rehash()
292 hash_table_insert(struct hash_table *ht, uint32_t hash, in hash_table_insert() argument
300 if (ht->entries >= ht->max_entries) { in hash_table_insert()
301 _mesa_hash_table_rehash(ht, ht->size_index + 1); in hash_table_insert()
302 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { in hash_table_insert()
303 _mesa_hash_table_rehash(ht, ht->size_index); in hash_table_insert()
306 start_hash_address = hash % ht->size; in hash_table_insert()
309 struct hash_entry *entry = ht->table + hash_address; in hash_table_insert()
312 if (!entry_is_present(ht, entry)) { in hash_table_insert()
331 if (!entry_is_deleted(ht, entry) && in hash_table_insert()
333 ht->key_equals_function(key, entry->key)) { in hash_table_insert()
340 double_hash = 1 + hash % ht->rehash; in hash_table_insert()
342 hash_address = (hash_address + double_hash) % ht->size; in hash_table_insert()
346 if (entry_is_deleted(ht, available_entry)) in hash_table_insert()
347 ht->deleted_entries--; in hash_table_insert()
351 ht->entries++; in hash_table_insert()
368 _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data) in _mesa_hash_table_insert() argument
370 assert(ht->key_hash_function); in _mesa_hash_table_insert()
371 return hash_table_insert(ht, ht->key_hash_function(key), key, data); in _mesa_hash_table_insert()
375 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, in _mesa_hash_table_insert_pre_hashed() argument
378 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); in _mesa_hash_table_insert_pre_hashed()
379 return hash_table_insert(ht, hash, key, data); in _mesa_hash_table_insert_pre_hashed()
389 _mesa_hash_table_remove(struct hash_table *ht, in _mesa_hash_table_remove() argument
395 entry->key = ht->deleted_key; in _mesa_hash_table_remove()
396 ht->entries--; in _mesa_hash_table_remove()
397 ht->deleted_entries++; in _mesa_hash_table_remove()
407 _mesa_hash_table_next_entry(struct hash_table *ht, in _mesa_hash_table_next_entry() argument
411 entry = ht->table; in _mesa_hash_table_next_entry()
415 for (; entry != ht->table + ht->size; entry++) { in _mesa_hash_table_next_entry()
416 if (entry_is_present(ht, entry)) { in _mesa_hash_table_next_entry()
433 _mesa_hash_table_random_entry(struct hash_table *ht, in _mesa_hash_table_random_entry() argument
437 uint32_t i = rand() % ht->size; in _mesa_hash_table_random_entry()
439 if (ht->entries == 0) in _mesa_hash_table_random_entry()
442 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) { in _mesa_hash_table_random_entry()
443 if (entry_is_present(ht, entry) && in _mesa_hash_table_random_entry()
449 for (entry = ht->table; entry != ht->table + i; entry++) { in _mesa_hash_table_random_entry()
450 if (entry_is_present(ht, entry) && in _mesa_hash_table_random_entry()