diff options
Diffstat (limited to 'libmisc/include')
| -rw-r--r-- | libmisc/include/libmisc/map.h | 148 |
1 files changed, 148 insertions, 0 deletions
diff --git a/libmisc/include/libmisc/map.h b/libmisc/include/libmisc/map.h new file mode 100644 index 0000000..f846f57 --- /dev/null +++ b/libmisc/include/libmisc/map.h @@ -0,0 +1,148 @@ +/* libmisc/map.h - A map/dict data structure + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#ifndef _LIBMISC_MAP_H_ +#define _LIBMISC_MAP_H_ + +#include <stdbool.h> +#include <stddef.h> /* for size_t */ +#include <stdint.h> /* for uint8_t */ + +#include <libmisc/linkedlist.h> + +/* Type ***********************************************************************/ + +struct _map { + size_t len; + size_t nbuckets; + lm_dll_root *buckets; + + unsigned iterating; + + size_t sizeof_kv; + size_t offsetof_k, sizeof_k; + size_t offsetof_v, sizeof_v; +}; + +/** + * MAP_DECLARE(MAPNAME, KEY_T, VAL_T) declares `struct MAPNAME`. + */ +#define MAP_DECLARE(MAPNAME, KEY_T, VAL_T) \ + struct MAPNAME { \ + struct _map core; \ + struct { \ + lm_dll_node; \ + uint8_t flags; \ + KEY_T key; \ + VAL_T val; \ + } kv_typ[0]; \ + } + +#define _map_init(M) do { \ + if (!(M)->core.sizeof_kv) { \ + (M)->core.sizeof_kv = sizeof((M)->kv_typ[0]); \ + (M)->core.sizeof_k = sizeof((M)->kv_typ[0].key); \ + (M)->core.sizeof_v = sizeof((M)->kv_typ[0].val); \ + (M)->core.offsetof_k = offsetof(typeof((M)->kv_typ[0]), key); \ + (M)->core.offsetof_v = offsetof(typeof((M)->kv_typ[0]), val); \ + } \ +} while(0) + +/* Methods ********************************************************************/ + +/** + * map_len(map) returns the number of entries currently in `map`. + */ +#define map_len(M) ((M)->core.len) + +/** + * map_load(map, key) returns a pointer to the value in `map` + * associated with `key`, or else NULL. + */ +#define map_load(M, K) ({ \ + _map_init(M); \ + typeof((M)->kv_typ[0].key) _k = K; \ + (typeof((M)->kv_typ[0].val)*)_map_load(&(M)->core, &_k); \ +}) +void *_map_load(struct _map *m, void *kp); + +/** + * map_del(map, key) ensures that `key` is not present in `map`. + * Returns whether `key` was in `map` before the call. + */ +#define map_del(M, K) ({ \ + _map_init(M); \ + typeof((M)->kv_typ[0].key) _k = K; \ + _map_del(&(M)->core, &_k); \ +}) +bool _map_del(struct _map *m, void *kp); + +/** + * map_store(map, key, val) sets a value in the map. Returns a + * pointer to the map's copy of `val`. + */ +#define map_store(M, K, ...) ({ \ + _map_init(M); \ + typeof((M)->kv_typ[0].key) _k = K; \ + typeof((M)->kv_typ[0].val) _v = __VA_ARGS__; \ + (typeof((M)->kv_typ[0].val)*)_map_store(&(M)->core, &_k, &_v); \ +}) +void *_map_store(struct _map *m, void *kp, void *vp); + +/** + * map_free(map) frees the memory associated with the map. + */ +#define map_free(M) _map_free(&(M)->core); +void _map_free(struct _map *m); + +/* Iteration ******************************************************************/ + +struct _map_kv { + lm_dll_node; + uint8_t flags; +}; + +struct _map_iter { + struct _map *m; + void *keyp; + void **valpp; + + size_t i; + struct _map_kv *kv; +}; + +/** + * MAP_FOREACH iterates over a map: + * + * MAP_FOREACH(MAP_EACH(MAP, key, valp)) { + * ... + * } + * + * It is safe to mutate the map with map_store() and, map_del() while + * iterating, but entries added by map_store() may or may not be + * visited by the iteration. + */ +#define MAP_FOREACH(M, KNAME, VNAME) _MAP_FOREACH(__COUNTER__, M, KNAME, VNAME) +#define _MAP_FOREACH(CNT, M, KNAME, VNAME) \ + for (bool _once_##CNT = true; _once_##CNT;) \ + for (typeof((M)->kv_typ[0].key) KNAME; _once_##CNT;) \ + for (typeof((M)->kv_typ[0].val) *VNAME; _once_##CNT;) \ + for ( \ + struct _map_iter _iter_##CNT = ({ \ + _map_init(M); \ + _map_iter_before(&(M)->core, &KNAME, (void**)&VNAME); \ + }); \ + _once_##CNT; \ + ({ \ + _once_##CNT = false; \ + _map_iter_after(&_iter_##CNT); \ + })) \ + while (_map_iter_next(&_iter_##CNT)) +struct _map_iter _map_iter_before(struct _map *m, void *keyp, void **valpp); +bool _map_iter_next(struct _map_iter *iter); +void _map_iter_after(struct _map_iter *iter); + +#endif /* _LIBMISC_MAP_H_ */ |