hashmap.c

/*
 * 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 <assert.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <sys/types.h>

#include "include/hashmap.h"
#include "include/threads.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;
}