diff options
| author | Stef Walter <stefw@gnome.org> | 2012-03-27 12:14:56 +0200 |
|---|---|---|
| committer | Stef Walter <stefw@gnome.org> | 2012-03-27 12:14:56 +0200 |
| commit | af8d28014f97ab0d9e4d00961e72aefd7adb470b (patch) | |
| tree | 96b476f934489f745625731d2b1ba76a6826f517 | |
| parent | f40f63c2b608a399df431df366bf681e6b2bb20e (diff) | |
Fix broken hashmap behavior
* We were relying on undefined gcc behavior related to the &
operator.
* This would show up as a test failure when running with -O2 on
certain GCC versions, as well as failure on clang 3.1
| -rw-r--r-- | p11-kit/hashmap.c | 12 | ||||
| -rw-r--r-- | tests/hash-test.c | 2 |
2 files changed, 5 insertions, 9 deletions
diff --git a/p11-kit/hashmap.c b/p11-kit/hashmap.c index ceb8a17..1c4aff1 100644 --- a/p11-kit/hashmap.c +++ b/p11-kit/hashmap.c @@ -64,7 +64,7 @@ next_entry (hashiter *iter) { hashbucket *bucket = iter->next; while (!bucket) { - if (iter->index > iter->map->num_buckets) + if (iter->index >= iter->map->num_buckets) return NULL; bucket = iter->map->buckets[iter->index++]; } @@ -109,7 +109,7 @@ lookup_or_create_bucket (hashmap *map, hash = map->hash_func (key); /* scan linked list */ - for (bucketp = &map->buckets[map->num_buckets & hash]; + for (bucketp = &map->buckets[hash % map->num_buckets]; *bucketp != NULL; bucketp = &(*bucketp)->next) { if((*bucketp)->hashed == hash && map->equal_func ((*bucketp)->key, key)) break; @@ -167,14 +167,13 @@ _p11_hash_set (hashmap *map, /* check that the collision rate isn't too high */ if (map->num_items > map->num_buckets) { num_buckets = map->num_buckets * 2 + 1; - new_buckets = (hashbucket **)calloc (sizeof (hashbucket *), - num_buckets + 1); + new_buckets = (hashbucket **)calloc (sizeof (hashbucket *), num_buckets); /* Ignore failures, maybe we can expand later */ if(new_buckets) { _p11_hash_iterate (map, &iter); while ((bucket = next_entry (&iter)) != NULL) { - unsigned int i = bucket->hashed & num_buckets; + unsigned int i = bucket->hashed % num_buckets; bucket->next = new_buckets[i]; new_buckets[i] = bucket; } @@ -276,8 +275,7 @@ _p11_hash_create (hash_hash_func hash_func, map->value_destroy_func = value_destroy_func; map->num_buckets = 9; - map->buckets = (hashbucket **)calloc (sizeof (hashbucket *), - map->num_buckets + 1); + map->buckets = (hashbucket **)calloc (sizeof (hashbucket *), map->num_buckets); if (!map->buckets) { free (map); return NULL; diff --git a/tests/hash-test.c b/tests/hash-test.c index 876088b..530c67c 100644 --- a/tests/hash-test.c +++ b/tests/hash-test.c @@ -171,8 +171,6 @@ test_set_clear (CuTest *tc) map = _p11_hash_create (_p11_hash_direct_hash, _p11_hash_direct_equal, NULL, NULL); - fprintf (stderr, "%p setting\n", value); - if (!_p11_hash_set (map, key, value)) CuFail (tc, "should not be reached"); |