1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
|
/* SPDX-License-Identifier: LGPL-2.1 */
/**
* hmap.h - a simple generic hashmap. v2.0.0
*
* Copyright (c) 2022-2023 - Yaroslav de la Peña Smirnov
*
* Documentation
* =============
*
* In order to use this hashmap, you need to incapsulate struct hmap_entry
* inside your own structure. For example::
*
* struct my_struct {
* char *key;
* uint64_t data;
* struct hmap_entry entry;
* };
*
* Then you can insert any instance of such struct into the hashmap by calling
* the corresponding method and passing it the pointer to @entry.
*
* For search and removal operations you just need to fill your structure with
* your key. The hmap_cmp_fn and hmap_hash_fn functions you provided will be
* called by hmap in order to perform the needed operations.
*
* When you get a hmap_entry pointer from hmap's API, you can get your
* containing structure with the help of the hmap_item macro, for example::
*
* struct hmap_entry *e = hmap_get(map, key);
* struct my_struct *my = hmap_item(e, struct my_struct, entry);
*
*/
#ifndef HMAP_H
#define HMAP_H
#include "../utils.h"
#include <inttypes.h>
#include <stdbool.h>
#include <sys/types.h>
#ifndef HMAP_INIT_CAP
#define HMAP_INIT_CAP 64
#endif
/**
* Structures
* ==========
*/
/**
* struct hmap - opaque structure for generic hashmap.
*/
struct hmap;
/**
* struct hmap_entry - the base class for a hashmap entry.
* @next: linked list in case of collisions.
* @hash: the hash value of the entry key.
*
* This structure should only be manipulated using the methods below. The @hash
* member should be filled by the hmap_hash_fn function provided to hmap_new().
*/
struct hmap_entry {
struct hmap_entry *next;
size_t hash;
};
/**
* struct hmap_iter - iterator over hmap entries.
* @map: hashmap.
* @next: next item to be returned.
* @cursor: current position in buckets table.
*
* If you want to remove entries while iterating, be sure to change the dynamic
* resizing setting to on = false with hmap_dynamic_get().
*/
struct hmap_iter {
struct hmap *map;
struct hmap_entry *next;
size_t cursor;
};
/**
* Typedefs
* ========
*/
typedef bool (*hmap_cmp_fn)(const struct hmap_entry *ent,
const struct hmap_entry *key);
typedef void (*hmap_hash_fn)(struct hmap_entry *ent);
/**
* Methods
* =======
*/
/**
* hmap_new_with() - allocate new hashmap with given parameters.
* @cmp_fn: key comparison function.
* @hash_fn: key hashing function.
* @cap: initial hashmap capacity.
* @dynamic: whether the hashmap should dynamically grow/shrink based on load
* factor.
*
* Return: pointer to hmap object.
*/
struct hmap *hmap_new_with(hmap_cmp_fn cmp_fn, hmap_hash_fn hash_fn, size_t cap,
bool dynamic);
/**
* hmap_new - allocate new hashmap with default parameters.
* @cmp_fn: key comparison function.
* @hash_fn: key hashing function.
*
* Return: pointer to hmap object.
*/
#define hmap_new(cmp_fn, hash_fn) \
hmap_new_with(cmp_fn, hash_fn, HMAP_INIT_CAP, true)
/**
* hmap_free() - free all resources used by @map.
* @map: hashmap.
*
* This function does not release or free any resources associated with any
* entries stored in the hashmap. It is the responsibility of the caller to free
* any such resources.
*/
void hmap_free(struct hmap *map);
/**
* hmap_item - get the pointer to the containing structure for this entry.
* @entry: struct hmap_entry pointer.
* @type: containing struct.
* @member: the member in the struct that holds hmap_entry.
*/
#define hmap_item(entry, type, member) container_of(entry, type, member)
/**
* hmap_add() - add entry to @map.
* @map: hashmap.
* @ent: entry to add.
*
* If there's already an entry with the same key, it wil still add it and hold
* both.
*/
void hmap_add(struct hmap *map, struct hmap_entry *ent);
/**
* hmap_get() - get entry with @key from @map.
* @map: hashmap.
* @key: hmap_entry object that holds the key.
*
* In order to pass the key, you just need to fill what is needed by your
* hashing and comparison functions; you could even use a separate structure
* that just holds the key, if you use the appropriate logic in your functions.
*
* If there are entries with duplicate keys, it will get the first it finds. If
* your want to get the next duplicate-key entry use hmap_get_next_dup().
*
* Return: pointer to entry; NULL if no entry with such key.
*/
struct hmap_entry *hmap_get(struct hmap *map, struct hmap_entry *key);
/**
* hmap_get_next_dup() - get the next entry with the same key as @ent.
* @map: hashmap.
* @ent: entry with duplicate key.
*
* Return: pointer to entry; NULL if no more entries with same key.
*/
struct hmap_entry *hmap_get_next_dup(struct hmap *map, struct hmap_entry *ent);
/**
* hmap_remove() - remove entry with @key from @map.
* @map: hashmap.
* @key: hmap_entry object that holds the key.
*
* If there are entries with duplicates keys, it will remove the first it finds.
*
* Return: pointer to removed entry; NULL if no entry with such key.
*/
struct hmap_entry *hmap_remove(struct hmap *map, struct hmap_entry *key);
/**
* hmap_entry_cnt() - get the current number of entries in @map.
* @map: hashmap.
*
* Return: number of entries held by @map.
*/
size_t hmap_entry_cnt(struct hmap *map);
/**
* hmap_dynamic_set() - enable/disable hashmap resizing.
* @map: hashmap.
* @on: whether to turn on/off.
*/
void hmap_dynamic_set(struct hmap *map, bool on);
/**
* hmap_dynamic_get() - get current hashmap resizing setting.
* @map: hashmap.
*
* Return: current dynamic resizing setting.
*/
bool hmap_dynamic_get(struct hmap *map);
/**
* hmap_cur_cap() - get the current capacity of @map.
* @map: hashmap.
*
* Return: current @map capacity.
*/
size_t hmap_cur_cap(struct hmap *map);
/**
* hmap_iter_init() - initialize and reset hmap iterator.
* @iter: pointer to hmap_iter object.
* @map: hashmap to iterate over.
*/
void hmap_iter_init(struct hmap_iter *iter, struct hmap *map);
/**
* hmap_iter_next() - get the next entry.
* @iter: iterator.
*
* Return: pointer to entry; NULL if no more entries are left.
*/
struct hmap_entry *hmap_iter_next(struct hmap_iter *iter);
/**
* hmap_iter_foreach - loop to iterate over every entry.
* @iter: pointer to iterator.
* @entry: hmap_entry pointer to hold the next entry.
*/
#define hmap_iter_foreach(iter, entry) \
for (entry = hmap_iter_next((iter)); entry; entry = hmap_iter_next((iter)))
#endif /* HMAP_H */
|
