diff options
| -rw-r--r-- | man/queue.9 | 43 | ||||
| -rw-r--r-- | src/kernel/queue.h | 37 | ||||
| -rw-r--r-- | src/kernel/vfs/request.c | 20 |
3 files changed, 84 insertions, 16 deletions
diff --git a/man/queue.9 b/man/queue.9 new file mode 100644 index 0000000..d53adf8 --- /dev/null +++ b/man/queue.9 @@ -0,0 +1,43 @@ +.Dd July 14, 2024 +.Dt QUEUE 9 +.Os Camellia +.Sh NAME +.Nm QUEUE_INIT , +.Nm QUEUE_APPEND , +.Nm QUEUE_POP +.Nd macros for intrusive linked lists +.Sh SYNOPSIS +.In kernel/queue.h +.Bd -literal +struct YourNode { + ... + struct YourNode *NAME_next; +}; +struct YourHead { + struct YourNode *head, **slot; +}; +.Ed +.Fn QUEUE_INIT "YourHead *q" +.Fn QUEUE_APPEND "YourHead *q" "NAME" "YourNode *el" +.Ft YourNode * +.Fn QUEUE_POP "YourHead *q" "NAME" +.Sh DESCRIPTION +These macros, inspired by BSD's +.In sys/queue.h , +operate on intrusive linked lists. +Currently, only +.Em queues +\(em singly-linked lists with O(1) insertions at the end \(em +are supported. +.Pp +The linked list internals are intentionally exposed, as they're also meant +to be used by e.g. memory management code for integrity checks. +It's fine to modify them directly. +.Sh RATIONALE +The macros are a bit ugly, but they prevent code duplication, +and using the same implementation everywhere probably makes bugs less likely. +.Pp +I've considered just using +.In sys/queue.h , +which has the benefit of being more familiar to other programmers, +but I dislike how it hides the list internals from the programmer. diff --git a/src/kernel/queue.h b/src/kernel/queue.h new file mode 100644 index 0000000..896824f --- /dev/null +++ b/src/kernel/queue.h @@ -0,0 +1,37 @@ +/* documented in queue(9) */ +#include <kernel/panic.h> + +/* struct QueueNode { + * ... + * struct QueueNode *name_next; + * ... + * } + * struct QueueHead { + * struct QueueNode *head, **slot; + * } + */ + +#define QUEUE_INIT(q) do { \ + (q)->head = NULL; \ + (q)->slot = &(q)->head; \ +} while(0) + +#define QUEUE_APPEND(q, name, el) do { \ + assert((el)->name##_next == NULL); \ + assert((q)->slot != NULL); \ + assert(*(q)->slot == NULL); \ + *(q)->slot = (el); \ + (q)->slot = &(el)->name##_next; \ +} while(0) + +#define QUEUE_POP(q, name) ({ \ + typeof((q)->head) __q_el = (q)->head; \ + if (__q_el) { \ + (q)->head = __q_el->name##_next; \ + __q_el->name##_next = NULL; \ + if ((q)->slot == &__q_el->name##_next) { \ + (q)->slot = &(q)->head; \ + } \ + } \ + __q_el; \ +}) diff --git a/src/kernel/vfs/request.c b/src/kernel/vfs/request.c index 8a80f04..8e6f14a 100644 --- a/src/kernel/vfs/request.c +++ b/src/kernel/vfs/request.c @@ -3,6 +3,7 @@ #include <kernel/malloc.h> #include <kernel/panic.h> #include <kernel/proc.h> +#include <kernel/queue.h> #include <kernel/vfs/request.h> #include <shared/mem.h> @@ -236,32 +237,19 @@ vfsback_provdown(VfsBackend *b) void reqqueue_init(ReqQueue *q) { - q->head = NULL; - q->slot = &q->head; + QUEUE_INIT(q); } void reqqueue_join(ReqQueue *q, VfsReq *req) { - assert(req->reqqueue_next == NULL); - assert(q->slot != NULL); - assert(*q->slot == NULL); - *q->slot = req; - q->slot = &req->reqqueue_next; + QUEUE_APPEND(q, reqqueue, req); } VfsReq * reqqueue_pop(ReqQueue *q) { - VfsReq *req = q->head; - if (req) { - q->head = req->reqqueue_next; - req->reqqueue_next = NULL; - if (q->slot == &req->reqqueue_next) { - q->slot = &q->head; - } - } - return req; + return QUEUE_POP(q, reqqueue); } void |