1dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/*
2dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project
3dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project *
4dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License");
5dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * you may not use this file except in compliance with the License.
6dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * You may obtain a copy of the License at
7dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project *
8dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project *      http://www.apache.org/licenses/LICENSE-2.0
9dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project *
10dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Unless required by applicable law or agreed to in writing, software
11dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS,
12dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * See the License for the specific language governing permissions and
14dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * limitations under the License.
15dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */
16dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
17dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <cutils/hashmap.h>
18dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <assert.h>
19dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <errno.h>
20dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <cutils/threads.h>
21dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <stdlib.h>
22dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <string.h>
23dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <stdbool.h>
24dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <sys/types.h>
25dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
26dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projecttypedef struct Entry Entry;
27dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstruct Entry {
28dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    void* key;
29dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int hash;
30dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    void* value;
31dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry* next;
32dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project};
33dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
34dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstruct Hashmap {
35dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry** buckets;
36dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t bucketCount;
37dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int (*hash)(void* key);
38dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    bool (*equals)(void* keyA, void* keyB);
39dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    mutex_t lock;
40dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t size;
41dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project};
42dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
43dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source ProjectHashmap* hashmapCreate(size_t initialCapacity,
44dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        int (*hash)(void* key), bool (*equals)(void* keyA, void* keyB)) {
45dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    assert(hash != NULL);
46dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    assert(equals != NULL);
47dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
48dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Hashmap* map = malloc(sizeof(Hashmap));
49dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    if (map == NULL) {
50dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        return NULL;
51dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
52dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
53dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    // 0.75 load factor.
54dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t minimumBucketCount = initialCapacity * 4 / 3;
55dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    map->bucketCount = 1;
56dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    while (map->bucketCount <= minimumBucketCount) {
57dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Bucket count must be power of 2.
58dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        map->bucketCount <<= 1;
59dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
60dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
61dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    map->buckets = calloc(map->bucketCount, sizeof(Entry*));
62dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    if (map->buckets == NULL) {
63dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        free(map);
64dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        return NULL;
65dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
66dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
67dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    map->size = 0;
68dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
69dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    map->hash = hash;
70dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    map->equals = equals;
71dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
72dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    mutex_init(&map->lock);
73dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
74dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return map;
75dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
76dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
77dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/**
78dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Hashes the given key.
79dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */
80dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic inline int hashKey(Hashmap* map, void* key) {
81dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int h = map->hash(key);
82dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
83dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    // We apply this secondary hashing discovered by Doug Lea to defend
84dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    // against bad hashes.
85dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    h += ~(h << 9);
86dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    h ^= (((unsigned int) h) >> 14);
87dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    h += (h << 4);
88dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    h ^= (((unsigned int) h) >> 10);
89dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
90dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return h;
91dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
92dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
93dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectsize_t hashmapSize(Hashmap* map) {
94dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return map->size;
95dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
96dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
97dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic inline size_t calculateIndex(size_t bucketCount, int hash) {
98dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return ((size_t) hash) & (bucketCount - 1);
99dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
100dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
101dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic void expandIfNecessary(Hashmap* map) {
102dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    // If the load factor exceeds 0.75...
103dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    if (map->size > (map->bucketCount * 3 / 4)) {
104dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Start off with a 0.33 load factor.
105dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        size_t newBucketCount = map->bucketCount << 1;
106dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        Entry** newBuckets = calloc(newBucketCount, sizeof(Entry*));
107dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        if (newBuckets == NULL) {
108dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            // Abort expansion.
109dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            return;
110dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
111dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
112dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Move over existing entries.
113dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        size_t i;
114dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        for (i = 0; i < map->bucketCount; i++) {
115dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            Entry* entry = map->buckets[i];
116dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            while (entry != NULL) {
117dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                Entry* next = entry->next;
118dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                size_t index = calculateIndex(newBucketCount, entry->hash);
119dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                entry->next = newBuckets[index];
120dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                newBuckets[index] = entry;
121dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                entry = next;
122dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            }
123dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
124dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
125dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Copy over internals.
126dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        free(map->buckets);
127dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        map->buckets = newBuckets;
128dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        map->bucketCount = newBucketCount;
129dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
130dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
131dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
132dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid hashmapLock(Hashmap* map) {
133dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    mutex_lock(&map->lock);
134dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
135dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
136dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid hashmapUnlock(Hashmap* map) {
137dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    mutex_unlock(&map->lock);
138dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
139dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
140dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid hashmapFree(Hashmap* map) {
141dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t i;
142dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    for (i = 0; i < map->bucketCount; i++) {
143dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        Entry* entry = map->buckets[i];
144dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        while (entry != NULL) {
145dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            Entry* next = entry->next;
146dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            free(entry);
147dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            entry = next;
148dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
149dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
150dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    free(map->buckets);
151dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    mutex_destroy(&map->lock);
152dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    free(map);
153dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
154dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
155dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint hashmapHash(void* key, size_t keySize) {
156dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int h = keySize;
157dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    char* data = (char*) key;
158dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t i;
159dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    for (i = 0; i < keySize; i++) {
160dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        h = h * 31 + *data;
161dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        data++;
162dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
163dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return h;
164dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
165dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
166dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic Entry* createEntry(void* key, int hash, void* value) {
167dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry* entry = malloc(sizeof(Entry));
168dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    if (entry == NULL) {
169dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        return NULL;
170dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
171dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    entry->key = key;
172dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    entry->hash = hash;
173dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    entry->value = value;
174dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    entry->next = NULL;
175dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return entry;
176dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
177dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
178dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic inline bool equalKeys(void* keyA, int hashA, void* keyB, int hashB,
179dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        bool (*equals)(void*, void*)) {
180dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    if (keyA == keyB) {
181dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        return true;
182dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
183dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    if (hashA != hashB) {
184dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        return false;
185dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
186dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return equals(keyA, keyB);
187dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
188dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
189dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid* hashmapPut(Hashmap* map, void* key, void* value) {
190dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int hash = hashKey(map, key);
191dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t index = calculateIndex(map->bucketCount, hash);
192dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
193dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry** p = &(map->buckets[index]);
194dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    while (true) {
195dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        Entry* current = *p;
196dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
197dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Add a new entry.
198dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        if (current == NULL) {
199dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            *p = createEntry(key, hash, value);
200dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            if (*p == NULL) {
201dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                errno = ENOMEM;
202dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                return NULL;
203dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            }
204dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            map->size++;
205dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            expandIfNecessary(map);
206dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            return NULL;
207dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
208dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
209dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Replace existing entry.
210dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
211dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            void* oldValue = current->value;
212dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            current->value = value;
213dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            return oldValue;
214dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
215dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
216dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Move to next entry.
217dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        p = &current->next;
218dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
219dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
220dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
221dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid* hashmapGet(Hashmap* map, void* key) {
222dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int hash = hashKey(map, key);
223dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t index = calculateIndex(map->bucketCount, hash);
224dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
225dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry* entry = map->buckets[index];
226dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    while (entry != NULL) {
227dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        if (equalKeys(entry->key, entry->hash, key, hash, map->equals)) {
228dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            return entry->value;
229dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
230dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        entry = entry->next;
231dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
232dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
233dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return NULL;
234dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
235dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
236dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectbool hashmapContainsKey(Hashmap* map, void* key) {
237dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int hash = hashKey(map, key);
238dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t index = calculateIndex(map->bucketCount, hash);
239dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
240dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry* entry = map->buckets[index];
241dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    while (entry != NULL) {
242dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        if (equalKeys(entry->key, entry->hash, key, hash, map->equals)) {
243dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            return true;
244dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
245dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        entry = entry->next;
246dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
247dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
248dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return false;
249dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
250dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
251dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid* hashmapMemoize(Hashmap* map, void* key,
252dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        void* (*initialValue)(void* key, void* context), void* context) {
253dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int hash = hashKey(map, key);
254dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t index = calculateIndex(map->bucketCount, hash);
255dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
256dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry** p = &(map->buckets[index]);
257dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    while (true) {
258dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        Entry* current = *p;
259dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
260dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Add a new entry.
261dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        if (current == NULL) {
262dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            *p = createEntry(key, hash, NULL);
263dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            if (*p == NULL) {
264dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                errno = ENOMEM;
265dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                return NULL;
266dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            }
267dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            void* value = initialValue(key, context);
268dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            (*p)->value = value;
269dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            map->size++;
270dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            expandIfNecessary(map);
271dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            return value;
272dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
273dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
274dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Return existing value.
275dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
276dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            return current->value;
277dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
278dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
279dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        // Move to next entry.
280dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        p = &current->next;
281dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
282dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
283dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
284dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid* hashmapRemove(Hashmap* map, void* key) {
285dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int hash = hashKey(map, key);
286dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t index = calculateIndex(map->bucketCount, hash);
287dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
288dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    // Pointer to the current entry.
289dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry** p = &(map->buckets[index]);
290dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    Entry* current;
291dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    while ((current = *p) != NULL) {
292dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
293dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            void* value = current->value;
294dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            *p = current->next;
295dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            free(current);
296dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            map->size--;
297dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            return value;
298dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
299dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
300dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        p = &current->next;
301dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
302dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
303dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return NULL;
304dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
305dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
306dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid hashmapForEach(Hashmap* map,
307dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        bool (*callback)(void* key, void* value, void* context),
308dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        void* context) {
309dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t i;
310dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    for (i = 0; i < map->bucketCount; i++) {
311dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        Entry* entry = map->buckets[i];
312dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        while (entry != NULL) {
3134fab9ac04e444f8ad057e67006320ca25381948eDima Zavin            Entry *next = entry->next;
314dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            if (!callback(entry->key, entry->value, context)) {
315dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                return;
316dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            }
3174fab9ac04e444f8ad057e67006320ca25381948eDima Zavin            entry = next;
318dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
319dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
320dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
321dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
322dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectsize_t hashmapCurrentCapacity(Hashmap* map) {
323dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t bucketCount = map->bucketCount;
324dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return bucketCount * 3 / 4;
325dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
326dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
327dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectsize_t hashmapCountCollisions(Hashmap* map) {
328dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t collisions = 0;
329dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    size_t i;
330dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    for (i = 0; i < map->bucketCount; i++) {
331dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        Entry* entry = map->buckets[i];
332dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        while (entry != NULL) {
333dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            if (entry->next != NULL) {
334dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project                collisions++;
335dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            }
336dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project            entry = entry->next;
337dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project        }
338dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    }
339dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return collisions;
340dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
341dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
342dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint hashmapIntHash(void* key) {
343dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    // Return the key value itself.
344dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return *((int*) key);
345dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
346dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project
347dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectbool hashmapIntEquals(void* keyA, void* keyB) {
348dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int a = *((int*) keyA);
349dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    int b = *((int*) keyB);
350dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project    return a == b;
351dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}
352