blob: e29bc2461cc93ac6c0f713e23dbbdf241e9c1cd0 [file] [log] [blame]
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -08001/*
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 if (!callback(entry->key, entry->value, context)) {
314 return;
315 }
316 entry = entry->next;
317 }
318 }
319}
320
321size_t hashmapCurrentCapacity(Hashmap* map) {
322 size_t bucketCount = map->bucketCount;
323 return bucketCount * 3 / 4;
324}
325
326size_t hashmapCountCollisions(Hashmap* map) {
327 size_t collisions = 0;
328 size_t i;
329 for (i = 0; i < map->bucketCount; i++) {
330 Entry* entry = map->buckets[i];
331 while (entry != NULL) {
332 if (entry->next != NULL) {
333 collisions++;
334 }
335 entry = entry->next;
336 }
337 }
338 return collisions;
339}
340
341int hashmapIntHash(void* key) {
342 // Return the key value itself.
343 return *((int*) key);
344}
345
346bool hashmapIntEquals(void* keyA, void* keyB) {
347 int a = *((int*) keyA);
348 int b = *((int*) keyB);
349 return a == b;
350}