X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fintmap%2Fintmap.h;h=207b7c9d2b18f993fd3a2a7692f8146391e3f864;hb=fedf515165bfafaf4fb98252ecda1abe050c8da5;hp=f06f02d0ee599c9045c496ba7ad979d83c8b0cf0;hpb=d9e93014a999102aa1cc9979e041cd58e6aca724;p=ccan diff --git a/ccan/intmap/intmap.h b/ccan/intmap/intmap.h index f06f02d0..207b7c9d 100644 --- a/ccan/intmap/intmap.h +++ b/ccan/intmap/intmap.h @@ -11,12 +11,9 @@ /* Must be an unsigned type. */ #ifndef intmap_index_t #define intmap_index_t uint64_t +#define sintmap_index_t int64_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 * @@ -261,52 +258,173 @@ void *intmap_del_(struct intmap *map, intmap_index_t index); void intmap_clear_(struct intmap *map); /** - * uintmap_first - get first index in an unsigned intmap + * uintmap_first - get first value in an unsigned intmap * @umap: the typed intmap to iterate through. + * @indexp: a pointer to store the index. * - * Returns UINTMAP_NONE and sets errno to ENOENT if it's empty. - * Otherwise errno is set to 0. + * Returns NULL if the map is empty, otherwise populates *@indexp and + * returns the lowest entry. */ -#define uintmap_first(umap) \ - intmap_first_(uintmap_unwrap_(umap)) +#define uintmap_first(umap, indexp) \ + tcon_cast((umap), uintmap_canary, \ + intmap_first_(uintmap_unwrap_(umap), (indexp))) + +void *intmap_first_(const struct intmap *map, intmap_index_t *indexp); /** - * sintmap_first - get first index in a signed intmap + * sintmap_first - get first value in a signed intmap * @smap: the typed intmap to iterate through. + * @indexp: a pointer to store the index. * - * Returns SINTMAP_NONE and sets errno to ENOENT if it's - * empty. Otherwise errno is set to 0. + * Returns NULL if the map is empty, otherwise populates *@indexp and + * returns the lowest entry. */ -#define sintmap_first(smap) \ - SINTMAP_UNOFF(intmap_first_(sintmap_unwrap_(smap))) - -intmap_index_t intmap_first_(const struct intmap *map); +#define sintmap_first(smap, indexp) \ + tcon_cast((smap), sintmap_canary, \ + sintmap_first_(sintmap_unwrap_(smap), (indexp))) /** * 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) + * @indexp: the preceding index (may not exist) * - * Returns UINTMAP_NONE and sets errno to ENOENT if there are no - * others. Otherwise errno is set to 0. + * Returns NULL if the there is no entry > @indexp, otherwise + * populates *@indexp and returns the lowest entry > @indexp. */ -#define uintmap_after(umap, i) \ - intmap_after_(uintmap_unwrap_(umap), (i)) +#define uintmap_after(umap, indexp) \ + tcon_cast((umap), uintmap_canary, \ + intmap_after_(uintmap_unwrap_(umap), (indexp))) + +void *intmap_after_(const struct intmap *map, intmap_index_t *indexp); /** * sintmap_after - get the closest following index in a signed intmap * @smap: the typed intmap to iterate through. - * @i: the preceeding index. + * @indexp: the preceding index (may not exist) * - * Returns SINTMAP_NONE and sets errno to ENOENT if there are no - * others. Otherwise errno is set to 0. + * Returns NULL if the there is no entry > @indexp, otherwise + * populates *@indexp and returns the lowest entry > @indexp. */ -#define sintmap_after(smap, i) \ - SINTMAP_UNOFF(intmap_after_(sintmap_unwrap_(smap), SINTMAP_OFF((i)))) +#define sintmap_after(smap, indexp) \ + tcon_cast((smap), sintmap_canary, \ + sintmap_after_(sintmap_unwrap_(smap), (indexp))) -intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t i); +/** + * uintmap_last - get last value in an unsigned intmap + * @umap: the typed intmap to iterate through. + * @indexp: a pointer to store the index. + * + * Returns NULL if the map is empty, otherwise populates *@indexp and + * returns the highest entry. + */ +#define uintmap_last(umap, indexp) \ + tcon_cast((umap), uintmap_canary, \ + intmap_last_(uintmap_unwrap_(umap), (indexp))) -/* TODO: We could implement intmap_prefix, intmap_iterate... */ +void *intmap_last_(const struct intmap *map, intmap_index_t *indexp); + +/** + * sintmap_last - get last value in a signed intmap + * @smap: the typed intmap to iterate through. + * @indexp: a pointer to store the index. + * + * Returns NULL if the map is empty, otherwise populates *@indexp and + * returns the highest entry. + */ +#define sintmap_last(smap, indexp) \ + tcon_cast((smap), sintmap_canary, \ + sintmap_last_(sintmap_unwrap_(smap), (indexp))) + +/** + * uintmap_iterate - ordered iteration over an unsigned intmap + * @umap: the typed intmap to iterate through. + * @handle: the function to call. + * @arg: the argument for the function (types should match). + * + * @handle's prototype should be: + * bool @handle(intmap_index_t index, type value, typeof(arg) arg) + * + * If @handle returns false, the iteration will stop and uintmap_iterate will + * return false, otherwise uintmap_iterate will return true. + * You should not alter the map within the @handle function! + * + * Example: + * typedef UINTMAP(int *) umap_intp; + * static bool dump_some(intmap_index_t index, int *value, int *num) + * { + * // Only dump out num nodes. + * if (*(num--) == 0) + * return false; + * printf("%lu=>%i\n", (unsigned long)index, *value); + * return true; + * } + * + * static void dump_map(const umap_intp *map) + * { + * int max = 100; + * uintmap_iterate(map, dump_some, &max); + * if (max < 0) + * printf("... (truncated to 100 entries)\n"); + * } + */ +#define uintmap_iterate(map, handle, arg) \ + intmap_iterate_(tcon_unwrap(map), \ + typesafe_cb_cast(bool (*)(intmap_index_t, \ + void *, void *), \ + bool (*)(intmap_index_t, \ + tcon_type((map), \ + uintmap_canary), \ + __typeof__(arg)), (handle)), \ + (arg), 0) + +/** + * sintmap_iterate - ordered iteration over a signed intmap + * @smap: the typed intmap to iterate through. + * @handle: the function to call. + * @arg: the argument for the function (types should match). + * + * @handle's prototype should be: + * bool @handle(sintmap_index_t index, type value, typeof(arg) arg) + * + * If @handle returns false, the iteration will stop and sintmap_iterate will + * return false, otherwise sintmap_iterate will return true. + * You should not alter the map within the @handle function! + * + * Example: + * typedef SINTMAP(int *) smap_intp; + * static bool dump_some(sintmap_index_t index, int *value, int *num) + * { + * // Only dump out num nodes. + * if (*(num--) == 0) + * return false; + * printf("%li=>%i\n", (long)index, *value); + * return true; + * } + * + * static void dump_map(const smap_intp *map) + * { + * int max = 100; + * sintmap_iterate(map, dump_some, &max); + * if (max < 0) + * printf("... (truncated to 100 entries)\n"); + * } + */ +#define sintmap_iterate(map, handle, arg) \ + intmap_iterate_(tcon_unwrap(map), \ + typesafe_cb_cast(bool (*)(intmap_index_t, \ + void *, void *), \ + bool (*)(sintmap_index_t, \ + tcon_type((map), \ + sintmap_canary), \ + __typeof__(arg)), (handle)), \ + (arg), SINTMAP_OFFSET) + +bool intmap_iterate_(const struct intmap *map, + bool (*handle)(intmap_index_t, void *, void *), + void *data, + intmap_index_t offset); + +/* TODO: We could implement intmap_prefix. */ /* These make sure it really is a uintmap/sintmap */ #define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary)) @@ -317,4 +435,33 @@ intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t i); #define SINTMAP_OFF(index) ((intmap_index_t)(index) + SINTMAP_OFFSET) #define SINTMAP_UNOFF(index) ((intmap_index_t)(index) - SINTMAP_OFFSET) +/* Due to multi-evaluation, these can't be macros */ +static inline void *sintmap_first_(const struct intmap *map, + sintmap_index_t *indexp) +{ + intmap_index_t i; + void *ret = intmap_first_(map, &i); + *indexp = SINTMAP_UNOFF(i); + return ret; + +} + +static inline void *sintmap_after_(const struct intmap *map, + sintmap_index_t *indexp) +{ + intmap_index_t i = SINTMAP_OFF(*indexp); + void *ret = intmap_after_(map, &i); + *indexp = SINTMAP_UNOFF(i); + return ret; +} + +static inline void *sintmap_last_(const struct intmap *map, + sintmap_index_t *indexp) +{ + intmap_index_t i; + void *ret = intmap_last_(map, &i); + *indexp = SINTMAP_UNOFF(i); + return ret; + +} #endif /* CCAN_INTMAP_H */