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