Lines Matching refs:ht
102 entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry) in entry_is_deleted() argument
104 return entry->key == ht->deleted_key; in entry_is_deleted()
108 entry_is_present(const struct hash_table *ht, struct hash_entry *entry) in entry_is_present() argument
110 return entry->key != NULL && entry->key != ht->deleted_key; in entry_is_present()
119 struct hash_table *ht; in _mesa_hash_table_create() local
121 ht = ralloc(mem_ctx, struct hash_table); in _mesa_hash_table_create()
122 if (ht == NULL) in _mesa_hash_table_create()
125 ht->size_index = 0; in _mesa_hash_table_create()
126 ht->size = hash_sizes[ht->size_index].size; in _mesa_hash_table_create()
127 ht->rehash = hash_sizes[ht->size_index].rehash; in _mesa_hash_table_create()
128 ht->max_entries = hash_sizes[ht->size_index].max_entries; in _mesa_hash_table_create()
129 ht->key_hash_function = key_hash_function; in _mesa_hash_table_create()
130 ht->key_equals_function = key_equals_function; in _mesa_hash_table_create()
131 ht->table = rzalloc_array(ht, struct hash_entry, ht->size); in _mesa_hash_table_create()
132 ht->entries = 0; in _mesa_hash_table_create()
133 ht->deleted_entries = 0; in _mesa_hash_table_create()
134 ht->deleted_key = &deleted_key_value; in _mesa_hash_table_create()
136 if (ht->table == NULL) { in _mesa_hash_table_create()
137 ralloc_free(ht); in _mesa_hash_table_create()
141 return ht; in _mesa_hash_table_create()
151 _mesa_hash_table_destroy(struct hash_table *ht, in _mesa_hash_table_destroy() argument
154 if (!ht) in _mesa_hash_table_destroy()
160 hash_table_foreach(ht, entry) { in _mesa_hash_table_destroy()
164 ralloc_free(ht); in _mesa_hash_table_destroy()
174 _mesa_hash_table_clear(struct hash_table *ht, in _mesa_hash_table_clear() argument
179 for (entry = ht->table; entry != ht->table + ht->size; entry++) { in _mesa_hash_table_clear()
183 if (delete_function != NULL && entry->key != ht->deleted_key) in _mesa_hash_table_clear()
189 ht->entries = 0; in _mesa_hash_table_clear()
190 ht->deleted_entries = 0; in _mesa_hash_table_clear()
204 _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key) in _mesa_hash_table_set_deleted_key() argument
206 ht->deleted_key = deleted_key; in _mesa_hash_table_set_deleted_key()
210 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) in hash_table_search() argument
212 uint32_t start_hash_address = hash % ht->size; in hash_table_search()
218 struct hash_entry *entry = ht->table + hash_address; in hash_table_search()
222 } else if (entry_is_present(ht, entry) && entry->hash == hash) { in hash_table_search()
223 if (ht->key_equals_function(key, entry->key)) { in hash_table_search()
228 double_hash = 1 + hash % ht->rehash; in hash_table_search()
230 hash_address = (hash_address + double_hash) % ht->size; in hash_table_search()
243 _mesa_hash_table_search(struct hash_table *ht, const void *key) in _mesa_hash_table_search() argument
245 assert(ht->key_hash_function); in _mesa_hash_table_search()
246 return hash_table_search(ht, ht->key_hash_function(key), key); in _mesa_hash_table_search()
250 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash, in _mesa_hash_table_search_pre_hashed() argument
253 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); in _mesa_hash_table_search_pre_hashed()
254 return hash_table_search(ht, hash, key); in _mesa_hash_table_search_pre_hashed()
258 hash_table_insert(struct hash_table *ht, uint32_t hash,
262 _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index) in _mesa_hash_table_rehash() argument
270 table = rzalloc_array(ht, struct hash_entry, in _mesa_hash_table_rehash()
275 old_ht = *ht; in _mesa_hash_table_rehash()
277 ht->table = table; in _mesa_hash_table_rehash()
278 ht->size_index = new_size_index; in _mesa_hash_table_rehash()
279 ht->size = hash_sizes[ht->size_index].size; in _mesa_hash_table_rehash()
280 ht->rehash = hash_sizes[ht->size_index].rehash; in _mesa_hash_table_rehash()
281 ht->max_entries = hash_sizes[ht->size_index].max_entries; in _mesa_hash_table_rehash()
282 ht->entries = 0; in _mesa_hash_table_rehash()
283 ht->deleted_entries = 0; in _mesa_hash_table_rehash()
286 hash_table_insert(ht, entry->hash, entry->key, entry->data); in _mesa_hash_table_rehash()
293 hash_table_insert(struct hash_table *ht, uint32_t hash, in hash_table_insert() argument
301 if (ht->entries >= ht->max_entries) { in hash_table_insert()
302 _mesa_hash_table_rehash(ht, ht->size_index + 1); in hash_table_insert()
303 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { in hash_table_insert()
304 _mesa_hash_table_rehash(ht, ht->size_index); in hash_table_insert()
307 start_hash_address = hash % ht->size; in hash_table_insert()
310 struct hash_entry *entry = ht->table + hash_address; in hash_table_insert()
313 if (!entry_is_present(ht, entry)) { in hash_table_insert()
332 if (!entry_is_deleted(ht, entry) && in hash_table_insert()
334 ht->key_equals_function(key, entry->key)) { in hash_table_insert()
341 double_hash = 1 + hash % ht->rehash; in hash_table_insert()
343 hash_address = (hash_address + double_hash) % ht->size; in hash_table_insert()
347 if (entry_is_deleted(ht, available_entry)) in hash_table_insert()
348 ht->deleted_entries--; in hash_table_insert()
352 ht->entries++; in hash_table_insert()
369 _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data) in _mesa_hash_table_insert() argument
371 assert(ht->key_hash_function); in _mesa_hash_table_insert()
372 return hash_table_insert(ht, ht->key_hash_function(key), key, data); in _mesa_hash_table_insert()
376 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, in _mesa_hash_table_insert_pre_hashed() argument
379 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); in _mesa_hash_table_insert_pre_hashed()
380 return hash_table_insert(ht, hash, key, data); in _mesa_hash_table_insert_pre_hashed()
390 _mesa_hash_table_remove(struct hash_table *ht, in _mesa_hash_table_remove() argument
396 entry->key = ht->deleted_key; in _mesa_hash_table_remove()
397 ht->entries--; in _mesa_hash_table_remove()
398 ht->deleted_entries++; in _mesa_hash_table_remove()
408 _mesa_hash_table_next_entry(struct hash_table *ht, in _mesa_hash_table_next_entry() argument
412 entry = ht->table; in _mesa_hash_table_next_entry()
416 for (; entry != ht->table + ht->size; entry++) { in _mesa_hash_table_next_entry()
417 if (entry_is_present(ht, entry)) { in _mesa_hash_table_next_entry()
434 _mesa_hash_table_random_entry(struct hash_table *ht, in _mesa_hash_table_random_entry() argument
438 uint32_t i = rand() % ht->size; in _mesa_hash_table_random_entry()
440 if (ht->entries == 0) in _mesa_hash_table_random_entry()
443 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) { in _mesa_hash_table_random_entry()
444 if (entry_is_present(ht, entry) && in _mesa_hash_table_random_entry()
450 for (entry = ht->table; entry != ht->table + i; entry++) { in _mesa_hash_table_random_entry()
451 if (entry_is_present(ht, entry) && in _mesa_hash_table_random_entry()
536 struct hash_table_u64 *ht; in _mesa_hash_table_u64_create() local
538 ht = CALLOC_STRUCT(hash_table_u64); in _mesa_hash_table_u64_create()
539 if (!ht) in _mesa_hash_table_u64_create()
543 ht->table = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, in _mesa_hash_table_u64_create()
546 ht->table = _mesa_hash_table_create(mem_ctx, key_u64_hash, in _mesa_hash_table_u64_create()
550 if (ht->table) in _mesa_hash_table_u64_create()
551 _mesa_hash_table_set_deleted_key(ht->table, uint_key(DELETED_KEY_VALUE)); in _mesa_hash_table_u64_create()
553 return ht; in _mesa_hash_table_u64_create()
557 _mesa_hash_table_u64_destroy(struct hash_table_u64 *ht, in _mesa_hash_table_u64_destroy() argument
560 if (!ht) in _mesa_hash_table_u64_destroy()
563 if (ht->deleted_key_data) { in _mesa_hash_table_u64_destroy()
565 struct hash_table *table = ht->table; in _mesa_hash_table_u64_destroy()
571 deleted_entry.data = ht->deleted_key_data; in _mesa_hash_table_u64_destroy()
575 ht->deleted_key_data = NULL; in _mesa_hash_table_u64_destroy()
578 _mesa_hash_table_destroy(ht->table, delete_function); in _mesa_hash_table_u64_destroy()
579 free(ht); in _mesa_hash_table_u64_destroy()
583 _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key, in _mesa_hash_table_u64_insert() argument
587 ht->deleted_key_data = data; in _mesa_hash_table_u64_insert()
592 _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data); in _mesa_hash_table_u64_insert()
600 _mesa_hash_table_insert(ht->table, _key, data); in _mesa_hash_table_u64_insert()
605 hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key) in hash_table_u64_search() argument
608 return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key); in hash_table_u64_search()
611 return _mesa_hash_table_search(ht->table, &_key); in hash_table_u64_search()
616 _mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key) in _mesa_hash_table_u64_search() argument
621 return ht->deleted_key_data; in _mesa_hash_table_u64_search()
623 entry = hash_table_u64_search(ht, key); in _mesa_hash_table_u64_search()
631 _mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key) in _mesa_hash_table_u64_remove() argument
636 ht->deleted_key_data = NULL; in _mesa_hash_table_u64_remove()
640 entry = hash_table_u64_search(ht, key); in _mesa_hash_table_u64_remove()
645 _mesa_hash_table_remove(ht->table, entry); in _mesa_hash_table_u64_remove()
649 _mesa_hash_table_remove(ht->table, entry); in _mesa_hash_table_u64_remove()