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