diff options
author | Luke T. Shumaker <lukeshu@lukeshu.com> | 2025-04-15 08:42:24 -0600 |
---|---|---|
committer | Luke T. Shumaker <lukeshu@lukeshu.com> | 2025-04-15 08:42:24 -0600 |
commit | 802ed1e3cd0252cafd1be2aada0addf4d3f7eb2e (patch) | |
tree | 70f49ed30f0f9839709a093c6af54661eeaad4ee | |
parent | 0450e14b3a86e4448537c03253eeebf509f8909e (diff) | |
parent | 32a1b710b40ce9d53cd0a7bc0c183da87e07f397 (diff) |
-rw-r--r-- | cmd/sbc_harness/usb_keyboard.c | 6 | ||||
-rw-r--r-- | lib9p/srv.c | 22 | ||||
-rw-r--r-- | libcr_ipc/chan.c | 38 | ||||
-rw-r--r-- | libcr_ipc/include/libcr_ipc/chan.h | 189 | ||||
-rw-r--r-- | libcr_ipc/include/libcr_ipc/mutex.h | 8 | ||||
-rw-r--r-- | libcr_ipc/include/libcr_ipc/rpc.h | 185 | ||||
-rw-r--r-- | libcr_ipc/include/libcr_ipc/rwmutex.h | 12 | ||||
-rw-r--r-- | libcr_ipc/include/libcr_ipc/sema.h | 10 | ||||
-rw-r--r-- | libcr_ipc/mutex.c | 13 | ||||
-rw-r--r-- | libcr_ipc/rpc.c | 35 | ||||
-rw-r--r-- | libcr_ipc/rwmutex.c | 46 | ||||
-rw-r--r-- | libcr_ipc/sema.c | 26 | ||||
-rw-r--r-- | libcr_ipc/tests/test_chan.c | 10 | ||||
-rw-r--r-- | libcr_ipc/tests/test_rpc.c | 12 | ||||
-rw-r--r-- | libcr_ipc/tests/test_select.c | 4 | ||||
-rw-r--r-- | libhw_cr/w5500.c | 6 | ||||
-rw-r--r-- | libmisc/include/libmisc/linkedlist.h | 112 | ||||
-rw-r--r-- | libmisc/include/libmisc/map.h | 86 | ||||
-rw-r--r-- | libmisc/linkedlist.c | 14 | ||||
-rw-r--r-- | libmisc/map.c | 73 |
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; |