Lines Matching refs:ht
125 key_pointer_is_reserved(const struct hash_table *ht, const void *key)
127 return key == NULL || key == ht->deleted_key;
137 entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry)
139 return entry->key == ht->deleted_key;
143 entry_is_present(const struct hash_table *ht, struct hash_entry *entry)
145 return entry->key != NULL && entry->key != ht->deleted_key;
149 _mesa_hash_table_init(struct hash_table *ht,
155 ht->size_index = 0;
156 ht->size = hash_sizes[ht->size_index].size;
157 ht->rehash = hash_sizes[ht->size_index].rehash;
158 ht->size_magic = hash_sizes[ht->size_index].size_magic;
159 ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
160 ht->max_entries = hash_sizes[ht->size_index].max_entries;
161 ht->key_hash_function = key_hash_function;
162 ht->key_equals_function = key_equals_function;
163 ht->table = rzalloc_array(mem_ctx, struct hash_entry, ht->size);
164 ht->entries = 0;
165 ht->deleted_entries = 0;
166 ht->deleted_key = &deleted_key_value;
168 return ht->table != NULL;
177 struct hash_table *ht;
182 ht = ralloc(mem_ctx, struct hash_table);
183 if (ht == NULL)
186 if (!_mesa_hash_table_init(ht, ht, key_hash_function, key_equals_function)) {
187 ralloc_free(ht);
191 return ht;
217 struct hash_table *ht;
219 ht = ralloc(dst_mem_ctx, struct hash_table);
220 if (ht == NULL)
223 memcpy(ht, src, sizeof(struct hash_table));
225 ht->table = ralloc_array(ht, struct hash_entry, ht->size);
226 if (ht->table == NULL) {
227 ralloc_free(ht);
231 memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry));
233 return ht;
243 _mesa_hash_table_destroy(struct hash_table *ht,
246 if (!ht)
250 hash_table_foreach(ht, entry) {
254 ralloc_free(ht);
258 hash_table_clear_fast(struct hash_table *ht)
260 memset(ht->table, 0, sizeof(struct hash_entry) * hash_sizes[ht->size_index].size);
261 ht->entries = ht->deleted_entries = 0;
271 _mesa_hash_table_clear(struct hash_table *ht,
274 if (!ht)
280 for (entry = ht->table; entry != ht->table + ht->size; entry++) {
281 if (entry_is_present(ht, entry))
286 ht->entries = 0;
287 ht->deleted_entries = 0;
289 hash_table_clear_fast(ht);
303 _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key)
305 ht->deleted_key = deleted_key;
309 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
311 assert(!key_pointer_is_reserved(ht, key));
313 uint32_t size = ht->size;
314 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
315 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
316 ht->rehash_magic);
320 struct hash_entry *entry = ht->table + hash_address;
324 } else if (entry_is_present(ht, entry) && entry->hash == hash) {
325 if (ht->key_equals_function(key, entry->key)) {
345 _mesa_hash_table_search(struct hash_table *ht, const void *key)
347 assert(ht->key_hash_function);
348 return hash_table_search(ht, ht->key_hash_function(key), key);
352 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
355 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
356 return hash_table_search(ht, hash, key);
360 hash_table_insert(struct hash_table *ht, uint32_t hash,
364 hash_table_insert_rehash(struct hash_table *ht, uint32_t hash,
367 uint32_t size = ht->size;
368 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
369 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
370 ht->rehash_magic);
373 struct hash_entry *entry = ht->table + hash_address;
389 _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
394 if (ht->size_index == new_size_index && ht->deleted_entries == ht->max_entries) {
395 hash_table_clear_fast(ht);
396 assert(!ht->entries);
403 table = rzalloc_array(ralloc_parent(ht->table), struct hash_entry,
408 old_ht = *ht;
410 ht->table = table;
411 ht->size_index = new_size_index;
412 ht->size = hash_sizes[ht->size_index].size;
413 ht->rehash = hash_sizes[ht->size_index].rehash;
414 ht->size_magic = hash_sizes[ht->size_index].size_magic;
415 ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
416 ht->max_entries = hash_sizes[ht->size_index].max_entries;
417 ht->entries = 0;
418 ht->deleted_entries = 0;
421 hash_table_insert_rehash(ht, entry->hash, entry->key, entry->data);
424 ht->entries = old_ht.entries;
430 hash_table_insert(struct hash_table *ht, uint32_t hash,
435 assert(!key_pointer_is_reserved(ht, key));
437 if (ht->entries >= ht->max_entries) {
438 _mesa_hash_table_rehash(ht, ht->size_index + 1);
439 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
440 _mesa_hash_table_rehash(ht, ht->size_index);
443 uint32_t size = ht->size;
444 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
445 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
446 ht->rehash_magic);
449 struct hash_entry *entry = ht->table + hash_address;
451 if (!entry_is_present(ht, entry)) {
470 if (!entry_is_deleted(ht, entry) &&
472 ht->key_equals_function(key, entry->key)) {
484 if (entry_is_deleted(ht, available_entry))
485 ht->deleted_entries--;
489 ht->entries++;
506 _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data)
508 assert(ht->key_hash_function);
509 return hash_table_insert(ht, ht->key_hash_function(key), key, data);
513 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
516 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
517 return hash_table_insert(ht, hash, key, data);
527 _mesa_hash_table_remove(struct hash_table *ht,
533 entry->key = ht->deleted_key;
534 ht->entries--;
535 ht->deleted_entries++;
541 void _mesa_hash_table_remove_key(struct hash_table *ht,
544 _mesa_hash_table_remove(ht, _mesa_hash_table_search(ht, key));
553 _mesa_hash_table_next_entry_unsafe(const struct hash_table *ht, struct hash_entry *entry)
555 assert(!ht->deleted_entries);
556 if (!ht->entries)
559 entry = ht->table;
562 if (entry != ht->table + ht->size)
563 return entry->key ? entry : _mesa_hash_table_next_entry_unsafe(ht, entry);
575 _mesa_hash_table_next_entry(struct hash_table *ht,
579 entry = ht->table;
583 for (; entry != ht->table + ht->size; entry++) {
584 if (entry_is_present(ht, entry)) {
601 _mesa_hash_table_random_entry(struct hash_table *ht,
605 uint32_t i = rand() % ht->size;
607 if (ht->entries == 0)
610 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
611 if (entry_is_present(ht, entry) &&
617 for (entry = ht->table; entry != ht->table + i; entry++) {
618 if (entry_is_present(ht, entry) &&
732 _mesa_hash_table_reserve(struct hash_table *ht, unsigned size)
734 if (size < ht->max_entries)
736 for (unsigned i = ht->size_index + 1; i < ARRAY_SIZE(hash_sizes); i++) {
738 _mesa_hash_table_rehash(ht, i);
742 return ht->max_entries >= size;
776 struct hash_table_u64 *ht;
778 ht = CALLOC_STRUCT(hash_table_u64);
779 if (!ht)
783 ht->table = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
786 ht->table = _mesa_hash_table_create(mem_ctx, key_u64_hash,
790 if (ht->table)
791 _mesa_hash_table_set_deleted_key(ht->table, uint_key(DELETED_KEY_VALUE));
793 return ht;
809 _mesa_hash_table_u64_clear(struct hash_table_u64 *ht)
811 if (!ht)
814 _mesa_hash_table_clear(ht->table, _mesa_hash_table_u64_delete_key);
815 ht->freed_key_data = NULL;
816 ht->deleted_key_data = NULL;
820 _mesa_hash_table_u64_destroy(struct hash_table_u64 *ht)
822 if (!ht)
825 _mesa_hash_table_u64_clear(ht);
826 _mesa_hash_table_destroy(ht->table, NULL);
827 free(ht);
831 _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key,
835 ht->freed_key_data = data;
840 ht->deleted_key_data = data;
845 _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data);
853 _mesa_hash_table_insert(ht->table, _key, data);
858 hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
861 return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key);
864 return _mesa_hash_table_search(ht->table, &_key);
869 _mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
874 return ht->freed_key_data;
877 return ht->deleted_key_data;
879 entry = hash_table_u64_search(ht, key);
887 _mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key)
892 ht->freed_key_data = NULL;
897 ht->deleted_key_data = NULL;
901 entry = hash_table_u64_search(ht, key);
906 _mesa_hash_table_remove(ht->table, entry);
910 _mesa_hash_table_remove(ht->table, entry);