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 */
80static inline int hashKey(Hashmap* map, void* key) {
81    int h = map->hash(key);
82
83    // We apply this secondary hashing discovered by Doug Lea to defend
84    // against bad hashes.
85    h += ~(h << 9);
86    h ^= (((unsigned int) h) >> 14);
87    h += (h << 4);
88    h ^= (((unsigned int) h) >> 10);
89
90    return h;
91}
92
93size_t hashmapSize(Hashmap* map) {
94    return map->size;
95}
96
97static inline size_t calculateIndex(size_t bucketCount, int hash) {
98    return ((size_t) hash) & (bucketCount - 1);
99}
100
101static void expandIfNecessary(Hashmap* map) {
102    // If the load factor exceeds 0.75...
103    if (map->size > (map->bucketCount * 3 / 4)) {
104        // Start off with a 0.33 load factor.
105        size_t newBucketCount = map->bucketCount << 1;
106        Entry** newBuckets = calloc(newBucketCount, sizeof(Entry*));
107        if (newBuckets == NULL) {
108            // Abort expansion.
109            return;
110        }
111
112        // Move over existing entries.
113        size_t i;
114        for (i = 0; i < map->bucketCount; i++) {
115            Entry* entry = map->buckets[i];
116            while (entry != NULL) {
117                Entry* next = entry->next;
118                size_t index = calculateIndex(newBucketCount, entry->hash);
119                entry->next = newBuckets[index];
120                newBuckets[index] = entry;
121                entry = next;
122            }
123        }
124
125        // Copy over internals.
126        free(map->buckets);
127        map->buckets = newBuckets;
128        map->bucketCount = newBucketCount;
129    }
130}
131
132void hashmapLock(Hashmap* map) {
133    mutex_lock(&map->lock);
134}
135
136void hashmapUnlock(Hashmap* map) {
137    mutex_unlock(&map->lock);
138}
139
140void hashmapFree(Hashmap* map) {
141    size_t i;
142    for (i = 0; i < map->bucketCount; i++) {
143        Entry* entry = map->buckets[i];
144        while (entry != NULL) {
145            Entry* next = entry->next;
146            free(entry);
147            entry = next;
148        }
149    }
150    free(map->buckets);
151    mutex_destroy(&map->lock);
152    free(map);
153}
154
155int hashmapHash(void* key, size_t keySize) {
156    int h = keySize;
157    char* data = (char*) key;
158    size_t i;
159    for (i = 0; i < keySize; i++) {
160        h = h * 31 + *data;
161        data++;
162    }
163    return h;
164}
165
166static Entry* createEntry(void* key, int hash, void* value) {
167    Entry* entry = malloc(sizeof(Entry));
168    if (entry == NULL) {
169        return NULL;
170    }
171    entry->key = key;
172    entry->hash = hash;
173    entry->value = value;
174    entry->next = NULL;
175    return entry;
176}
177
178static inline bool equalKeys(void* keyA, int hashA, void* keyB, int hashB,
179        bool (*equals)(void*, void*)) {
180    if (keyA == keyB) {
181        return true;
182    }
183    if (hashA != hashB) {
184        return false;
185    }
186    return equals(keyA, keyB);
187}
188
189void* hashmapPut(Hashmap* map, void* key, void* value) {
190    int hash = hashKey(map, key);
191    size_t index = calculateIndex(map->bucketCount, hash);
192
193    Entry** p = &(map->buckets[index]);
194    while (true) {
195        Entry* current = *p;
196
197        // Add a new entry.
198        if (current == NULL) {
199            *p = createEntry(key, hash, value);
200            if (*p == NULL) {
201                errno = ENOMEM;
202                return NULL;
203            }
204            map->size++;
205            expandIfNecessary(map);
206            return NULL;
207        }
208
209        // Replace existing entry.
210        if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
211            void* oldValue = current->value;
212            current->value = value;
213            return oldValue;
214        }
215
216        // Move to next entry.
217        p = &current->next;
218    }
219}
220
221void* hashmapGet(Hashmap* map, void* key) {
222    int hash = hashKey(map, key);
223    size_t index = calculateIndex(map->bucketCount, hash);
224
225    Entry* entry = map->buckets[index];
226    while (entry != NULL) {
227        if (equalKeys(entry->key, entry->hash, key, hash, map->equals)) {
228            return entry->value;
229        }
230        entry = entry->next;
231    }
232
233    return NULL;
234}
235
236bool hashmapContainsKey(Hashmap* map, void* key) {
237    int hash = hashKey(map, key);
238    size_t index = calculateIndex(map->bucketCount, hash);
239
240    Entry* entry = map->buckets[index];
241    while (entry != NULL) {
242        if (equalKeys(entry->key, entry->hash, key, hash, map->equals)) {
243            return true;
244        }
245        entry = entry->next;
246    }
247
248    return false;
249}
250
251void* hashmapMemoize(Hashmap* map, void* key,
252        void* (*initialValue)(void* key, void* context), void* context) {
253    int hash = hashKey(map, key);
254    size_t index = calculateIndex(map->bucketCount, hash);
255
256    Entry** p = &(map->buckets[index]);
257    while (true) {
258        Entry* current = *p;
259
260        // Add a new entry.
261        if (current == NULL) {
262            *p = createEntry(key, hash, NULL);
263            if (*p == NULL) {
264                errno = ENOMEM;
265                return NULL;
266            }
267            void* value = initialValue(key, context);
268            (*p)->value = value;
269            map->size++;
270            expandIfNecessary(map);
271            return value;
272        }
273
274        // Return existing value.
275        if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
276            return current->value;
277        }
278
279        // Move to next entry.
280        p = &current->next;
281    }
282}
283
284void* hashmapRemove(Hashmap* map, void* key) {
285    int hash = hashKey(map, key);
286    size_t index = calculateIndex(map->bucketCount, hash);
287
288    // Pointer to the current entry.
289    Entry** p = &(map->buckets[index]);
290    Entry* current;
291    while ((current = *p) != NULL) {
292        if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
293            void* value = current->value;
294            *p = current->next;
295            free(current);
296            map->size--;
297            return value;
298        }
299
300        p = &current->next;
301    }
302
303    return NULL;
304}
305
306void hashmapForEach(Hashmap* map,
307        bool (*callback)(void* key, void* value, void* context),
308        void* context) {
309    size_t i;
310    for (i = 0; i < map->bucketCount; i++) {
311        Entry* entry = map->buckets[i];
312        while (entry != NULL) {
313            Entry *next = entry->next;
314            if (!callback(entry->key, entry->value, context)) {
315                return;
316            }
317            entry = next;
318        }
319    }
320}
321
322size_t hashmapCurrentCapacity(Hashmap* map) {
323    size_t bucketCount = map->bucketCount;
324    return bucketCount * 3 / 4;
325}
326
327size_t hashmapCountCollisions(Hashmap* map) {
328    size_t collisions = 0;
329    size_t i;
330    for (i = 0; i < map->bucketCount; i++) {
331        Entry* entry = map->buckets[i];
332        while (entry != NULL) {
333            if (entry->next != NULL) {
334                collisions++;
335            }
336            entry = entry->next;
337        }
338    }
339    return collisions;
340}
341
342int hashmapIntHash(void* key) {
343    // Return the key value itself.
344    return *((int*) key);
345}
346
347bool hashmapIntEquals(void* keyA, void* keyB) {
348    int a = *((int*) keyA);
349    int b = *((int*) keyB);
350    return a == b;
351}
352