container_of: don't put member_ptr in container_off.
[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 <ccan/compiler/compiler.h>
5 #include <ccan/tcon/tcon.h>
6 #include <stddef.h>
7 #include <Judy.h>
8 #include <stdbool.h>
9 #include <string.h>
10 #include <assert.h>
11 #ifdef CCAN_JMAP_DEBUG
12 #include <stdio.h>
13 #endif
14
15 /**
16  * struct map - private definition of a jmap.
17  *
18  * It's exposed here so you can put it in your structures and so we can
19  * supply inline functions.
20  */
21 struct jmap {
22         Pvoid_t judy;
23         JError_t err;
24         const char *errstr;
25         /* Used if !NDEBUG */
26         int num_accesses;
27         /* Used if CCAN_JMAP_DEBUG */
28         unsigned long *acc_value;
29         unsigned long acc_index;
30         const char *funcname;
31 };
32
33 /**
34  * JMAP_MEMBERS - declare members for a type-specific jmap.
35  * @itype: index type for this map, or void * for any pointer.
36  * @ctype: contents type for this map, or void * for any pointer.
37  *
38  * Example:
39  *      struct jmap_long_to_charp {
40  *              JMAP_MEMBERS(long, char *);
41  *      };
42  */
43 #define JMAP_MEMBERS(itype, ctype)              \
44         struct jmap raw;                        \
45         TCON(itype icanary; ctype ccanary)
46
47 /**
48  * jmap_new - create a new, empty jmap.
49  *
50  * See Also:
51  *      JMAP_MEMBERS()
52  *
53  * Example:
54  *      struct jmap_long_to_charp {
55  *              JMAP_MEMBERS(long, char *);
56  *      };
57  *
58  *      struct jmap_long_to_charp *map = jmap_new(struct jmap_long_to_charp);
59  *      if (!map)
60  *              errx(1, "Failed to allocate jmap");
61  */
62 #define jmap_new(type) ((type *)jmap_new_(sizeof(type)))
63
64 /**
65  * jmap_free - destroy a jmap.
66  * @map: the map returned from jmap_new.
67  *
68  * Example:
69  *      jmap_free(map);
70  */
71 #define jmap_free(map) jmap_free_(&(map)->raw)
72
73 /**
74  * jmap_error - test for an error in the a previous jmap_ operation.
75  * @map: the map to test.
76  *
77  * Under normal circumstances, return NULL to indicate no error has occurred.
78  * Otherwise, it will return a string containing the error.  This string
79  * can only be freed by jmap_free() on the map.
80  *
81  * Other than out-of-memory, errors are caused by memory corruption or
82  * interface misuse.
83  *
84  * Example:
85  *      const char *errstr;
86  *
87  *      errstr = jmap_error(map);
88  *      if (errstr)
89  *              errx(1, "Woah, error on newly created map?! %s", errstr);
90  */
91 #define jmap_error(map) jmap_error_(&(map)->raw)
92
93 /**
94  * jmap_rawi - unwrap the typed map and check the index type
95  * @map: the typed jmap
96  * @expr: the expression to check the index type against (not evaluated)
97  *
98  * This macro usually causes the compiler to emit a warning if the
99  * variable is of an unexpected type.  It is used internally where we
100  * need to access the raw underlying jmap.
101  */
102 #define jmap_rawi(map, expr) (&tcon_check((map), icanary, (expr))->raw)
103
104 /**
105  * jmap_rawc - unwrap the typed map and check the contents type
106  * @map: the typed jmap
107  * @expr: the expression to check the content type against (not evaluated)
108  *
109  * This macro usually causes the compiler to emit a warning if the
110  * variable is of an unexpected type.  It is used internally where we
111  * need to access the raw underlying jmap.
112  */
113 #define jmap_rawc(map, expr) (&tcon_check((map), ccanary, (expr))->raw)
114
115 /**
116  * jmap_rawci - unwrap the typed map and check the index and contents types
117  * @map: the typed jmap
118  * @iexpr: the expression to check the index type against (not evaluated)
119  * @cexpr: the expression to check the contents type against (not evaluated)
120  *
121  * This macro usually causes the compiler to emit a warning if the
122  * variable is of an unexpected type.  It is used internally where we
123  * need to access the raw underlying jmap.
124  */
125 #define jmap_rawci(map, iexpr, cexpr) \
126         (&tcon_check(tcon_check((map), ccanary, (cexpr)), icanary, (iexpr))->raw)
127
128 /**
129  * jmap_add - add or replace a value for a given index in the map.
130  * @map: map from jmap_new
131  * @index: the index to map
132  * @value: the value to associate with the index
133  *
134  * Adds index into the map; replaces value if it's already there.
135  * Returns false on error (out of memory).
136  *
137  * Example:
138  *      if (!jmap_add(map, 0, "hello"))
139  *              err(1, "jmap_add failed!");
140  */
141 #define jmap_add(map, index, value)                             \
142         jmap_add_(jmap_rawci((map), (index), (value)),          \
143                   (unsigned long)(index), (unsigned long)value)
144
145 /**
146  * jmap_set - change a value for an existing index in the map.
147  * @map: map from jmap_new
148  * @index: the index to map
149  * @value: the value to associate with the index
150  *
151  * This sets the value of an index if it already exists, and return true,
152  * otherwise returns false and does nothing.
153  *
154  * Example:
155  *      if (!jmap_set(map, 0, "goodbye"))
156  *              err(1, "jmap_set: index 0 not found");
157  */
158 #define jmap_set(map, index, value)                             \
159         jmap_set_(jmap_rawci((map), (index), (value)),          \
160                   (unsigned long)(index), (unsigned long)value)
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 #define jmap_del(map, index)                                            \
172         jmap_del_(jmap_rawi((map), (index)), (unsigned long)(index))
173
174 /**
175  * jmap_test - test if a given index is defined.
176  * @map: map from jmap_new
177  * @index: the index to find
178  *
179  * Example:
180  *      jmap_add(map, 1, "hello");
181  *      assert(jmap_test(map, 1));
182  */
183 #define jmap_test(map, index)                           \
184         jmap_test_(jmap_rawi((map), (index)), (unsigned long)(index))
185
186 /**
187  * jmap_get - get a value for a given index.
188  * @map: map from jmap_new
189  * @index: the index to find
190  *
191  * Returns 0 if !jmap_test(map, index).
192  *
193  * Example:
194  *      const char *str = "hello";
195  *      jmap_add(map, 2, str);
196  *      assert(jmap_get(map, 0) == str);
197  *
198  * See Also:
199  *      jmap_getval()
200  */
201 #define jmap_get(map, index)                                            \
202         tcon_cast((map), ccanary,                                       \
203                   jmap_get_(jmap_rawi((map), (index)), (unsigned long)(index)))
204
205 /**
206  * jmap_count - get population of the map.
207  * @map: map from jmap_new
208  *
209  * Example:
210  *      assert(jmap_count(map) < 1000);
211  */
212 #define jmap_count(map)                         \
213         jmap_popcount_(&(map)->raw, 0, -1UL)
214
215 /**
216  * jmap_popcount - get population of (some part of) the map.
217  * @map: map from jmap_new
218  * @start: first index to count
219  * @end_incl: last index to count (use -1 for end).
220  *
221  * Example:
222  *      assert(jmap_popcount(map, 0, 1000) <= jmap_popcount(map, 0, 2000));
223  */
224 #define jmap_popcount(map, start, end_incl)                             \
225         jmap_popcount_(jmap_rawi((map), (start) ? (start) : (end_incl)), \
226                        (unsigned long)(start), (unsigned long)(end_incl))
227
228 /**
229  * jmap_nth - return the index of the nth value in the map.
230  * @map: map from jmap_new
231  * @n: which index we are interested in (0-based)
232  * @invalid: what to return if n >= map population
233  *
234  * This normally returns the nth index in the map, and often there is a
235  * convenient known-invalid value (ie. something which is never in the
236  * map).  Otherwise you can use jmap_nthval().
237  *
238  * Example:
239  *      unsigned long i, index;
240  *
241  *      // We know 0 isn't in map.
242  *      assert(!jmap_test(map, 0));
243  *      for (i = 0; (index = jmap_nth(map, i, 0)) != 0; i++) {
244  *              assert(jmap_popcount(map, 0, index) == i);
245  *              printf("Index %lu = %lu\n", i, index);
246  *      }
247  *
248  * See Also:
249  *      jmap_nthval();
250  */
251 #define jmap_nth(map, n, invalid)                                       \
252         tcon_cast((map), icanary,                                       \
253                   jmap_nth_(jmap_rawi((map), (invalid)),                        \
254                             (n), (unsigned long)(invalid)))
255
256 /**
257  * jmap_first - return the first index in the map (must not contain 0).
258  * @map: map from jmap_new
259  *
260  * This is equivalent to jmap_nth(map, 0, 0).
261  *
262  * Example:
263  *      assert(!jmap_test(map, 0));
264  *      printf("Map indices (increasing order):");
265  *      for (i = jmap_first(map); i; i = jmap_next(map, i))
266  *              printf(" %lu", i);
267  *      printf("\n");
268  *
269  * See Also:
270  *      jmap_firstval()
271  */
272 #define jmap_first(map)                                         \
273         tcon_cast((map), icanary, jmap_first_(&(map)->raw))
274
275 /**
276  * jmap_next - return the next index in the map.
277  * @map: map from jmap_new
278  * @prev: previous index
279  *
280  * This is usually used to find an adjacent index after jmap_first.
281  * See Also:
282  *      jmap_nextval()
283  */
284 #define jmap_next(map, prev)                                            \
285         tcon_cast((map), icanary, jmap_next_(jmap_rawi((map), (prev)),  \
286                                              (unsigned long)(prev)))
287
288 /**
289  * jmap_last - return the last index in the map.
290  * @map: map from jmap_new
291  *
292  * Returns 0 if map is empty.
293  *
294  * Example:
295  *      assert(!jmap_test(map, 0));
296  *      printf("Map indices (increasing order):");
297  *      for (i = jmap_last(map); i; i = jmap_prev(map, i))
298  *              printf(" %lu", i);
299  *      printf("\n");
300  * See Also:
301  *      jmap_lastval()
302  */
303 #define jmap_last(map)                                          \
304         tcon_cast((map), icanary, jmap_last_(&(map)->raw))
305
306 /**
307  * jmap_prev - return the previous index in the map (must not contain 0)
308  * @map: map from jmap_new
309  * @prev: previous index
310  *
311  * This is usually used to find an prior adjacent index after jmap_last.
312  * Returns 0 if no previous indices in map.
313  *
314  * See Also:
315  *      jmap_prevval()
316  */
317 #define jmap_prev(map, prev)                                            \
318         tcon_cast((map), icanary, jmap_prev_(jmap_rawi((map), (prev)), (prev)))
319
320 /**
321  * jmap_getval - access a value in-place for a given index.
322  * @map: map from jmap_new
323  * @index: the index to find
324  *
325  * Returns a pointer into the map, or NULL if the index isn't in the
326  * map.  Like the other val functions (jmap_nthval, jmap_firstval
327  * etc), this pointer cannot be used after a jmap_add or jmap_del
328  * call, and you must call jmap_putval() once you are finished.
329  *
330  * Unless you define NDEBUG, jmap_add and kmap_del will check that you
331  * have called jmap_putval().
332  *
333  * Example:
334  *      char **p;
335  *      jmap_add(map, 0, "hello");
336  *      p = jmap_getval(map, 0);
337  *      if (!p)
338  *              errx(1, "Could not find 0 in map!");
339  *      if (strcmp(*p, "hello") != 0)
340  *              errx(1, "Value in map was not correct?!");
341  *      *p = (char *)"goodbye";
342  *      jmap_putval(map, &p);
343  *      // Accessing p now would probably crash.
344  *
345  * See Also:
346  *      jmap_putval(), jmap_firstval()
347  */
348 #define jmap_getval(map, index)                                         \
349         tcon_cast_ptr((map), ccanary,                                   \
350                       jmap_getval_(jmap_rawi((map), (index)),           \
351                                    (unsigned long)(index)))
352
353 /**
354  * jmap_putval - revoke access to a value.
355  * @map: map from jmap_new
356  * @p: the pointer to a pointer to the value
357  *
358  * @p is a pointer to the (successful) value retuned from one of the
359  * jmap_*val functions (listed below).  After this, it will be invalid.
360  *
361  * Unless NDEBUG is defined, this will actually alter the value of p
362  * to point to garbage to help avoid accidental use.
363  *
364  * See Also:
365  *      jmap_getval(), jmap_nthval(), jmap_firstval(), jmap_nextval(),
366  *              jmap_lastval(), jmap_prevval().
367  */
368 #define jmap_putval(map, p)                                             \
369         jmap_putval_(jmap_rawc((map), **(p)), (p))
370
371 /**
372  * jmap_nthval - access the value of the nth value in the map.
373  * @map: map from jmap_new
374  * @n: which index we are interested in (0-based)
375  * @index: set to the nth index in the map.
376  *
377  * This returns a pointer to the value at the nth index in the map,
378  * or NULL if there are n is greater than the population of the map.
379  * You must use jmap_putval() on the pointer once you are done with it.
380  *
381  * Example:
382  *      char **val;
383  *
384  *      // We know 0 isn't in map.
385  *      assert(!jmap_test(map, 0));
386  *      for (i = 0; (val = jmap_nthval(map, i, &index)) != NULL; i++) {
387  *              assert(jmap_popcount(map, 0, index) == i);
388  *              printf("Index %lu = %lu, value = %s\n", i, index, *val);
389  *              jmap_putval(map, &val);
390  *      }
391  *
392  * See Also:
393  *      jmap_nth();
394  */
395 #define jmap_nthval(map, n, index)                                      \
396         tcon_cast_ptr((map), ccanary,                                   \
397                       jmap_nthval_(jmap_rawi((map), *(index)), (n), (index)))
398
399 /**
400  * jmap_firstval - access the first value in the map.
401  * @map: map from jmap_new
402  * @index: set to the first index in the map.
403  *
404  * Returns NULL if the map is empty; otherwise this returns a pointer to
405  * the first value, which you must call jmap_putval() on!
406  *
407  * Example:
408  *      // Add one to every value (ie. make it point into second char of string)
409  *      for (val = jmap_firstval(map, &i); val; val = jmap_nextval(map, &i)) {
410  *              (*val)++;
411  *              jmap_putval(map, &val);
412  *      }
413  *      printf("\n");
414  *
415  * See Also:
416  *      jmap_first, jmap_nextval()
417  */
418 #define jmap_firstval(map, index)             \
419         tcon_cast_ptr((map), ccanary,                           \
420                       jmap_firstval_(jmap_rawi((map), *(index)),        \
421                                      (unsigned long *)(index)))
422
423 /**
424  * jmap_nextval - access the next value in the map.
425  * @map: map from jmap_new
426  * @index: previous index, updated with the new index.
427  *
428  * This returns a pointer to a value (which you must call jmap_putval on)
429  * or NULL.  This usually used to find an adjacent value after jmap_firstval.
430  *
431  * See Also:
432  *      jmap_firstval(), jmap_putval()
433  */
434 #define jmap_nextval(map, index)                                \
435         tcon_cast_ptr((map), ccanary,                           \
436                       jmap_nextval_(jmap_rawi((map), *(index)), \
437                                     (unsigned long *)(index)))
438
439
440 /**
441  * jmap_lastval - access the last value in the map.
442  * @map: map from jmap_new
443  * @index: set to the last index in the map.
444  *
445  * See Also:
446  *      jmap_last(), jmap_putval()
447  */
448 #define jmap_lastval(map, index)              \
449         tcon_cast_ptr((map), ccanary,                           \
450                       jmap_lastval_(jmap_rawi((map), *(index)), \
451                                     (unsigned long *)(index)))
452
453
454 /**
455  * jmap_prevval - access the previous value in the map.
456  * @map: map from jmap_new
457  * @index: previous index, updated with the new index.
458  *
459  * This returns a pointer to a value (which you must call jmap_putval on)
460  * or NULL.  This usually used to find an adjacent value after jmap_lastval.
461  *
462  * See Also:
463  *      jmap_lastval(), jmap_putval()
464  */
465 #define jmap_prevval(map, index)                                \
466         tcon_cast_ptr((map), ccanary,                           \
467                       jmap_prevval_(jmap_rawi((map), *(index)), \
468                                     (unsigned long *)(index)))
469
470
471
472 /* Debugging checks. */
473 static inline void jmap_debug_add_access(const struct jmap *map,
474                                          unsigned long index,
475                                          unsigned long *val,
476                                          const char *funcname)
477 {
478 #ifdef CCAN_JMAP_DEBUG
479         if (!map->acc_value) {
480                 ((struct jmap *)map)->acc_value = val;
481                 ((struct jmap *)map)->acc_index = index;
482                 ((struct jmap *)map)->funcname = funcname;
483         }
484 #endif
485         if (val)
486                 assert(++((struct jmap *)map)->num_accesses);
487 }
488
489 static inline void jmap_debug_del_access(struct jmap *map, unsigned long **val)
490 {
491         assert(--map->num_accesses >= 0);
492 #ifdef CCAN_JMAP_DEBUG
493         if (map->acc_value == *val)
494                 map->acc_value = NULL;
495 #endif
496         /* Set it to some invalid value.  Not NULL, they might rely on that! */
497         assert(memset(val, 0x42, sizeof(void *)));
498 }
499
500 static inline void jmap_debug_access(struct jmap *map)
501 {
502 #ifdef CCAN_JMAP_DEBUG
503         if (map->num_accesses && map->acc_value)
504                 fprintf(stderr,
505                         "jmap: still got index %lu, val %lu (%p) from %s\n",
506                         map->acc_index, *map->acc_value, map->acc_value,
507                         map->funcname);
508 #endif
509         assert(!map->num_accesses);
510 }
511
512 /* Private functions */
513 struct jmap *jmap_new_(size_t size);
514 void jmap_free_(const struct jmap *map);
515 const char *COLD jmap_error_str_(struct jmap *map);
516 static inline const char *jmap_error_(struct jmap *map)
517 {
518         if (JU_ERRNO(&map->err) <= JU_ERRNO_NFMAX)
519                 return NULL;
520         return jmap_error_str_(map);
521 }
522 static inline bool jmap_add_(struct jmap *map,
523                              unsigned long index, unsigned long value)
524 {
525         unsigned long *val;
526         jmap_debug_access(map);
527         val = (unsigned long *)JudyLIns(&map->judy, index, &map->err);
528         if (val == PJERR)
529                 return false;
530         *val = value;
531         return true;
532 }
533 static inline bool jmap_set_(const struct jmap *map,
534                              unsigned long index, unsigned long value)
535 {
536         unsigned long *val;
537         val = (unsigned long *)JudyLGet(map->judy, index,
538                                         (JError_t *)&map->err);
539         if (val && val != PJERR) {
540                 *val = value;
541                 return true;
542         }
543         return false;
544 }
545 static inline bool jmap_del_(struct jmap *map, unsigned long index)
546 {
547         jmap_debug_access(map);
548         return JudyLDel(&map->judy, index, &map->err) == 1;
549 }
550 static inline bool jmap_test_(const struct jmap *map, unsigned long index)
551 {
552         return JudyLGet(map->judy, index, (JError_t *)&map->err) != NULL;
553 }
554 static inline unsigned long jmap_get_(const struct jmap *map,
555                                       unsigned long index)
556 {
557         unsigned long *val;
558         val = (unsigned long *)JudyLGet(map->judy, index,
559                                         (JError_t *)&map->err);
560         if (!val || val == PJERR)
561                 return 0;
562         return *val;
563 }
564 static inline unsigned long jmap_popcount_(const struct jmap *map,
565                                            unsigned long start,
566                                            unsigned long end_incl)
567 {
568         return JudyLCount(map->judy, start, end_incl, (JError_t *)&map->err);
569 }
570 static inline unsigned long jmap_nth_(const struct jmap *map,
571                                       unsigned long n, unsigned long invalid)
572 {
573         unsigned long index;
574         if (!JudyLByCount(map->judy, n+1, &index, (JError_t *)&map->err))
575                 index = invalid;
576         return index;
577 }
578 static inline unsigned long jmap_first_(const struct jmap *map)
579 {
580         unsigned long index = 0;
581         if (!JudyLFirst(map->judy, &index, (JError_t *)&map->err))
582                 index = 0;
583         else
584                 assert(index != 0);
585         return index;
586 }
587 static inline unsigned long jmap_next_(const struct jmap *map,
588                                        unsigned long prev)
589 {
590         if (!JudyLNext(map->judy, &prev, (JError_t *)&map->err))
591                 prev = 0;
592         else
593                 assert(prev != 0);
594         return prev;
595 }
596 static inline unsigned long jmap_last_(const struct jmap *map)
597 {
598         unsigned long index = -1;
599         if (!JudyLLast(map->judy, &index, (JError_t *)&map->err))
600                 index = 0;
601         else
602                 assert(index != 0);
603         return index;
604 }
605 static inline unsigned long jmap_prev_(const struct jmap *map,
606                                        unsigned long prev)
607 {
608         if (!JudyLPrev(map->judy, &prev, (JError_t *)&map->err))
609                 prev = 0;
610         else
611                 assert(prev != 0);
612         return prev;
613 }
614 static inline void *jmap_getval_(struct jmap *map, unsigned long index)
615 {
616         unsigned long *val;
617         val = (unsigned long *)JudyLGet(map->judy, index,
618                                         (JError_t *)&map->err);
619         jmap_debug_add_access(map, index, val, "jmap_getval");
620         return val;
621 }
622 static inline void jmap_putval_(struct jmap *map, void *p)
623 {
624         jmap_debug_del_access(map, p);
625 }
626 static inline unsigned long *jmap_nthval_(const struct jmap *map, unsigned long n,
627                                           unsigned long *index)
628 {
629         unsigned long *val;
630         val = (unsigned long *)JudyLByCount(map->judy, n+1, index,
631                                      (JError_t *)&map->err);
632         jmap_debug_add_access(map, *index, val, "jmap_nthval");
633         return val;
634 }
635 static inline unsigned long *jmap_firstval_(const struct jmap *map,
636                                             unsigned long *index)
637 {
638         unsigned long *val;
639         *index = 0;
640         val = (unsigned long *)JudyLFirst(map->judy, index,
641                                           (JError_t *)&map->err);
642         jmap_debug_add_access(map, *index, val, "jmap_firstval");
643         return val;
644 }
645 static inline unsigned long *jmap_nextval_(const struct jmap *map,
646                                            unsigned long *index)
647 {
648         unsigned long *val;
649         val = (unsigned long *)JudyLNext(map->judy, index,
650                                          (JError_t *)&map->err);
651         jmap_debug_add_access(map, *index, val, "jmap_nextval");
652         return val;
653 }
654 static inline unsigned long *jmap_lastval_(const struct jmap *map,
655                                            unsigned long *index)
656 {
657         unsigned long *val;
658         *index = -1;
659         val = (unsigned long *)JudyLLast(map->judy, index,
660                                          (JError_t *)&map->err);
661         jmap_debug_add_access(map, *index, val, "jmap_lastval");
662         return val;
663 }
664 static inline unsigned long *jmap_prevval_(const struct jmap *map,
665                                            unsigned long *index)
666 {
667         unsigned long *val;
668         val = (unsigned long *)JudyLPrev(map->judy, index,
669                                          (JError_t *)&map->err);
670         jmap_debug_add_access(map, *index, val, "jmap_prevval");
671         return val;
672 }
673 #endif /* CCAN_JMAP_H */