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