f06f02d0ee599c9045c496ba7ad979d83c8b0cf0
[ccan] / ccan / intmap / intmap.h
1 /* CC0 license (public domain) - see LICENSE file for details */
2 #ifndef CCAN_INTMAP_H
3 #define CCAN_INTMAP_H
4 #include "config.h"
5 #include <ccan/tcon/tcon.h>
6 #include <ccan/typesafe_cb/typesafe_cb.h>
7 #include <inttypes.h>
8 #include <stdlib.h>
9 #include <stdbool.h>
10
11 /* Must be an unsigned type. */
12 #ifndef intmap_index_t
13 #define intmap_index_t uint64_t
14 #endif
15
16 /* Maximum possible values of each type */
17 #define UINTMAP_NONE ((intmap_index_t)-1)
18 #define SINTMAP_NONE (((intmap_index_t)1 << (sizeof(intmap_index_t)*8))-1)
19
20 /**
21  * struct intmap - representation of an integer map
22  *
23  * It's exposed here to allow you to embed it and so we can inline the
24  * trivial functions.
25  */
26 struct intmap {
27         union {
28                 struct node *n;
29                 intmap_index_t i;
30         } u;
31         void *v;
32 };
33
34 /**
35  * UINTMAP - declare a type-specific intmap (for unsigned integers)
36  * @membertype: type for this map's values, or void * for any pointer.
37  *
38  * You use this to create your own typed intmap for a particular
39  * (non-NULL) pointer type.
40  *
41  * Example:
42  *      UINTMAP(int *) uint_intmap;
43  *      uintmap_init(&uint_intmap);
44  */
45 #define UINTMAP(membertype)                                     \
46         TCON_WRAP(struct intmap, membertype uintmap_canary)
47
48 /**
49  * SINTMAP - declare a type-specific intmap (for signed integers)
50  * @membertype: type for this map's values, or void * for any pointer.
51  *
52  * You use this to create your own typed intmap for a particular type.
53  * You can use an integer type as membertype, *but* remember you can't
54  * use "0" as a value!
55  *
56  * This is different from UINTMAP because we want it to sort into
57  * least (most negative) to largest order.
58  *
59  * Example:
60  *      SINTMAP(int *) sint_intmap;
61  *      sintmap_init(&sint_intmap);
62  */
63 #define SINTMAP(membertype)                                     \
64         TCON_WRAP(struct intmap, membertype sintmap_canary)
65
66 /**
67  * uintmap_init - initialize an unsigned integer map (empty)
68  * @umap: the typed intmap to initialize.
69  *
70  * For completeness; if you've arranged for it to be NULL already you don't
71  * need this.
72  *
73  * Example:
74  *      UINTMAP(int *) uint_intmap;
75  *
76  *      uintmap_init(&uint_intmap);
77  */
78 #define uintmap_init(umap) intmap_init_(uintmap_unwrap_(umap))
79
80 /**
81  * sintmap_init - initialize a signed integer map (empty)
82  * @smap: the typed intmap to initialize.
83  *
84  * For completeness; if you've arranged for it to be NULL already you don't
85  * need this.
86  *
87  * Example:
88  *      SINTMAP(int *) sint_intmap;
89  *
90  *      sintmap_init(&sint_intmap);
91  */
92 #define sintmap_init(smap) intmap_init_(sintmap_unwrap_(smap))
93
94 static inline void intmap_init_(struct intmap *map)
95 {
96         map->u.n = NULL;
97         map->v = NULL;
98 }
99
100 /**
101  * uintmap_empty - is this unsigned integer map empty?
102  * @umap: the typed intmap to check.
103  *
104  * Example:
105  *      if (!uintmap_empty(&uint_intmap))
106  *              abort();
107  */
108 #define uintmap_empty(umap) intmap_empty_(uintmap_unwrap_(umap))
109
110 /**
111  * sintmap_empty - is this signed integer map empty?
112  * @smap: the typed intmap to check.
113  *
114  * Example:
115  *      if (!sintmap_empty(&sint_intmap))
116  *              abort();
117  */
118 #define sintmap_empty(smap) intmap_empty_(sintmap_unwrap_(smap))
119
120 static inline bool intmap_empty_(const struct intmap *map)
121 {
122         return map->v == NULL && map->u.n == NULL;
123 }
124
125 /**
126  * uintmap_get - get a value from an unsigned integer map
127  * @umap: the typed intmap to search.
128  * @index: the unsigned index to search for.
129  *
130  * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
131  *
132  * Example:
133  *      int *val = uintmap_get(&uint_intmap, 100);
134  *      if (val)
135  *              printf("100 => %i\n", *val);
136  */
137 #define uintmap_get(umap, index)                                        \
138         tcon_cast((umap), uintmap_canary,                               \
139                       intmap_get_(uintmap_unwrap_(umap), (index)))
140
141 /**
142  * sintmap_get - get a value from a signed integer map
143  * @smap: the typed intmap to search.
144  * @index: the signed index to search for.
145  *
146  * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
147  *
148  * Example:
149  *      int *val2 = sintmap_get(&sint_intmap, -100);
150  *      if (val2)
151  *              printf("-100 => %i\n", *val2);
152  */
153 #define sintmap_get(smap, index)                                        \
154         tcon_cast((smap), sintmap_canary,                               \
155                   intmap_get_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
156
157 void *intmap_get_(const struct intmap *map, intmap_index_t index);
158
159 /**
160  * uintmap_add - place a member in an unsigned integer map.
161  * @umap: the typed intmap to add to.
162  * @index: the unsigned index to place in the map.
163  * @value: the (non-NULL) value.
164  *
165  * This returns false if we run out of memory (errno = ENOMEM), or
166  * (more normally) if that index already appears in the map (EEXIST).
167  *
168  * Note that the value is not copied, just the pointer.
169  *
170  * Example:
171  *      val = malloc(sizeof *val);
172  *      *val = 17;
173  *      if (!uintmap_add(&uint_intmap, 100, val))
174  *              printf("100 was already in the map\n");
175  */
176 #define uintmap_add(umap, index, value)                                 \
177         intmap_add_(uintmap_unwrap_(tcon_check((umap), uintmap_canary,  \
178                                                (value))),               \
179                     (index), (void *)(value))
180
181 /**
182  * sintmap_add - place a member in a signed integer map.
183  * @smap: the typed intmap to add to.
184  * @index: the signed index to place in the map.
185  * @value: the (non-NULL) value.
186  *
187  * This returns false if we run out of memory (errno = ENOMEM), or
188  * (more normally) if that index already appears in the map (EEXIST).
189  *
190  * Note that the value is not copied, just the pointer.
191  *
192  * Example:
193  *      val = malloc(sizeof *val);
194  *      *val = 17;
195  *      if (!sintmap_add(&sint_intmap, -100, val))
196  *              printf("-100 was already in the map\n");
197  */
198 #define sintmap_add(smap, index, value)                                 \
199         intmap_add_(sintmap_unwrap_(tcon_check((smap), sintmap_canary,  \
200                                                (value))),               \
201                     SINTMAP_OFF(index), (void *)(value))
202
203 bool intmap_add_(struct intmap *map, intmap_index_t member, const void *value);
204
205 /**
206  * uintmap_del - remove a member from an unsigned integer map.
207  * @umap: the typed intmap to delete from.
208  * @index: the unsigned index to remove from the map.
209  *
210  * This returns the value, or NULL if there was no value at that
211  * index.
212  *
213  * Example:
214  *      if (uintmap_del(&uint_intmap, 100) == NULL)
215  *              printf("100 was not in the map?\n");
216  */
217 #define uintmap_del(umap, index)                                        \
218         tcon_cast((umap), uintmap_canary,                               \
219                   intmap_del_(uintmap_unwrap_(umap), (index)))
220
221 /**
222  * sintmap_del - remove a member from a signed integer map.
223  * @smap: the typed intmap to delete from.
224  * @index: the signed index to remove from the map.
225  *
226  * This returns the value, or NULL if there was no value at that
227  * index.
228  *
229  * Example:
230  *      if (sintmap_del(&sint_intmap, -100) == NULL)
231  *              printf("-100 was not in the map?\n");
232  */
233 #define sintmap_del(smap, index)                                        \
234         tcon_cast((smap), sintmap_canary,                               \
235                   intmap_del_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
236
237 void *intmap_del_(struct intmap *map, intmap_index_t index);
238
239 /**
240  * uintmap_clear - remove every member from an unsigned integer map.
241  * @umap: the typed intmap to clear.
242  *
243  * The map will be empty after this.
244  *
245  * Example:
246  *      uintmap_clear(&uint_intmap);
247  */
248 #define uintmap_clear(umap) intmap_clear_(uintmap_unwrap_(umap))
249
250 /**
251  * sintmap_clear - remove every member from a signed integer map.
252  * @smap: the typed intmap to clear.
253  *
254  * The map will be empty after this.
255  *
256  * Example:
257  *      sintmap_clear(&sint_intmap);
258  */
259 #define sintmap_clear(smap) intmap_clear_(sintmap_unwrap_(smap))
260
261 void intmap_clear_(struct intmap *map);
262
263 /**
264  * uintmap_first - get first index in an unsigned intmap
265  * @umap: the typed intmap to iterate through.
266  *
267  * Returns UINTMAP_NONE and sets errno to ENOENT if it's empty.
268  * Otherwise errno is set to 0.
269  */
270 #define uintmap_first(umap)                     \
271         intmap_first_(uintmap_unwrap_(umap))
272
273 /**
274  * sintmap_first - get first index in a signed intmap
275  * @smap: the typed intmap to iterate through.
276  *
277  * Returns SINTMAP_NONE and sets errno to ENOENT if it's
278  * empty.  Otherwise errno is set to 0.
279  */
280 #define sintmap_first(smap)                                     \
281         SINTMAP_UNOFF(intmap_first_(sintmap_unwrap_(smap)))
282
283 intmap_index_t intmap_first_(const struct intmap *map);
284
285 /**
286  * uintmap_after - get the closest following index in an unsigned intmap
287  * @umap: the typed intmap to iterate through.
288  * @i: the preceeding index (may not exist)
289  *
290  * Returns UINTMAP_NONE and sets errno to ENOENT if there are no
291  * others.  Otherwise errno is set to 0.
292  */
293 #define uintmap_after(umap, i)                          \
294         intmap_after_(uintmap_unwrap_(umap), (i))
295
296 /**
297  * sintmap_after - get the closest following index in a signed intmap
298  * @smap: the typed intmap to iterate through.
299  * @i: the preceeding index.
300  *
301  * Returns SINTMAP_NONE and sets errno to ENOENT if there are no
302  * others.  Otherwise errno is set to 0.
303  */
304 #define sintmap_after(smap, i)                                          \
305         SINTMAP_UNOFF(intmap_after_(sintmap_unwrap_(smap), SINTMAP_OFF((i))))
306
307 intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t i);
308
309 /* TODO: We could implement intmap_prefix, intmap_iterate... */
310
311 /* These make sure it really is a uintmap/sintmap */
312 #define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary))
313 #define sintmap_unwrap_(s) (tcon_unwrap(s) + 0*tcon_sizeof((s), sintmap_canary))
314
315 /* We have to offset indices if they're signed, so ordering works. */
316 #define SINTMAP_OFFSET          ((intmap_index_t)1 << (sizeof(intmap_index_t)*8-1))
317 #define SINTMAP_OFF(index)      ((intmap_index_t)(index) + SINTMAP_OFFSET)
318 #define SINTMAP_UNOFF(index)    ((intmap_index_t)(index) - SINTMAP_OFFSET)
319
320 #endif /* CCAN_INTMAP_H */