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