projects
/
mesa.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
meson: Don't build intel shared components by default
[mesa.git]
/
src
/
util
/
set.c
diff --git
a/src/util/set.c
b/src/util/set.c
index c3252a09401efdb3a2361a616585e02cc098b0e7..392506639547d0d13cfbe89c8d5026f03e34a9bb 100644
(file)
--- a/
src/util/set.c
+++ b/
src/util/set.c
@@
-45,8
+45,8
@@
* free to avoid exponential performance degradation as the hash table fills
*/
* free to avoid exponential performance degradation as the hash table fills
*/
-uint32_t deleted_key_value;
-const void *deleted_key = &deleted_key_value;
+
static const
uint32_t deleted_key_value;
+
static
const void *deleted_key = &deleted_key_value;
static const struct {
uint32_t max_entries, size, rehash;
static const struct {
uint32_t max_entries, size, rehash;
@@
-251,6
+251,7
@@
static struct set_entry *
set_add(struct set *ht, uint32_t hash, const void *key)
{
uint32_t hash_address;
set_add(struct set *ht, uint32_t hash, const void *key)
{
uint32_t hash_address;
+ struct set_entry *available_entry = NULL;
if (ht->entries >= ht->max_entries) {
set_rehash(ht, ht->size_index + 1);
if (ht->entries >= ht->max_entries) {
set_rehash(ht, ht->size_index + 1);
@@
-264,12
+265,11
@@
set_add(struct set *ht, uint32_t hash, const void *key)
uint32_t double_hash;
if (!entry_is_present(entry)) {
uint32_t double_hash;
if (!entry_is_present(entry)) {
- if (entry_is_deleted(entry))
- ht->deleted_entries--;
- entry->hash = hash;
- entry->key = key;
- ht->entries++;
- return entry;
+ /* Stash the first available entry we find */
+ if (available_entry == NULL)
+ available_entry = entry;
+ if (entry_is_free(entry))
+ break;
}
/* Implement replacement when another insert happens
}
/* Implement replacement when another insert happens
@@
-282,7
+282,8
@@
set_add(struct set *ht, uint32_t hash, const void *key)
* If freeing of old keys is required to avoid memory leaks,
* perform a search before inserting.
*/
* If freeing of old keys is required to avoid memory leaks,
* perform a search before inserting.
*/
- if (entry->hash == hash &&
+ if (!entry_is_deleted(entry) &&
+ entry->hash == hash &&
ht->key_equals_function(key, entry->key)) {
entry->key = key;
return entry;
ht->key_equals_function(key, entry->key)) {
entry->key = key;
return entry;
@@
-293,6
+294,15
@@
set_add(struct set *ht, uint32_t hash, const void *key)
hash_address = (hash_address + double_hash) % ht->size;
} while (hash_address != hash % ht->size);
hash_address = (hash_address + double_hash) % ht->size;
} while (hash_address != hash % ht->size);
+ if (available_entry) {
+ if (entry_is_deleted(available_entry))
+ ht->deleted_entries--;
+ available_entry->hash = hash;
+ available_entry->key = key;
+ ht->entries++;
+ return available_entry;
+ }
+
/* We could hit here if a required resize failed. An unchecked-malloc
* application could ignore this result.
*/
/* We could hit here if a required resize failed. An unchecked-malloc
* application could ignore this result.
*/