1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
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_ */
|
