summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib9p/map.h114
-rw-r--r--lib9p/srv.c107
-rw-r--r--libmisc/CMakeLists.txt2
-rw-r--r--libmisc/include/libmisc/map.h148
-rw-r--r--libmisc/map.c224
-rw-r--r--libmisc/tests/test_map.c60
6 files changed, 480 insertions, 175 deletions
diff --git a/lib9p/map.h b/lib9p/map.h
deleted file mode 100644
index c5eab0f..0000000
--- a/lib9p/map.h
+++ /dev/null
@@ -1,114 +0,0 @@
-/* lib9p/map.h - A really dumb map/dict data structure
- *
- * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com>
- * SPDX-License-Identifier: AGPL-3.0-or-later
- */
-
-/**
- * `#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) LM_CAT3(_,TNAME,_kv)
-#define MAP_METHOD(TNAME, MNAME) LM_CAT3(TNAME,_,MNAME)
-#define MAP_FOREACH(m, k, v) \
- for (size_t i = 0; i < LM_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 < LM_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 == LM_ARRAY_LEN(m->items))
- return NULL;
- for (size_t i = 0; i < LM_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);
- }
- assert_notreached("should have returned from inside for() loop");
-}
-
-/**
- * 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 < LM_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_ */
diff --git a/lib9p/srv.c b/lib9p/srv.c
index 1e52609..5660f08 100644
--- a/lib9p/srv.c
+++ b/lib9p/srv.c
@@ -19,6 +19,7 @@
#include <libcr_ipc/mutex.h>
#include <libmisc/assert.h>
#include <libmisc/endian.h>
+#include <libmisc/map.h>
#include <libhw/generic/net.h>
#define LOG_NAME 9P_SRV
@@ -79,12 +80,7 @@ struct srv_pathinfo {
unsigned int io_refcount;
};
-#define NAME pathmap
-#define KEY_T srv_path_t
-#define VAL_T struct srv_pathinfo
-/* ( naive ) + ( working space for walk() ) */
-#define CAP ( (CONFIG_9P_SRV_MAX_FIDS*CONFIG_9P_SRV_MAX_DEPTH) + (CONFIG_9P_SRV_MAX_REQS*2) )
-#include "map.h"
+MAP_DECLARE(pathmap, srv_path_t, struct srv_pathinfo);
#define FIDFLAG_OPEN_R (1<<0)
#define FIDFLAG_OPEN_W (1<<1)
@@ -106,17 +102,8 @@ struct _srv_fidinfo {
};
};
-#define NAME fidmap
-#define KEY_T lib9p_fid_t
-#define VAL_T struct _srv_fidinfo
-#define CAP CONFIG_9P_SRV_MAX_FIDS
-#include "map.h"
-
-#define NAME reqmap
-#define KEY_T lib9p_tag_t
-#define VAL_T struct _lib9p_srv_req *
-#define CAP CONFIG_9P_SRV_MAX_REQS
-#include "map.h"
+MAP_DECLARE(fidmap, lib9p_fid_t, struct _srv_fidinfo);
+MAP_DECLARE(reqmap, lib9p_tag_t, struct _lib9p_srv_req *);
/* The hierarchy of concepts is:
*
@@ -330,15 +317,18 @@ void lib9p_srv_read(struct lib9p_srv *srv, lo_interface net_stream_conn _conn) {
/* ...but usually in another coroutine. */
_lib9p_srv_reqch_send_req(&srv->_reqch, &req);
}
- if (sess.reqs.len == 0)
+ if (map_len(&sess.reqs) == 0)
io_close(conn.fd);
else {
io_close_read(conn.fd);
sess.closing = true;
cr_pause_and_yield();
- assert(sess.reqs.len == 0);
+ assert(map_len(&sess.reqs) == 0);
io_close_write(conn.fd);
}
+ map_free(&sess.paths);
+ map_free(&sess.fids);
+ map_free(&sess.reqs);
}
/* write coroutine ************************************************************/
@@ -364,7 +354,8 @@ void lib9p_srv_worker_loop(struct lib9p_srv *srv) {
* stack to our stack. */
req = *rpc_handle.req;
/* Record that we have it. */
- reqmap_store(&req.parent_sess->reqs, req.tag, &req);
+ struct _lib9p_srv_req **reqpp = map_store(&req.parent_sess->reqs, req.tag, &req);
+ assert(reqpp && *reqpp == &req);
/* Notify the reader coroutine that we're done with
* its data. */
_lib9p_srv_reqch_send_resp(rpc_handle, 0);
@@ -375,8 +366,8 @@ void lib9p_srv_worker_loop(struct lib9p_srv *srv) {
/* Release resources. ****************************************/
while (_lib9p_srv_flushch_can_send(&req.ctx._flushch))
_lib9p_srv_flushch_send(&req.ctx._flushch, false);
- reqmap_del(&req.parent_sess->reqs, req.tag);
- if (req.parent_sess->closing && !req.parent_sess->reqs.len)
+ map_del(&req.parent_sess->reqs, req.tag);
+ if (req.parent_sess->closing && !map_len(&req.parent_sess->reqs))
cr_unpause(req.parent_sess->parent_conn->reader);
}
}
@@ -494,11 +485,11 @@ static inline struct srv_pathinfo *srv_util_pathsave(struct _lib9p_srv_req *ctx,
assert(!LO_IS_NULL(file));
struct lib9p_qid qid = LO_CALL(file, qid);
- struct srv_pathinfo *pathinfo = pathmap_load(&ctx->parent_sess->paths, qid.path);
+ struct srv_pathinfo *pathinfo = map_load(&ctx->parent_sess->paths, qid.path);
if (pathinfo)
assert(LO_EQ(pathinfo->file, file));
else {
- pathinfo = pathmap_store(&ctx->parent_sess->paths, qid.path,
+ pathinfo = map_store(&ctx->parent_sess->paths, qid.path,
(struct srv_pathinfo){
.file = file,
.parent_dir = parent_path,
@@ -507,7 +498,7 @@ static inline struct srv_pathinfo *srv_util_pathsave(struct _lib9p_srv_req *ctx,
});
assert(pathinfo);
if (parent_path != qid.path) {
- struct srv_pathinfo *parent = pathmap_load(&ctx->parent_sess->paths, parent_path);
+ struct srv_pathinfo *parent = map_load(&ctx->parent_sess->paths, parent_path);
assert(parent);
parent->gc_refcount++;
}
@@ -523,14 +514,14 @@ static inline struct srv_pathinfo *srv_util_pathsave(struct _lib9p_srv_req *ctx,
static inline void srv_util_pathfree(struct _lib9p_srv_req *ctx, srv_path_t path) {
assert(ctx);
- struct srv_pathinfo *pathinfo = pathmap_load(&ctx->parent_sess->paths, path);
+ struct srv_pathinfo *pathinfo = map_load(&ctx->parent_sess->paths, path);
assert(pathinfo);
pathinfo->gc_refcount--;
if (pathinfo->gc_refcount == 0) {
if (pathinfo->parent_dir != path)
srv_util_pathfree(ctx, pathinfo->parent_dir);
LO_CALL(pathinfo->file, free);
- pathmap_del(&ctx->parent_sess->paths, path);
+ map_del(&ctx->parent_sess->paths, path);
}
}
@@ -548,13 +539,14 @@ static inline struct _srv_fidinfo *srv_util_fidsave(struct _lib9p_srv_req *ctx,
assert(ctx);
assert(fid != LIB9P_FID_NOFID);
assert(pathinfo);
+ infof("pathinfo=%p", pathinfo);
struct lib9p_qid qid = LO_CALL(pathinfo->file, qid);
- struct _srv_fidinfo *fidinfo = fidmap_load(&ctx->parent_sess->fids, fid);
+ struct _srv_fidinfo *fidinfo = map_load(&ctx->parent_sess->fids, fid);
if (fidinfo) {
if (overwrite) {
- struct srv_pathinfo *old_pathinfo = pathmap_load(&ctx->parent_sess->paths, fidinfo->path);
+ struct srv_pathinfo *old_pathinfo = map_load(&ctx->parent_sess->paths, fidinfo->path);
assert(old_pathinfo);
if (srv_util_pathisdir(old_pathinfo)) {
if (!LO_IS_NULL(fidinfo->dir.io))
@@ -570,12 +562,8 @@ static inline struct _srv_fidinfo *srv_util_fidsave(struct _lib9p_srv_req *ctx,
return NULL;
}
} else {
- fidinfo = fidmap_store(&ctx->parent_sess->fids, fid, (struct _srv_fidinfo){});
- if (!fidinfo) {
- lib9p_error(&ctx->ctx.basectx,
- LINUX_EMFILE, "too many open files");
- return NULL;
- }
+ fidinfo = map_store(&ctx->parent_sess->fids, fid, (struct _srv_fidinfo){});
+ assert(fidinfo);
}
*fidinfo = (struct _srv_fidinfo){
.path = qid.path,
@@ -624,25 +612,22 @@ static void handle_Tversion(struct _lib9p_srv_req *ctx,
: req->max_msg_size;
/* Close the old session. */
- if (ctx->parent_sess->reqs.len) {
+ if (map_len(&ctx->parent_sess->reqs)) {
/* Flush all in-progress requests, and wait for them
* to finish. */
- struct cr_select_arg *list = alloca(sizeof(struct cr_select_arg) * ctx->parent_sess->reqs.len);
- while (ctx->parent_sess->reqs.len) {
- uint16_t tag [[gnu::unused]];
- struct _lib9p_srv_req **reqpp;
+ struct cr_select_arg *list = alloca(sizeof(struct cr_select_arg) * map_len(&ctx->parent_sess->reqs));
+ while (map_len(&ctx->parent_sess->reqs)) {
size_t i = 0;
bool flushed;
MAP_FOREACH(&ctx->parent_sess->reqs, tag, reqpp) {
list[i] = CR_SELECT_RECV(&((*reqpp)->ctx._flushch), &flushed);
}
+ assert(i == map_len(&ctx->parent_sess->reqs));
cr_select_v(i, list);
}
}
- if (ctx->parent_sess->fids.len) {
+ if (map_len(&ctx->parent_sess->fids)) {
/* Close all FIDs. */
- uint32_t fid;
- struct _srv_fidinfo *fidinfo [[gnu::unused]];
MAP_FOREACH(&ctx->parent_sess->fids, fid, fidinfo) {
handle_Tclunk(ctx,
&(struct lib9p_msg_Tclunk){.fid = fid},
@@ -687,7 +672,7 @@ static void handle_Tattach(struct _lib9p_srv_req *ctx,
if (srv->auth) {
/*
- struct lib9p_srv_filehandle *fh = fidmap_get(req->afid);
+ struct lib9p_srv_filehandle *fh = map_get(req->afid);
if (!fh)
lib9p_error(&ctx->ctx.basectx,
LINUX_EACCES, "FID provided as auth-file is not a valid FID");
@@ -755,7 +740,7 @@ static void handle_Tflush(struct _lib9p_srv_req *ctx,
struct lib9p_msg_Rflush *resp) {
util_handler_common(ctx, req, resp);
- struct _lib9p_srv_req **oldreqp = reqmap_load(&ctx->parent_sess->reqs, req->oldtag);
+ struct _lib9p_srv_req **oldreqp = map_load(&ctx->parent_sess->reqs, req->oldtag);
if (oldreqp)
_lib9p_srv_flushch_recv(&((*oldreqp)->ctx._flushch));
}
@@ -771,14 +756,14 @@ static void handle_Twalk(struct _lib9p_srv_req *ctx,
return;
}
- struct _srv_fidinfo *fidinfo = fidmap_load(&ctx->parent_sess->fids, req->fid);
+ struct _srv_fidinfo *fidinfo = map_load(&ctx->parent_sess->fids, req->fid);
if (!fidinfo) {
lib9p_errorf(&ctx->ctx.basectx,
LINUX_EBADF, "bad file number %"PRIu32, req->fid);
return;
}
- struct srv_pathinfo *pathinfo = pathmap_load(&ctx->parent_sess->paths, fidinfo->path);
+ struct srv_pathinfo *pathinfo = map_load(&ctx->parent_sess->paths, fidinfo->path);
assert(pathinfo);
pathinfo->gc_refcount++;
@@ -786,7 +771,7 @@ static void handle_Twalk(struct _lib9p_srv_req *ctx,
for (resp->nwqid = 0; resp->nwqid < req->nwname; resp->nwqid++) {
struct srv_pathinfo *new_pathinfo;
if (lib9p_str_eq(req->wname[resp->nwqid], lib9p_str(".."))) {
- new_pathinfo = pathmap_load(&ctx->parent_sess->paths, pathinfo->parent_dir);
+ new_pathinfo = map_load(&ctx->parent_sess->paths, pathinfo->parent_dir);
assert(new_pathinfo);
new_pathinfo->gc_refcount++;
} else {
@@ -838,7 +823,7 @@ static void handle_Topen(struct _lib9p_srv_req *ctx,
util_handler_common(ctx, req, resp);
/* Check that the FID is valid for this. */
- struct _srv_fidinfo *fidinfo = fidmap_load(&ctx->parent_sess->fids, req->fid);
+ struct _srv_fidinfo *fidinfo = map_load(&ctx->parent_sess->fids, req->fid);
if (!fidinfo) {
lib9p_errorf(&ctx->ctx.basectx,
LINUX_EBADF, "bad file number %"PRIu32, req->fid);
@@ -849,7 +834,7 @@ static void handle_Topen(struct _lib9p_srv_req *ctx,
LINUX_EALREADY, "FID is already open");
return;
}
- struct srv_pathinfo *pathinfo = pathmap_load(&ctx->parent_sess->paths, fidinfo->path);
+ struct srv_pathinfo *pathinfo = map_load(&ctx->parent_sess->paths, fidinfo->path);
assert(pathinfo);
if (srv_util_pathisdir(pathinfo)) {
if ( ((req->mode & LIB9P_O_MODE_MASK) != LIB9P_O_MODE_READ) ||
@@ -867,7 +852,7 @@ static void handle_Topen(struct _lib9p_srv_req *ctx,
/* Check permissions. */
if (reqmode & LIB9P_O_RCLOSE) {
- struct srv_pathinfo *parent = pathmap_load(&ctx->parent_sess->paths, pathinfo->parent_dir);
+ struct srv_pathinfo *parent = map_load(&ctx->parent_sess->paths, pathinfo->parent_dir);
assert(parent);
struct lib9p_stat parent_stat = LO_CALL(parent->file, stat, &ctx->ctx);
if (lib9p_ctx_has_error(&ctx->ctx.basectx))
@@ -968,7 +953,7 @@ static void handle_Tread(struct _lib9p_srv_req *ctx,
/* TODO: serialize simultaneous reads to the same FID */
/* Check that the FID is valid for this. */
- struct _srv_fidinfo *fidinfo = fidmap_load(&ctx->parent_sess->fids, req->fid);
+ struct _srv_fidinfo *fidinfo = map_load(&ctx->parent_sess->fids, req->fid);
if (!fidinfo) {
lib9p_errorf(&ctx->ctx.basectx,
LINUX_EBADF, "bad file number %"PRIu32, req->fid);
@@ -981,7 +966,7 @@ static void handle_Tread(struct _lib9p_srv_req *ctx,
}
/* Variables. */
- struct srv_pathinfo *pathinfo = pathmap_load(&ctx->parent_sess->paths, fidinfo->path);
+ struct srv_pathinfo *pathinfo = map_load(&ctx->parent_sess->paths, fidinfo->path);
assert(pathinfo);
/* Do it. */
@@ -1032,7 +1017,7 @@ static void handle_Twrite(struct _lib9p_srv_req *ctx,
/* TODO: serialize simultaneous writes to the same FID */
/* Check that the FID is valid for this. */
- struct _srv_fidinfo *fidinfo = fidmap_load(&ctx->parent_sess->fids, req->fid);
+ struct _srv_fidinfo *fidinfo = map_load(&ctx->parent_sess->fids, req->fid);
if (!fidinfo) {
lib9p_errorf(&ctx->ctx.basectx,
LINUX_EBADF, "bad file number %"PRIu32, req->fid);
@@ -1045,7 +1030,7 @@ static void handle_Twrite(struct _lib9p_srv_req *ctx,
}
/* Variables. */
- struct srv_pathinfo *pathinfo = pathmap_load(&ctx->parent_sess->paths, fidinfo->path);
+ struct srv_pathinfo *pathinfo = map_load(&ctx->parent_sess->paths, fidinfo->path);
assert(pathinfo);
/* Do it. */
@@ -1053,7 +1038,7 @@ static void handle_Twrite(struct _lib9p_srv_req *ctx,
}
static void clunkremove(struct _lib9p_srv_req *ctx, lib9p_fid_t fid, bool remove) {
- struct _srv_fidinfo *fidinfo = fidmap_load(&ctx->parent_sess->fids, fid);
+ struct _srv_fidinfo *fidinfo = map_load(&ctx->parent_sess->fids, fid);
if (!fidinfo) {
lib9p_errorf(&ctx->ctx.basectx,
LINUX_EBADF, "bad file number %"PRIu32, fid);
@@ -1061,7 +1046,7 @@ static void clunkremove(struct _lib9p_srv_req *ctx, lib9p_fid_t fid, bool remove
}
if (fidinfo->flags & FIDFLAG_RCLOSE)
remove = true;
- struct srv_pathinfo *pathinfo = pathmap_load(&ctx->parent_sess->paths, fidinfo->path);
+ struct srv_pathinfo *pathinfo = map_load(&ctx->parent_sess->paths, fidinfo->path);
assert(pathinfo);
if (remove) {
@@ -1070,7 +1055,7 @@ static void clunkremove(struct _lib9p_srv_req *ctx, lib9p_fid_t fid, bool remove
LINUX_EBUSY, "cannot remove root");
goto clunk;
}
- struct srv_pathinfo *parent = pathmap_load(&ctx->parent_sess->paths, pathinfo->parent_dir);
+ struct srv_pathinfo *parent = map_load(&ctx->parent_sess->paths, pathinfo->parent_dir);
assert(parent);
struct lib9p_stat parent_stat = LO_CALL(parent->file, stat, &ctx->ctx);
if (!srv_util_check_perm(ctx, &parent_stat, 0b010)) {
@@ -1090,7 +1075,7 @@ static void clunkremove(struct _lib9p_srv_req *ctx, lib9p_fid_t fid, bool remove
pathinfo->io_refcount--;
}
srv_util_pathfree(ctx, LO_CALL(pathinfo->file, qid).path);
- fidmap_del(&ctx->parent_sess->fids, fid);
+ map_del(&ctx->parent_sess->fids, fid);
}
static void handle_Tclunk(struct _lib9p_srv_req *ctx,
@@ -1115,13 +1100,13 @@ static void handle_Tstat(struct _lib9p_srv_req *ctx,
struct lib9p_msg_Rstat *resp) {
util_handler_common(ctx, req, resp);
- struct _srv_fidinfo *fidinfo = fidmap_load(&ctx->parent_sess->fids, req->fid);
+ struct _srv_fidinfo *fidinfo = map_load(&ctx->parent_sess->fids, req->fid);
if (!fidinfo) {
lib9p_errorf(&ctx->ctx.basectx,
LINUX_EBADF, "bad file number %"PRIu32, req->fid);
return;
}
- struct srv_pathinfo *pathinfo = pathmap_load(&ctx->parent_sess->paths, fidinfo->path);
+ struct srv_pathinfo *pathinfo = map_load(&ctx->parent_sess->paths, fidinfo->path);
assert(pathinfo);
resp->stat = LO_CALL(pathinfo->file, stat, &ctx->ctx);
diff --git a/libmisc/CMakeLists.txt b/libmisc/CMakeLists.txt
index c80e060..fdbe949 100644
--- a/libmisc/CMakeLists.txt
+++ b/libmisc/CMakeLists.txt
@@ -10,6 +10,7 @@ target_sources(libmisc INTERFACE
intercept.c
linkedlist.c
log.c
+ map.c
)
target_compile_options(libmisc INTERFACE "$<$<COMPILE_LANGUAGE:C>:-fplan9-extensions>")
@@ -19,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/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_ */
diff --git a/libmisc/map.c b/libmisc/map.c
new file mode 100644
index 0000000..bb8a2d2
--- /dev/null
+++ b/libmisc/map.c
@@ -0,0 +1,224 @@
+/* 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 *********************************************************/
+
+#define cast(n) lm_dll_node_cast(struct _map_kv, n)
+
+static inline void *_map_kv_keyp(struct _map *m, struct _map_kv *kv) {
+ assert(m);
+ assert(kv);
+ return ((void*)kv)+m->offsetof_k;
+}
+static inline void *_map_kv_valp(struct _map *m, struct _map_kv *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,
+ lm_dll_root **ret_bucket,
+ struct _map_kv **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 *kv = cast((*ret_bucket)->front); kv; kv = cast(kv->rear)) {
+ if (!(kv->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);
+ lm_dll_root *new_buckets = calloc(new_nbuckets, sizeof(lm_dll_root));
+ for (size_t i = 0; i < m->nbuckets; i++) {
+ while (m->buckets[i].front) {
+ struct _map_kv *kv = cast(m->buckets[i].front);
+ lm_dll_pop_from_front(&m->buckets[i]);
+ hash_t h = hash(_map_kv_keyp(m, kv), m->sizeof_k);
+ lm_dll_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;
+ lm_dll_root *bucket;
+ struct _map_kv *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;
+ lm_dll_root *bucket;
+ struct _map_kv *kv;
+ _map_lookup(m, keyp, &h, &bucket, &kv);
+
+ if (!kv)
+ return false;
+ if (kv->flags & FLAG_ITER) {
+ kv->flags |= FLAG_DEL;
+ } else {
+ lm_dll_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;
+ lm_dll_root *bucket;
+ struct _map_kv *old;
+ _map_lookup(m, keyp, &h, &bucket, &old);
+
+ if (old) {
+ lm_dll_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 *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);
+ lm_dll_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 *kv = cast(m->buckets[i].front);
+ lm_dll_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 = cast(state->m->buckets[state->i].front);
+ } else {
+ struct _map_kv *old_kv = state->kv;
+ state->kv = cast(old_kv->rear);
+
+ old_kv->flags &= ~FLAG_ITER;
+ if (old_kv->flags & FLAG_DEL) {
+ lm_dll_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 = cast(state->m->buckets[state->i].front);
+ }
+ }
+ state->kv->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_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;
+}
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2025-04-24 03:38:34 +0000