1 /* CC0 license (public domain) - see LICENSE file for details */
2 #ifndef CCAN_INTMAP_H
3 #define CCAN_INTMAP_H
4 #include "config.h"
5 #include <ccan/tcon/tcon.h>
6 #include <ccan/typesafe_cb/typesafe_cb.h>
7 #include <inttypes.h>
8 #include <stdlib.h>
9 #include <stdbool.h>
10
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
15 #endif
16
17 /**
18 * struct intmap - representation of an integer map
19 *
20 * It's exposed here to allow you to embed it and so we can inline the
21 * trivial functions.
22 */
23 struct intmap {
24 union {
25 struct node *n;
26 intmap_index_t i;
27 } u;
28 void *v;
29 };
30
31 /**
32 * UINTMAP - declare a type-specific intmap (for unsigned integers)
33 * @membertype: type for this map's values, or void * for any pointer.
34 *
35 * You use this to create your own typed intmap for a particular
36 * (non-NULL) pointer type.
37 *
38 * Example:
39 * UINTMAP(int *) uint_intmap;
40 * uintmap_init(&uint_intmap);
41 */
42 #define UINTMAP(membertype) \
43 TCON_WRAP(struct intmap, membertype uintmap_canary)
44
45 /**
46 * SINTMAP - declare a type-specific intmap (for signed integers)
47 * @membertype: type for this map's values, or void * for any pointer.
48 *
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
51 * use "0" as a value!
52 *
53 * This is different from UINTMAP because we want it to sort into
54 * least (most negative) to largest order.
55 *
56 * Example:
57 * SINTMAP(int *) sint_intmap;
58 * sintmap_init(&sint_intmap);
59 */
60 #define SINTMAP(membertype) \
61 TCON_WRAP(struct intmap, membertype sintmap_canary)
62
63 /**
64 * uintmap_init - initialize an unsigned integer map (empty)
65 * @umap: the typed intmap to initialize.
66 *
67 * For completeness; if you've arranged for it to be NULL already you don't
68 * need this.
69 *
70 * Example:
71 * UINTMAP(int *) uint_intmap;
72 *
73 * uintmap_init(&uint_intmap);
74 */
75 #define uintmap_init(umap) intmap_init_(uintmap_unwrap_(umap))
76
77 /**
78 * sintmap_init - initialize a signed integer map (empty)
79 * @smap: the typed intmap to initialize.
80 *
81 * For completeness; if you've arranged for it to be NULL already you don't
82 * need this.
83 *
84 * Example:
85 * SINTMAP(int *) sint_intmap;
86 *
87 * sintmap_init(&sint_intmap);
88 */
89 #define sintmap_init(smap) intmap_init_(sintmap_unwrap_(smap))
90
intmap_init_(struct intmap * map)91 static inline void intmap_init_(struct intmap *map)
92 {
93 map->u.n = NULL;
94 map->v = NULL;
95 }
96
97 /**
98 * uintmap_empty - is this unsigned integer map empty?
99 * @umap: the typed intmap to check.
100 *
101 * Example:
102 * if (!uintmap_empty(&uint_intmap))
103 * abort();
104 */
105 #define uintmap_empty(umap) intmap_empty_(uintmap_unwrap_(umap))
106
107 /**
108 * sintmap_empty - is this signed integer map empty?
109 * @smap: the typed intmap to check.
110 *
111 * Example:
112 * if (!sintmap_empty(&sint_intmap))
113 * abort();
114 */
115 #define sintmap_empty(smap) intmap_empty_(sintmap_unwrap_(smap))
116
intmap_empty_(const struct intmap * map)117 static inline bool intmap_empty_(const struct intmap *map)
118 {
119 return map->v == NULL && map->u.n == NULL;
120 }
121
122 /**
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.
126 *
127 * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
128 *
129 * Example:
130 * int *val = uintmap_get(&uint_intmap, 100);
131 * if (val)
132 * printf("100 => %i\n", *val);
133 */
134 #define uintmap_get(umap, index) \
135 tcon_cast((umap), uintmap_canary, \
136 intmap_get_(uintmap_unwrap_(umap), (index)))
137
138 /**
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.
142 *
143 * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
144 *
145 * Example:
146 * int *val2 = sintmap_get(&sint_intmap, -100);
147 * if (val2)
148 * printf("-100 => %i\n", *val2);
149 */
150 #define sintmap_get(smap, index) \
151 tcon_cast((smap), sintmap_canary, \
152 intmap_get_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
153
154 void *intmap_get_(const struct intmap *map, intmap_index_t index);
155
156 /**
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.
161 *
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).
164 *
165 * Note that the value is not copied, just the pointer.
166 *
167 * Example:
168 * val = malloc(sizeof *val);
169 * *val = 17;
170 * if (!uintmap_add(&uint_intmap, 100, val))
171 * printf("100 was already in the map\n");
172 */
173 #define uintmap_add(umap, index, value) \
174 intmap_add_(uintmap_unwrap_(tcon_check((umap), uintmap_canary, \
175 (value))), \
176 (index), (void *)(value))
177
178 /**
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.
183 *
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).
186 *
187 * Note that the value is not copied, just the pointer.
188 *
189 * Example:
190 * val = malloc(sizeof *val);
191 * *val = 17;
192 * if (!sintmap_add(&sint_intmap, -100, val))
193 * printf("-100 was already in the map\n");
194 */
195 #define sintmap_add(smap, index, value) \
196 intmap_add_(sintmap_unwrap_(tcon_check((smap), sintmap_canary, \
197 (value))), \
198 SINTMAP_OFF(index), (void *)(value))
199
200 bool intmap_add_(struct intmap *map, intmap_index_t member, const void *value);
201
202 /**
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.
206 *
207 * This returns the value, or NULL if there was no value at that
208 * index.
209 *
210 * Example:
211 * if (uintmap_del(&uint_intmap, 100) == NULL)
212 * printf("100 was not in the map?\n");
213 */
214 #define uintmap_del(umap, index) \
215 tcon_cast((umap), uintmap_canary, \
216 intmap_del_(uintmap_unwrap_(umap), (index)))
217
218 /**
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.
222 *
223 * This returns the value, or NULL if there was no value at that
224 * index.
225 *
226 * Example:
227 * if (sintmap_del(&sint_intmap, -100) == NULL)
228 * printf("-100 was not in the map?\n");
229 */
230 #define sintmap_del(smap, index) \
231 tcon_cast((smap), sintmap_canary, \
232 intmap_del_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
233
234 void *intmap_del_(struct intmap *map, intmap_index_t index);
235
236 /**
237 * uintmap_clear - remove every member from an unsigned integer map.
238 * @umap: the typed intmap to clear.
239 *
240 * The map will be empty after this.
241 *
242 * Example:
243 * uintmap_clear(&uint_intmap);
244 */
245 #define uintmap_clear(umap) intmap_clear_(uintmap_unwrap_(umap))
246
247 /**
248 * sintmap_clear - remove every member from a signed integer map.
249 * @smap: the typed intmap to clear.
250 *
251 * The map will be empty after this.
252 *
253 * Example:
254 * sintmap_clear(&sint_intmap);
255 */
256 #define sintmap_clear(smap) intmap_clear_(sintmap_unwrap_(smap))
257
258 void intmap_clear_(struct intmap *map);
259
260 /**
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.
264 *
265 * Returns NULL if the map is empty, otherwise populates *@indexp and
266 * returns the lowest entry.
267 */
268 #define uintmap_first(umap, indexp) \
269 tcon_cast((umap), uintmap_canary, \
270 intmap_first_(uintmap_unwrap_(umap), (indexp)))
271
272 void *intmap_first_(const struct intmap *map, intmap_index_t *indexp);
273
274 /**
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.
278 *
279 * Returns NULL if the map is empty, otherwise populates *@indexp and
280 * returns the lowest entry.
281 */
282 #define sintmap_first(smap, indexp) \
283 tcon_cast((smap), sintmap_canary, \
284 sintmap_first_(sintmap_unwrap_(smap), (indexp)))
285
286 /**
287 * uintmap_after - get the closest following index in an unsigned intmap
288 * @umap: the typed intmap to iterate through.
289 * @indexp: the preceding index (may not exist)
290 *
291 * Returns NULL if the there is no entry > @indexp, otherwise
292 * populates *@indexp and returns the lowest entry > @indexp.
293 */
294 #define uintmap_after(umap, indexp) \
295 tcon_cast((umap), uintmap_canary, \
296 intmap_after_(uintmap_unwrap_(umap), (indexp)))
297
298 void *intmap_after_(const struct intmap *map, intmap_index_t *indexp);
299
300 /**
301 * sintmap_after - get the closest following index in a signed intmap
302 * @smap: the typed intmap to iterate through.
303 * @indexp: the preceding index (may not exist)
304 *
305 * Returns NULL if the there is no entry > @indexp, otherwise
306 * populates *@indexp and returns the lowest entry > @indexp.
307 */
308 #define sintmap_after(smap, indexp) \
309 tcon_cast((smap), sintmap_canary, \
310 sintmap_after_(sintmap_unwrap_(smap), (indexp)))
311
312 /**
313 * uintmap_before - get the closest preceding index in an unsigned intmap
314 * @umap: the typed intmap to iterate through.
315 * @indexp: the succeeding index (may not exist)
316 *
317 * Returns NULL if the there is no entry < @indexp, otherwise
318 * populates *@indexp and returns the highest entry < @indexp.
319 */
320 #define uintmap_before(umap, indexp) \
321 tcon_cast((umap), uintmap_canary, \
322 intmap_before_(uintmap_unwrap_(umap), (indexp)))
323
324 void *intmap_before_(const struct intmap *map, intmap_index_t *indexp);
325
326 /**
327 * sintmap_before - get the closest preceding index in a signed intmap
328 * @smap: the typed intmap to iterate through.
329 * @indexp: the succeeding index (may not exist)
330 *
331 * Returns NULL if the there is no entry < @indexp, otherwise
332 * populates *@indexp and returns the highest entry < @indexp.
333 */
334 #define sintmap_before(smap, indexp) \
335 tcon_cast((smap), sintmap_canary, \
336 sintmap_before_(sintmap_unwrap_(smap), (indexp)))
337
338 /**
339 * uintmap_last - get last value in an unsigned intmap
340 * @umap: the typed intmap to iterate through.
341 * @indexp: a pointer to store the index.
342 *
343 * Returns NULL if the map is empty, otherwise populates *@indexp and
344 * returns the highest entry.
345 */
346 #define uintmap_last(umap, indexp) \
347 tcon_cast((umap), uintmap_canary, \
348 intmap_last_(uintmap_unwrap_(umap), (indexp)))
349
350 void *intmap_last_(const struct intmap *map, intmap_index_t *indexp);
351
352 /**
353 * sintmap_last - get last value in a signed intmap
354 * @smap: the typed intmap to iterate through.
355 * @indexp: a pointer to store the index.
356 *
357 * Returns NULL if the map is empty, otherwise populates *@indexp and
358 * returns the highest entry.
359 */
360 #define sintmap_last(smap, indexp) \
361 tcon_cast((smap), sintmap_canary, \
362 sintmap_last_(sintmap_unwrap_(smap), (indexp)))
363
364 /**
365 * uintmap_iterate - ordered iteration over an unsigned intmap
366 * @umap: the typed intmap to iterate through.
367 * @handle: the function to call.
368 * @arg: the argument for the function (types should match).
369 *
370 * @handle's prototype should be:
371 * bool @handle(intmap_index_t index, type value, typeof(arg) arg)
372 *
373 * If @handle returns false, the iteration will stop and uintmap_iterate will
374 * return false, otherwise uintmap_iterate will return true.
375 * You should not alter the map within the @handle function!
376 *
377 * Example:
378 * typedef UINTMAP(int *) umap_intp;
379 * static bool dump_some(intmap_index_t index, int *value, int *num)
380 * {
381 * // Only dump out num nodes.
382 * if (*(num--) == 0)
383 * return false;
384 * printf("%lu=>%i\n", (unsigned long)index, *value);
385 * return true;
386 * }
387 *
388 * static void dump_map(const umap_intp *map)
389 * {
390 * int max = 100;
391 * uintmap_iterate(map, dump_some, &max);
392 * if (max < 0)
393 * printf("... (truncated to 100 entries)\n");
394 * }
395 */
396 #define uintmap_iterate(map, handle, arg) \
397 intmap_iterate_(tcon_unwrap(map), \
398 typesafe_cb_cast(bool (*)(intmap_index_t, \
399 void *, void *), \
400 bool (*)(intmap_index_t, \
401 tcon_type((map), \
402 uintmap_canary), \
403 __typeof__(arg)), (handle)), \
404 (arg), 0)
405
406 /**
407 * sintmap_iterate - ordered iteration over a signed intmap
408 * @smap: the typed intmap to iterate through.
409 * @handle: the function to call.
410 * @arg: the argument for the function (types should match).
411 *
412 * @handle's prototype should be:
413 * bool @handle(sintmap_index_t index, type value, typeof(arg) arg)
414 *
415 * If @handle returns false, the iteration will stop and sintmap_iterate will
416 * return false, otherwise sintmap_iterate will return true.
417 * You should not alter the map within the @handle function!
418 *
419 * Example:
420 * typedef SINTMAP(int *) smap_intp;
421 * static bool dump_some(sintmap_index_t index, int *value, int *num)
422 * {
423 * // Only dump out num nodes.
424 * if (*(num--) == 0)
425 * return false;
426 * printf("%li=>%i\n", (long)index, *value);
427 * return true;
428 * }
429 *
430 * static void dump_map(const smap_intp *map)
431 * {
432 * int max = 100;
433 * sintmap_iterate(map, dump_some, &max);
434 * if (max < 0)
435 * printf("... (truncated to 100 entries)\n");
436 * }
437 */
438 #define sintmap_iterate(map, handle, arg) \
439 intmap_iterate_(tcon_unwrap(map), \
440 typesafe_cb_cast(bool (*)(intmap_index_t, \
441 void *, void *), \
442 bool (*)(sintmap_index_t, \
443 tcon_type((map), \
444 sintmap_canary), \
445 __typeof__(arg)), (handle)), \
446 (arg), SINTMAP_OFFSET)
447
448 bool intmap_iterate_(const struct intmap *map,
449 bool (*handle)(intmap_index_t, void *, void *),
450 void *data,
451 intmap_index_t offset);
452
453 /* TODO: We could implement intmap_prefix. */
454
455 /* These make sure it really is a uintmap/sintmap */
456 #define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary))
457 #define sintmap_unwrap_(s) (tcon_unwrap(s) + 0*tcon_sizeof((s), sintmap_canary))
458
459 /* We have to offset indices if they're signed, so ordering works. */
460 #define SINTMAP_OFFSET ((intmap_index_t)1 << (sizeof(intmap_index_t)*8-1))
461 #define SINTMAP_OFF(index) ((intmap_index_t)(index) + SINTMAP_OFFSET)
462 #define SINTMAP_UNOFF(index) ((intmap_index_t)(index) - SINTMAP_OFFSET)
463
464 /* Due to multi-evaluation, these can't be macros */
sintmap_first_(const struct intmap * map,sintmap_index_t * indexp)465 static inline void *sintmap_first_(const struct intmap *map,
466 sintmap_index_t *indexp)
467 {
468 intmap_index_t i;
469 void *ret = intmap_first_(map, &i);
470 *indexp = SINTMAP_UNOFF(i);
471 return ret;
472
473 }
474
sintmap_after_(const struct intmap * map,sintmap_index_t * indexp)475 static inline void *sintmap_after_(const struct intmap *map,
476 sintmap_index_t *indexp)
477 {
478 intmap_index_t i = SINTMAP_OFF(*indexp);
479 void *ret = intmap_after_(map, &i);
480 *indexp = SINTMAP_UNOFF(i);
481 return ret;
482 }
483
sintmap_before_(const struct intmap * map,sintmap_index_t * indexp)484 static inline void *sintmap_before_(const struct intmap *map,
485 sintmap_index_t *indexp)
486 {
487 intmap_index_t i = SINTMAP_OFF(*indexp);
488 void *ret = intmap_before_(map, &i);
489 *indexp = SINTMAP_UNOFF(i);
490 return ret;
491 }
492
sintmap_last_(const struct intmap * map,sintmap_index_t * indexp)493 static inline void *sintmap_last_(const struct intmap *map,
494 sintmap_index_t *indexp)
495 {
496 intmap_index_t i;
497 void *ret = intmap_last_(map, &i);
498 *indexp = SINTMAP_UNOFF(i);
499 return ret;
500
501 }
502 #endif /* CCAN_INTMAP_H */
503