1 /* CC0 license (public domain) - see LICENSE file for details */
5 #include <ccan/tcon/tcon.h>
6 #include <ccan/typesafe_cb/typesafe_cb.h>
11 /* Must be an unsigned type. */
12 #ifndef intmap_index_t
13 #define intmap_index_t uint64_t
14 #define sintmap_index_t int64_t
18 * struct intmap - representation of an integer map
20 * It's exposed here to allow you to embed it and so we can inline the
32 * UINTMAP - declare a type-specific intmap (for unsigned integers)
33 * @membertype: type for this map's values, or void * for any pointer.
35 * You use this to create your own typed intmap for a particular
36 * (non-NULL) pointer type.
39 * UINTMAP(int *) uint_intmap;
40 * uintmap_init(&uint_intmap);
42 #define UINTMAP(membertype) \
43 TCON_WRAP(struct intmap, membertype uintmap_canary)
46 * SINTMAP - declare a type-specific intmap (for signed integers)
47 * @membertype: type for this map's values, or void * for any pointer.
49 * You use this to create your own typed intmap for a particular type.
50 * You can use an integer type as membertype, *but* remember you can't
53 * This is different from UINTMAP because we want it to sort into
54 * least (most negative) to largest order.
57 * SINTMAP(int *) sint_intmap;
58 * sintmap_init(&sint_intmap);
60 #define SINTMAP(membertype) \
61 TCON_WRAP(struct intmap, membertype sintmap_canary)
64 * uintmap_init - initialize an unsigned integer map (empty)
65 * @umap: the typed intmap to initialize.
67 * For completeness; if you've arranged for it to be NULL already you don't
71 * UINTMAP(int *) uint_intmap;
73 * uintmap_init(&uint_intmap);
75 #define uintmap_init(umap) intmap_init_(uintmap_unwrap_(umap))
78 * sintmap_init - initialize a signed integer map (empty)
79 * @smap: the typed intmap to initialize.
81 * For completeness; if you've arranged for it to be NULL already you don't
85 * SINTMAP(int *) sint_intmap;
87 * sintmap_init(&sint_intmap);
89 #define sintmap_init(smap) intmap_init_(sintmap_unwrap_(smap))
91 static inline void intmap_init_(struct intmap *map)
98 * uintmap_empty - is this unsigned integer map empty?
99 * @umap: the typed intmap to check.
102 * if (!uintmap_empty(&uint_intmap))
105 #define uintmap_empty(umap) intmap_empty_(uintmap_unwrap_(umap))
108 * sintmap_empty - is this signed integer map empty?
109 * @smap: the typed intmap to check.
112 * if (!sintmap_empty(&sint_intmap))
115 #define sintmap_empty(smap) intmap_empty_(sintmap_unwrap_(smap))
117 static inline bool intmap_empty_(const struct intmap *map)
119 return map->v == NULL && map->u.n == NULL;
123 * uintmap_get - get a value from an unsigned integer map
124 * @umap: the typed intmap to search.
125 * @index: the unsigned index to search for.
127 * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
130 * int *val = uintmap_get(&uint_intmap, 100);
132 * printf("100 => %i\n", *val);
134 #define uintmap_get(umap, index) \
135 tcon_cast((umap), uintmap_canary, \
136 intmap_get_(uintmap_unwrap_(umap), (index)))
139 * sintmap_get - get a value from a signed integer map
140 * @smap: the typed intmap to search.
141 * @index: the signed index to search for.
143 * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
146 * int *val2 = sintmap_get(&sint_intmap, -100);
148 * printf("-100 => %i\n", *val2);
150 #define sintmap_get(smap, index) \
151 tcon_cast((smap), sintmap_canary, \
152 intmap_get_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
154 void *intmap_get_(const struct intmap *map, intmap_index_t index);
157 * uintmap_add - place a member in an unsigned integer map.
158 * @umap: the typed intmap to add to.
159 * @index: the unsigned index to place in the map.
160 * @value: the (non-NULL) value.
162 * This returns false if we run out of memory (errno = ENOMEM), or
163 * (more normally) if that index already appears in the map (EEXIST).
165 * Note that the value is not copied, just the pointer.
168 * val = malloc(sizeof *val);
170 * if (!uintmap_add(&uint_intmap, 100, val))
171 * printf("100 was already in the map\n");
173 #define uintmap_add(umap, index, value) \
174 intmap_add_(uintmap_unwrap_(tcon_check((umap), uintmap_canary, \
176 (index), (void *)(value))
179 * sintmap_add - place a member in a signed integer map.
180 * @smap: the typed intmap to add to.
181 * @index: the signed index to place in the map.
182 * @value: the (non-NULL) value.
184 * This returns false if we run out of memory (errno = ENOMEM), or
185 * (more normally) if that index already appears in the map (EEXIST).
187 * Note that the value is not copied, just the pointer.
190 * val = malloc(sizeof *val);
192 * if (!sintmap_add(&sint_intmap, -100, val))
193 * printf("-100 was already in the map\n");
195 #define sintmap_add(smap, index, value) \
196 intmap_add_(sintmap_unwrap_(tcon_check((smap), sintmap_canary, \
198 SINTMAP_OFF(index), (void *)(value))
200 bool intmap_add_(struct intmap *map, intmap_index_t member, const void *value);
203 * uintmap_del - remove a member from an unsigned integer map.
204 * @umap: the typed intmap to delete from.
205 * @index: the unsigned index to remove from the map.
207 * This returns the value, or NULL if there was no value at that
211 * if (uintmap_del(&uint_intmap, 100) == NULL)
212 * printf("100 was not in the map?\n");
214 #define uintmap_del(umap, index) \
215 tcon_cast((umap), uintmap_canary, \
216 intmap_del_(uintmap_unwrap_(umap), (index)))
219 * sintmap_del - remove a member from a signed integer map.
220 * @smap: the typed intmap to delete from.
221 * @index: the signed index to remove from the map.
223 * This returns the value, or NULL if there was no value at that
227 * if (sintmap_del(&sint_intmap, -100) == NULL)
228 * printf("-100 was not in the map?\n");
230 #define sintmap_del(smap, index) \
231 tcon_cast((smap), sintmap_canary, \
232 intmap_del_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
234 void *intmap_del_(struct intmap *map, intmap_index_t index);
237 * uintmap_clear - remove every member from an unsigned integer map.
238 * @umap: the typed intmap to clear.
240 * The map will be empty after this.
243 * uintmap_clear(&uint_intmap);
245 #define uintmap_clear(umap) intmap_clear_(uintmap_unwrap_(umap))
248 * sintmap_clear - remove every member from a signed integer map.
249 * @smap: the typed intmap to clear.
251 * The map will be empty after this.
254 * sintmap_clear(&sint_intmap);
256 #define sintmap_clear(smap) intmap_clear_(sintmap_unwrap_(smap))
258 void intmap_clear_(struct intmap *map);
261 * uintmap_first - get first value in an unsigned intmap
262 * @umap: the typed intmap to iterate through.
263 * @indexp: a pointer to store the index.
265 * Returns NULL if the map is empty, otherwise populates *@indexp and
266 * returns the lowest entry.
268 #define uintmap_first(umap, indexp) \
269 tcon_cast((umap), uintmap_canary, \
270 intmap_first_(uintmap_unwrap_(umap), (indexp)))
272 void *intmap_first_(const struct intmap *map, intmap_index_t *indexp);
275 * sintmap_first - get first value in a signed intmap
276 * @smap: the typed intmap to iterate through.
277 * @indexp: a pointer to store the index.
279 * Returns NULL if the map is empty, otherwise populates *@indexp and
280 * returns the lowest entry.
282 #define sintmap_first(smap, indexp) \
283 tcon_cast((smap), sintmap_canary, \
284 sintmap_first_(sintmap_unwrap_(smap), (indexp)))
287 * uintmap_after - get the closest following index in an unsigned intmap
288 * @umap: the typed intmap to iterate through.
289 * @indexp: the preceeding index (may not exist)
291 * Returns NULL if the there is no entry > @indexp, otherwise
292 * populates *@indexp and returns the lowest entry > @indexp.
294 #define uintmap_after(umap, indexp) \
295 tcon_cast((umap), uintmap_canary, \
296 intmap_after_(uintmap_unwrap_(umap), (indexp)))
298 void *intmap_after_(const struct intmap *map, intmap_index_t *indexp);
301 * sintmap_after - get the closest following index in a signed intmap
302 * @smap: the typed intmap to iterate through.
303 * @indexp: the preceeding index (may not exist)
305 * Returns NULL if the there is no entry > @indexp, otherwise
306 * populates *@indexp and returns the lowest entry > @indexp.
308 #define sintmap_after(smap, indexp) \
309 tcon_cast((smap), sintmap_canary, \
310 sintmap_after_(sintmap_unwrap_(smap), (indexp)))
312 /* TODO: We could implement intmap_prefix. */
314 /* These make sure it really is a uintmap/sintmap */
315 #define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary))
316 #define sintmap_unwrap_(s) (tcon_unwrap(s) + 0*tcon_sizeof((s), sintmap_canary))
318 /* We have to offset indices if they're signed, so ordering works. */
319 #define SINTMAP_OFFSET ((intmap_index_t)1 << (sizeof(intmap_index_t)*8-1))
320 #define SINTMAP_OFF(index) ((intmap_index_t)(index) + SINTMAP_OFFSET)
321 #define SINTMAP_UNOFF(index) ((intmap_index_t)(index) - SINTMAP_OFFSET)
323 /* Due to multi-evaluation, these can't be macros */
324 static inline void *sintmap_first_(const struct intmap *map,
325 sintmap_index_t *indexp)
328 void *ret = intmap_first_(map, &i);
329 *indexp = SINTMAP_UNOFF(i);
334 static inline void *sintmap_after_(const struct intmap *map,
335 sintmap_index_t *indexp)
337 intmap_index_t i = SINTMAP_OFF(*indexp);
338 void *ret = intmap_after_(map, &i);
339 *indexp = SINTMAP_UNOFF(i);
342 #endif /* CCAN_INTMAP_H */