7 #include <ccan/compiler/compiler.h>
14 * jmap_new - create a new, empty jmap.
20 * struct jmap *map = jmap_new();
22 * errx(1, "Failed to allocate jmap");
24 struct jmap *jmap_new(void);
27 * jmap_free - destroy a jmap.
28 * @map: the map returned from jmap_new.
33 void jmap_free(const struct jmap *map);
35 /* This is exposed in the header so we can inline. Treat it as private! */
43 unsigned long *acc_value;
44 unsigned long acc_index;
47 const char *COLD jmap_error_(struct jmap *map);
49 /* Debugging checks. */
50 static inline void jmap_debug_add_access(const struct jmap *map,
56 if (!map->acc_value) {
57 ((struct jmap *)map)->acc_value = val;
58 ((struct jmap *)map)->acc_index = index;
59 ((struct jmap *)map)->funcname = funcname;
63 assert(++((struct jmap *)map)->num_accesses);
66 static inline void jmap_debug_del_access(struct jmap *map, unsigned long **val)
68 assert(--map->num_accesses >= 0);
70 if (map->acc_value == *val)
71 map->acc_value = NULL;
73 /* Set it to some invalid value. Not NULL, they might rely on that! */
74 assert(memset(val, 0x42, sizeof(*val)));
77 static inline void jmap_debug_access(struct jmap *map)
80 if (map->num_accesses && map->acc_value)
82 "jmap: still got index %lu, val %lu (%p) from %s\n",
83 map->acc_index, *map->acc_value, map->acc_value,
86 assert(!map->num_accesses);
90 * jmap_error - test for an error in the a previous jmap_ operation.
91 * @map: the map to test.
93 * Under normal circumstances, return NULL to indicate no error has occurred.
94 * Otherwise, it will return a string containing the error. This string
95 * can only be freed by jmap_free() on the map.
97 * Other than out-of-memory, errors are caused by memory corruption or
101 * struct jmap *map = jmap_new();
102 * const char *errstr;
105 * err(1, "allocating jmap");
106 * errstr = jmap_error(map);
108 * errx(1, "Woah, error on newly created map?! %s", errstr);
110 static inline const char *jmap_error(struct jmap *map)
112 if (JU_ERRNO(&map->err) <= JU_ERRNO_NFMAX)
114 return jmap_error_(map);
118 * jmap_add - add or replace a value for a given index in the map.
119 * @map: map from jmap_new
120 * @index: the index to map
121 * @value: the value to associate with the index
123 * Adds index into the map; replaces value if it's already there.
124 * Returns false on error (out of memory).
127 * if (!jmap_add(map, 0, 1))
128 * err(1, "jmap_add failed!");
130 static inline bool jmap_add(struct jmap *map,
131 unsigned long index, unsigned long value)
134 jmap_debug_access(map);
135 val = (unsigned long *)JudyLIns(&map->judy, index, &map->err);
143 * jmap_set - change a value for an existing index in the map.
144 * @map: map from jmap_new
145 * @index: the index to map
146 * @value: the value to associate with the index
148 * This sets the value of an index if it already exists, and return true,
149 * otherwise returns false and does nothing.
152 * if (!jmap_set(map, 0, 2))
153 * err(1, "jmap_set: index 0 not found");
155 static inline bool jmap_set(const struct jmap *map,
156 unsigned long index, unsigned long value)
159 val = (unsigned long *)JudyLGet(map->judy, index,
160 (JError_t *)&map->err);
161 if (val && val != PJERR) {
169 * jmap_del - remove an index from the map.
170 * @map: map from jmap_new
171 * @index: the index to map
174 * if (!jmap_del(map, 0))
175 * err(1, "jmap_del failed!");
177 static inline bool jmap_del(struct jmap *map, unsigned long index)
179 jmap_debug_access(map);
180 return JudyLDel(&map->judy, index, &map->err) == 1;
184 * jmap_test - test if a given index is defined.
185 * @map: map from jmap_new
186 * @index: the index to find
189 * jmap_add(map, 0, 1);
190 * assert(jmap_test(map, 0));
192 static inline bool jmap_test(const struct jmap *map, unsigned long index)
194 return JudyLGet(map->judy, index, (JError_t *)&map->err) != NULL;
198 * jmap_get - get a value for a given index.
199 * @map: map from jmap_new
200 * @index: the index to find
201 * @invalid: the value to return if the index isn't found.
204 * jmap_add(map, 0, 1);
205 * assert(jmap_get(map, 0, -1) == 1);
210 static inline unsigned long jmap_get(const struct jmap *map,
212 unsigned long invalid)
215 val = (unsigned long *)JudyLGet(map->judy, index,
216 (JError_t *)&map->err);
217 if (!val || val == PJERR)
223 * jmap_popcount - get population of (some part of) the map.
224 * @map: map from jmap_new
225 * @start: first index to count
226 * @end_incl: last index to count (use -1 for end).
229 * assert(jmap_popcount(map, 0, 1000) <= jmap_popcount(map, 0, 2000));
231 static inline unsigned long jmap_popcount(const struct jmap *map,
233 unsigned long end_incl)
235 return JudyLCount(map->judy, start, end_incl, (JError_t *)&map->err);
239 * jmap_nth - return the index of the nth value in the map.
240 * @map: map from jmap_new
241 * @n: which index we are interested in (0-based)
242 * @invalid: what to return if n >= map population
244 * This normally returns the nth index in the map, and often there is a
245 * convenient known-invalid value (ie. something which is never in the
246 * map). Otherwise you can use jmap_nthval().
249 * unsigned long i, index;
251 * // We know 0 isn't in map.
252 * assert(!jmap_test(map, 0));
253 * for (i = 0; (index = jmap_nth(map, i, 0)) != 0; i++) {
254 * assert(jmap_popcount(map, 0, index) == i);
255 * printf("Index %lu = %lu\n", i, index);
261 static inline unsigned long jmap_nth(const struct jmap *map,
262 unsigned long n, unsigned long invalid)
265 if (!JudyLByCount(map->judy, n+1, &index, (JError_t *)&map->err))
271 * jmap_first - return the first index in the map.
272 * @map: map from jmap_new
273 * @invalid: return value if jmap is empty.
275 * This is equivalent to jmap_nth(map, 0, invalid).
278 * assert(!jmap_test(map, 0));
279 * printf("Map indices (increasing order):");
280 * for (i = jmap_first(map, 0); i; i = jmap_next(map, i, 0))
287 static inline unsigned long jmap_first(const struct jmap *map,
288 unsigned long invalid)
290 unsigned long index = 0;
291 if (!JudyLFirst(map->judy, &index, (JError_t *)&map->err))
294 assert(index != invalid);
299 * jmap_next - return the next index in the map.
300 * @map: map from jmap_new
301 * @prev: previous index
302 * @invalid: return value if there prev was final index in map.
304 * This is usually used to find an adjacent index after jmap_first.
308 static inline unsigned long jmap_next(const struct jmap *map,
310 unsigned long invalid)
312 if (!JudyLNext(map->judy, &prev, (JError_t *)&map->err))
315 assert(prev != invalid);
320 * jmap_last - return the last index in the map.
321 * @map: map from jmap_new
322 * @invalid: return value if map is empty.
325 * assert(!jmap_test(map, 0));
326 * printf("Map indices (increasing order):");
327 * for (i = jmap_last(map, 0); i; i = jmap_prev(map, i, 0))
333 static inline unsigned long jmap_last(const struct jmap *map,
334 unsigned long invalid)
336 unsigned long index = -1;
337 if (!JudyLLast(map->judy, &index, (JError_t *)&map->err))
340 assert(index != invalid);
345 * jmap_prev - return the previous index in the map.
346 * @map: map from jmap_new
347 * @prev: previous index
348 * @invalid: return value if no previous indices are in the map.
350 * This is usually used to find an prior adjacent index after jmap_last.
354 static inline unsigned long jmap_prev(const struct jmap *map,
356 unsigned long invalid)
358 if (!JudyLPrev(map->judy, &prev, (JError_t *)&map->err))
361 assert(prev != invalid);
366 * jmap_getval - access a value in-place for a given index.
367 * @map: map from jmap_new
368 * @index: the index to find
370 * Returns a pointer into the map, or NULL if the index isn't in the
371 * map. Like the other val functions (jmap_nthval, jmap_firstval
372 * etc), this pointer cannot be used after a jmap_add or jmap_del
373 * call, and you must call jmap_putval() once you are finished.
375 * Unless you define NDEBUG, jmap_add and kmap_del will check that you
376 * have called jmap_putval().
380 * jmap_add(map, 0, 1);
381 * p = jmap_getval(map, 0);
383 * errx(1, "Could not find 0 in map!");
385 * errx(1, "Value in map was not 0?!");
387 * jmap_putval(map, &p);
388 * // Accessing p now would probably crash.
391 * jmap_putval(), jmap_firstval()
393 static inline unsigned long *jmap_getval(struct jmap *map, unsigned long index)
396 val = (unsigned long *)JudyLGet(map->judy, index,
397 (JError_t *)&map->err);
398 jmap_debug_add_access(map, index, val, "jmap_getval");
403 * jmap_putval - revoke access to a value.
404 * @map: map from jmap_new
405 * @p: the pointer to a pointer to the value
407 * @p is a pointer to the (successful) value retuned from one of the
408 * jmap_*val functions (listed below). After this, it will be invalid.
410 * Unless NDEBUG is defined, this will actually alter the value of p
411 * to point to garbage to help avoid accidental use.
414 * jmap_getval(), jmap_nthval(), jmap_firstval(), jmap_nextval(),
415 * jmap_lastval(), jmap_prevval().
417 static inline void jmap_putval(struct jmap *map, unsigned long **p)
419 jmap_debug_del_access(map, p);
423 * jmap_nthval - access the value of the nth value in the map.
424 * @map: map from jmap_new
425 * @n: which index we are interested in (0-based)
427 * This returns a pointer to the value at the nth index in the map,
428 * or NULL if there are n is greater than the population of the map.
429 * You must use jmap_putval() on the pointer once you are done with it.
432 * unsigned long *val;
434 * // We know 0 isn't in map.
435 * assert(!jmap_test(map, 0));
436 * for (i = 0; (val = jmap_nthval(map, i, &index)) != NULL; i++) {
437 * assert(jmap_popcount(map, 0, index) == i);
438 * printf("Index %lu = %lu, value = %lu\n", i, index, *val);
439 * jmap_putval(map, &val);
445 static inline unsigned long *jmap_nthval(const struct jmap *map,
446 unsigned long n, unsigned long *index)
449 val = (unsigned long *)JudyLByCount(map->judy, n+1, index,
450 (JError_t *)&map->err);
451 jmap_debug_add_access(map, *index, val, "jmap_nthval");
456 * jmap_firstval - access the first value in the map.
457 * @map: map from jmap_new
458 * @index: set to the first index in the map.
460 * Returns NULL if the map is empty; otherwise this returns a pointer to
461 * the first value, which you must call jmap_putval() on!
464 * // Add one to every value.
465 * for (val = jmap_firstval(map, &i); val; val = jmap_nextval(map, &i)) {
467 * jmap_putval(map, &val);
472 * jmap_first, jmap_nextval()
474 static inline unsigned long *jmap_firstval(const struct jmap *map,
475 unsigned long *index)
479 val = (unsigned long *)JudyLFirst(map->judy, index,
480 (JError_t *)&map->err);
481 jmap_debug_add_access(map, *index, val, "jmap_firstval");
486 * jmap_nextval - access the next value in the map.
487 * @map: map from jmap_new
488 * @index: previous index, updated with the new index.
490 * This returns a pointer to a value (which you must call jmap_putval on)
491 * or NULL. This usually used to find an adjacent value after jmap_firstval.
494 * jmap_firstval(), jmap_putval()
496 static inline unsigned long *jmap_nextval(const struct jmap *map,
497 unsigned long *index)
500 val = (unsigned long *)JudyLNext(map->judy, index,
501 (JError_t *)&map->err);
502 jmap_debug_add_access(map, *index, val, "jmap_nextval");
507 * jmap_lastval - access the last value in the map.
508 * @map: map from jmap_new
509 * @index: set to the last index in the map.
512 * jmap_last(), jmap_putval()
514 static inline unsigned long *jmap_lastval(const struct jmap *map,
515 unsigned long *index)
519 val = (unsigned long *)JudyLLast(map->judy, index,
520 (JError_t *)&map->err);
521 jmap_debug_add_access(map, *index, val, "jmap_lastval");
526 * jmap_prevval - access the previous value in the map.
527 * @map: map from jmap_new
528 * @index: previous index, updated with the new index.
530 * This returns a pointer to a value (which you must call jmap_putval on)
531 * or NULL. This usually used to find an adjacent value after jmap_lastval.
534 * jmap_lastval(), jmap_putval()
536 static inline unsigned long *jmap_prevval(const struct jmap *map,
537 unsigned long *index)
540 val = (unsigned long *)JudyLPrev(map->judy, index,
541 (JError_t *)&map->err);
542 jmap_debug_add_access(map, *index, val, "jmap_prevval");
545 #endif /* CCAN_JMAP_H */