5 typedef size_t Word_t, *PWord_t;
9 #include <ccan/compiler/compiler.h>
16 * jmap_new - create a new, empty jmap.
22 * struct jmap *map = jmap_new();
24 * errx(1, "Failed to allocate jmap");
26 struct jmap *jmap_new(void);
29 * jmap_free - destroy a jmap.
30 * @map: the map returned from jmap_new.
35 void jmap_free(const struct jmap *map);
37 /* This is exposed in the header so we can inline. Treat it as private! */
49 const char *COLD_ATTRIBUTE jmap_error_(struct jmap *map);
51 /* Debugging checks. */
52 static inline void jmap_debug_add_access(const struct jmap *map,
53 size_t index, size_t *val,
57 if (!map->acc_value) {
58 ((struct jmap *)map)->acc_value = val;
59 ((struct jmap *)map)->acc_index = index;
60 ((struct jmap *)map)->funcname = funcname;
64 assert(++((struct jmap *)map)->num_accesses);
67 static inline void jmap_debug_del_access(struct jmap *map, size_t **val)
69 assert(--map->num_accesses >= 0);
71 if (map->acc_value == *val)
72 map->acc_value = NULL;
74 /* Set it to some invalid value. Not NULL, they might rely on that! */
75 assert(memset(val, 0x42, sizeof(*val)));
78 static inline void jmap_debug_access(struct jmap *map)
81 if (map->num_accesses && map->acc_value)
83 "jmap: still got index %zu, val %zu (%p) from %s\n",
84 map->acc_index, *map->acc_value, map->acc_value,
87 assert(!map->num_accesses);
91 * jmap_error - test for an error in the a previous jmap_ operation.
92 * @map: the map to test.
94 * Under normal circumstances, return NULL to indicate no error has occurred.
95 * Otherwise, it will return a string containing the error. This string
96 * can only be freed by jmap_free() on the map.
98 * Other than out-of-memory, errors are caused by memory corruption or
102 * struct jmap *map = jmap_new();
103 * const char *errstr;
106 * err(1, "allocating jmap");
107 * errstr = jmap_error(map);
109 * errx(1, "Woah, error on newly created map?! %s", errstr);
111 static inline const char *jmap_error(struct jmap *map)
113 if (JU_ERRNO(&map->err) <= JU_ERRNO_NFMAX)
115 return jmap_error_(map);
119 * jmap_add - add or replace a value for a given index in the map.
120 * @map: map from jmap_new
121 * @index: the index to map
122 * @value: the value to associate with the index
124 * Adds index into the map; replaces value if it's already there.
125 * Returns false on error (out of memory).
128 * if (!jmap_add(map, 0, 1))
129 * err(1, "jmap_add failed!");
131 static inline bool jmap_add(struct jmap *map, size_t index, size_t value)
134 jmap_debug_access(map);
135 val = (size_t *)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, size_t index, size_t value)
158 val = (size_t *)JudyLGet(map->judy, index, (JError_t *)&map->err);
159 if (val && val != PJERR) {
167 * jmap_del - remove an index from the map.
168 * @map: map from jmap_new
169 * @index: the index to map
172 * if (!jmap_del(map, 0))
173 * err(1, "jmap_del failed!");
175 static inline bool jmap_del(struct jmap *map, size_t index)
177 jmap_debug_access(map);
178 return JudyLDel(&map->judy, index, &map->err) == 1;
182 * jmap_test - test if a given index is defined.
183 * @map: map from jmap_new
184 * @index: the index to find
187 * jmap_add(map, 0, 1);
188 * assert(jmap_test(map, 0));
190 static inline bool jmap_test(const struct jmap *map, size_t index)
192 return JudyLGet(map->judy, index, (JError_t *)&map->err) != NULL;
196 * jmap_get - get a value for a given index.
197 * @map: map from jmap_new
198 * @index: the index to find
199 * @invalid: the value to return if the index isn't found.
202 * jmap_add(map, 0, 1);
203 * assert(jmap_get(map, 0, -1) == 1);
208 static inline size_t jmap_get(const struct jmap *map, size_t index,
212 val = (size_t *)JudyLGet(map->judy, index, (JError_t *)&map->err);
213 if (!val || val == PJERR)
219 * jmap_popcount - get population of (some part of) the map.
220 * @map: map from jmap_new
221 * @start: first index to count
222 * @end_incl: last index to count (use -1 for end).
225 * assert(jmap_popcount(map, 0, 1000) <= jmap_popcount(map, 0, 2000));
227 static inline size_t jmap_popcount(const struct jmap *map,
228 size_t start, size_t end_incl)
230 return JudyLCount(map->judy, start, end_incl, (JError_t *)&map->err);
234 * jmap_nth - return the index of the nth value in the map.
235 * @map: map from jmap_new
236 * @n: which index we are interested in (0-based)
237 * @invalid: what to return if n >= map population
239 * This normally returns the nth index in the map, and often there is a
240 * convenient known-invalid value (ie. something which is never in the
241 * map). Otherwise you can use jmap_nthval().
246 * // We know 0 isn't in map.
247 * assert(!jmap_test(map, 0));
248 * for (i = 0; (index = jmap_nth(map, i, 0)) != 0; i++) {
249 * assert(jmap_popcount(map, 0, index) == i);
250 * printf("Index %zu = %zu\n", i, index);
256 static inline size_t jmap_nth(const struct jmap *map,
257 size_t n, size_t invalid)
260 if (!JudyLByCount(map->judy, n+1, &index, (JError_t *)&map->err))
266 * jmap_first - return the first index in the map.
267 * @map: map from jmap_new
268 * @invalid: return value if jmap is empty.
270 * This is equivalent to jmap_nth(map, 0, invalid).
273 * assert(!jmap_test(map, 0));
274 * printf("Map indices (increasing order):");
275 * for (i = jmap_first(map, 0); i; i = jmap_next(map, i, 0))
282 static inline size_t jmap_first(const struct jmap *map, size_t invalid)
285 if (!JudyLFirst(map->judy, &index, (JError_t *)&map->err))
288 assert(index != invalid);
293 * jmap_next - return the next index in the map.
294 * @map: map from jmap_new
295 * @prev: previous index
296 * @invalid: return value if there prev was final index in map.
298 * This is usually used to find an adjacent index after jmap_first.
302 static inline size_t jmap_next(const struct jmap *map, size_t prev,
305 if (!JudyLNext(map->judy, &prev, (JError_t *)&map->err))
308 assert(prev != invalid);
313 * jmap_last - return the last index in the map.
314 * @map: map from jmap_new
315 * @invalid: return value if map is empty.
318 * assert(!jmap_test(map, 0));
319 * printf("Map indices (increasing order):");
320 * for (i = jmap_last(map, 0); i; i = jmap_prev(map, i, 0))
326 static inline size_t jmap_last(const struct jmap *map, size_t invalid)
329 if (!JudyLLast(map->judy, &index, (JError_t *)&map->err))
332 assert(index != invalid);
337 * jmap_prev - return the previous index in the map.
338 * @map: map from jmap_new
339 * @prev: previous index
340 * @invalid: return value if no previous indices are in the map.
342 * This is usually used to find an prior adjacent index after jmap_last.
346 static inline size_t jmap_prev(const struct jmap *map, size_t prev,
349 if (!JudyLPrev(map->judy, &prev, (JError_t *)&map->err))
352 assert(prev != invalid);
357 * jmap_getval - access a value in-place for a given index.
358 * @map: map from jmap_new
359 * @index: the index to find
361 * Returns a pointer into the map, or NULL if the index isn't in the
362 * map. Like the other val functions (jmap_nthval, jmap_firstval
363 * etc), this pointer cannot be used after a jmap_add or jmap_del
364 * call, and you must call jmap_putval() once you are finished.
366 * Unless you define NDEBUG, jmap_add and kmap_del will check that you
367 * have called jmap_putval().
371 * jmap_add(map, 0, 1);
372 * p = jmap_getval(map, 0);
374 * errx(1, "Could not find 0 in map!");
376 * errx(1, "Value in map was not 0?!");
378 * jmap_putval(map, &p);
379 * // Accessing p now would probably crash.
382 * jmap_putval(), jmap_firstval()
384 static inline size_t *jmap_getval(struct jmap *map, size_t index)
387 val = (size_t *)JudyLGet(map->judy, index, (JError_t *)&map->err);
388 jmap_debug_add_access(map, index, val, "jmap_getval");
393 * jmap_putval - revoke access to a value.
394 * @map: map from jmap_new
395 * @p: the pointer to a pointer to the value
397 * @p is a pointer to the (successful) value retuned from one of the
398 * jmap_*val functions (listed below). After this, it will be invalid.
400 * Unless NDEBUG is defined, this will actually alter the value of p
401 * to point to garbage to help avoid accidental use.
404 * jmap_getval(), jmap_nthval(), jmap_firstval(), jmap_nextval(),
405 * jmap_lastval(), jmap_prevval().
407 static inline void jmap_putval(struct jmap *map, size_t **p)
409 jmap_debug_del_access(map, p);
413 * jmap_nthval - access the value of the nth value in the map.
414 * @map: map from jmap_new
415 * @n: which index we are interested in (0-based)
417 * This returns a pointer to the value at the nth index in the map,
418 * or NULL if there are n is greater than the population of the map.
419 * You must use jmap_putval() on the pointer once you are done with it.
424 * // We know 0 isn't in map.
425 * assert(!jmap_test(map, 0));
426 * for (i = 0; (val = jmap_nthval(map, i, &index)) != NULL; i++) {
427 * assert(jmap_popcount(map, 0, index) == i);
428 * printf("Index %zu = %zu, value = %zu\n", i, index, *val);
429 * jmap_putval(map, &val);
435 static inline size_t *jmap_nthval(const struct jmap *map,
436 size_t n, size_t *index)
439 val = (size_t *)JudyLByCount(map->judy, n+1, index,
440 (JError_t *)&map->err);
441 jmap_debug_add_access(map, *index, val, "jmap_nthval");
446 * jmap_firstval - access the first value in the map.
447 * @map: map from jmap_new
448 * @index: set to the first index in the map.
450 * Returns NULL if the map is empty; otherwise this returns a pointer to
451 * the first value, which you must call jmap_putval() on!
454 * // Add one to every value.
455 * for (val = jmap_firstval(map, &i); val; val = jmap_nextval(map, &i)) {
457 * jmap_putval(map, &val);
462 * jmap_first, jmap_nextval()
464 static inline size_t *jmap_firstval(const struct jmap *map, size_t *index)
468 val = (size_t *)JudyLFirst(map->judy, index, (JError_t *)&map->err);
469 jmap_debug_add_access(map, *index, val, "jmap_firstval");
474 * jmap_nextval - access the next value in the map.
475 * @map: map from jmap_new
476 * @index: previous index, updated with the new index.
478 * This returns a pointer to a value (which you must call jmap_putval on)
479 * or NULL. This usually used to find an adjacent value after jmap_firstval.
482 * jmap_firstval(), jmap_putval()
484 static inline size_t *jmap_nextval(const struct jmap *map, size_t *index)
487 val = (size_t *)JudyLNext(map->judy, index, (JError_t *)&map->err);
488 jmap_debug_add_access(map, *index, val, "jmap_nextval");
493 * jmap_lastval - access the last value in the map.
494 * @map: map from jmap_new
495 * @index: set to the last index in the map.
498 * jmap_last(), jmap_putval()
500 static inline size_t *jmap_lastval(const struct jmap *map, size_t *index)
504 val = (size_t *)JudyLLast(map->judy, index, (JError_t *)&map->err);
505 jmap_debug_add_access(map, *index, val, "jmap_lastval");
510 * jmap_prevval - access the previous value in the map.
511 * @map: map from jmap_new
512 * @index: previous index, updated with the new index.
514 * This returns a pointer to a value (which you must call jmap_putval on)
515 * or NULL. This usually used to find an adjacent value after jmap_lastval.
518 * jmap_lastval(), jmap_putval()
520 static inline size_t *jmap_prevval(const struct jmap *map, size_t *index)
523 val = (size_t *)JudyLPrev(map->judy, index, (JError_t *)&map->err);
524 jmap_debug_add_access(map, *index, val, "jmap_prevval");
527 #endif /* CCAN_JMAP_H */