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
16 /* Maximum possible values of each type */
17 #define UINTMAP_NONE ((intmap_index_t)-1)
18 #define SINTMAP_NONE (((intmap_index_t)1 << (sizeof(intmap_index_t)*8))-1)
21 * struct intmap - representation of an integer map
23 * It's exposed here to allow you to embed it and so we can inline the
35 * UINTMAP - declare a type-specific intmap (for unsigned integers)
36 * @membertype: type for this map's values, or void * for any pointer.
38 * You use this to create your own typed intmap for a particular
39 * (non-NULL) pointer type.
42 * UINTMAP(int *) uint_intmap;
43 * uintmap_init(&uint_intmap);
45 #define UINTMAP(membertype) \
46 TCON_WRAP(struct intmap, membertype uintmap_canary)
49 * SINTMAP - declare a type-specific intmap (for signed integers)
50 * @membertype: type for this map's values, or void * for any pointer.
52 * You use this to create your own typed intmap for a particular type.
53 * You can use an integer type as membertype, *but* remember you can't
56 * This is different from UINTMAP because we want it to sort into
57 * least (most negative) to largest order.
60 * SINTMAP(int *) sint_intmap;
61 * sintmap_init(&sint_intmap);
63 #define SINTMAP(membertype) \
64 TCON_WRAP(struct intmap, membertype sintmap_canary)
67 * uintmap_init - initialize an unsigned integer map (empty)
68 * @umap: the typed intmap to initialize.
70 * For completeness; if you've arranged for it to be NULL already you don't
74 * UINTMAP(int *) uint_intmap;
76 * uintmap_init(&uint_intmap);
78 #define uintmap_init(umap) intmap_init_(uintmap_unwrap_(umap))
81 * sintmap_init - initialize a signed integer map (empty)
82 * @smap: the typed intmap to initialize.
84 * For completeness; if you've arranged for it to be NULL already you don't
88 * SINTMAP(int *) sint_intmap;
90 * sintmap_init(&sint_intmap);
92 #define sintmap_init(smap) intmap_init_(sintmap_unwrap_(smap))
94 static inline void intmap_init_(struct intmap *map)
101 * uintmap_empty - is this unsigned integer map empty?
102 * @umap: the typed intmap to check.
105 * if (!uintmap_empty(&uint_intmap))
108 #define uintmap_empty(umap) intmap_empty_(uintmap_unwrap_(umap))
111 * sintmap_empty - is this signed integer map empty?
112 * @smap: the typed intmap to check.
115 * if (!sintmap_empty(&sint_intmap))
118 #define sintmap_empty(smap) intmap_empty_(sintmap_unwrap_(smap))
120 static inline bool intmap_empty_(const struct intmap *map)
122 return map->v == NULL && map->u.n == NULL;
126 * uintmap_get - get a value from an unsigned integer map
127 * @umap: the typed intmap to search.
128 * @index: the unsigned index to search for.
130 * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
133 * int *val = uintmap_get(&uint_intmap, 100);
135 * printf("100 => %i\n", *val);
137 #define uintmap_get(umap, index) \
138 tcon_cast((umap), uintmap_canary, \
139 intmap_get_(uintmap_unwrap_(umap), (index)))
142 * sintmap_get - get a value from a signed integer map
143 * @smap: the typed intmap to search.
144 * @index: the signed index to search for.
146 * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
149 * int *val2 = sintmap_get(&sint_intmap, -100);
151 * printf("-100 => %i\n", *val2);
153 #define sintmap_get(smap, index) \
154 tcon_cast((smap), sintmap_canary, \
155 intmap_get_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
157 void *intmap_get_(const struct intmap *map, intmap_index_t index);
160 * uintmap_add - place a member in an unsigned integer map.
161 * @umap: the typed intmap to add to.
162 * @index: the unsigned index to place in the map.
163 * @value: the (non-NULL) value.
165 * This returns false if we run out of memory (errno = ENOMEM), or
166 * (more normally) if that index already appears in the map (EEXIST).
168 * Note that the value is not copied, just the pointer.
171 * val = malloc(sizeof *val);
173 * if (!uintmap_add(&uint_intmap, 100, val))
174 * printf("100 was already in the map\n");
176 #define uintmap_add(umap, index, value) \
177 intmap_add_(uintmap_unwrap_(tcon_check((umap), uintmap_canary, \
179 (index), (void *)(value))
182 * sintmap_add - place a member in a signed integer map.
183 * @smap: the typed intmap to add to.
184 * @index: the signed index to place in the map.
185 * @value: the (non-NULL) value.
187 * This returns false if we run out of memory (errno = ENOMEM), or
188 * (more normally) if that index already appears in the map (EEXIST).
190 * Note that the value is not copied, just the pointer.
193 * val = malloc(sizeof *val);
195 * if (!sintmap_add(&sint_intmap, -100, val))
196 * printf("-100 was already in the map\n");
198 #define sintmap_add(smap, index, value) \
199 intmap_add_(sintmap_unwrap_(tcon_check((smap), sintmap_canary, \
201 SINTMAP_OFF(index), (void *)(value))
203 bool intmap_add_(struct intmap *map, intmap_index_t member, const void *value);
206 * uintmap_del - remove a member from an unsigned integer map.
207 * @umap: the typed intmap to delete from.
208 * @index: the unsigned index to remove from the map.
210 * This returns the value, or NULL if there was no value at that
214 * if (uintmap_del(&uint_intmap, 100) == NULL)
215 * printf("100 was not in the map?\n");
217 #define uintmap_del(umap, index) \
218 tcon_cast((umap), uintmap_canary, \
219 intmap_del_(uintmap_unwrap_(umap), (index)))
222 * sintmap_del - remove a member from a signed integer map.
223 * @smap: the typed intmap to delete from.
224 * @index: the signed index to remove from the map.
226 * This returns the value, or NULL if there was no value at that
230 * if (sintmap_del(&sint_intmap, -100) == NULL)
231 * printf("-100 was not in the map?\n");
233 #define sintmap_del(smap, index) \
234 tcon_cast((smap), sintmap_canary, \
235 intmap_del_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
237 void *intmap_del_(struct intmap *map, intmap_index_t index);
240 * uintmap_clear - remove every member from an unsigned integer map.
241 * @umap: the typed intmap to clear.
243 * The map will be empty after this.
246 * uintmap_clear(&uint_intmap);
248 #define uintmap_clear(umap) intmap_clear_(uintmap_unwrap_(umap))
251 * sintmap_clear - remove every member from a signed integer map.
252 * @smap: the typed intmap to clear.
254 * The map will be empty after this.
257 * sintmap_clear(&sint_intmap);
259 #define sintmap_clear(smap) intmap_clear_(sintmap_unwrap_(smap))
261 void intmap_clear_(struct intmap *map);
264 * uintmap_first - get first index in an unsigned intmap
265 * @umap: the typed intmap to iterate through.
267 * Returns UINTMAP_NONE and sets errno to ENOENT if it's empty.
268 * Otherwise errno is set to 0.
270 #define uintmap_first(umap) \
271 intmap_first_(uintmap_unwrap_(umap))
274 * sintmap_first - get first index in a signed intmap
275 * @smap: the typed intmap to iterate through.
277 * Returns SINTMAP_NONE and sets errno to ENOENT if it's
278 * empty. Otherwise errno is set to 0.
280 #define sintmap_first(smap) \
281 SINTMAP_UNOFF(intmap_first_(sintmap_unwrap_(smap)))
283 intmap_index_t intmap_first_(const struct intmap *map);
286 * uintmap_after - get the closest following index in an unsigned intmap
287 * @umap: the typed intmap to iterate through.
288 * @i: the preceeding index (may not exist)
290 * Returns UINTMAP_NONE and sets errno to ENOENT if there are no
291 * others. Otherwise errno is set to 0.
293 #define uintmap_after(umap, i) \
294 intmap_after_(uintmap_unwrap_(umap), (i))
297 * sintmap_after - get the closest following index in a signed intmap
298 * @smap: the typed intmap to iterate through.
299 * @i: the preceeding index.
301 * Returns SINTMAP_NONE and sets errno to ENOENT if there are no
302 * others. Otherwise errno is set to 0.
304 #define sintmap_after(smap, i) \
305 SINTMAP_UNOFF(intmap_after_(sintmap_unwrap_(smap), SINTMAP_OFF((i))))
307 intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t i);
309 /* TODO: We could implement intmap_prefix, intmap_iterate... */
311 /* These make sure it really is a uintmap/sintmap */
312 #define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary))
313 #define sintmap_unwrap_(s) (tcon_unwrap(s) + 0*tcon_sizeof((s), sintmap_canary))
315 /* We have to offset indices if they're signed, so ordering works. */
316 #define SINTMAP_OFFSET ((intmap_index_t)1 << (sizeof(intmap_index_t)*8-1))
317 #define SINTMAP_OFF(index) ((intmap_index_t)(index) + SINTMAP_OFFSET)
318 #define SINTMAP_UNOFF(index) ((intmap_index_t)(index) - SINTMAP_OFFSET)
320 #endif /* CCAN_INTMAP_H */