diff options
Diffstat (limited to 'libmisc')
| -rw-r--r-- | libmisc/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | libmisc/include/libmisc/_intercept.h | 4 | ||||
| -rw-r--r-- | libmisc/include/libmisc/linkedlist.h | 108 | ||||
| -rw-r--r-- | libmisc/include/libmisc/macro.h | 13 | ||||
| -rw-r--r-- | libmisc/include/libmisc/map.h | 146 | ||||
| -rw-r--r-- | libmisc/include/libmisc/private.h | 4 | ||||
| -rw-r--r-- | libmisc/include/libmisc/rand.h | 6 | ||||
| -rw-r--r-- | libmisc/linkedlist.c | 64 | ||||
| -rw-r--r-- | libmisc/map.c | 229 | ||||
| -rw-r--r-- | libmisc/tests/test_macro.c | 1 | ||||
| -rw-r--r-- | libmisc/tests/test_map.c | 60 | ||||
| -rw-r--r-- | libmisc/tests/test_private.c | 10 |
12 files changed, 635 insertions, 15 deletions
diff --git a/libmisc/CMakeLists.txt b/libmisc/CMakeLists.txt index 70ec691..fdbe949 100644 --- a/libmisc/CMakeLists.txt +++ b/libmisc/CMakeLists.txt @@ -4,11 +4,13 @@ # SPDX-License-Identifier: AGPL-3.0-or-later add_library(libmisc INTERFACE) -target_include_directories(libmisc SYSTEM INTERFACE ${CMAKE_CURRENT_SOURCE_DIR}/include) +target_include_directories(libmisc PUBLIC INTERFACE ${CMAKE_CURRENT_SOURCE_DIR}/include) target_sources(libmisc INTERFACE assert.c intercept.c + linkedlist.c log.c + map.c ) target_compile_options(libmisc INTERFACE "$<$<COMPILE_LANGUAGE:C>:-fplan9-extensions>") @@ -18,5 +20,6 @@ add_lib_test(libmisc test_endian) add_lib_test(libmisc test_hash) add_lib_test(libmisc test_log) add_lib_test(libmisc test_macro) +add_lib_test(libmisc test_map) add_lib_test(libmisc test_private) add_lib_test(libmisc test_rand) diff --git a/libmisc/include/libmisc/_intercept.h b/libmisc/include/libmisc/_intercept.h index ab76857..a264144 100644 --- a/libmisc/include/libmisc/_intercept.h +++ b/libmisc/include/libmisc/_intercept.h @@ -13,7 +13,7 @@ * own `__lm_` wrappers that GCC/glibc won't interfere with. */ -[[format(printf, 1, 2)]] +[[gnu::format(printf, 1, 2)]] int __lm_printf(const char *format, ...); [[noreturn]] void __lm_abort(void); @@ -21,7 +21,7 @@ int __lm_printf(const char *format, ...); /* __lm_light_printf is expected to have less stack use than regular * __lm_printf, if possible. */ -[[format(printf, 1, 2)]] +[[gnu::format(printf, 1, 2)]] int __lm_light_printf(const char *format, ...); #endif /* _LIBMISC__INTERCEPT_H_ */ diff --git a/libmisc/include/libmisc/linkedlist.h b/libmisc/include/libmisc/linkedlist.h new file mode 100644 index 0000000..e8c65db --- /dev/null +++ b/libmisc/include/libmisc/linkedlist.h @@ -0,0 +1,108 @@ +/* libmisc/linkedlist.h - Singly- and doubly- linked lists + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#ifndef _LIBMISC_LINKEDLIST_H_ +#define _LIBMISC_LINKEDLIST_H_ + +/* low-level (intrusive) singly linked list ***********************************/ + +struct _slist_node { + struct _slist_node *rear; +}; + +struct _slist_root { + struct _slist_node *front, *rear; +}; + +void _slist_push_to_rear(struct _slist_root *root, struct _slist_node *node); +void _slist_pop_from_front(struct _slist_root *root); + +/* low-level (intrusive) doubly linked list ***********************************/ + +struct _dlist_node { + struct _dlist_node *front, *rear; +}; + +struct _dlist_root { + struct _dlist_node *front, *rear; +}; + +void _dlist_push_to_rear(struct _dlist_root *root, struct _dlist_node *node); +void _dlist_remove(struct _dlist_root *root, struct _dlist_node *node); +void _dlist_pop_from_front(struct _dlist_root *root); + +/* singly linked list (non-intrusive) *****************************************/ + +#define SLIST_DECLARE(NAME) \ + struct NAME##_node; \ + struct NAME { \ + struct NAME##_node *front, *rear; \ + struct NAME *_slist_root_typ[0]; \ + } + +#define SLIST_DECLARE_NODE(NAME, VAL_T) \ + struct NAME##_node { \ + struct NAME##_node *rear; \ + VAL_T val; \ + } + +#define slist_push_to_rear(ROOT, NODE) { \ + /* These temporary variables are to get the compiler to check \ + * the types. */ \ + typeof(*(ROOT)->_slist_root_typ[0]) *_rootp = ROOT; \ + typeof(*_rootp->front) *_nodep = NODE; \ + _slist_push_to_rear((struct _slist_root *)_rootp, \ + (struct _slist_node *)_nodep); \ +} while(0) + +#define slist_pop_from_front(ROOT) { \ + /* This temporary variables are to get the compiler to check \ + * the type. */ \ + typeof(*(ROOT)->_slist_root_typ[0]) *_rootp = ROOT; \ + _slist_pop_from_front((struct _slist_root *)_rootp); \ +} while(0) + +/* doubly linked list (non-intrusive) *****************************************/ + +#define DLIST_DECLARE(NAME) \ + struct NAME##_node; \ + struct NAME { \ + struct NAME##_node *front, *rear; \ + struct NAME *_dlist_root_typ[0]; \ + } + +#define DLIST_DECLARE_NODE(NAME, VAL_T) \ + struct NAME##_node { \ + struct NAME##_node *front, *rear; \ + VAL_T val; \ + } + +#define dlist_push_to_rear(ROOT, NODE) { \ + /* These temporary variables are to get the compiler to check \ + * the types. */ \ + typeof(*(ROOT)->_dlist_root_typ[0]) *_rootp = ROOT; \ + typeof(*_rootp->front) *_nodep = NODE; \ + _dlist_push_to_rear((struct _dlist_root *)_rootp, \ + (struct _dlist_node *)_nodep); \ +} while(0) + +#define dlist_remove(ROOT, NODE) { \ + /* These temporary variables are to get the compiler to check \ + * the types. */ \ + typeof(*(ROOT)->_dlist_root_typ[0]) *_rootp = ROOT; \ + typeof(*_rootp->front) *_nodep = NODE; \ + _dlist_remove((struct _dlist_root *)_rootp, \ + (struct _dlist_node *)_nodep); \ +} while(0) + +#define dlist_pop_from_front(ROOT) { \ + /* This temporary variables are to get the compiler to check \ + * the type. */ \ + typeof(*(ROOT)->_dlist_root_typ[0]) *_rootp = ROOT; \ + _dlist_pop_from_front((struct _dlist_root *)_rootp); \ +} while(0) + +#endif /* _LIBMISC_LINKEDLIST_H_ */ diff --git a/libmisc/include/libmisc/macro.h b/libmisc/include/libmisc/macro.h index b3e235c..6cb15fb 100644 --- a/libmisc/include/libmisc/macro.h +++ b/libmisc/include/libmisc/macro.h @@ -14,9 +14,20 @@ #define LM_NEVER_INLINE [[gnu::noinline]] #define LM_FLATTEN [[gnu::flatten]] -/* numeric */ +/* types */ #define LM_ARRAY_LEN(ary) (sizeof(ary)/sizeof((ary)[0])) + +#define LM_CAST_FIELD_TO_STRUCT(STRUCT_TYP, FIELD_NAME, PTR_TO_FIELD) ({ \ + /* The _fptr assignment is to get the compiler to do type checking. */ \ + typeof(((STRUCT_TYP *)NULL)->FIELD_NAME) *_fptr = (PTR_TO_FIELD); \ + _fptr \ + ? ((STRUCT_TYP*)( ((void*)_fptr) - offsetof(STRUCT_TYP, FIELD_NAME))) \ + : NULL; \ +}) + +/* numeric */ + #define LM_CEILDIV(n, d) ( ((n)+(d)-1) / (d) ) /** Return ceil(n/d) */ #define LM_ROUND_UP(n, d) ( LM_CEILDIV(n, d) * (d) ) /** Return `n` rounded up to the nearest multiple of `d` */ #define LM_ROUND_DOWN(n, d) ( ((n)/(d)) * (d) ) /** Return `n` rounded down to the nearest multiple of `d` */ diff --git a/libmisc/include/libmisc/map.h b/libmisc/include/libmisc/map.h new file mode 100644 index 0000000..41ac069 --- /dev/null +++ b/libmisc/include/libmisc/map.h @@ -0,0 +1,146 @@ +/* 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 ***********************************************************************/ + +DLIST_DECLARE(_map_kv_list); + +struct _map { + size_t len; + size_t nbuckets; + struct _map_kv_list *buckets; + + unsigned int 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##_kv { \ + uint8_t flags; \ + KEY_T key; \ + VAL_T val; \ + }; \ + DLIST_DECLARE_NODE(_##MAPNAME##_kv_list, struct _##MAPNAME##_kv); \ + struct MAPNAME { \ + struct _map core; \ + struct _##MAPNAME##_kv_list_node 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].val.key); \ + (M)->core.sizeof_v = sizeof((M)->kv_typ[0].val.val); \ + (M)->core.offsetof_k = offsetof(typeof((M)->kv_typ[0]), val.key); \ + (M)->core.offsetof_v = offsetof(typeof((M)->kv_typ[0]), val.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].val.key) _k = K; \ + (typeof((M)->kv_typ[0].val.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].val.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].val.key) _k = K; \ + typeof((M)->kv_typ[0].val.val) _v = __VA_ARGS__; \ + (typeof((M)->kv_typ[0].val.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_iter { + struct _map *m; + void *keyp; + void **valpp; + + size_t i; + struct _map_kv_list_node *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].val.key) KNAME; _once_##CNT;) \ + for (typeof((M)->kv_typ[0].val.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_ */ diff --git a/libmisc/include/libmisc/private.h b/libmisc/include/libmisc/private.h index c5382a7..5518d1f 100644 --- a/libmisc/include/libmisc/private.h +++ b/libmisc/include/libmisc/private.h @@ -11,7 +11,7 @@ #define YES LM_SENTINEL() #define IS_IMPLEMENTATION_FOR(name) LM_IS_SENTINEL(IMPLEMENTATION_FOR_##name) -#define BEGIN_PRIVATE(name) LM_IF(IS_IMPLEMENTATION_FOR(name))()(struct {) -#define END_PRIVATE(name) LM_IF(IS_IMPLEMENTATION_FOR(name))()(} LM_CAT2_(_HIDDEN_, __COUNTER__);) +#define BEGIN_PRIVATE(name) LM_IF(IS_IMPLEMENTATION_FOR(name))()(struct {) struct {} LM_CAT2_(_PRIVATE_FORCE_SEMICOLON_, __COUNTER__) +#define END_PRIVATE(name) LM_IF(IS_IMPLEMENTATION_FOR(name))(struct {} LM_CAT2_(_PRIVATE_FORCE_SEMICOLON_, __COUNTER__))(} LM_CAT2_(_PRIVATE_, __COUNTER__)) #endif /* _LIBMISC_PRIVATE_H_ */ diff --git a/libmisc/include/libmisc/rand.h b/libmisc/include/libmisc/rand.h index 8072841..7ef238b 100644 --- a/libmisc/include/libmisc/rand.h +++ b/libmisc/include/libmisc/rand.h @@ -1,6 +1,6 @@ /* libmisc/rand.h - Non-crytpographic random-number utilities * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> * SPDX-License-Identifier: AGPL-3.0-or-later */ @@ -29,14 +29,14 @@ static inline uint64_t rand_uint63n(uint64_t cnt) { uint64_t fair_cnt = ((UINT64_C(1)<<62) / cnt) * cnt; uint64_t rnd; do { - rnd = (random() << 31) | random(); + rnd = (((uint64_t)random()) << 31) | random(); } while (rnd >= fair_cnt); return rnd % cnt; } else if (cnt <= UINT64_C(1)<<63) { uint64_t fair_cnt = ((UINT64_C(1)<<63) / cnt) * cnt; uint64_t rnd; do { - rnd = (random() << 62) | (random() << 31) | random(); + rnd = (((uint64_t)random()) << 62) | (((uint64_t)random()) << 31) | random(); } while (rnd >= fair_cnt); return rnd % cnt; } diff --git a/libmisc/linkedlist.c b/libmisc/linkedlist.c new file mode 100644 index 0000000..71a0aa9 --- /dev/null +++ b/libmisc/linkedlist.c @@ -0,0 +1,64 @@ +/* libmisc/linkedlist.c - Singly- and doubly- linked lists + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <stddef.h> /* for NULL */ + +#include <libmisc/assert.h> + +#include <libmisc/linkedlist.h> + +/* singly linked list *********************************************************/ + +void _slist_push_to_rear(struct _slist_root *root, struct _slist_node *node) { + assert(root); + node->rear = NULL; + if (root->rear) + root->rear->rear = node; + else + root->front = node; + root->rear = node; +} + +void _slist_pop_from_front(struct _slist_root *root) { + assert(root); + assert(root->front); + root->front = root->front->rear; + if (!root->front) + root->rear = NULL; +} + +/* doubly linked list *********************************************************/ + +void _dlist_push_to_rear(struct _dlist_root *root, struct _dlist_node *node) { + assert(root); + assert(node); + node->front = root->rear; + node->rear = NULL; + if (root->rear) + root->rear->rear = node; + else + root->front = node; + root->rear = node; +} + +void _dlist_remove(struct _dlist_root *root, struct _dlist_node *node) { + assert(root); + assert(node); + if (node->front) + node->front->rear = node->rear; + else + root->front = node->rear; + if (node->rear) + node->rear->front = node->front; + else + root->rear = node->front; +} + +void _dlist_pop_from_front(struct _dlist_root *root) { + assert(root); + assert(root->front); + _dlist_remove(root, root->front); +} diff --git a/libmisc/map.c b/libmisc/map.c new file mode 100644 index 0000000..7629c8c --- /dev/null +++ b/libmisc/map.c @@ -0,0 +1,229 @@ +/* libmisc/map.c - A map/dict data structure + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <stdlib.h> +#include <string.h> + +#include <libmisc/hash.h> +#include <libmisc/assert.h> +#include <libmisc/map.h> + +#define FLAG_ITER (UINT8_C(1)<<0) +#define FLAG_DEL (UINT8_C(1)<<1) + +/* Internal utilities *********************************************************/ + +struct _map_kv { + uint8_t flags; + /* opaque key; */ + /* opaque val; */ +}; +DLIST_DECLARE_NODE(_map_kv_list, struct _map_kv); + +static inline void *_map_kv_keyp(struct _map *m, struct _map_kv_list_node *kv) { + assert(m); + assert(kv); + return ((void*)kv)+m->offsetof_k; +} +static inline void *_map_kv_valp(struct _map *m, struct _map_kv_list_node *kv) { + assert(m); + assert(kv); + return ((void*)kv)+m->offsetof_v; +} + +static inline void _map_lookup(struct _map *m, void *keyp, + hash_t *ret_hash, + struct _map_kv_list **ret_bucket, + struct _map_kv_list_node **ret_kv) { + assert(m); + assert(keyp); + assert(ret_hash); + assert(ret_bucket); + assert(ret_kv); + *ret_hash = hash(keyp, m->sizeof_k); + if (m->nbuckets == 0) { + *ret_bucket = NULL; + *ret_kv = NULL; + return; + } + *ret_bucket = &m->buckets[*ret_hash % m->nbuckets]; + for (struct _map_kv_list_node *kv = (*ret_bucket)->front; kv; kv = kv->rear) { + if (!(kv->val.flags & FLAG_DEL) && + memcmp(_map_kv_keyp(m, kv), keyp, m->sizeof_k) == 0) { + *ret_kv = kv; + return; + } + } + *ret_kv = NULL; +} + +static inline void _map_resize(struct _map *m, size_t new_nbuckets) { + assert(m); + assert(new_nbuckets); + struct _map_kv_list *new_buckets = calloc(new_nbuckets, sizeof(struct _map_kv_list)); + for (size_t i = 0; i < m->nbuckets; i++) { + while (m->buckets[i].front) { + struct _map_kv_list_node *kv = m->buckets[i].front; + dlist_pop_from_front(&m->buckets[i]); + hash_t h = hash(_map_kv_keyp(m, kv), m->sizeof_k); + dlist_push_to_rear(&new_buckets[h % new_nbuckets], kv); + } + } + m->nbuckets = new_nbuckets; + free(m->buckets); + m->buckets = new_buckets; +} + +static bool _map_autoresize(struct _map *m) { + assert(m); + if (m->len > (m->nbuckets * 8/10)) { + size_t nbuckets = 1; + while (m->len > (nbuckets * 8/10)) + nbuckets <<= 1; + _map_resize(m, nbuckets); + return true; + } + return false; +} + +/* Methods ********************************************************************/ + +void *_map_load(struct _map *m, void *keyp) { + assert(m); + assert(keyp); + + hash_t h; + struct _map_kv_list *bucket; + struct _map_kv_list_node *kv; + _map_lookup(m, keyp, &h, &bucket, &kv); + + if (!kv) + return NULL; + return _map_kv_valp(m, kv); +} + +bool _map_del(struct _map *m, void *keyp) { + assert(m); + assert(keyp); + + hash_t h; + struct _map_kv_list *bucket; + struct _map_kv_list_node *kv; + _map_lookup(m, keyp, &h, &bucket, &kv); + + if (!kv) + return false; + if (kv->val.flags & FLAG_ITER) { + kv->val.flags |= FLAG_DEL; + } else { + dlist_remove(bucket, kv); + free(kv); + } + m->len--; + return true; +} + +void *_map_store(struct _map *m, void *keyp, void *valp) { + assert(m); + assert(keyp); + assert(valp); + + hash_t h; + struct _map_kv_list *bucket; + struct _map_kv_list_node *old; + _map_lookup(m, keyp, &h, &bucket, &old); + + if (old) { + dlist_remove(bucket, old); + free(old); + m->len--; + } + m->len++; + if (!m->iterating && _map_autoresize(m)) { + h = hash(keyp, m->sizeof_k); + bucket = &m->buckets[h % m->nbuckets]; + } + struct _map_kv_list_node *kv = calloc(1, m->sizeof_kv); + memcpy(_map_kv_keyp(m, kv), keyp, m->sizeof_k); + memcpy(_map_kv_valp(m, kv), valp, m->sizeof_v); + dlist_push_to_rear(bucket, kv); + return _map_kv_valp(m, kv); +} + +void _map_free(struct _map *m) { + assert(m); + + for (size_t i = 0; i < m->nbuckets; i++) { + while (m->buckets[i].front) { + struct _map_kv_list_node *kv = m->buckets[i].front; + dlist_pop_from_front(&m->buckets[i]); + free(kv); + } + } + free(m->buckets); + m->len = 0; + m->nbuckets = 0; + m->buckets = NULL; +} + +/* Iteration ******************************************************************/ + +struct _map_iter _map_iter_before(struct _map *m, void *keyp, void **valpp) { + assert(m); + assert(keyp); + assert(valpp); + + struct _map_iter state = { + .m = m, + .keyp = keyp, + .valpp = valpp, + }; + m->iterating++; + return state; +} + +void _map_iter_after(struct _map_iter *state) { + assert(state); + assert(state->m); + + state->m->iterating--; + if (!state->m->iterating) + _map_autoresize(state->m); +} + +bool _map_iter_next(struct _map_iter *state) { + assert(state); + assert(state->m); + assert(state->valpp); + + if (!state->kv) { + if (!state->m->len) + return false; + while (!state->m->buckets[state->i].front) + state->i++; + state->kv = state->m->buckets[state->i].front; + } else { + struct _map_kv_list_node *old_kv = state->kv; + state->kv = old_kv->rear; + + old_kv->val.flags &= ~FLAG_ITER; + if (old_kv->val.flags & FLAG_DEL) { + dlist_remove(&state->m->buckets[state->i], old_kv); + free(old_kv); + } + + while (!state->kv) { + state->i++; + if (state->i == state->m->nbuckets) + return false; + state->kv = state->m->buckets[state->i].front; + } + } + state->kv->val.flags |= FLAG_ITER; + memcpy(state->keyp, _map_kv_keyp(state->m, state->kv), state->m->sizeof_k); + *(state->valpp) = _map_kv_valp(state->m, state->kv); + return true; +} diff --git a/libmisc/tests/test_macro.c b/libmisc/tests/test_macro.c index 69655d1..1320eb3 100644 --- a/libmisc/tests/test_macro.c +++ b/libmisc/tests/test_macro.c @@ -27,7 +27,6 @@ int main() { /* ... */ test_assert(LM_NEXT_POWER_OF_2(0x8000000000000000-1) == 0x8000000000000000); /* Valid up to 0x8000000000000000-1 = (1<<63)-1 */ - test_assert(LM_NEXT_POWER_OF_2(0x8000000000000000) == 0); /* :( */ printf("== LM_FLOORLOG2 ===========================================\n"); /* valid down to 1. */ diff --git a/libmisc/tests/test_map.c b/libmisc/tests/test_map.c new file mode 100644 index 0000000..855dace --- /dev/null +++ b/libmisc/tests/test_map.c @@ -0,0 +1,60 @@ +/* libmisc/tests/test_map.c - Tests for <libmisc/map.h> + * + * Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libmisc/map.h> + +#include "test.h" + +MAP_DECLARE(intmap, int, int); + +int main() { + struct intmap m = {}; + test_assert(map_len(&m) == 0); + + int *v = map_store(&m, 3, 8); + test_assert(v && *v == 8); + test_assert(map_len(&m) == 1); + + v = map_load(&m, 3); + test_assert(v); + test_assert(*v == 8); + + v = NULL; + + test_assert(map_del(&m, 3)); + test_assert(map_len(&m) == 0); + test_assert(!map_del(&m, 3)); + + map_store(&m, 1, 11); + map_store(&m, 2, 12); + map_store(&m, 3, 13); + test_assert(map_len(&m) == 3); + bool seen_1 = false, seen_2 = false, seen_3 = false; + MAP_FOREACH(&m, ik, iv) { + switch (ik) { + case 1: seen_1 = true; break; + case 2: seen_2 = true; break; + case 3: seen_3 = true; break; + } + switch (ik) { + case 1: case 2: case 3: + map_store(&m, ik+20, (*iv)+20); + test_assert(map_del(&m, ik)); + test_assert(!map_del(&m, ik)); + test_assert(map_load(&m, ik) == NULL); + break; + } + } + test_assert(map_len(&m) == 3); + test_assert(seen_1); v = map_load(&m, 21); test_assert(v && *v == 31); v = map_load(&m, 1); test_assert(!v); + test_assert(seen_2); v = map_load(&m, 22); test_assert(v && *v == 32); v = map_load(&m, 2); test_assert(!v); + test_assert(seen_3); v = map_load(&m, 23); test_assert(v && *v == 33); v = map_load(&m, 3); test_assert(!v); + + map_free(&m); + test_assert(map_len(&m) == 0); + + return 0; +} diff --git a/libmisc/tests/test_private.c b/libmisc/tests/test_private.c index 7aaf1ee..024dddb 100644 --- a/libmisc/tests/test_private.c +++ b/libmisc/tests/test_private.c @@ -1,6 +1,6 @@ /* libmisc/tests/test_private.c - Tests for <libmisc/private.h> * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> * SPDX-License-Identifier: AGPL-3.0-or-later */ @@ -8,18 +8,18 @@ struct a { int foo; - BEGIN_PRIVATE(A) + BEGIN_PRIVATE(A); int bar; - END_PRIVATE(A) + END_PRIVATE(A); }; #define IMPLEMENTATION_FOR_B YES struct b { int foo; - BEGIN_PRIVATE(B) + BEGIN_PRIVATE(B); int bar; - END_PRIVATE(B) + END_PRIVATE(B); }; int main() { |