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