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 = ¤t->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 = ¤t->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 = ¤t->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