93c03b9b03bbf3b0f043bf8d5cc456160f5adbe7
[ccan] / ccan / jmap / jmap.h
1 #ifndef CCAN_JMAP_H
2 #define CCAN_JMAP_H
3 #include <stddef.h>
4 #define _WORD_T
5 typedef size_t Word_t, *PWord_t;
6 #include <Judy.h>
7 #include <stdbool.h>
8 #include <string.h>
9 #include <ccan/compiler/compiler.h>
10 #include <assert.h>
11 #ifdef DEBUG
12 #include <stdio.h>
13 #endif
14
15 /**
16  * jmap_new - create a new, empty jmap.
17  *
18  * See Also:
19  *      JMAP_DEFINE_TYPE()
20  *
21  * Example:
22  *      struct jmap *map = jmap_new();
23  *      if (!map)
24  *              errx(1, "Failed to allocate jmap");
25  */
26 struct jmap *jmap_new(void);
27
28 /**
29  * jmap_free - destroy a jmap.
30  * @map: the map returned from jmap_new.
31  *
32  * Example:
33  *      jmap_free(map);
34  */
35 void jmap_free(const struct jmap *map);
36
37 /* This is exposed in the header so we can inline.  Treat it as private! */
38 struct jmap {
39         Pvoid_t judy;
40         JError_t err;
41         const char *errstr;
42         /* Used if !NDEBUG */
43         int num_accesses;
44         /* Used if DEBUG */
45         size_t *acc_value;
46         size_t acc_index;
47         const char *funcname;
48 };
49 const char *COLD_ATTRIBUTE jmap_error_(struct jmap *map);
50
51 /* Debugging checks. */
52 static inline void jmap_debug_add_access(const struct jmap *map,
53                                          size_t index, size_t *val,
54                                          const char *funcname)
55 {
56 #ifdef 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, size_t **val)
68 {
69         assert(--map->num_accesses >= 0);
70 #ifdef 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 DEBUG
81         if (map->num_accesses && map->acc_value)
82                 fprintf(stderr,
83                         "jmap: still got index %zu, val %zu (%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, size_t index, size_t value)
132 {
133         size_t *val;
134         jmap_debug_access(map);
135         val = (size_t *)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, size_t index, size_t value)
156 {
157         size_t *val;
158         val = (size_t *)JudyLGet(map->judy, index, (JError_t *)&map->err);
159         if (val && val != PJERR) {
160                 *val = value;
161                 return true;
162         }
163         return false;
164 }
165
166 /**
167  * jmap_del - remove an index from the map.
168  * @map: map from jmap_new
169  * @index: the index to map
170  *
171  * Example:
172  *      if (!jmap_del(map, 0))
173  *              err(1, "jmap_del failed!");
174  */
175 static inline bool jmap_del(struct jmap *map, size_t index)
176 {
177         jmap_debug_access(map);
178         return JudyLDel(&map->judy, index, &map->err) == 1;
179 }
180
181 /**
182  * jmap_test - test if a given index is defined.
183  * @map: map from jmap_new
184  * @index: the index to find
185  *
186  * Example:
187  *      jmap_add(map, 0, 1);
188  *      assert(jmap_test(map, 0));
189  */
190 static inline bool jmap_test(const struct jmap *map, size_t index)
191 {
192         return JudyLGet(map->judy, index, (JError_t *)&map->err) != NULL;
193 }
194
195 /**
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.
200  *
201  * Example:
202  *      jmap_add(map, 0, 1);
203  *      assert(jmap_get(map, 0, -1) == 1);
204  *
205  * See Also:
206  *      jmap_getval()
207  */
208 static inline size_t jmap_get(const struct jmap *map, size_t index,
209                               size_t invalid)
210 {
211         size_t *val;
212         val = (size_t *)JudyLGet(map->judy, index, (JError_t *)&map->err);
213         if (!val || val == PJERR)
214                 return invalid;
215         return *val;
216 }
217
218 /**
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).
223  *
224  * Example:
225  *      assert(jmap_popcount(map, 0, 1000) <= jmap_popcount(map, 0, 2000));
226  */
227 static inline size_t jmap_popcount(const struct jmap *map,
228                                    size_t start, size_t end_incl)
229 {
230         return JudyLCount(map->judy, start, end_incl, (JError_t *)&map->err);
231 }
232
233 /**
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
238  *
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().
242  *
243  * Example:
244  *      size_t i, index;
245  *
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);
251  *      }
252  *
253  * See Also:
254  *      jmap_nthval();
255  */
256 static inline size_t jmap_nth(const struct jmap *map,
257                               size_t n, size_t invalid)
258 {
259         size_t index;
260         if (!JudyLByCount(map->judy, n+1, &index, (JError_t *)&map->err))
261                 index = invalid;
262         return index;
263 }
264
265 /**
266  * jmap_first - return the first index in the map.
267  * @map: map from jmap_new
268  * @invalid: return value if jmap is empty.
269  *
270  * This is equivalent to jmap_nth(map, 0, invalid).
271  *
272  * Example:
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))
276  *              printf(" %zu", i);
277  *      printf("\n");
278  *
279  * See Also:
280  *      jmap_firstval()
281  */
282 static inline size_t jmap_first(const struct jmap *map, size_t invalid)
283 {
284         size_t index = 0;
285         if (!JudyLFirst(map->judy, &index, (JError_t *)&map->err))
286                 index = invalid;
287         else
288                 assert(index != invalid);
289         return index;
290 }
291
292 /**
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.
297  *
298  * This is usually used to find an adjacent index after jmap_first.
299  * See Also:
300  *      jmap_nextval()
301  */
302 static inline size_t jmap_next(const struct jmap *map, size_t prev,
303                                size_t invalid)
304 {
305         if (!JudyLNext(map->judy, &prev, (JError_t *)&map->err))
306                 prev = invalid;
307         else
308                 assert(prev != invalid);
309         return prev;
310 }
311
312 /**
313  * jmap_last - return the last index in the map.
314  * @map: map from jmap_new
315  * @invalid: return value if map is empty.
316  *
317  * Example:
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))
321  *              printf(" %zu", i);
322  *      printf("\n");
323  * See Also:
324  *      jmap_lastval()
325  */
326 static inline size_t jmap_last(const struct jmap *map, size_t invalid)
327 {
328         size_t index = -1;
329         if (!JudyLLast(map->judy, &index, (JError_t *)&map->err))
330                 index = invalid;
331         else
332                 assert(index != invalid);
333         return index;
334 }
335
336 /**
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.
341  *
342  * This is usually used to find an prior adjacent index after jmap_last.
343  * See Also:
344  *      jmap_prevval()
345  */
346 static inline size_t jmap_prev(const struct jmap *map, size_t prev,
347                                size_t invalid)
348 {
349         if (!JudyLPrev(map->judy, &prev, (JError_t *)&map->err))
350                 prev = invalid;
351         else
352                 assert(prev != invalid);
353         return prev;
354 }
355
356 /**
357  * jmap_getval - access a value in-place for a given index.
358  * @map: map from jmap_new
359  * @index: the index to find
360  *
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.
365  *
366  * Unless you define NDEBUG, jmap_add and kmap_del will check that you
367  * have called jmap_putval().
368  *
369  * Example:
370  *      size_t *p;
371  *      jmap_add(map, 0, 1);
372  *      p = jmap_getval(map, 0);
373  *      if (!p)
374  *              errx(1, "Could not find 0 in map!");
375  *      if (*p != 1)
376  *              errx(1, "Value in map was not 0?!");
377  *      *p = 7;
378  *      jmap_putval(map, &p);
379  *      // Accessing p now would probably crash.
380  *
381  * See Also:
382  *      jmap_putval(), jmap_firstval()
383  */
384 static inline size_t *jmap_getval(struct jmap *map, size_t index)
385 {
386         size_t *val;
387         val = (size_t *)JudyLGet(map->judy, index, (JError_t *)&map->err);
388         jmap_debug_add_access(map, index, val, "jmap_getval");
389         return val;
390 }
391
392 /**
393  * jmap_putval - revoke access to a value.
394  * @map: map from jmap_new
395  * @p: the pointer to a pointer to the value
396  *
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.
399  *
400  * Unless NDEBUG is defined, this will actually alter the value of p
401  * to point to garbage to help avoid accidental use.
402  *
403  * See Also:
404  *      jmap_getval(), jmap_nthval(), jmap_firstval(), jmap_nextval(),
405  *              jmap_lastval(), jmap_prevval().
406  */
407 static inline void jmap_putval(struct jmap *map, size_t **p)
408 {
409         jmap_debug_del_access(map, p);
410 }
411
412 /**
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)
416  *
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.
420  *
421  * Example:
422  *      size_t *val;
423  *
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);
430  *      }
431  *
432  * See Also:
433  *      jmap_nth();
434  */
435 static inline size_t *jmap_nthval(const struct jmap *map,
436                                   size_t n, size_t *index)
437 {
438         size_t *val;
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");
442         return val;
443 }
444
445 /**
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.
449  *
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!
452  *
453  * Example:
454  *      // Add one to every value.
455  *      for (val = jmap_firstval(map, &i); val; val = jmap_nextval(map, &i)) {
456  *              (*val)++;
457  *              jmap_putval(map, &val);
458  *      }
459  *      printf("\n");
460  *
461  * See Also:
462  *      jmap_first, jmap_nextval()
463  */
464 static inline size_t *jmap_firstval(const struct jmap *map, size_t *index)
465 {
466         size_t *val;
467         *index = 0;
468         val = (size_t *)JudyLFirst(map->judy, index, (JError_t *)&map->err);
469         jmap_debug_add_access(map, *index, val, "jmap_firstval");
470         return val;
471 }
472
473 /**
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.
477  *
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.
480  *
481  * See Also:
482  *      jmap_firstval(), jmap_putval()
483  */
484 static inline size_t *jmap_nextval(const struct jmap *map, size_t *index)
485 {
486         size_t *val;
487         val = (size_t *)JudyLNext(map->judy, index, (JError_t *)&map->err);
488         jmap_debug_add_access(map, *index, val, "jmap_nextval");
489         return val;
490 }
491
492 /**
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.
496  *
497  * See Also:
498  *      jmap_last(), jmap_putval()
499  */
500 static inline size_t *jmap_lastval(const struct jmap *map, size_t *index)
501 {
502         size_t *val;
503         *index = -1;
504         val = (size_t *)JudyLLast(map->judy, index, (JError_t *)&map->err);
505         jmap_debug_add_access(map, *index, val, "jmap_lastval");
506         return val;
507 }
508
509 /**
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.
513  *
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.
516  *
517  * See Also:
518  *      jmap_lastval(), jmap_putval()
519  */
520 static inline size_t *jmap_prevval(const struct jmap *map, size_t *index)
521 {
522         size_t *val;
523         val = (size_t *)JudyLPrev(map->judy, index, (JError_t *)&map->err);
524         jmap_debug_add_access(map, *index, val, "jmap_prevval");
525         return val;
526 }
527 #endif /* CCAN_JMAP_H */