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