Commit | Line | Data |
---|---|---|
1e494cf4 JB |
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 | |
28 | extern "C" { | |
29 | #endif | |
30 | ||
31 | /** A hash map. */ | |
32 | typedef 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 | */ | |
41 | Hashmap* 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 | */ | |
47 | void hashmapFree(Hashmap* map); | |
48 | ||
49 | /** | |
50 | * Hashes the memory pointed to by key with the given size. Useful for | |
51 | * implementing hash functions. | |
52 | */ | |
53 | int 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 | */ | |
62 | void* 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 | */ | |
68 | void* hashmapGet(Hashmap* map, void* key); | |
69 | ||
70 | /** | |
71 | * Returns true if the map contains an entry for the given key. | |
72 | */ | |
73 | bool 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 | */ | |
82 | void* 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 | */ | |
89 | void* hashmapRemove(Hashmap* map, void* key); | |
90 | ||
91 | /** | |
92 | * Gets the number of entries in this map. | |
93 | */ | |
94 | size_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 | */ | |
100 | void 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 | */ | |
111 | void hashmapLock(Hashmap* map); | |
112 | ||
113 | /** | |
114 | * Unlocks the hash map so other threads can access it. | |
115 | */ | |
116 | void hashmapUnlock(Hashmap* map); | |
117 | ||
118 | /** | |
119 | * Key utilities. | |
120 | */ | |
121 | ||
122 | /** | |
123 | * Hashes int keys. 'key' is a pointer to int. | |
124 | */ | |
125 | int hashmapIntHash(void* key); | |
126 | ||
127 | /** | |
128 | * Compares two int keys for equality. | |
129 | */ | |
130 | bool hashmapIntEquals(void* keyA, void* keyB); | |
131 | ||
132 | /** | |
133 | * For debugging. | |
134 | */ | |
135 | ||
136 | /** | |
137 | * Gets current capacity. | |
138 | */ | |
139 | size_t hashmapCurrentCapacity(Hashmap* map); | |
140 | ||
141 | /** | |
142 | * Counts the number of entry collisions. | |
143 | */ | |
144 | size_t hashmapCountCollisions(Hashmap* map); | |
145 | ||
146 | #ifdef __cplusplus | |
147 | } | |
148 | #endif | |
149 | ||
150 | #endif /* __HASHMAP_H */ |