blob: ede3b981da0cb40f429737f51bee0985fd8a1131 [file] [log] [blame]
/*
* Copyright (C) 2007 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <cutils/hashmap.h>
#include <assert.h>
#include <errno.h>
#include <cutils/threads.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <sys/types.h>
typedef struct Entry Entry;
struct Entry {
void* key;
int hash;
void* value;
Entry* next;
};
struct Hashmap {
Entry** buckets;
size_t bucketCount;
int (*hash)(void* key);
bool (*equals)(void* keyA, void* keyB);
mutex_t lock;
size_t size;
};
Hashmap* hashmapCreate(size_t initialCapacity,
int (*hash)(void* key), bool (*equals)(void* keyA, void* keyB)) {
assert(hash != NULL);
assert(equals != NULL);
Hashmap* map = malloc(sizeof(Hashmap));
if (map == NULL) {
return NULL;
}
// 0.75 load factor.
size_t minimumBucketCount = initialCapacity * 4 / 3;
map->bucketCount = 1;
while (map->bucketCount <= minimumBucketCount) {
// Bucket count must be power of 2.
map->bucketCount <<= 1;
}
map->buckets = calloc(map->bucketCount, sizeof(Entry*));
if (map->buckets == NULL) {
free(map);
return NULL;
}
map->size = 0;
map->hash = hash;
map->equals = equals;
mutex_init(&map->lock);
return map;
}
/**
* Hashes the given key.
*/
#ifdef __clang__
__attribute__((no_sanitize("integer")))
#endif
static inline int hashKey(Hashmap* map, void* key) {
int h = map->hash(key);
// We apply this secondary hashing discovered by Doug Lea to defend
// against bad hashes.
h += ~(h << 9);
h ^= (((unsigned int) h) >> 14);
h += (h << 4);
h ^= (((unsigned int) h) >> 10);
return h;
}
size_t hashmapSize(Hashmap* map) {
return map->size;
}
static inline size_t calculateIndex(size_t bucketCount, int hash) {
return ((size_t) hash) & (bucketCount - 1);
}
static void expandIfNecessary(Hashmap* map) {
// If the load factor exceeds 0.75...
if (map->size > (map->bucketCount * 3 / 4)) {
// Start off with a 0.33 load factor.
size_t newBucketCount = map->bucketCount << 1;
Entry** newBuckets = calloc(newBucketCount, sizeof(Entry*));
if (newBuckets == NULL) {
// Abort expansion.
return;
}
// Move over existing entries.
size_t i;
for (i = 0; i < map->bucketCount; i++) {
Entry* entry = map->buckets[i];
while (entry != NULL) {
Entry* next = entry->next;
size_t index = calculateIndex(newBucketCount, entry->hash);
entry->next = newBuckets[index];
newBuckets[index] = entry;
entry = next;
}
}
// Copy over internals.
free(map->buckets);
map->buckets = newBuckets;
map->bucketCount = newBucketCount;
}
}
void hashmapLock(Hashmap* map) {
mutex_lock(&map->lock);
}
void hashmapUnlock(Hashmap* map) {
mutex_unlock(&map->lock);
}
void hashmapFree(Hashmap* map) {
size_t i;
for (i = 0; i < map->bucketCount; i++) {
Entry* entry = map->buckets[i];
while (entry != NULL) {
Entry* next = entry->next;
free(entry);
entry = next;
}
}
free(map->buckets);
mutex_destroy(&map->lock);
free(map);
}
#ifdef __clang__
__attribute__((no_sanitize("integer")))
#endif
/* FIXME: relies on signed integer overflow, which is undefined behavior */
int hashmapHash(void* key, size_t keySize) {
int h = keySize;
char* data = (char*) key;
size_t i;
for (i = 0; i < keySize; i++) {
h = h * 31 + *data;
data++;
}
return h;
}
static Entry* createEntry(void* key, int hash, void* value) {
Entry* entry = malloc(sizeof(Entry));
if (entry == NULL) {
return NULL;
}
entry->key = key;
entry->hash = hash;
entry->value = value;
entry->next = NULL;
return entry;
}
static inline bool equalKeys(void* keyA, int hashA, void* keyB, int hashB,
bool (*equals)(void*, void*)) {
if (keyA == keyB) {
return true;
}
if (hashA != hashB) {
return false;
}
return equals(keyA, keyB);
}
void* hashmapPut(Hashmap* map, void* key, void* value) {
int hash = hashKey(map, key);
size_t index = calculateIndex(map->bucketCount, hash);
Entry** p = &(map->buckets[index]);
while (true) {
Entry* current = *p;
// Add a new entry.
if (current == NULL) {
*p = createEntry(key, hash, value);
if (*p == NULL) {
errno = ENOMEM;
return NULL;
}
map->size++;
expandIfNecessary(map);
return NULL;
}
// Replace existing entry.
if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
void* oldValue = current->value;
current->value = value;
return oldValue;
}
// Move to next entry.
p = &current->next;
}
}
void* hashmapGet(Hashmap* map, void* key) {
int hash = hashKey(map, key);
size_t index = calculateIndex(map->bucketCount, hash);
Entry* entry = map->buckets[index];
while (entry != NULL) {
if (equalKeys(entry->key, entry->hash, key, hash, map->equals)) {
return entry->value;
}
entry = entry->next;
}
return NULL;
}
bool hashmapContainsKey(Hashmap* map, void* key) {
int hash = hashKey(map, key);
size_t index = calculateIndex(map->bucketCount, hash);
Entry* entry = map->buckets[index];
while (entry != NULL) {
if (equalKeys(entry->key, entry->hash, key, hash, map->equals)) {
return true;
}
entry = entry->next;
}
return false;
}
void* hashmapMemoize(Hashmap* map, void* key,
void* (*initialValue)(void* key, void* context), void* context) {
int hash = hashKey(map, key);
size_t index = calculateIndex(map->bucketCount, hash);
Entry** p = &(map->buckets[index]);
while (true) {
Entry* current = *p;
// Add a new entry.
if (current == NULL) {
*p = createEntry(key, hash, NULL);
if (*p == NULL) {
errno = ENOMEM;
return NULL;
}
void* value = initialValue(key, context);
(*p)->value = value;
map->size++;
expandIfNecessary(map);
return value;
}
// Return existing value.
if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
return current->value;
}
// Move to next entry.
p = &current->next;
}
}
void* hashmapRemove(Hashmap* map, void* key) {
int hash = hashKey(map, key);
size_t index = calculateIndex(map->bucketCount, hash);
// Pointer to the current entry.
Entry** p = &(map->buckets[index]);
Entry* current;
while ((current = *p) != NULL) {
if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
void* value = current->value;
*p = current->next;
free(current);
map->size--;
return value;
}
p = &current->next;
}
return NULL;
}
void hashmapForEach(Hashmap* map,
bool (*callback)(void* key, void* value, void* context),
void* context) {
size_t i;
for (i = 0; i < map->bucketCount; i++) {
Entry* entry = map->buckets[i];
while (entry != NULL) {
Entry *next = entry->next;
if (!callback(entry->key, entry->value, context)) {
return;
}
entry = next;
}
}
}
size_t hashmapCurrentCapacity(Hashmap* map) {
size_t bucketCount = map->bucketCount;
return bucketCount * 3 / 4;
}
size_t hashmapCountCollisions(Hashmap* map) {
size_t collisions = 0;
size_t i;
for (i = 0; i < map->bucketCount; i++) {
Entry* entry = map->buckets[i];
while (entry != NULL) {
if (entry->next != NULL) {
collisions++;
}
entry = entry->next;
}
}
return collisions;
}
int hashmapIntHash(void* key) {
// Return the key value itself.
return *((int*) key);
}
bool hashmapIntEquals(void* keyA, void* keyB) {
int a = *((int*) keyA);
int b = *((int*) keyB);
return a == b;
}