summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLuke T. Shumaker <lukeshu@lukeshu.com>2025-04-15 08:42:24 -0600
committerLuke T. Shumaker <lukeshu@lukeshu.com>2025-04-15 08:42:24 -0600
commit802ed1e3cd0252cafd1be2aada0addf4d3f7eb2e (patch)
tree70f49ed30f0f9839709a093c6af54661eeaad4ee
parent0450e14b3a86e4448537c03253eeebf509f8909e (diff)
parent32a1b710b40ce9d53cd0a7bc0c183da87e07f397 (diff)
Merge branch 'lukeshu/generics'HEADmain
-rw-r--r--cmd/sbc_harness/usb_keyboard.c6
-rw-r--r--lib9p/srv.c22
-rw-r--r--libcr_ipc/chan.c38
-rw-r--r--libcr_ipc/include/libcr_ipc/chan.h189
-rw-r--r--libcr_ipc/include/libcr_ipc/mutex.h8
-rw-r--r--libcr_ipc/include/libcr_ipc/rpc.h185
-rw-r--r--libcr_ipc/include/libcr_ipc/rwmutex.h12
-rw-r--r--libcr_ipc/include/libcr_ipc/sema.h10
-rw-r--r--libcr_ipc/mutex.c13
-rw-r--r--libcr_ipc/rpc.c35
-rw-r--r--libcr_ipc/rwmutex.c46
-rw-r--r--libcr_ipc/sema.c26
-rw-r--r--libcr_ipc/tests/test_chan.c10
-rw-r--r--libcr_ipc/tests/test_rpc.c12
-rw-r--r--libcr_ipc/tests/test_select.c4
-rw-r--r--libhw_cr/w5500.c6
-rw-r--r--libmisc/include/libmisc/linkedlist.h112
-rw-r--r--libmisc/include/libmisc/map.h86
-rw-r--r--libmisc/linkedlist.c14
-rw-r--r--libmisc/map.c73
20 files changed, 483 insertions, 424 deletions
diff --git a/cmd/sbc_harness/usb_keyboard.c b/cmd/sbc_harness/usb_keyboard.c
index f3cb42d..7dd8a24 100644
--- a/cmd/sbc_harness/usb_keyboard.c
+++ b/cmd/sbc_harness/usb_keyboard.c
@@ -54,8 +54,8 @@ COROUTINE usb_keyboard_cr(void *_chan) {
while (!tud_hid_n_ready(kbd_ifc))
cr_yield();
- if (usb_keyboard_rpc_can_recv_req(chan)) {
- usb_keyboard_rpc_req_t req = usb_keyboard_rpc_recv_req(chan);
+ if (cr_rpc_can_recv_req(chan)) {
+ usb_keyboard_rpc_req_t req = cr_rpc_recv_req(chan);
uint32_t rune = req.req;
modifier = ascii2keycode[rune][0] ? KEYBOARD_MODIFIER_LEFTSHIFT : 0;
@@ -69,7 +69,7 @@ COROUTINE usb_keyboard_cr(void *_chan) {
keycodes[0] = 0;
tud_hid_n_keyboard_report(kbd_ifc, report_id, modifier, keycodes);
- usb_keyboard_rpc_send_resp(req, 1);
+ cr_rpc_send_resp(req, 1);
} else {
modifier = 0;
keycodes[0] = 0;
diff --git a/lib9p/srv.c b/lib9p/srv.c
index 7e2bab0..dae73ea 100644
--- a/lib9p/srv.c
+++ b/lib9p/srv.c
@@ -45,14 +45,14 @@ static_assert(CONFIG_9P_SRV_MAX_HOSTMSG_SIZE <= SSIZE_MAX);
bool lib9p_srv_flush_requested(struct lib9p_srv_ctx *ctx) {
assert(ctx);
- return _lib9p_srv_flushch_can_send(&ctx->flushch);
+ return cr_chan_can_send(&ctx->flushch);
}
void lib9p_srv_acknowledge_flush(struct lib9p_srv_ctx *ctx) {
assert(ctx);
- assert(_lib9p_srv_flushch_can_send(&ctx->flushch));
+ assert(cr_chan_can_send(&ctx->flushch));
lib9p_error(&ctx->basectx, LIB9P_ERRNO_L_ECANCELED, "request canceled by flush");
- _lib9p_srv_flushch_send(&ctx->flushch, true);
+ cr_chan_send(&ctx->flushch, true);
}
/* structs ********************************************************************/
@@ -443,7 +443,7 @@ void lib9p_srv_accept_and_read_loop(struct lib9p_srv *srv, lo_interface net_stre
srv->readers--;
if (srv->readers == 0)
while (srv->writers > 0)
- _lib9p_srv_reqch_send_req(&srv->_reqch, NULL);
+ cr_rpc_send_req(&srv->_reqch, NULL);
return;
}
lib9p_srv_read(srv, conn);
@@ -514,7 +514,7 @@ void lib9p_srv_read(struct lib9p_srv *srv, lo_interface net_stream_conn _conn) {
handle_message(&req);
else
/* ...but usually in another coroutine. */
- _lib9p_srv_reqch_send_req(&srv->_reqch, &req);
+ cr_rpc_send_req(&srv->_reqch, &req);
}
if (map_len(&sess.reqs) == 0)
io_close(conn.fd);
@@ -560,10 +560,10 @@ void lib9p_srv_worker_loop(struct lib9p_srv *srv) {
for (;;) {
/* Receive the request from the reader coroutine. ************/
- rpc_handle = _lib9p_srv_reqch_recv_req(&srv->_reqch);
+ rpc_handle = cr_rpc_recv_req(&srv->_reqch);
if (!rpc_handle.req) {
srv->writers--;
- _lib9p_srv_reqch_send_resp(rpc_handle, 0);
+ cr_rpc_send_resp(rpc_handle, 0);
return;
}
/* Copy the request from the reader coroutine's
@@ -574,14 +574,14 @@ void lib9p_srv_worker_loop(struct lib9p_srv *srv) {
assert(reqpp && *reqpp == &req);
/* Notify the reader coroutine that we're done with
* its data. */
- _lib9p_srv_reqch_send_resp(rpc_handle, 0);
+ cr_rpc_send_resp(rpc_handle, 0);
/* Process the request. **************************************/
handle_message(&req);
/* Release resources. ****************************************/
- while (_lib9p_srv_flushch_can_send(&req.flushch))
- _lib9p_srv_flushch_send(&req.flushch, false);
+ while (cr_chan_can_send(&req.flushch))
+ cr_chan_send(&req.flushch, false);
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);
@@ -868,7 +868,7 @@ static void handle_Tflush(struct srv_req *ctx,
struct srv_req **oldreqp = map_load(&ctx->parent_sess->reqs, req->oldtag);
if (oldreqp)
- _lib9p_srv_flushch_recv(&((*oldreqp)->flushch));
+ cr_chan_recv(&((*oldreqp)->flushch));
}
static void handle_Twalk(struct srv_req *ctx,
diff --git a/libcr_ipc/chan.c b/libcr_ipc/chan.c
index 6ccfa44..6cbe890 100644
--- a/libcr_ipc/chan.c
+++ b/libcr_ipc/chan.c
@@ -16,17 +16,17 @@
/* base channels **************************************************************/
struct cr_chan_waiter {
- lm_dll_node;
cid_t cid;
void *val_ptr;
void (*dequeue)(void *, size_t);
void *dequeue_arg1;
size_t dequeue_arg2;
};
+DLIST_DECLARE_NODE(_cr_chan_waiter_list, struct cr_chan_waiter);
void cr_chan_dequeue(void *_ch, size_t) {
struct _cr_chan *ch = _ch;
- lm_dll_pop_from_front(&ch->waiters);
+ dlist_pop_from_front(&ch->waiters);
}
void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void *val_ptr, size_t val_size) {
@@ -35,23 +35,23 @@ void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void
if (ch->waiters.front && ch->waiter_typ != self_typ) { /* non-blocking fast-path */
/* Copy. */
- struct cr_chan_waiter *front = lm_dll_node_cast(struct cr_chan_waiter, ch->waiters.front);
+ struct _cr_chan_waiter_list_node *front = ch->waiters.front;
if (self_typ == _CR_CHAN_SENDER)
- memcpy(front->val_ptr, val_ptr, val_size);
+ memcpy(front->val.val_ptr, val_ptr, val_size);
else
- memcpy(val_ptr, front->val_ptr, val_size);
- cr_unpause(front->cid);
- front->dequeue(front->dequeue_arg1,
- front->dequeue_arg2);
+ memcpy(val_ptr, front->val.val_ptr, val_size);
+ cr_unpause(front->val.cid);
+ front->val.dequeue(front->val.dequeue_arg1,
+ front->val.dequeue_arg2);
cr_yield();
} else { /* blocking slow-path */
- struct cr_chan_waiter self = {
+ struct _cr_chan_waiter_list_node self = { .val = {
.cid = cr_getcid(),
.val_ptr = val_ptr,
.dequeue = cr_chan_dequeue,
.dequeue_arg1 = ch,
- };
- lm_dll_push_to_rear(&ch->waiters, &self);
+ }};
+ dlist_push_to_rear(&ch->waiters, &self);
ch->waiter_typ = self_typ;
cr_pause_and_yield();
}
@@ -66,9 +66,9 @@ enum cr_select_class {
};
struct cr_select_waiters {
- size_t cnt;
- struct cr_select_arg *args;
- struct cr_chan_waiter *nodes;
+ size_t cnt;
+ struct cr_select_arg *args;
+ struct _cr_chan_waiter_list_node *nodes;
};
static inline enum cr_select_class cr_select_getclass(struct cr_select_arg arg) {
@@ -93,8 +93,8 @@ static inline enum cr_select_class cr_select_getclass(struct cr_select_arg arg)
void cr_select_dequeue(void *_waiters, size_t idx) {
struct cr_select_waiters *waiters = _waiters;
for (size_t i = 0; i < waiters->cnt; i++)
- lm_dll_remove(&(waiters->args[i].ch->waiters),
- &(waiters->nodes[i]));
+ dlist_remove(&(waiters->args[i].ch->waiters),
+ &(waiters->nodes[i]));
waiters->cnt = idx;
}
@@ -153,14 +153,14 @@ size_t cr_select_v(size_t arg_cnt, struct cr_select_arg arg_vec[]) {
.nodes = alloca(sizeof(struct cr_chan_waiter) * arg_cnt),
};
for (size_t i = 0; i < arg_cnt; i++) {
- waiters.nodes[i] = (struct cr_chan_waiter){
+ waiters.nodes[i] = (struct _cr_chan_waiter_list_node){ .val = {
.cid = cr_getcid(),
.val_ptr = arg_vec[i].val_ptr,
.dequeue = cr_select_dequeue,
.dequeue_arg1 = &waiters,
.dequeue_arg2 = i,
- };
- lm_dll_push_to_rear(&arg_vec[i].ch->waiters, &waiters.nodes[i]);
+ }};
+ dlist_push_to_rear(&arg_vec[i].ch->waiters, &waiters.nodes[i]);
}
cr_pause_and_yield();
return waiters.cnt;
diff --git a/libcr_ipc/include/libcr_ipc/chan.h b/libcr_ipc/include/libcr_ipc/chan.h
index 80acdb8..5a87643 100644
--- a/libcr_ipc/include/libcr_ipc/chan.h
+++ b/libcr_ipc/include/libcr_ipc/chan.h
@@ -10,16 +10,12 @@
#include <stdbool.h> /* for bool */
#include <stddef.h> /* for size_t */
-#include <libmisc/linkedlist.h> /* for lm_dll_root */
-#include <libmisc/macro.h> /* for LM_CAT2_() */
+#include <libmisc/linkedlist.h> /* for DLIST_DECLARE() */
/* base channels **************************************************************/
/**
- * CR_CHAN_DECLARE(NAME, VAL_T) declares the following type and
- * methods:
- *
- * type:
+ * CR_CHAN_DECLARE(NAME, VAL_T) declares the following type:
*
* / **
* * A NAME##_t is a fair unbuffered channel that transports
@@ -32,87 +28,89 @@
* * something from an interrupt handler.
* * /
* typedef ... NAME##_t;
+ */
+#define CR_CHAN_DECLARE(NAME, VAL_T) \
+ typedef struct { \
+ struct _cr_chan core; \
+ VAL_T val_typ[0]; \
+ } NAME##_t
+
+/**
+ * cr_chan_send(ch, val) sends `val` over `ch`.
*
- * methods:
+ * @runs_in coroutine
+ * @cr_pauses maybe
+ * @cr_yields always
*
- * / **
- * * NAME##_send(ch, val) sends `val` over `ch`.
- * *
- * * @runs_in coroutine
- * * @cr_pauses maybe
- * * @cr_yields always
- * * /
- * void NAME##_send(NAME##_t *ch, VAL_T val);
+ * void cr_chan_send(NAME##_t *ch, VAL_T val);
+ */
+#define cr_chan_send(CH, VAL) do { \
+ cr_assert_in_coroutine(); \
+ typeof((CH)->val_typ[0]) _val_lvalue = VAL; \
+ _cr_chan_xfer(_CR_CHAN_SENDER, &(CH)->core, \
+ &_val_lvalue, sizeof(_val_lvalue)); \
+} while(0)
+
+/**
+ * cr_chan_recv(ch) reads and returns a value from ch.
*
- * / **
- * * NAME##_recv(ch) reads and returns a value from ch.
- * *
- * * @runs_in coroutine
- * * @cr_pauses maybe
- * * @cr_yields always
- * * /
- * VAL_T NAME##_recv(NAME##_t *ch);
+ * @runs_in coroutine
+ * @cr_pauses maybe
+ * @cr_yields always
*
- * / **
- * * NAME##_can_send(ch) returns whether NAME##_send(ch, val)
- * * would run without pausing.
- * *
- * * @runs_in coroutine
- * * @cr_pauses never
- * * @cr_yields never
- * * /
- * bool NAME##_can_send(NAME##_t *ch);
+ * VAL_T cr_chan_recv(NAME##_T ch);
+ */
+#define cr_chan_recv(CH) ({ \
+ cr_assert_in_coroutine(); \
+ typeof((CH)->val_typ[0]) _val_lvalue; \
+ _cr_chan_xfer(_CR_CHAN_RECVER, &(CH)->core, \
+ &_val_lvalue, sizeof(_val_lvalue)); \
+ _val_lvalue; \
+})
+
+/**
+ * cr_chan_can_send(ch) returns whether cr_chan_send(ch, val) would
+ * run without pausing.
*
- * / **
- * * NAME##_can_recv(ch) returns whether NAME##_recv(ch) would
- * * return without pausing.
- * *
- * * @runs_in coroutine
- * * @cr_pauses never
- * * @cr_yields never
- * * /
- * NAME##_can_recv(NAME##_t *ch);
+ * @runs_in coroutine
+ * @cr_pauses never
+ * @cr_yields never
+ *
+ * bool cr_chan_can_send(NAME##_t *ch);
*/
-#define CR_CHAN_DECLARE(NAME, VAL_T) \
- typedef struct { \
- struct _cr_chan core; \
- VAL_T vals[0]; \
- } NAME##_t; \
- \
- static inline void NAME##_send(NAME##_t *ch, VAL_T val) { \
- cr_assert_in_coroutine(); \
- _cr_chan_xfer(_CR_CHAN_SENDER, &ch->core, &val, sizeof(val)); \
- } \
- \
- static inline VAL_T NAME##_recv(NAME##_t *ch) { \
- cr_assert_in_coroutine(); \
- VAL_T val; \
- _cr_chan_xfer(_CR_CHAN_RECVER, &ch->core, &val, sizeof(val)); \
- return val; \
- } \
- \
- static inline bool NAME##_can_send(NAME##_t *ch) { \
- cr_assert_in_coroutine(); \
- return ch->core.waiters.front && \
- ch->core.waiter_typ == _CR_CHAN_RECVER; \
- } \
- \
- static inline bool NAME##_can_recv(NAME##_t *ch) { \
- cr_assert_in_coroutine(); \
- return ch->core.waiters.front && \
- ch->core.waiter_typ == _CR_CHAN_SENDER; \
- } \
- \
- extern int LM_CAT2_(_CR_CHAN_FORCE_SEMICOLON_, __COUNTER__)
+#define cr_chan_can_send(CH) ({ \
+ cr_assert_in_coroutine(); \
+ (bool)((CH)->core.waiters.front && \
+ (CH)->core.waiter_typ == _CR_CHAN_RECVER); \
+})
+
+/**
+ * cr_chan_can_recv(ch) returns whether cr_chan_recv(ch) would return
+ * without pausing.
+ *
+ * @runs_in coroutine
+ * @cr_pauses never
+ * @cr_yields never
+ *
+ * bool cr_chan_can_recv(NAME##_t *ch);
+ */
+#define cr_chan_can_recv(CH) ({ \
+ cr_assert_in_coroutine(); \
+ (bool)((CH)->core.waiters.front && \
+ (CH)->core.waiter_typ == _CR_CHAN_SENDER); \
+})
+
enum _cr_chan_waiter_typ {
_CR_CHAN_SENDER,
_CR_CHAN_RECVER,
};
+DLIST_DECLARE(_cr_chan_waiter_list);
+
struct _cr_chan {
- enum _cr_chan_waiter_typ waiter_typ;
- lm_dll_root waiters;
+ enum _cr_chan_waiter_typ waiter_typ;
+ struct _cr_chan_waiter_list waiters;
};
void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void *val_ptr, size_t val_size);
@@ -134,31 +132,30 @@ struct cr_select_arg {
size_t val_siz;
};
-#define CR_SELECT_RECV(CH, VALP) \
- /* The _valp temporary variable is to get the compiler to check that \
- * the types are compatible. */ \
- ((struct cr_select_arg){ \
- .op = _CR_SELECT_OP_RECV, \
- .ch = &((CH)->core), \
- .val_ptr = ({ typeof((CH)->vals[0]) *_valp = VALP; _valp; }), \
- .val_siz = sizeof((CH)->vals[0]), \
- })
+#define CR_SELECT_RECV(CH, VALP) ((struct cr_select_arg){ \
+ .op = _CR_SELECT_OP_RECV, \
+ .ch = &((CH)->core), \
+ /* The _valp temporary variable is to get the compiler to check that \
+ * the types are compatible. */ \
+ .val_ptr = ({ typeof((CH)->val_typ[0]) *_valp = VALP; _valp; }), \
+ .val_siz = sizeof((CH)->val_typ[0]), \
+})
+
/* BUG: It's bogus that CR_SELECT_SEND takes VALP instead of VAL, but
* since we need an address, taking VAL would introduce uncomfortable
* questions about where VAL sits on the stack. */
-#define CR_SELECT_SEND(CH, VALP) \
- /* The _valp temporary variable is to get the compiler to check that \
- * the types are compatible. */ \
- ((struct cr_select_arg){ \
- .op = _CR_SELECT_OP_SEND, \
- .ch = &((CH)->core), \
- .val_ptr = ({ typeof((CH)->vals[0]) *_valp = VALP; _valp; }), \
- .val_siz = sizeof((CH)->vals[0]), \
- })
-#define CR_SELECT_DEFAULT \
- ((struct cr_select_arg){ \
- .op = _CR_SELECT_OP_DEFAULT, \
- })
+#define CR_SELECT_SEND(CH, VALP) ((struct cr_select_arg){ \
+ .op = _CR_SELECT_OP_SEND, \
+ .ch = &((CH)->core), \
+ /* The _valp temporary variable is to get the compiler to check that \
+ * the types are compatible. */ \
+ .val_ptr = ({ typeof((CH)->val_typ[0]) *_valp = VALP; _valp; }), \
+ .val_siz = sizeof((CH)->val_typ[0]), \
+})
+
+#define CR_SELECT_DEFAULT ((struct cr_select_arg){ \
+ .op = _CR_SELECT_OP_DEFAULT, \
+})
/* cr_select_v(arg_cnt, arg_vec) **********************************************/
diff --git a/libcr_ipc/include/libcr_ipc/mutex.h b/libcr_ipc/include/libcr_ipc/mutex.h
index 0f3c9c2..e5f43c8 100644
--- a/libcr_ipc/include/libcr_ipc/mutex.h
+++ b/libcr_ipc/include/libcr_ipc/mutex.h
@@ -9,9 +9,11 @@
#include <stdbool.h> /* for bool */
-#include <libmisc/linkedlist.h>
+#include <libmisc/linkedlist.h> /* for SLIST_DECLARE() */
#include <libmisc/private.h>
+SLIST_DECLARE(_cr_mutex_waiter_list);
+
/**
* A cr_mutex_t is a fair mutex.
*
@@ -22,8 +24,8 @@
*/
typedef struct {
BEGIN_PRIVATE(LIBCR_IPC_MUTEX_H);
- bool locked;
- lm_sll_root waiters;
+ bool locked;
+ struct _cr_mutex_waiter_list waiters;
END_PRIVATE(LIBCR_IPC_MUTEX_H);
} cr_mutex_t;
diff --git a/libcr_ipc/include/libcr_ipc/rpc.h b/libcr_ipc/include/libcr_ipc/rpc.h
index f091685..ecf48cf 100644
--- a/libcr_ipc/include/libcr_ipc/rpc.h
+++ b/libcr_ipc/include/libcr_ipc/rpc.h
@@ -9,14 +9,10 @@
#include <stdbool.h> /* for bool */
-#include <libmisc/linkedlist.h> /* for lm_sll_root */
-#include <libmisc/macro.h> /* for LM_CAT2_() */
+#include <libmisc/linkedlist.h> /* for SLIST_DECLARE() */
/**
- * CR_RPC_DECLARE(NAME, REQ_T, RESP_T) declares the following types
- * and methods:
- *
- * type:
+ * CR_RPC_DECLARE(NAME, REQ_T, RESP_T) declares the following types:
*
* / **
* * A NAME##_t is a fair rpc-channel on which the requester submits a
@@ -38,114 +34,109 @@
* * the response RESP_T to the correct requester. `REQ_T req` is the
* * only public member.
* typedef struct { REQ_T req; ... } NAME##_req_t;
+ */
+#define CR_RPC_DECLARE(NAME, REQ_T, RESP_T) \
+ typedef struct { \
+ REQ_T req; \
+ \
+ RESP_T *_resp; /* where to write resp to */ \
+ cid_t _requester; \
+ } NAME##_req_t; \
+ \
+ typedef struct { \
+ struct _cr_rpc core; \
+ NAME##_req_t handle_typ[0]; \
+ } NAME##_t
+
+/* Methods for NAME##_t *******************************************************/
+
+/**
+ * cr_rpc_send_req(ch, req) submits the `req` request over `ch` and
+ * returns the response.
*
- * methods:
+ * @runs_in coroutine
+ * @cr_pauses always
+ * @cr_yields always
*
- * / **
- * * NAME##_send_req(ch, req) submits the `req` request over `ch` and
- * * returns the response.
- * *
- * * @runs_in coroutine
- * * @cr_pauses always
- * * @cr_yields always
- * * /
- * RESP_T NAME##_send_req(NAME##_t *ch, REQ_T req);
+ * RESP_T cr_rpc_send_req(NAME##_t *ch, REQ_T req);
+ */
+#define cr_rpc_send_req(CH, REQ) ({ \
+ cr_assert_in_coroutine(); \
+ typeof((CH)->handle_typ[0].req) _req_lvalue = REQ; \
+ typeof(*(CH)->handle_typ[0]._resp) _resp_lvalue; \
+ _cr_rpc_send_req(&(CH)->core, \
+ &_req_lvalue, sizeof(_req_lvalue), \
+ &_resp_lvalue); \
+ _resp_lvalue; \
+})
+
+/**
+ * cr_rpc_recv_req(ch) reads a request from ch, and returns a
+ * NAME##_req_t handle wrapping that request.
*
- * / **
- * * NAME##_recv_req(ch) reads a request from ch, and returns a
- * * NAME##_req_t handle wrapping that request.
- * *
- * * @runs_in coroutine
- * * @cr_pauses maybe
- * * @cr_yields maybe
- * * /
- * NAME##_req_t NAME##_recv_req(NAME##_t *ch);
+ * @runs_in coroutine
+ * @cr_pauses maybe
+ * @cr_yields maybe
*
- * / **
- * * NAME##_can_recv_req(ch) returns whether NAME##_recv_req(ch)
- * * would return without pausing.
- * *
- * * @runs_in coroutine
- * * @cr_pauses never
- * * @cr_yields never
- * * /
- * bool NAME##_can_recv_req(NAME##_t *ch);
+ * NAME##_req_t cr_rcp_recv_req(NAME##_t *ch);
+ */
+#define cr_rpc_recv_req(CH) ({ \
+ cr_assert_in_coroutine(); \
+ typeof((CH)->handle_typ[0]) ret; \
+ _cr_rpc_recv_req(&(CH)->core, \
+ &ret.req, sizeof(ret.req), \
+ (void **)&ret._resp, \
+ &ret._requester); \
+ ret; \
+})
+
+/**
+ * cr_rpc_can_recv_req(ch) returns whether NAME##_recv_req(ch)
+ * would return without pausing.
*
- * type:
+ * @runs_in coroutine
+ * @cr_pauses never
+ * @cr_yields never
*
- * / **
- * * A NAME##_req_t is a handle that wraps a REQ_T, and is a channel
- * * that a response may be written to.
- * * /
- * typedef ... NAME##_req_t;
+ * bool cr_rpc_can_recv_req(NAME##_t *ch);
+ */
+#define cr_rpc_can_recv_req(CH) ({ \
+ cr_assert_in_coroutine(); \
+ (bool)((CH)->core.waiters.front && \
+ (CH)->core.waiter_typ == _CR_RPC_REQUESTER); \
+})
+
+/* Methods for NAME##_req_t ***************************************************/
+
+/**
+ * cr_rpc_send_resp(req, resp) sends the given response to the given
+ * request.
*
- * methods:
+ * @runs_in coroutine
+ * @cr_pauses never
+ * @cr_yields always
*
- * / **
- * * cr_rpc_send_resp(req, resp) sends the given response to the given
- * * request.
- * *
- * * @runs_in coroutine
- * * @cr_pauses never
- * * @cr_yields always
- * * /
- * void NAME##_send_resp(NAME##_req_t req, RESP_T resp);
+ * void cr_rpc_send_resp(NAME##_req_t req, RESP_T resp);
*/
-#define CR_RPC_DECLARE(NAME, REQ_T, RESP_T) \
- typedef struct { \
- REQ_T req; \
- \
- RESP_T *_resp; /* where to write resp to */ \
- cid_t _requester; \
- } NAME##_req_t; \
- \
- typedef struct { \
- struct _cr_rpc core; \
- NAME##_req_t handle[0]; \
- } NAME##_t; \
- \
- static inline RESP_T NAME##_send_req(NAME##_t *ch, REQ_T req) { \
- cr_assert_in_coroutine(); \
- RESP_T resp; \
- _cr_rpc_send_req(&ch->core, \
- &req, sizeof(req), \
- &resp); \
- return resp; \
- } \
- \
- static inline NAME##_req_t NAME##_recv_req(NAME##_t *ch) { \
- cr_assert_in_coroutine(); \
- NAME##_req_t ret; \
- _cr_rpc_recv_req(&ch->core, \
- &ret.req, sizeof(ret.req), \
- (void **)&ret._resp, \
- &ret._requester); \
- return ret; \
- } \
- \
- static inline bool NAME##_can_recv_req(NAME##_t *ch) { \
- cr_assert_in_coroutine(); \
- return ch->core.waiters.front && \
- ch->core.waiter_typ == _CR_RPC_REQUESTER; \
- } \
- \
- static inline void NAME##_send_resp(NAME##_req_t req, RESP_T resp) { \
- cr_assert_in_coroutine(); \
- *(req._resp) = resp; \
- cr_unpause(req._requester); \
- cr_yield(); \
- } \
- \
- extern int LM_CAT2_(_CR_RPC_FORCE_SEMICOLON_, __COUNTER__)
+#define cr_rpc_send_resp(REQ, RESP) { \
+ cr_assert_in_coroutine(); \
+ *((REQ)._resp) = RESP; \
+ cr_unpause(REQ._requester); \
+ cr_yield(); \
+} while(0)
+
+/* Background details *********************************************************/
enum _cr_rpc_waiter_typ {
_CR_RPC_REQUESTER,
_CR_RPC_RESPONDER,
};
+SLIST_DECLARE(_cr_rpc_waiter_list);
+
struct _cr_rpc {
enum _cr_rpc_waiter_typ waiter_typ;
- lm_sll_root waiters;
+ struct _cr_rpc_waiter_list waiters;
};
void _cr_rpc_send_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void *resp_ptr);
diff --git a/libcr_ipc/include/libcr_ipc/rwmutex.h b/libcr_ipc/include/libcr_ipc/rwmutex.h
index d48abe9..8ccae63 100644
--- a/libcr_ipc/include/libcr_ipc/rwmutex.h
+++ b/libcr_ipc/include/libcr_ipc/rwmutex.h
@@ -9,9 +9,11 @@
#include <stdbool.h>
-#include <libmisc/linkedlist.h>
+#include <libmisc/linkedlist.h> /* for SLIST_DECLARE() */
#include <libmisc/private.h>
+SLIST_DECLARE(_cr_rwmutex_waiter_list);
+
/**
* A cr_rwmutex_t is a fair read/write mutex.
*
@@ -25,10 +27,10 @@
*/
typedef struct {
BEGIN_PRIVATE(LIBCR_IPC_RWMUTEX_H);
- unsigned nreaders;
- bool locked;
- bool unpausing;
- lm_sll_root waiters;
+ unsigned nreaders;
+ bool locked;
+ bool unpausing;
+ struct _cr_rwmutex_waiter_list waiters;
END_PRIVATE(LIBCR_IPC_RWMUTEX_H);
} cr_rwmutex_t;
diff --git a/libcr_ipc/include/libcr_ipc/sema.h b/libcr_ipc/include/libcr_ipc/sema.h
index cc387f4..8b5ac5b 100644
--- a/libcr_ipc/include/libcr_ipc/sema.h
+++ b/libcr_ipc/include/libcr_ipc/sema.h
@@ -9,9 +9,11 @@
#include <stdbool.h>
-#include <libmisc/linkedlist.h>
+#include <libmisc/linkedlist.h> /* for SLIST_DECLARE() */
#include <libmisc/private.h>
+SLIST_DECLARE(_cr_sema_waiter_list);
+
/**
* A cr_sema_t is a fair unbounded[1] counting semaphore.
*
@@ -19,9 +21,9 @@
*/
typedef struct {
BEGIN_PRIVATE(LIBCR_IPC_SEMA_H);
- unsigned int cnt;
- bool unpausing;
- lm_sll_root waiters;
+ unsigned int cnt;
+ bool unpausing;
+ struct _cr_sema_waiter_list waiters;
END_PRIVATE(LIBCR_IPC_SEMA_H);
} cr_sema_t;
diff --git a/libcr_ipc/mutex.c b/libcr_ipc/mutex.c
index b0ebe05..1b4e626 100644
--- a/libcr_ipc/mutex.c
+++ b/libcr_ipc/mutex.c
@@ -5,14 +5,15 @@
*/
#include <libcr/coroutine.h> /* for cid_t, cr_* */
+#include <libmisc/assert.h>
#define IMPLEMENTATION_FOR_LIBCR_IPC_MUTEX_H YES
#include <libcr_ipc/mutex.h>
struct cr_mutex_waiter {
- lm_sll_node;
cid_t cid;
};
+SLIST_DECLARE_NODE(_cr_mutex_waiter_list, struct cr_mutex_waiter);
void cr_mutex_lock(cr_mutex_t *mu) {
assert(mu);
@@ -21,10 +22,10 @@ void cr_mutex_lock(cr_mutex_t *mu) {
if (!mu->locked) /* non-blocking fast-path */
mu->locked = true;
else { /* blocking slow-path */
- struct cr_mutex_waiter self = {
+ struct _cr_mutex_waiter_list_node self = { .val = {
.cid = cr_getcid(),
- };
- lm_sll_push_to_rear(&mu->waiters, &self);
+ }};
+ slist_push_to_rear(&mu->waiters, &self);
cr_pause_and_yield();
}
assert(mu->locked);
@@ -36,8 +37,8 @@ void cr_mutex_unlock(cr_mutex_t *mu) {
assert(mu->locked);
if (mu->waiters.front) {
- cr_unpause(lm_sll_node_cast(struct cr_mutex_waiter, mu->waiters.front)->cid);
- lm_sll_pop_from_front(&mu->waiters);
+ cr_unpause(mu->waiters.front->val.cid);
+ slist_pop_from_front(&mu->waiters);
} else
mu->locked = false;
}
diff --git a/libcr_ipc/rpc.c b/libcr_ipc/rpc.c
index 6d9422f..fcf51ba 100644
--- a/libcr_ipc/rpc.c
+++ b/libcr_ipc/rpc.c
@@ -7,23 +7,26 @@
#include <string.h> /* for memcpy() */
#include <libcr/coroutine.h> /* for cid_t, cr_* */
+#include <libmisc/assert.h>
#include <libcr_ipc/rpc.h>
struct cr_rpc_requester {
- lm_sll_node;
cid_t cid;
void *req_ptr; /* where to read req from */
void *resp_ptr; /* where to write resp to */
};
-
struct cr_rpc_responder {
- lm_sll_node;
/* before enqueued | after dequeued */
/* -------------------+-------------------- */
cid_t cid; /* responder cid | requester cid */
void *ptr; /* where to write req | where to write resp */
};
+union cr_rpc_waiter {
+ struct cr_rpc_requester requester;
+ struct cr_rpc_responder responder;
+};
+SLIST_DECLARE_NODE(_cr_rpc_waiter_list, union cr_rpc_waiter);
void _cr_rpc_send_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void *resp_ptr) {
assert(ch);
@@ -31,9 +34,8 @@ void _cr_rpc_send_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void *
assert(resp_ptr);
if (ch->waiters.front && ch->waiter_typ != _CR_RPC_REQUESTER) { /* fast-path (still blocks) */
- struct cr_rpc_responder *responder =
- lm_sll_node_cast(struct cr_rpc_responder, ch->waiters.front);
- lm_sll_pop_from_front(&ch->waiters);
+ struct cr_rpc_responder *responder = &ch->waiters.front->val.responder;
+ slist_pop_from_front(&ch->waiters);
/* Copy the req to the responder's stack. */
memcpy(responder->ptr, req_ptr, req_size);
/* Notify the responder that we have done so. */
@@ -43,12 +45,12 @@ void _cr_rpc_send_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void *
/* Wait for the responder to set `*resp_ptr`. */
cr_pause_and_yield();
} else { /* blocking slow-path */
- struct cr_rpc_requester self = {
+ struct _cr_rpc_waiter_list_node self = { .val = { .requester = {
.cid = cr_getcid(),
.req_ptr = req_ptr,
.resp_ptr = resp_ptr,
- };
- lm_sll_push_to_rear(&ch->waiters, &self);
+ }}};
+ slist_push_to_rear(&ch->waiters, &self);
/* Wait for a responder to both copy our req and sed
* `*resp_ptr`. */
cr_pause_and_yield();
@@ -62,22 +64,21 @@ void _cr_rpc_recv_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void *
assert(ret_requester);
if (ch->waiters.front && ch->waiter_typ != _CR_RPC_RESPONDER) { /* non-blocking fast-path */
- struct cr_rpc_requester *requester =
- lm_sll_node_cast(struct cr_rpc_requester, ch->waiters.front);
- lm_sll_pop_from_front(&ch->waiters);
+ struct cr_rpc_requester *requester = &ch->waiters.front->val.requester;
+ slist_pop_from_front(&ch->waiters);
memcpy(req_ptr, requester->req_ptr, req_size);
*ret_requester = requester->cid;
*ret_resp_ptr = requester->resp_ptr;
} else { /* blocking slow-path */
- struct cr_rpc_responder self = {
+ struct _cr_rpc_waiter_list_node self = { .val = { .responder = {
.cid = cr_getcid(),
.ptr = req_ptr,
- };
- lm_sll_push_to_rear(&ch->waiters, &self);
+ }}};
+ slist_push_to_rear(&ch->waiters, &self);
ch->waiter_typ = _CR_RPC_RESPONDER;
cr_pause_and_yield();
- *ret_requester = self.cid;
- *ret_resp_ptr = self.ptr;
+ *ret_requester = self.val.responder.cid;
+ *ret_resp_ptr = self.val.responder.ptr;
}
}
diff --git a/libcr_ipc/rwmutex.c b/libcr_ipc/rwmutex.c
index 4c5da81..191b7fe 100644
--- a/libcr_ipc/rwmutex.c
+++ b/libcr_ipc/rwmutex.c
@@ -5,31 +5,32 @@
*/
#include <libcr/coroutine.h> /* for cid_t, cr_* */
+#include <libmisc/assert.h>
#define IMPLEMENTATION_FOR_LIBCR_IPC_RWMUTEX_H YES
#include <libcr_ipc/rwmutex.h>
struct cr_rwmutex_waiter {
- lm_sll_node;
bool is_reader;
cid_t cid;
};
+SLIST_DECLARE_NODE(_cr_rwmutex_waiter_list, struct cr_rwmutex_waiter);
void cr_rwmutex_lock(cr_rwmutex_t *mu) {
assert(mu);
cr_assert_in_coroutine();
- struct cr_rwmutex_waiter self = {
+ struct _cr_rwmutex_waiter_list_node self = { .val = {
.is_reader = false,
.cid = cr_getcid(),
- };
- lm_sll_push_to_rear(&mu->waiters, &self);
- if (mu->waiters.front != &self.lm_sll_node || mu->locked)
+ }};
+ slist_push_to_rear(&mu->waiters, &self);
+ if (mu->waiters.front != &self || mu->locked)
cr_pause_and_yield();
- assert(mu->waiters.front == &self.lm_sll_node);
+ assert(mu->waiters.front == &self);
/* We now hold the lock (and are mu->waiters.front). */
- lm_sll_pop_from_front(&mu->waiters);
+ slist_pop_from_front(&mu->waiters);
assert(mu->nreaders == 0);
mu->locked = true;
mu->unpausing = false;
@@ -39,24 +40,23 @@ void cr_rwmutex_rlock(cr_rwmutex_t *mu) {
assert(mu);
cr_assert_in_coroutine();
- struct cr_rwmutex_waiter self = {
+ struct _cr_rwmutex_waiter_list_node self = { .val = {
.is_reader = true,
.cid = cr_getcid(),
- };
- lm_sll_push_to_rear(&mu->waiters, &self);
- if (mu->waiters.front != &self.lm_sll_node || (mu->locked && mu->nreaders == 0))
+ }};
+ slist_push_to_rear(&mu->waiters, &self);
+ if (mu->waiters.front != &self || (mu->locked && mu->nreaders == 0))
cr_pause_and_yield();
- assert(mu->waiters.front == &self.lm_sll_node);
+ assert(mu->waiters.front == &self);
/* We now hold the lock (and are mu->waiters.front). */
- lm_sll_pop_from_front(&mu->waiters);
+ slist_pop_from_front(&mu->waiters);
mu->nreaders++;
mu->locked = true;
- struct cr_rwmutex_waiter *waiter =
- lm_sll_node_cast(struct cr_rwmutex_waiter, mu->waiters.front);
- if (waiter && waiter->is_reader) {
+ struct _cr_rwmutex_waiter_list_node *waiter = mu->waiters.front;
+ if (waiter && waiter->val.is_reader) {
assert(mu->unpausing);
- cr_unpause(waiter->cid);
+ cr_unpause(waiter->val.cid);
} else {
mu->unpausing = false;
}
@@ -70,10 +70,9 @@ void cr_rwmutex_unlock(cr_rwmutex_t *mu) {
assert(mu->nreaders == 0);
assert(!mu->unpausing);
if (mu->waiters.front) {
- struct cr_rwmutex_waiter *waiter =
- lm_sll_node_cast(struct cr_rwmutex_waiter, mu->waiters.front);
+ struct _cr_rwmutex_waiter_list_node *waiter = mu->waiters.front;
mu->unpausing = true;
- cr_unpause(waiter->cid);
+ cr_unpause(waiter->val.cid);
} else {
mu->locked = false;
}
@@ -88,11 +87,10 @@ void cr_rwmutex_runlock(cr_rwmutex_t *mu) {
mu->nreaders--;
if (mu->nreaders == 0 && !mu->unpausing) {
if (mu->waiters.front) {
- struct cr_rwmutex_waiter *waiter =
- lm_sll_node_cast(struct cr_rwmutex_waiter, mu->waiters.front);
- assert(!waiter->is_reader);
+ struct _cr_rwmutex_waiter_list_node *waiter = mu->waiters.front;
+ assert(!waiter->val.is_reader);
mu->unpausing = true;
- cr_unpause(waiter->cid);
+ cr_unpause(waiter->val.cid);
} else {
mu->locked = false;
}
diff --git a/libcr_ipc/sema.c b/libcr_ipc/sema.c
index cb984b6..f2ac9b6 100644
--- a/libcr_ipc/sema.c
+++ b/libcr_ipc/sema.c
@@ -5,14 +5,15 @@
*/
#include <libcr/coroutine.h> /* for cid_t, cr_* */
+#include <libmisc/assert.h>
#define IMPLEMENTATION_FOR_LIBCR_IPC_SEMA_H YES
#include <libcr_ipc/sema.h>
struct cr_sema_waiter {
- lm_sll_node;
- cid_t cid;
+ cid_t cid;
};
+SLIST_DECLARE_NODE(_cr_sema_waiter_list, struct cr_sema_waiter);
void cr_sema_signal(cr_sema_t *sema) {
assert(sema);
@@ -21,8 +22,7 @@ void cr_sema_signal(cr_sema_t *sema) {
bool saved = cr_save_and_disable_interrupts();
sema->cnt++;
if (sema->waiters.front && !sema->unpausing) {
- cr_unpause(
- lm_sll_node_cast(struct cr_sema_waiter, sema->waiters.front)->cid);
+ cr_unpause(sema->waiters.front->val.cid);
sema->unpausing = true;
}
cr_restore_interrupts(saved);
@@ -34,8 +34,7 @@ void cr_sema_signal_from_intrhandler(cr_sema_t *sema) {
sema->cnt++;
if (sema->waiters.front && !sema->unpausing) {
- cr_unpause_from_intrhandler(
- lm_sll_node_cast(struct cr_sema_waiter, sema->waiters.front)->cid);
+ cr_unpause_from_intrhandler(sema->waiters.front->val.cid);
sema->unpausing = true;
}
}
@@ -46,18 +45,17 @@ void cr_sema_wait(cr_sema_t *sema) {
bool saved = cr_save_and_disable_interrupts();
- struct cr_sema_waiter self = {
+ struct _cr_sema_waiter_list_node self = { .val = {
.cid = cr_getcid(),
- };
- lm_sll_push_to_rear(&sema->waiters, &self);
- if (sema->waiters.front != &self.lm_sll_node || !sema->cnt)
+ }};
+ slist_push_to_rear(&sema->waiters, &self);
+ if (sema->waiters.front != &self || !sema->cnt)
cr_pause_and_yield();
- assert(sema->waiters.front == &self.lm_sll_node && sema->cnt);
- lm_sll_pop_from_front(&sema->waiters);
+ assert(sema->waiters.front == &self && sema->cnt);
+ slist_pop_from_front(&sema->waiters);
sema->cnt--;
if (sema->cnt && sema->waiters.front)
- cr_unpause(
- lm_sll_node_cast(struct cr_sema_waiter, sema->waiters.front)->cid);
+ cr_unpause(sema->waiters.front->val.cid);
else
sema->unpausing = false;
cr_restore_interrupts(saved);
diff --git a/libcr_ipc/tests/test_chan.c b/libcr_ipc/tests/test_chan.c
index 9b6f018..e5d9dc8 100644
--- a/libcr_ipc/tests/test_chan.c
+++ b/libcr_ipc/tests/test_chan.c
@@ -15,12 +15,12 @@ COROUTINE cr_producer(void *_ch) {
intchan_t *ch = _ch;
cr_begin();
- intchan_send(ch, 1);
+ cr_chan_send(ch, 1);
- while (!intchan_can_send(ch))
+ while (!cr_chan_can_send(ch))
cr_yield();
- intchan_send(ch, 2);
+ cr_chan_send(ch, 2);
cr_end();
@@ -31,10 +31,10 @@ COROUTINE cr_consumer(void *_ch) {
intchan_t *ch = _ch;
cr_begin();
- x = intchan_recv(ch);
+ x = cr_chan_recv(ch);
test_assert(x == 1);
- x = intchan_recv(ch);
+ x = cr_chan_recv(ch);
test_assert(x == 2);
cr_end();
diff --git a/libcr_ipc/tests/test_rpc.c b/libcr_ipc/tests/test_rpc.c
index 1e3c471..910b738 100644
--- a/libcr_ipc/tests/test_rpc.c
+++ b/libcr_ipc/tests/test_rpc.c
@@ -18,10 +18,10 @@ COROUTINE cr_caller(void *_ch) {
intrpc_t *ch = _ch;
cr_begin();
- int resp = intrpc_send_req(ch, 1);
+ int resp = cr_rpc_send_req(ch, 1);
test_assert(resp == 2);
- resp = intrpc_send_req(ch, 3);
+ resp = cr_rpc_send_req(ch, 3);
test_assert(resp == 4);
cr_exit();
@@ -31,9 +31,9 @@ COROUTINE cr_worker1(void *_ch) {
intrpc_t *ch = _ch;
cr_begin();
- intrpc_req_t req = intrpc_recv_req(ch);
+ intrpc_req_t req = cr_rpc_recv_req(ch);
test_assert(req.req == 1);
- intrpc_send_resp(req, 2);
+ cr_rpc_send_resp(req, 2);
cr_exit();
}
@@ -42,9 +42,9 @@ COROUTINE cr_worker2(void *_ch) {
intrpc_t *ch = _ch;
cr_begin();
- intrpc_req_t req = intrpc_recv_req(ch);
+ intrpc_req_t req = cr_rpc_recv_req(ch);
test_assert(req.req == 3);
- intrpc_send_resp(req, 4);
+ cr_rpc_send_resp(req, 4);
cr_exit();
}
diff --git a/libcr_ipc/tests/test_select.c b/libcr_ipc/tests/test_select.c
index 1db645b..f0a71a3 100644
--- a/libcr_ipc/tests/test_select.c
+++ b/libcr_ipc/tests/test_select.c
@@ -65,7 +65,7 @@ COROUTINE cr_producer(void *_n) {
int n = *(int *)_n;
cr_begin();
- intchan_send(&ch[n], n);
+ cr_chan_send(&ch[n], n);
cr_end();
}
@@ -73,7 +73,7 @@ COROUTINE cr_producer(void *_n) {
COROUTINE cr_final(void *) {
cr_begin();
- int ret = intchan_recv(&fch);
+ int ret = cr_chan_recv(&fch);
printf("ret=%d\n", ret);
test_assert(ret == 567);
diff --git a/libhw_cr/w5500.c b/libhw_cr/w5500.c
index fa427d9..c04e344 100644
--- a/libhw_cr/w5500.c
+++ b/libhw_cr/w5500.c
@@ -217,7 +217,7 @@ static COROUTINE w5500_irq_cr(void *_chip) {
}
if (send_bits) {
debugf("w5500_irq_cr(): signal sock[%"PRIu8"]->write_ch", socknum);
- _w5500_sockintr_ch_send(&socket->write_ch, send_bits);
+ cr_chan_send(&socket->write_ch, send_bits);
}
break;
}
@@ -666,7 +666,7 @@ static ssize_t w5500_tcp_writev(struct _w5500_socket *socket, const struct iovec
w5500_socket_cmd(socket, CMD_SEND);
cr_mutex_unlock(&chip->mu);
- switch (_w5500_sockintr_ch_recv(&socket->write_ch)) {
+ switch (cr_chan_recv(&socket->write_ch)) {
case SOCKINTR_SEND_OK:
debugf(" => sent %zu", freesize);
done += freesize;
@@ -853,7 +853,7 @@ static ssize_t w5500_udp_sendto(struct _w5500_socket *socket, void *buf, size_t
w5500_socket_cmd(socket, CMD_SEND);
cr_mutex_unlock(&chip->mu);
- switch (_w5500_sockintr_ch_recv(&socket->write_ch)) {
+ switch (cr_chan_recv(&socket->write_ch)) {
case SOCKINTR_SEND_OK:
debugf(" => sent");
return count;
diff --git a/libmisc/include/libmisc/linkedlist.h b/libmisc/include/libmisc/linkedlist.h
index 8adef66..e8c65db 100644
--- a/libmisc/include/libmisc/linkedlist.h
+++ b/libmisc/include/libmisc/linkedlist.h
@@ -7,40 +7,102 @@
#ifndef _LIBMISC_LINKEDLIST_H_
#define _LIBMISC_LINKEDLIST_H_
-#include <libmisc/assert.h>
-#include <libmisc/macro.h>
+/* low-level (intrusive) singly linked list ***********************************/
-/* singly linked list *********************************************************/
+struct _slist_node {
+ struct _slist_node *rear;
+};
-typedef struct _lm_sll_node {
- struct _lm_sll_node *rear;
-} lm_sll_node;
+struct _slist_root {
+ struct _slist_node *front, *rear;
+};
-typedef struct {
- lm_sll_node *front, *rear;
-} lm_sll_root;
+void _slist_push_to_rear(struct _slist_root *root, struct _slist_node *node);
+void _slist_pop_from_front(struct _slist_root *root);
-#define lm_sll_node_cast(node_typ, node_ptr) \
- LM_CAST_FIELD_TO_STRUCT(node_typ, lm_sll_node, node_ptr)
+/* low-level (intrusive) doubly linked list ***********************************/
-void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node);
-void lm_sll_pop_from_front(lm_sll_root *root);
+struct _dlist_node {
+ struct _dlist_node *front, *rear;
+};
-/* doubly linked list *********************************************************/
+struct _dlist_root {
+ struct _dlist_node *front, *rear;
+};
-typedef struct _lm_dll_node {
- struct _lm_dll_node *front, *rear;
-} lm_dll_node;
+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);
-typedef struct {
- lm_dll_node *front, *rear;
-} lm_dll_root;
+/* singly linked list (non-intrusive) *****************************************/
-#define lm_dll_node_cast(node_typ, node_ptr) \
- LM_CAST_FIELD_TO_STRUCT(node_typ, lm_dll_node, node_ptr)
+#define SLIST_DECLARE(NAME) \
+ struct NAME##_node; \
+ struct NAME { \
+ struct NAME##_node *front, *rear; \
+ struct NAME *_slist_root_typ[0]; \
+ }
-void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node);
-void lm_dll_remove(lm_dll_root *root, lm_dll_node *node);
-void lm_dll_pop_from_front(lm_dll_root *root);
+#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/map.h b/libmisc/include/libmisc/map.h
index f846f57..41ac069 100644
--- a/libmisc/include/libmisc/map.h
+++ b/libmisc/include/libmisc/map.h
@@ -15,12 +15,14 @@
/* Type ***********************************************************************/
+DLIST_DECLARE(_map_kv_list);
+
struct _map {
- size_t len;
- size_t nbuckets;
- lm_dll_root *buckets;
+ size_t len;
+ size_t nbuckets;
+ struct _map_kv_list *buckets;
- unsigned iterating;
+ unsigned int iterating;
size_t sizeof_kv;
size_t offsetof_k, sizeof_k;
@@ -30,25 +32,26 @@ struct _map {
/**
* 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_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].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); \
- } \
+#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 ********************************************************************/
@@ -64,8 +67,8 @@ struct _map {
*/
#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); \
+ 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);
@@ -73,10 +76,10 @@ 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); \
+#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);
@@ -84,11 +87,11 @@ 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); \
+#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);
@@ -100,18 +103,13 @@ 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;
+ struct _map *m;
+ void *keyp;
+ void **valpp;
- size_t i;
- struct _map_kv *kv;
+ size_t i;
+ struct _map_kv_list_node *kv;
};
/**
@@ -128,8 +126,8 @@ struct _map_iter {
#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 (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); \
diff --git a/libmisc/linkedlist.c b/libmisc/linkedlist.c
index 5fe0977..71a0aa9 100644
--- a/libmisc/linkedlist.c
+++ b/libmisc/linkedlist.c
@@ -6,11 +6,13 @@
#include <stddef.h> /* for NULL */
+#include <libmisc/assert.h>
+
#include <libmisc/linkedlist.h>
/* singly linked list *********************************************************/
-void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node) {
+void _slist_push_to_rear(struct _slist_root *root, struct _slist_node *node) {
assert(root);
node->rear = NULL;
if (root->rear)
@@ -20,7 +22,7 @@ void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node) {
root->rear = node;
}
-void lm_sll_pop_from_front(lm_sll_root *root) {
+void _slist_pop_from_front(struct _slist_root *root) {
assert(root);
assert(root->front);
root->front = root->front->rear;
@@ -30,7 +32,7 @@ void lm_sll_pop_from_front(lm_sll_root *root) {
/* doubly linked list *********************************************************/
-void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node) {
+void _dlist_push_to_rear(struct _dlist_root *root, struct _dlist_node *node) {
assert(root);
assert(node);
node->front = root->rear;
@@ -42,7 +44,7 @@ void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node) {
root->rear = node;
}
-void lm_dll_remove(lm_dll_root *root, lm_dll_node *node) {
+void _dlist_remove(struct _dlist_root *root, struct _dlist_node *node) {
assert(root);
assert(node);
if (node->front)
@@ -55,8 +57,8 @@ void lm_dll_remove(lm_dll_root *root, lm_dll_node *node) {
root->rear = node->front;
}
-void lm_dll_pop_from_front(lm_dll_root *root) {
+void _dlist_pop_from_front(struct _dlist_root *root) {
assert(root);
assert(root->front);
- lm_dll_remove(root, root->front);
+ _dlist_remove(root, root->front);
}
diff --git a/libmisc/map.c b/libmisc/map.c
index bb8a2d2..7629c8c 100644
--- a/libmisc/map.c
+++ b/libmisc/map.c
@@ -16,14 +16,19 @@
/* 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) {
+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 *kv) {
+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;
@@ -31,8 +36,8 @@ static inline void *_map_kv_valp(struct _map *m, struct _map_kv *kv) {
static inline void _map_lookup(struct _map *m, void *keyp,
hash_t *ret_hash,
- lm_dll_root **ret_bucket,
- struct _map_kv **ret_kv) {
+ struct _map_kv_list **ret_bucket,
+ struct _map_kv_list_node **ret_kv) {
assert(m);
assert(keyp);
assert(ret_hash);
@@ -45,8 +50,8 @@ static inline void _map_lookup(struct _map *m, void *keyp,
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) &&
+ 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;
@@ -58,13 +63,13 @@ static inline void _map_lookup(struct _map *m, void *keyp,
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));
+ 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 *kv = cast(m->buckets[i].front);
- lm_dll_pop_from_front(&m->buckets[i]);
+ 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);
- lm_dll_push_to_rear(&new_buckets[h % new_nbuckets], kv);
+ dlist_push_to_rear(&new_buckets[h % new_nbuckets], kv);
}
}
m->nbuckets = new_nbuckets;
@@ -91,8 +96,8 @@ void *_map_load(struct _map *m, void *keyp) {
assert(keyp);
hash_t h;
- lm_dll_root *bucket;
- struct _map_kv *kv;
+ struct _map_kv_list *bucket;
+ struct _map_kv_list_node *kv;
_map_lookup(m, keyp, &h, &bucket, &kv);
if (!kv)
@@ -105,16 +110,16 @@ bool _map_del(struct _map *m, void *keyp) {
assert(keyp);
hash_t h;
- lm_dll_root *bucket;
- struct _map_kv *kv;
+ struct _map_kv_list *bucket;
+ struct _map_kv_list_node *kv;
_map_lookup(m, keyp, &h, &bucket, &kv);
if (!kv)
return false;
- if (kv->flags & FLAG_ITER) {
- kv->flags |= FLAG_DEL;
+ if (kv->val.flags & FLAG_ITER) {
+ kv->val.flags |= FLAG_DEL;
} else {
- lm_dll_remove(bucket, kv);
+ dlist_remove(bucket, kv);
free(kv);
}
m->len--;
@@ -127,12 +132,12 @@ void *_map_store(struct _map *m, void *keyp, void *valp) {
assert(valp);
hash_t h;
- lm_dll_root *bucket;
- struct _map_kv *old;
+ struct _map_kv_list *bucket;
+ struct _map_kv_list_node *old;
_map_lookup(m, keyp, &h, &bucket, &old);
if (old) {
- lm_dll_remove(bucket, old);
+ dlist_remove(bucket, old);
free(old);
m->len--;
}
@@ -141,10 +146,10 @@ void *_map_store(struct _map *m, void *keyp, void *valp) {
h = hash(keyp, m->sizeof_k);
bucket = &m->buckets[h % m->nbuckets];
}
- struct _map_kv *kv = calloc(1, m->sizeof_kv);
+ 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);
- lm_dll_push_to_rear(bucket, kv);
+ dlist_push_to_rear(bucket, kv);
return _map_kv_valp(m, kv);
}
@@ -153,8 +158,8 @@ void _map_free(struct _map *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]);
+ struct _map_kv_list_node *kv = m->buckets[i].front;
+ dlist_pop_from_front(&m->buckets[i]);
free(kv);
}
}
@@ -199,14 +204,14 @@ bool _map_iter_next(struct _map_iter *state) {
return false;
while (!state->m->buckets[state->i].front)
state->i++;
- state->kv = cast(state->m->buckets[state->i].front);
+ state->kv = state->m->buckets[state->i].front;
} else {
- struct _map_kv *old_kv = state->kv;
- state->kv = cast(old_kv->rear);
+ struct _map_kv_list_node *old_kv = state->kv;
+ state->kv = old_kv->rear;
- old_kv->flags &= ~FLAG_ITER;
- if (old_kv->flags & FLAG_DEL) {
- lm_dll_remove(&state->m->buckets[state->i], old_kv);
+ 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);
}
@@ -214,10 +219,10 @@ bool _map_iter_next(struct _map_iter *state) {
state->i++;
if (state->i == state->m->nbuckets)
return false;
- state->kv = cast(state->m->buckets[state->i].front);
+ state->kv = state->m->buckets[state->i].front;
}
}
- state->kv->flags |= FLAG_ITER;
+ 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;