ccanlint: print coverage amount when -vv
[ccan] / ccan / jmap / jmap.h
1 #ifndef CCAN_JMAP_H
2 #define CCAN_JMAP_H
3 #include <stddef.h>
4 #include <Judy.h>
5 #include <stdbool.h>
6 #include <string.h>
7 #include <ccan/compiler/compiler.h>
8 #include <assert.h>
9 #ifdef DEBUG
10 #include <stdio.h>
11 #endif
12
13 /**
14  * jmap_new - create a new, empty jmap.
15  *
16  * See Also:
17  *      JMAP_DEFINE_TYPE()
18  *
19  * Example:
20  *      struct jmap *map = jmap_new();
21  *      if (!map)
22  *              errx(1, "Failed to allocate jmap");
23  */
24 struct jmap *jmap_new(void);
25
26 /**
27  * jmap_free - destroy a jmap.
28  * @map: the map returned from jmap_new.
29  *
30  * Example:
31  *      jmap_free(map);
32  */
33 void jmap_free(const struct jmap *map);
34
35 /* This is exposed in the header so we can inline.  Treat it as private! */
36 struct jmap {
37         Pvoid_t judy;
38         JError_t err;
39         const char *errstr;
40         /* Used if !NDEBUG */
41         int num_accesses;
42         /* Used if DEBUG */
43         unsigned long *acc_value;
44         unsigned long acc_index;
45         const char *funcname;
46 };
47 const char *COLD jmap_error_(struct jmap *map);
48
49 /* Debugging checks. */
50 static inline void jmap_debug_add_access(const struct jmap *map,
51                                          unsigned long index,
52                                          unsigned long *val,
53                                          const char *funcname)
54 {
55 #ifdef DEBUG
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;
60         }
61 #endif
62         if (val)
63                 assert(++((struct jmap *)map)->num_accesses);
64 }
65
66 static inline void jmap_debug_del_access(struct jmap *map, unsigned long **val)
67 {
68         assert(--map->num_accesses >= 0);
69 #ifdef DEBUG
70         if (map->acc_value == *val)
71                 map->acc_value = NULL;
72 #endif
73         /* Set it to some invalid value.  Not NULL, they might rely on that! */
74         assert(memset(val, 0x42, sizeof(*val)));
75 }
76
77 static inline void jmap_debug_access(struct jmap *map)
78 {
79 #ifdef DEBUG
80         if (map->num_accesses && map->acc_value)
81                 fprintf(stderr,
82                         "jmap: still got index %lu, val %lu (%p) from %s\n",
83                         map->acc_index, *map->acc_value, map->acc_value,
84                         map->funcname);
85 #endif
86         assert(!map->num_accesses);
87 }
88
89 /**
90  * jmap_error - test for an error in the a previous jmap_ operation.
91  * @map: the map to test.
92  *
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.
96  *
97  * Other than out-of-memory, errors are caused by memory corruption or
98  * interface misuse.
99  *
100  * Example:
101  *      struct jmap *map = jmap_new();
102  *      const char *errstr;
103  *
104  *      if (!map)
105  *              err(1, "allocating jmap");
106  *      errstr = jmap_error(map);
107  *      if (errstr)
108  *              errx(1, "Woah, error on newly created map?! %s", errstr);
109  */
110 static inline const char *jmap_error(struct jmap *map)
111 {
112         if (JU_ERRNO(&map->err) <= JU_ERRNO_NFMAX)
113                 return NULL;
114         return jmap_error_(map);
115 }
116
117 /**
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
122  *
123  * Adds index into the map; replaces value if it's already there.
124  * Returns false on error (out of memory).
125  *
126  * Example:
127  *      if (!jmap_add(map, 0, 1))
128  *              err(1, "jmap_add failed!");
129  */
130 static inline bool jmap_add(struct jmap *map,
131                             unsigned long index, unsigned long value)
132 {
133         unsigned long *val;
134         jmap_debug_access(map);
135         val = (unsigned long *)JudyLIns(&map->judy, index, &map->err);
136         if (val == PJERR)
137                 return false;
138         *val = value;
139         return true;
140 }
141
142 /**
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
147  *
148  * This sets the value of an index if it already exists, and return true,
149  * otherwise returns false and does nothing.
150  *
151  * Example:
152  *      if (!jmap_set(map, 0, 2))
153  *              err(1, "jmap_set: index 0 not found");
154  */
155 static inline bool jmap_set(const struct jmap *map,
156                             unsigned long index, unsigned long value)
157 {
158         unsigned long *val;
159         val = (unsigned long *)JudyLGet(map->judy, index,
160                                         (JError_t *)&map->err);
161         if (val && val != PJERR) {
162                 *val = value;
163                 return true;
164         }
165         return false;
166 }
167
168 /**
169  * jmap_del - remove an index from the map.
170  * @map: map from jmap_new
171  * @index: the index to map
172  *
173  * Example:
174  *      if (!jmap_del(map, 0))
175  *              err(1, "jmap_del failed!");
176  */
177 static inline bool jmap_del(struct jmap *map, unsigned long index)
178 {
179         jmap_debug_access(map);
180         return JudyLDel(&map->judy, index, &map->err) == 1;
181 }
182
183 /**
184  * jmap_test - test if a given index is defined.
185  * @map: map from jmap_new
186  * @index: the index to find
187  *
188  * Example:
189  *      jmap_add(map, 0, 1);
190  *      assert(jmap_test(map, 0));
191  */
192 static inline bool jmap_test(const struct jmap *map, unsigned long index)
193 {
194         return JudyLGet(map->judy, index, (JError_t *)&map->err) != NULL;
195 }
196
197 /**
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.
202  *
203  * Example:
204  *      jmap_add(map, 0, 1);
205  *      assert(jmap_get(map, 0, -1) == 1);
206  *
207  * See Also:
208  *      jmap_getval()
209  */
210 static inline unsigned long jmap_get(const struct jmap *map,
211                                      unsigned long index,
212                                      unsigned long invalid)
213 {
214         unsigned long *val;
215         val = (unsigned long *)JudyLGet(map->judy, index,
216                                         (JError_t *)&map->err);
217         if (!val || val == PJERR)
218                 return invalid;
219         return *val;
220 }
221
222 /**
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).
227  *
228  * Example:
229  *      assert(jmap_popcount(map, 0, 1000) <= jmap_popcount(map, 0, 2000));
230  */
231 static inline unsigned long jmap_popcount(const struct jmap *map,
232                                           unsigned long start,
233                                           unsigned long end_incl)
234 {
235         return JudyLCount(map->judy, start, end_incl, (JError_t *)&map->err);
236 }
237
238 /**
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
243  *
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().
247  *
248  * Example:
249  *      unsigned long i, index;
250  *
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);
256  *      }
257  *
258  * See Also:
259  *      jmap_nthval();
260  */
261 static inline unsigned long jmap_nth(const struct jmap *map,
262                                      unsigned long n, unsigned long invalid)
263 {
264         unsigned long index;
265         if (!JudyLByCount(map->judy, n+1, &index, (JError_t *)&map->err))
266                 index = invalid;
267         return index;
268 }
269
270 /**
271  * jmap_first - return the first index in the map.
272  * @map: map from jmap_new
273  * @invalid: return value if jmap is empty.
274  *
275  * This is equivalent to jmap_nth(map, 0, invalid).
276  *
277  * Example:
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))
281  *              printf(" %lu", i);
282  *      printf("\n");
283  *
284  * See Also:
285  *      jmap_firstval()
286  */
287 static inline unsigned long jmap_first(const struct jmap *map,
288                                        unsigned long invalid)
289 {
290         unsigned long index = 0;
291         if (!JudyLFirst(map->judy, &index, (JError_t *)&map->err))
292                 index = invalid;
293         else
294                 assert(index != invalid);
295         return index;
296 }
297
298 /**
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.
303  *
304  * This is usually used to find an adjacent index after jmap_first.
305  * See Also:
306  *      jmap_nextval()
307  */
308 static inline unsigned long jmap_next(const struct jmap *map,
309                                       unsigned long prev,
310                                       unsigned long invalid)
311 {
312         if (!JudyLNext(map->judy, &prev, (JError_t *)&map->err))
313                 prev = invalid;
314         else
315                 assert(prev != invalid);
316         return prev;
317 }
318
319 /**
320  * jmap_last - return the last index in the map.
321  * @map: map from jmap_new
322  * @invalid: return value if map is empty.
323  *
324  * Example:
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))
328  *              printf(" %lu", i);
329  *      printf("\n");
330  * See Also:
331  *      jmap_lastval()
332  */
333 static inline unsigned long jmap_last(const struct jmap *map,
334                                       unsigned long invalid)
335 {
336         unsigned long index = -1;
337         if (!JudyLLast(map->judy, &index, (JError_t *)&map->err))
338                 index = invalid;
339         else
340                 assert(index != invalid);
341         return index;
342 }
343
344 /**
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.
349  *
350  * This is usually used to find an prior adjacent index after jmap_last.
351  * See Also:
352  *      jmap_prevval()
353  */
354 static inline unsigned long jmap_prev(const struct jmap *map,
355                                       unsigned long prev,
356                                       unsigned long invalid)
357 {
358         if (!JudyLPrev(map->judy, &prev, (JError_t *)&map->err))
359                 prev = invalid;
360         else
361                 assert(prev != invalid);
362         return prev;
363 }
364
365 /**
366  * jmap_getval - access a value in-place for a given index.
367  * @map: map from jmap_new
368  * @index: the index to find
369  *
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.
374  *
375  * Unless you define NDEBUG, jmap_add and kmap_del will check that you
376  * have called jmap_putval().
377  *
378  * Example:
379  *      unsigned long *p;
380  *      jmap_add(map, 0, 1);
381  *      p = jmap_getval(map, 0);
382  *      if (!p)
383  *              errx(1, "Could not find 0 in map!");
384  *      if (*p != 1)
385  *              errx(1, "Value in map was not 0?!");
386  *      *p = 7;
387  *      jmap_putval(map, &p);
388  *      // Accessing p now would probably crash.
389  *
390  * See Also:
391  *      jmap_putval(), jmap_firstval()
392  */
393 static inline unsigned long *jmap_getval(struct jmap *map, unsigned long index)
394 {
395         unsigned long *val;
396         val = (unsigned long *)JudyLGet(map->judy, index,
397                                         (JError_t *)&map->err);
398         jmap_debug_add_access(map, index, val, "jmap_getval");
399         return val;
400 }
401
402 /**
403  * jmap_putval - revoke access to a value.
404  * @map: map from jmap_new
405  * @p: the pointer to a pointer to the value
406  *
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.
409  *
410  * Unless NDEBUG is defined, this will actually alter the value of p
411  * to point to garbage to help avoid accidental use.
412  *
413  * See Also:
414  *      jmap_getval(), jmap_nthval(), jmap_firstval(), jmap_nextval(),
415  *              jmap_lastval(), jmap_prevval().
416  */
417 static inline void jmap_putval(struct jmap *map, unsigned long **p)
418 {
419         jmap_debug_del_access(map, p);
420 }
421
422 /**
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)
426  *
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.
430  *
431  * Example:
432  *      unsigned long *val;
433  *
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);
440  *      }
441  *
442  * See Also:
443  *      jmap_nth();
444  */
445 static inline unsigned long *jmap_nthval(const struct jmap *map,
446                                          unsigned long n, unsigned long *index)
447 {
448         unsigned long *val;
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");
452         return val;
453 }
454
455 /**
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.
459  *
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!
462  *
463  * Example:
464  *      // Add one to every value.
465  *      for (val = jmap_firstval(map, &i); val; val = jmap_nextval(map, &i)) {
466  *              (*val)++;
467  *              jmap_putval(map, &val);
468  *      }
469  *      printf("\n");
470  *
471  * See Also:
472  *      jmap_first, jmap_nextval()
473  */
474 static inline unsigned long *jmap_firstval(const struct jmap *map,
475                                            unsigned long *index)
476 {
477         unsigned long *val;
478         *index = 0;
479         val = (unsigned long *)JudyLFirst(map->judy, index,
480                                           (JError_t *)&map->err);
481         jmap_debug_add_access(map, *index, val, "jmap_firstval");
482         return val;
483 }
484
485 /**
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.
489  *
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.
492  *
493  * See Also:
494  *      jmap_firstval(), jmap_putval()
495  */
496 static inline unsigned long *jmap_nextval(const struct jmap *map,
497                                           unsigned long *index)
498 {
499         unsigned long *val;
500         val = (unsigned long *)JudyLNext(map->judy, index,
501                                          (JError_t *)&map->err);
502         jmap_debug_add_access(map, *index, val, "jmap_nextval");
503         return val;
504 }
505
506 /**
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.
510  *
511  * See Also:
512  *      jmap_last(), jmap_putval()
513  */
514 static inline unsigned long *jmap_lastval(const struct jmap *map,
515                                           unsigned long *index)
516 {
517         unsigned long *val;
518         *index = -1;
519         val = (unsigned long *)JudyLLast(map->judy, index,
520                                          (JError_t *)&map->err);
521         jmap_debug_add_access(map, *index, val, "jmap_lastval");
522         return val;
523 }
524
525 /**
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.
529  *
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.
532  *
533  * See Also:
534  *      jmap_lastval(), jmap_putval()
535  */
536 static inline unsigned long *jmap_prevval(const struct jmap *map,
537                                           unsigned long *index)
538 {
539         unsigned long *val;
540         val = (unsigned long *)JudyLPrev(map->judy, index,
541                                          (JError_t *)&map->err);
542         jmap_debug_add_access(map, *index, val, "jmap_prevval");
543         return val;
544 }
545 #endif /* CCAN_JMAP_H */