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/** 18dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Hash map. 19dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 20dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 21dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#ifndef __HASHMAP_H 22dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#define __HASHMAP_H 23dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 24dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <stdbool.h> 25dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <stdlib.h> 26dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 27dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#ifdef __cplusplus 28dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectextern "C" { 29dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#endif 30dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 31dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** A hash map. */ 32dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projecttypedef struct Hashmap Hashmap; 33dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 34dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 35dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Creates a new hash map. Returns NULL if memory allocation fails. 36dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * 37dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * @param initialCapacity number of expected entries 38dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * @param hash function which hashes keys 39dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * @param equals function which compares keys for equality 40dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 41dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source ProjectHashmap* hashmapCreate(size_t initialCapacity, 42dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int (*hash)(void* key), bool (*equals)(void* keyA, void* keyB)); 43dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 44dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 45dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Frees the hash map. Does not free the keys or values themselves. 46dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 47dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid hashmapFree(Hashmap* map); 48dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 49dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 50dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Hashes the memory pointed to by key with the given size. Useful for 51dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * implementing hash functions. 52dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 53dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint hashmapHash(void* key, size_t keySize); 54dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 55dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 56dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Puts value for the given key in the map. Returns pre-existing value if 57dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * any. 58dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * 59dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * If memory allocation fails, this function returns NULL, the map's size 60dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * does not increase, and errno is set to ENOMEM. 61dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 62dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid* hashmapPut(Hashmap* map, void* key, void* value); 63dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 64dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 65dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Gets a value from the map. Returns NULL if no entry for the given key is 66dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * found or if the value itself is NULL. 67dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 68dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid* hashmapGet(Hashmap* map, void* key); 69dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 70dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 71dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Returns true if the map contains an entry for the given key. 72dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 73dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectbool hashmapContainsKey(Hashmap* map, void* key); 74dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 75dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 76dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Gets the value for a key. If a value is not found, this function gets a 77dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * value and creates an entry using the given callback. 78dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * 79dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * If memory allocation fails, the callback is not called, this function 80dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * returns NULL, and errno is set to ENOMEM. 81dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 82dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid* hashmapMemoize(Hashmap* map, void* key, 83dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void* (*initialValue)(void* key, void* context), void* context); 84dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 85dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 86dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Removes an entry from the map. Returns the removed value or NULL if no 87dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * entry was present. 88dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 89dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid* hashmapRemove(Hashmap* map, void* key); 90dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 91dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 92dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Gets the number of entries in this map. 93dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 94dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectsize_t hashmapSize(Hashmap* map); 95dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 96dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 97dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Invokes the given callback on each entry in the map. Stops iterating if 98dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * the callback returns false. 99dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 100dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid hashmapForEach(Hashmap* map, 101dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project bool (*callback)(void* key, void* value, void* context), 102dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void* context); 103dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 104dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 105dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Concurrency support. 106dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 107dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 108dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 109dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Locks the hash map so only the current thread can access it. 110dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 111dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid hashmapLock(Hashmap* map); 112dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 113dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 114dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Unlocks the hash map so other threads can access it. 115dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 116dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectvoid hashmapUnlock(Hashmap* map); 117dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 118dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 119dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Key utilities. 120dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 121dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 122dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 123dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Hashes int keys. 'key' is a pointer to int. 124dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 125dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint hashmapIntHash(void* key); 126dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 127dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 128dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Compares two int keys for equality. 129dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 130dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectbool hashmapIntEquals(void* keyA, void* keyB); 131dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 132dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 133dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * For debugging. 134dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 135dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 136dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 137dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Gets current capacity. 138dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 139dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectsize_t hashmapCurrentCapacity(Hashmap* map); 140dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 141dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/** 142dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Counts the number of entry collisions. 143dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 144dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectsize_t hashmapCountCollisions(Hashmap* map); 145dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 146dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#ifdef __cplusplus 147dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 148dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#endif 149dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 150dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#endif /* __HASHMAP_H */ 151