X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fintmap%2Fintmap.h;fp=ccan%2Fintmap%2Fintmap.h;h=f06f02d0ee599c9045c496ba7ad979d83c8b0cf0;hb=d9e93014a999102aa1cc9979e041cd58e6aca724;hp=0000000000000000000000000000000000000000;hpb=3f642347378afc9e1db1768d88c9f5b2baffe9ba;p=ccan diff --git a/ccan/intmap/intmap.h b/ccan/intmap/intmap.h new file mode 100644 index 00000000..f06f02d0 --- /dev/null +++ b/ccan/intmap/intmap.h @@ -0,0 +1,320 @@ +/* CC0 license (public domain) - see LICENSE file for details */ +#ifndef CCAN_INTMAP_H +#define CCAN_INTMAP_H +#include "config.h" +#include +#include +#include +#include +#include + +/* Must be an unsigned type. */ +#ifndef intmap_index_t +#define intmap_index_t uint64_t +#endif + +/* Maximum possible values of each type */ +#define UINTMAP_NONE ((intmap_index_t)-1) +#define SINTMAP_NONE (((intmap_index_t)1 << (sizeof(intmap_index_t)*8))-1) + +/** + * struct intmap - representation of an integer map + * + * It's exposed here to allow you to embed it and so we can inline the + * trivial functions. + */ +struct intmap { + union { + struct node *n; + intmap_index_t i; + } u; + void *v; +}; + +/** + * UINTMAP - declare a type-specific intmap (for unsigned integers) + * @membertype: type for this map's values, or void * for any pointer. + * + * You use this to create your own typed intmap for a particular + * (non-NULL) pointer type. + * + * Example: + * UINTMAP(int *) uint_intmap; + * uintmap_init(&uint_intmap); + */ +#define UINTMAP(membertype) \ + TCON_WRAP(struct intmap, membertype uintmap_canary) + +/** + * SINTMAP - declare a type-specific intmap (for signed integers) + * @membertype: type for this map's values, or void * for any pointer. + * + * You use this to create your own typed intmap for a particular type. + * You can use an integer type as membertype, *but* remember you can't + * use "0" as a value! + * + * This is different from UINTMAP because we want it to sort into + * least (most negative) to largest order. + * + * Example: + * SINTMAP(int *) sint_intmap; + * sintmap_init(&sint_intmap); + */ +#define SINTMAP(membertype) \ + TCON_WRAP(struct intmap, membertype sintmap_canary) + +/** + * uintmap_init - initialize an unsigned integer map (empty) + * @umap: the typed intmap to initialize. + * + * For completeness; if you've arranged for it to be NULL already you don't + * need this. + * + * Example: + * UINTMAP(int *) uint_intmap; + * + * uintmap_init(&uint_intmap); + */ +#define uintmap_init(umap) intmap_init_(uintmap_unwrap_(umap)) + +/** + * sintmap_init - initialize a signed integer map (empty) + * @smap: the typed intmap to initialize. + * + * For completeness; if you've arranged for it to be NULL already you don't + * need this. + * + * Example: + * SINTMAP(int *) sint_intmap; + * + * sintmap_init(&sint_intmap); + */ +#define sintmap_init(smap) intmap_init_(sintmap_unwrap_(smap)) + +static inline void intmap_init_(struct intmap *map) +{ + map->u.n = NULL; + map->v = NULL; +} + +/** + * uintmap_empty - is this unsigned integer map empty? + * @umap: the typed intmap to check. + * + * Example: + * if (!uintmap_empty(&uint_intmap)) + * abort(); + */ +#define uintmap_empty(umap) intmap_empty_(uintmap_unwrap_(umap)) + +/** + * sintmap_empty - is this signed integer map empty? + * @smap: the typed intmap to check. + * + * Example: + * if (!sintmap_empty(&sint_intmap)) + * abort(); + */ +#define sintmap_empty(smap) intmap_empty_(sintmap_unwrap_(smap)) + +static inline bool intmap_empty_(const struct intmap *map) +{ + return map->v == NULL && map->u.n == NULL; +} + +/** + * uintmap_get - get a value from an unsigned integer map + * @umap: the typed intmap to search. + * @index: the unsigned index to search for. + * + * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT). + * + * Example: + * int *val = uintmap_get(&uint_intmap, 100); + * if (val) + * printf("100 => %i\n", *val); + */ +#define uintmap_get(umap, index) \ + tcon_cast((umap), uintmap_canary, \ + intmap_get_(uintmap_unwrap_(umap), (index))) + +/** + * sintmap_get - get a value from a signed integer map + * @smap: the typed intmap to search. + * @index: the signed index to search for. + * + * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT). + * + * Example: + * int *val2 = sintmap_get(&sint_intmap, -100); + * if (val2) + * printf("-100 => %i\n", *val2); + */ +#define sintmap_get(smap, index) \ + tcon_cast((smap), sintmap_canary, \ + intmap_get_(sintmap_unwrap_(smap), SINTMAP_OFF(index))) + +void *intmap_get_(const struct intmap *map, intmap_index_t index); + +/** + * uintmap_add - place a member in an unsigned integer map. + * @umap: the typed intmap to add to. + * @index: the unsigned index to place in the map. + * @value: the (non-NULL) value. + * + * This returns false if we run out of memory (errno = ENOMEM), or + * (more normally) if that index already appears in the map (EEXIST). + * + * Note that the value is not copied, just the pointer. + * + * Example: + * val = malloc(sizeof *val); + * *val = 17; + * if (!uintmap_add(&uint_intmap, 100, val)) + * printf("100 was already in the map\n"); + */ +#define uintmap_add(umap, index, value) \ + intmap_add_(uintmap_unwrap_(tcon_check((umap), uintmap_canary, \ + (value))), \ + (index), (void *)(value)) + +/** + * sintmap_add - place a member in a signed integer map. + * @smap: the typed intmap to add to. + * @index: the signed index to place in the map. + * @value: the (non-NULL) value. + * + * This returns false if we run out of memory (errno = ENOMEM), or + * (more normally) if that index already appears in the map (EEXIST). + * + * Note that the value is not copied, just the pointer. + * + * Example: + * val = malloc(sizeof *val); + * *val = 17; + * if (!sintmap_add(&sint_intmap, -100, val)) + * printf("-100 was already in the map\n"); + */ +#define sintmap_add(smap, index, value) \ + intmap_add_(sintmap_unwrap_(tcon_check((smap), sintmap_canary, \ + (value))), \ + SINTMAP_OFF(index), (void *)(value)) + +bool intmap_add_(struct intmap *map, intmap_index_t member, const void *value); + +/** + * uintmap_del - remove a member from an unsigned integer map. + * @umap: the typed intmap to delete from. + * @index: the unsigned index to remove from the map. + * + * This returns the value, or NULL if there was no value at that + * index. + * + * Example: + * if (uintmap_del(&uint_intmap, 100) == NULL) + * printf("100 was not in the map?\n"); + */ +#define uintmap_del(umap, index) \ + tcon_cast((umap), uintmap_canary, \ + intmap_del_(uintmap_unwrap_(umap), (index))) + +/** + * sintmap_del - remove a member from a signed integer map. + * @smap: the typed intmap to delete from. + * @index: the signed index to remove from the map. + * + * This returns the value, or NULL if there was no value at that + * index. + * + * Example: + * if (sintmap_del(&sint_intmap, -100) == NULL) + * printf("-100 was not in the map?\n"); + */ +#define sintmap_del(smap, index) \ + tcon_cast((smap), sintmap_canary, \ + intmap_del_(sintmap_unwrap_(smap), SINTMAP_OFF(index))) + +void *intmap_del_(struct intmap *map, intmap_index_t index); + +/** + * uintmap_clear - remove every member from an unsigned integer map. + * @umap: the typed intmap to clear. + * + * The map will be empty after this. + * + * Example: + * uintmap_clear(&uint_intmap); + */ +#define uintmap_clear(umap) intmap_clear_(uintmap_unwrap_(umap)) + +/** + * sintmap_clear - remove every member from a signed integer map. + * @smap: the typed intmap to clear. + * + * The map will be empty after this. + * + * Example: + * sintmap_clear(&sint_intmap); + */ +#define sintmap_clear(smap) intmap_clear_(sintmap_unwrap_(smap)) + +void intmap_clear_(struct intmap *map); + +/** + * uintmap_first - get first index in an unsigned intmap + * @umap: the typed intmap to iterate through. + * + * Returns UINTMAP_NONE and sets errno to ENOENT if it's empty. + * Otherwise errno is set to 0. + */ +#define uintmap_first(umap) \ + intmap_first_(uintmap_unwrap_(umap)) + +/** + * sintmap_first - get first index in a signed intmap + * @smap: the typed intmap to iterate through. + * + * Returns SINTMAP_NONE and sets errno to ENOENT if it's + * empty. Otherwise errno is set to 0. + */ +#define sintmap_first(smap) \ + SINTMAP_UNOFF(intmap_first_(sintmap_unwrap_(smap))) + +intmap_index_t intmap_first_(const struct intmap *map); + +/** + * uintmap_after - get the closest following index in an unsigned intmap + * @umap: the typed intmap to iterate through. + * @i: the preceeding index (may not exist) + * + * Returns UINTMAP_NONE and sets errno to ENOENT if there are no + * others. Otherwise errno is set to 0. + */ +#define uintmap_after(umap, i) \ + intmap_after_(uintmap_unwrap_(umap), (i)) + +/** + * sintmap_after - get the closest following index in a signed intmap + * @smap: the typed intmap to iterate through. + * @i: the preceeding index. + * + * Returns SINTMAP_NONE and sets errno to ENOENT if there are no + * others. Otherwise errno is set to 0. + */ +#define sintmap_after(smap, i) \ + SINTMAP_UNOFF(intmap_after_(sintmap_unwrap_(smap), SINTMAP_OFF((i)))) + +intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t i); + +/* TODO: We could implement intmap_prefix, intmap_iterate... */ + +/* These make sure it really is a uintmap/sintmap */ +#define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary)) +#define sintmap_unwrap_(s) (tcon_unwrap(s) + 0*tcon_sizeof((s), sintmap_canary)) + +/* We have to offset indices if they're signed, so ordering works. */ +#define SINTMAP_OFFSET ((intmap_index_t)1 << (sizeof(intmap_index_t)*8-1)) +#define SINTMAP_OFF(index) ((intmap_index_t)(index) + SINTMAP_OFFSET) +#define SINTMAP_UNOFF(index) ((intmap_index_t)(index) - SINTMAP_OFFSET) + +#endif /* CCAN_INTMAP_H */