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
|
/* lib9p/map.h - A really dumb map/dict data structur
*
* Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com>
* SPDX-Licence-Identifier: AGPL-3.0-or-later
*/
#include "internal.h"
/**
* `#define` `NAME`, `KEY_T`, `VAL_T`, and `CAP`; then `#include
* "map.h".
*/
#ifndef NAME
#error NAME must be defined
#endif
#ifndef KEY_T
#error KEY_T must be defined
#endif
#ifndef VAL_T
#error VAL_T must be defined
#endif
#ifndef CAP
#error CAP must be defined
#endif
#ifndef MAP_KEY
#define MAP_KV(TNAME) CAT3(_,TNAME,_kv)
#define MAP_METHOD(TNAME, MNAME) CAT3(TNAME,_,MNAME)
#define MAP_FOREACH(m, k, v) \
for (size_t i = 0; i < ARRAY_LEN((m)->items); i++) \
if ( ({ k = (m)->items[i].key; v = &(m)->items[i].val; (m)->items[i].set; }) )
#endif
/* This implementation is just an array that we brute-force search
* over for a slot. I don't want to use the heap, which means
* statically-sized maps, and I'm probably going to choose a low
* static size, so this is fine. */
struct MAP_KV(NAME) {
bool set;
KEY_T key;
VAL_T val;
};
struct NAME {
size_t len;
struct MAP_KV(NAME) items[CAP];
};
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-function"
/**
* Load an item from the map; return a pointer to the in-map value, or
* NULL if the item is not in the map.
*/
static VAL_T *MAP_METHOD(NAME,load)(struct NAME *m, KEY_T k) {
if (!m->len)
return NULL;
for (size_t i = 0; i < ARRAY_LEN(m->items); i++)
if (m->items[i].set && m->items[i].key == k)
return &(m->items[i].val);
return NULL;
}
/**
* Store an item into the map, perhaps replacing an existing value.
* Return a pointer to the in-map value, or NULL if the map is full.
*/
static VAL_T *MAP_METHOD(NAME,store)(struct NAME *m, KEY_T k, VAL_T v) {
VAL_T *old = MAP_METHOD(NAME,load)(m, k);
if (old) {
*old = v;
return old;
}
if (m->len == ARRAY_LEN(m->items))
return NULL;
for (size_t i = 0; i < ARRAY_LEN(m->items); i++)
if (!m->items[i].set) {
m->len++;
m->items[i].set = true;
m->items[i].key = k;
m->items[i].val = v;
return &(m->items[i].val);
}
__builtin_unreachable();
}
/**
* Delete an item from the map. Returns true if an item was deleted,
* false if no such item was in the map.
*/
static bool MAP_METHOD(NAME,del)(struct NAME *m, KEY_T k) {
if (!m->len)
return NULL;
for (size_t i = 0; i < ARRAY_LEN(m->items); i++)
if (m->items[i].set && m->items[i].key == k) {
m->items[i].set = false;
m->len--;
return true;
}
return false;
}
#pragma GCC diagnostic pop
#undef NAME
#undef KEY_T
#undef VAL_T
#undef CAP
/* Keep the linter happy. */
#ifndef _LIB9P_MAP_H_
#define _LIB9P_MAP_H_
#endif /* _LIB9P_MAP_H_ */
|
