Lines Matching refs:ht
102 entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry)
104 return entry->key == ht->deleted_key;
108 entry_is_present(const struct hash_table *ht, struct hash_entry *entry)
110 return entry->key != NULL && entry->key != ht->deleted_key;
114 _mesa_hash_table_init(struct hash_table *ht,
120 ht->size_index = 0;
121 ht->size = hash_sizes[ht->size_index].size;
122 ht->rehash = hash_sizes[ht->size_index].rehash;
123 ht->max_entries = hash_sizes[ht->size_index].max_entries;
124 ht->key_hash_function = key_hash_function;
125 ht->key_equals_function = key_equals_function;
126 ht->table = rzalloc_array(mem_ctx, struct hash_entry, ht->size);
127 ht->entries = 0;
128 ht->deleted_entries = 0;
129 ht->deleted_key = &deleted_key_value;
131 return ht->table != NULL;
140 struct hash_table *ht;
145 ht = ralloc(mem_ctx, struct hash_table);
146 if (ht == NULL)
149 if (!_mesa_hash_table_init(ht, ht, key_hash_function, key_equals_function)) {
150 ralloc_free(ht);
154 return ht;
160 struct hash_table *ht;
162 ht = ralloc(dst_mem_ctx, struct hash_table);
163 if (ht == NULL)
166 memcpy(ht, src, sizeof(struct hash_table));
168 ht->table = ralloc_array(ht, struct hash_entry, ht->size);
169 if (ht->table == NULL) {
170 ralloc_free(ht);
174 memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry));
176 return ht;
186 _mesa_hash_table_destroy(struct hash_table *ht,
189 if (!ht)
193 hash_table_foreach(ht, entry) {
197 ralloc_free(ht);
207 _mesa_hash_table_clear(struct hash_table *ht,
212 for (entry = ht->table; entry != ht->table + ht->size; entry++) {
216 if (delete_function != NULL && entry->key != ht->deleted_key)
222 ht->entries = 0;
223 ht->deleted_entries = 0;
237 _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key)
239 ht->deleted_key = deleted_key;
243 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
245 uint32_t start_hash_address = hash % ht->size;
251 struct hash_entry *entry = ht->table + hash_address;
255 } else if (entry_is_present(ht, entry) && entry->hash == hash) {
256 if (ht->key_equals_function(key, entry->key)) {
261 double_hash = 1 + hash % ht->rehash;
263 hash_address = (hash_address + double_hash) % ht->size;
276 _mesa_hash_table_search(struct hash_table *ht, const void *key)
278 assert(ht->key_hash_function);
279 return hash_table_search(ht, ht->key_hash_function(key), key);
283 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
286 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
287 return hash_table_search(ht, hash, key);
291 hash_table_insert(struct hash_table *ht, uint32_t hash,
295 _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
303 table = rzalloc_array(ralloc_parent(ht->table), struct hash_entry,
308 old_ht = *ht;
310 ht->table = table;
311 ht->size_index = new_size_index;
312 ht->size = hash_sizes[ht->size_index].size;
313 ht->rehash = hash_sizes[ht->size_index].rehash;
314 ht->max_entries = hash_sizes[ht->size_index].max_entries;
315 ht->entries = 0;
316 ht->deleted_entries = 0;
319 hash_table_insert(ht, entry->hash, entry->key, entry->data);
326 hash_table_insert(struct hash_table *ht, uint32_t hash,
334 if (ht->entries >= ht->max_entries) {
335 _mesa_hash_table_rehash(ht, ht->size_index + 1);
336 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
337 _mesa_hash_table_rehash(ht, ht->size_index);
340 start_hash_address = hash % ht->size;
343 struct hash_entry *entry = ht->table + hash_address;
346 if (!entry_is_present(ht, entry)) {
365 if (!entry_is_deleted(ht, entry) &&
367 ht->key_equals_function(key, entry->key)) {
374 double_hash = 1 + hash % ht->rehash;
376 hash_address = (hash_address + double_hash) % ht->size;
380 if (entry_is_deleted(ht, available_entry))
381 ht->deleted_entries--;
385 ht->entries++;
402 _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data)
404 assert(ht->key_hash_function);
405 return hash_table_insert(ht, ht->key_hash_function(key), key, data);
409 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
412 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
413 return hash_table_insert(ht, hash, key, data);
423 _mesa_hash_table_remove(struct hash_table *ht,
429 entry->key = ht->deleted_key;
430 ht->entries--;
431 ht->deleted_entries++;
437 void _mesa_hash_table_remove_key(struct hash_table *ht,
440 _mesa_hash_table_remove(ht, _mesa_hash_table_search(ht, key));
450 _mesa_hash_table_next_entry(struct hash_table *ht,
454 entry = ht->table;
458 for (; entry != ht->table + ht->size; entry++) {
459 if (entry_is_present(ht, entry)) {
476 _mesa_hash_table_random_entry(struct hash_table *ht,
480 uint32_t i = rand() % ht->size;
482 if (ht->entries == 0)
485 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
486 if (entry_is_present(ht, entry) &&
492 for (entry = ht->table; entry != ht->table + i; entry++) {
493 if (entry_is_present(ht, entry) &&
588 struct hash_table_u64 *ht;
590 ht = CALLOC_STRUCT(hash_table_u64);
591 if (!ht)
595 ht->table = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
598 ht->table = _mesa_hash_table_create(mem_ctx, key_u64_hash,
602 if (ht->table)
603 _mesa_hash_table_set_deleted_key(ht->table, uint_key(DELETED_KEY_VALUE));
605 return ht;
609 _mesa_hash_table_u64_destroy(struct hash_table_u64 *ht,
612 if (!ht)
615 if (ht->deleted_key_data) {
617 struct hash_table *table = ht->table;
623 deleted_entry.data = ht->deleted_key_data;
627 ht->deleted_key_data = NULL;
630 _mesa_hash_table_destroy(ht->table, delete_function);
631 free(ht);
635 _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key,
639 ht->deleted_key_data = data;
644 _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data);
652 _mesa_hash_table_insert(ht->table, _key, data);
657 hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
660 return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key);
663 return _mesa_hash_table_search(ht->table, &_key);
668 _mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
673 return ht->deleted_key_data;
675 entry = hash_table_u64_search(ht, key);
683 _mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key)
688 ht->deleted_key_data = NULL;
692 entry = hash_table_u64_search(ht, key);
697 _mesa_hash_table_remove(ht->table, entry);
701 _mesa_hash_table_remove(ht->table, entry);