1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
4 #include <ccan/compiler/compiler.h>
5 #include <ccan/tcon/tcon.h>
11 #ifdef CCAN_JMAP_DEBUG
16 * struct map - private definition of a jmap.
18 * It's exposed here so you can put it in your structures and so we can
19 * supply inline functions.
27 /* Used if CCAN_JMAP_DEBUG */
28 unsigned long *acc_value;
29 unsigned long acc_index;
34 * JMAP_MEMBERS - declare members for a type-specific jmap.
35 * @itype: index type for this map, or void * for any pointer.
36 * @ctype: contents type for this map, or void * for any pointer.
39 * struct jmap_long_to_charp {
40 * JMAP_MEMBERS(long, char *);
43 #define JMAP_MEMBERS(itype, ctype) \
44 TCON_WRAP(struct jmap, itype icanary; ctype ccanary) jmap_
47 * jmap_new - create a new, empty jmap.
53 * struct jmap_long_to_charp {
54 * JMAP_MEMBERS(long, char *);
57 * struct jmap_long_to_charp *map = jmap_new(struct jmap_long_to_charp);
59 * errx(1, "Failed to allocate jmap");
61 #define jmap_new(type) ((type *)jmap_new_(sizeof(type)))
64 * jmap_raw_ - unwrap the typed map (no type checking)
65 * @map: the typed jmap
67 #define jmap_raw_(map) tcon_unwrap(&(map)->jmap_)
70 * jmap_free - destroy a jmap.
71 * @map: the map returned from jmap_new.
76 #define jmap_free(map) jmap_free_(jmap_raw_(map))
79 * jmap_error - test for an error in the a previous jmap_ operation.
80 * @map: the map to test.
82 * Under normal circumstances, return NULL to indicate no error has occurred.
83 * Otherwise, it will return a string containing the error. This string
84 * can only be freed by jmap_free() on the map.
86 * Other than out-of-memory, errors are caused by memory corruption or
92 * errstr = jmap_error(map);
94 * errx(1, "Woah, error on newly created map?! %s", errstr);
96 #define jmap_error(map) jmap_error_(jmap_raw_(map))
99 * jmap_rawi - unwrap the typed map and check the index type
100 * @map: the typed jmap
101 * @expr: the expression to check the index type against (not evaluated)
103 * This macro usually causes the compiler to emit a warning if the
104 * variable is of an unexpected type. It is used internally where we
105 * need to access the raw underlying jmap.
107 #define jmap_rawi(map, expr) \
108 tcon_unwrap(tcon_check(&(map)->jmap_, icanary, (expr)))
111 * jmap_rawc - unwrap the typed map and check the contents type
112 * @map: the typed jmap
113 * @expr: the expression to check the content type against (not evaluated)
115 * This macro usually causes the compiler to emit a warning if the
116 * variable is of an unexpected type. It is used internally where we
117 * need to access the raw underlying jmap.
119 #define jmap_rawc(map, expr) \
120 tcon_unwrap(tcon_check(&(map)->jmap_, ccanary, (expr)))
123 * jmap_rawci - unwrap the typed map and check the index and contents types
124 * @map: the typed jmap
125 * @iexpr: the expression to check the index type against (not evaluated)
126 * @cexpr: the expression to check the contents type against (not evaluated)
128 * This macro usually causes the compiler to emit a warning if the
129 * variable is of an unexpected type. It is used internally where we
130 * need to access the raw underlying jmap.
132 #define jmap_rawci(map, iexpr, cexpr) \
133 tcon_unwrap(tcon_check(tcon_check(&(map)->jmap_,\
134 ccanary, (cexpr)), icanary, (iexpr)))
137 * jmap_add - add or replace a value for a given index in the map.
138 * @map: map from jmap_new
139 * @index: the index to map
140 * @value: the value to associate with the index
142 * Adds index into the map; replaces value if it's already there.
143 * Returns false on error (out of memory).
146 * if (!jmap_add(map, 0, "hello"))
147 * err(1, "jmap_add failed!");
149 #define jmap_add(map, index, value) \
150 jmap_add_(jmap_rawci((map), (index), (value)), \
151 (unsigned long)(index), (unsigned long)value)
154 * jmap_set - change a value for an existing index in the map.
155 * @map: map from jmap_new
156 * @index: the index to map
157 * @value: the value to associate with the index
159 * This sets the value of an index if it already exists, and return true,
160 * otherwise returns false and does nothing.
163 * if (!jmap_set(map, 0, "goodbye"))
164 * err(1, "jmap_set: index 0 not found");
166 #define jmap_set(map, index, value) \
167 jmap_set_(jmap_rawci((map), (index), (value)), \
168 (unsigned long)(index), (unsigned long)value)
171 * jmap_del - remove an index from the map.
172 * @map: map from jmap_new
173 * @index: the index to map
176 * if (!jmap_del(map, 0))
177 * err(1, "jmap_del failed!");
179 #define jmap_del(map, index) \
180 jmap_del_(jmap_rawi((map), (index)), (unsigned long)(index))
183 * jmap_test - test if a given index is defined.
184 * @map: map from jmap_new
185 * @index: the index to find
188 * jmap_add(map, 1, "hello");
189 * assert(jmap_test(map, 1));
191 #define jmap_test(map, index) \
192 jmap_test_(jmap_rawi((map), (index)), (unsigned long)(index))
195 * jmap_get - get a value for a given index.
196 * @map: map from jmap_new
197 * @index: the index to find
199 * Returns 0 if !jmap_test(map, index).
202 * const char *str = "hello";
203 * jmap_add(map, 2, str);
204 * assert(jmap_get(map, 0) == str);
209 #define jmap_get(map, index) \
210 tcon_cast(&(map)->jmap_, ccanary, \
211 jmap_get_(jmap_rawi((map), (index)), (unsigned long)(index)))
214 * jmap_count - get population of the map.
215 * @map: map from jmap_new
218 * assert(jmap_count(map) < 1000);
220 #define jmap_count(map) \
221 jmap_popcount_(jmap_raw_(map), 0, -1UL)
224 * jmap_popcount - get population of (some part of) the map.
225 * @map: map from jmap_new
226 * @start: first index to count
227 * @end_incl: last index to count (use -1 for end).
230 * assert(jmap_popcount(map, 0, 1000) <= jmap_popcount(map, 0, 2000));
232 #define jmap_popcount(map, start, end_incl) \
233 jmap_popcount_(jmap_rawi((map), (start) ? (start) : (end_incl)), \
234 (unsigned long)(start), (unsigned long)(end_incl))
237 * jmap_nth - return the index of the nth value in the map.
238 * @map: map from jmap_new
239 * @n: which index we are interested in (0-based)
240 * @invalid: what to return if n >= map population
242 * This normally returns the nth index in the map, and often there is a
243 * convenient known-invalid value (ie. something which is never in the
244 * map). Otherwise you can use jmap_nthval().
247 * unsigned long i, index;
249 * // We know 0 isn't in map.
250 * assert(!jmap_test(map, 0));
251 * for (i = 0; (index = jmap_nth(map, i, 0)) != 0; i++) {
252 * assert(jmap_popcount(map, 0, index) == i);
253 * printf("Index %lu = %lu\n", i, index);
259 #define jmap_nth(map, n, invalid) \
260 tcon_cast(&(map)->jmap_, icanary, \
261 jmap_nth_(jmap_rawi((map), (invalid)), \
262 (n), (unsigned long)(invalid)))
265 * jmap_first - return the first index in the map (must not contain 0).
266 * @map: map from jmap_new
268 * This is equivalent to jmap_nth(map, 0, 0).
271 * assert(!jmap_test(map, 0));
272 * printf("Map indices (increasing order):");
273 * for (i = jmap_first(map); i; i = jmap_next(map, i))
280 #define jmap_first(map) \
281 tcon_cast(&(map)->jmap_, icanary, jmap_first_(jmap_raw_(map)))
284 * jmap_next - return the next index in the map.
285 * @map: map from jmap_new
286 * @prev: previous index
288 * This is usually used to find an adjacent index after jmap_first.
292 #define jmap_next(map, prev) \
293 tcon_cast(&(map)->jmap_, icanary, jmap_next_(jmap_rawi((map), (prev)), \
294 (unsigned long)(prev)))
297 * jmap_last - return the last index in the map.
298 * @map: map from jmap_new
300 * Returns 0 if map is empty.
303 * assert(!jmap_test(map, 0));
304 * printf("Map indices (increasing order):");
305 * for (i = jmap_last(map); i; i = jmap_prev(map, i))
311 #define jmap_last(map) \
312 tcon_cast(&(map)->jmap_, icanary, jmap_last_(jmap_raw_(map)))
315 * jmap_prev - return the previous index in the map (must not contain 0)
316 * @map: map from jmap_new
317 * @prev: previous index
319 * This is usually used to find an prior adjacent index after jmap_last.
320 * Returns 0 if no previous indices in map.
325 #define jmap_prev(map, prev) \
326 tcon_cast(&(map)->jmap_, icanary, \
327 jmap_prev_(jmap_rawi((map), (prev)), (prev)))
330 * jmap_getval - access a value in-place for a given index.
331 * @map: map from jmap_new
332 * @index: the index to find
334 * Returns a pointer into the map, or NULL if the index isn't in the
335 * map. Like the other val functions (jmap_nthval, jmap_firstval
336 * etc), this pointer cannot be used after a jmap_add or jmap_del
337 * call, and you must call jmap_putval() once you are finished.
339 * Unless you define NDEBUG, jmap_add and kmap_del will check that you
340 * have called jmap_putval().
344 * jmap_add(map, 0, "hello");
345 * p = jmap_getval(map, 0);
347 * errx(1, "Could not find 0 in map!");
348 * if (strcmp(*p, "hello") != 0)
349 * errx(1, "Value in map was not correct?!");
350 * *p = (char *)"goodbye";
351 * jmap_putval(map, &p);
352 * // Accessing p now would probably crash.
355 * jmap_putval(), jmap_firstval()
357 #define jmap_getval(map, index) \
358 tcon_cast_ptr(&(map)->jmap_, ccanary, \
359 jmap_getval_(jmap_rawi((map), (index)), \
360 (unsigned long)(index)))
363 * jmap_putval - revoke access to a value.
364 * @map: map from jmap_new
365 * @p: the pointer to a pointer to the value
367 * @p is a pointer to the (successful) value retuned from one of the
368 * jmap_*val functions (listed below). After this, it will be invalid.
370 * Unless NDEBUG is defined, this will actually alter the value of p
371 * to point to garbage to help avoid accidental use.
374 * jmap_getval(), jmap_nthval(), jmap_firstval(), jmap_nextval(),
375 * jmap_lastval(), jmap_prevval().
377 #define jmap_putval(map, p) \
378 jmap_putval_(jmap_rawc((map), **(p)), (p))
381 * jmap_nthval - access the value of the nth value in the map.
382 * @map: map from jmap_new
383 * @n: which index we are interested in (0-based)
384 * @index: set to the nth index in the map.
386 * This returns a pointer to the value at the nth index in the map,
387 * or NULL if there are n is greater than the population of the map.
388 * You must use jmap_putval() on the pointer once you are done with it.
393 * // We know 0 isn't in map.
394 * assert(!jmap_test(map, 0));
395 * for (i = 0; (val = jmap_nthval(map, i, &index)) != NULL; i++) {
396 * assert(jmap_popcount(map, 0, index) == i);
397 * printf("Index %lu = %lu, value = %s\n", i, index, *val);
398 * jmap_putval(map, &val);
404 #define jmap_nthval(map, n, index) \
405 tcon_cast_ptr(&(map)->jmap_, ccanary, \
406 jmap_nthval_(jmap_rawi((map), *(index)), (n), (index)))
409 * jmap_firstval - access the first value in the map.
410 * @map: map from jmap_new
411 * @index: set to the first index in the map.
413 * Returns NULL if the map is empty; otherwise this returns a pointer to
414 * the first value, which you must call jmap_putval() on!
417 * // Add one to every value (ie. make it point into second char of string)
418 * for (val = jmap_firstval(map, &i); val; val = jmap_nextval(map, &i)) {
420 * jmap_putval(map, &val);
425 * jmap_first, jmap_nextval()
427 #define jmap_firstval(map, index) \
428 tcon_cast_ptr(&(map)->jmap_, ccanary, \
429 jmap_firstval_(jmap_rawi((map), *(index)), \
430 (unsigned long *)(index)))
433 * jmap_nextval - access the next value in the map.
434 * @map: map from jmap_new
435 * @index: previous index, updated with the new index.
437 * This returns a pointer to a value (which you must call jmap_putval on)
438 * or NULL. This usually used to find an adjacent value after jmap_firstval.
441 * jmap_firstval(), jmap_putval()
443 #define jmap_nextval(map, index) \
444 tcon_cast_ptr(&(map)->jmap_, ccanary, \
445 jmap_nextval_(jmap_rawi((map), *(index)), \
446 (unsigned long *)(index)))
450 * jmap_lastval - access the last value in the map.
451 * @map: map from jmap_new
452 * @index: set to the last index in the map.
455 * jmap_last(), jmap_putval()
457 #define jmap_lastval(map, index) \
458 tcon_cast_ptr(&(map)->jmap_, ccanary, \
459 jmap_lastval_(jmap_rawi((map), *(index)), \
460 (unsigned long *)(index)))
464 * jmap_prevval - access the previous value in the map.
465 * @map: map from jmap_new
466 * @index: previous index, updated with the new index.
468 * This returns a pointer to a value (which you must call jmap_putval on)
469 * or NULL. This usually used to find an adjacent value after jmap_lastval.
472 * jmap_lastval(), jmap_putval()
474 #define jmap_prevval(map, index) \
475 tcon_cast_ptr(&(map)->jmap_, ccanary, \
476 jmap_prevval_(jmap_rawi((map), *(index)), \
477 (unsigned long *)(index)))
481 /* Debugging checks. */
482 static inline void jmap_debug_add_access(const struct jmap *map,
485 const char *funcname)
487 #ifdef CCAN_JMAP_DEBUG
488 if (!map->acc_value) {
489 ((struct jmap *)map)->acc_value = val;
490 ((struct jmap *)map)->acc_index = index;
491 ((struct jmap *)map)->funcname = funcname;
495 assert(++((struct jmap *)map)->num_accesses);
498 static inline void jmap_debug_del_access(struct jmap *map, unsigned long **val)
500 assert(--map->num_accesses >= 0);
501 #ifdef CCAN_JMAP_DEBUG
502 if (map->acc_value == *val)
503 map->acc_value = NULL;
505 /* Set it to some invalid value. Not NULL, they might rely on that! */
506 assert(memset(val, 0x42, sizeof(void *)));
509 static inline void jmap_debug_access(struct jmap *map)
511 #ifdef CCAN_JMAP_DEBUG
512 if (map->num_accesses && map->acc_value)
514 "jmap: still got index %lu, val %lu (%p) from %s\n",
515 map->acc_index, *map->acc_value, map->acc_value,
518 assert(!map->num_accesses);
521 /* Private functions */
522 struct jmap *jmap_new_(size_t size);
523 void jmap_free_(const struct jmap *map);
524 const char *COLD jmap_error_str_(struct jmap *map);
525 static inline const char *jmap_error_(struct jmap *map)
527 if (JU_ERRNO(&map->err) <= JU_ERRNO_NFMAX)
529 return jmap_error_str_(map);
531 static inline bool jmap_add_(struct jmap *map,
532 unsigned long index, unsigned long value)
535 jmap_debug_access(map);
536 val = (unsigned long *)JudyLIns(&map->judy, index, &map->err);
542 static inline bool jmap_set_(const struct jmap *map,
543 unsigned long index, unsigned long value)
546 val = (unsigned long *)JudyLGet(map->judy, index,
547 (JError_t *)&map->err);
548 if (val && val != PJERR) {
554 static inline bool jmap_del_(struct jmap *map, unsigned long index)
556 jmap_debug_access(map);
557 return JudyLDel(&map->judy, index, &map->err) == 1;
559 static inline bool jmap_test_(const struct jmap *map, unsigned long index)
561 return JudyLGet(map->judy, index, (JError_t *)&map->err) != NULL;
563 static inline unsigned long jmap_get_(const struct jmap *map,
567 val = (unsigned long *)JudyLGet(map->judy, index,
568 (JError_t *)&map->err);
569 if (!val || val == PJERR)
573 static inline unsigned long jmap_popcount_(const struct jmap *map,
575 unsigned long end_incl)
577 return JudyLCount(map->judy, start, end_incl, (JError_t *)&map->err);
579 static inline unsigned long jmap_nth_(const struct jmap *map,
580 unsigned long n, unsigned long invalid)
583 if (!JudyLByCount(map->judy, n+1, &index, (JError_t *)&map->err))
587 static inline unsigned long jmap_first_(const struct jmap *map)
589 unsigned long index = 0;
590 if (!JudyLFirst(map->judy, &index, (JError_t *)&map->err))
596 static inline unsigned long jmap_next_(const struct jmap *map,
599 if (!JudyLNext(map->judy, &prev, (JError_t *)&map->err))
605 static inline unsigned long jmap_last_(const struct jmap *map)
607 unsigned long index = -1;
608 if (!JudyLLast(map->judy, &index, (JError_t *)&map->err))
614 static inline unsigned long jmap_prev_(const struct jmap *map,
617 if (!JudyLPrev(map->judy, &prev, (JError_t *)&map->err))
623 static inline void *jmap_getval_(struct jmap *map, unsigned long index)
626 val = (unsigned long *)JudyLGet(map->judy, index,
627 (JError_t *)&map->err);
628 jmap_debug_add_access(map, index, val, "jmap_getval");
631 static inline void jmap_putval_(struct jmap *map, void *p)
633 jmap_debug_del_access(map, p);
635 static inline unsigned long *jmap_nthval_(const struct jmap *map, unsigned long n,
636 unsigned long *index)
639 val = (unsigned long *)JudyLByCount(map->judy, n+1, index,
640 (JError_t *)&map->err);
641 jmap_debug_add_access(map, *index, val, "jmap_nthval");
644 static inline unsigned long *jmap_firstval_(const struct jmap *map,
645 unsigned long *index)
649 val = (unsigned long *)JudyLFirst(map->judy, index,
650 (JError_t *)&map->err);
651 jmap_debug_add_access(map, *index, val, "jmap_firstval");
654 static inline unsigned long *jmap_nextval_(const struct jmap *map,
655 unsigned long *index)
658 val = (unsigned long *)JudyLNext(map->judy, index,
659 (JError_t *)&map->err);
660 jmap_debug_add_access(map, *index, val, "jmap_nextval");
663 static inline unsigned long *jmap_lastval_(const struct jmap *map,
664 unsigned long *index)
668 val = (unsigned long *)JudyLLast(map->judy, index,
669 (JError_t *)&map->err);
670 jmap_debug_add_access(map, *index, val, "jmap_lastval");
673 static inline unsigned long *jmap_prevval_(const struct jmap *map,
674 unsigned long *index)
677 val = (unsigned long *)JudyLPrev(map->judy, index,
678 (JError_t *)&map->err);
679 jmap_debug_add_access(map, *index, val, "jmap_prevval");
682 #endif /* CCAN_JMAP_H */