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