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