From 8db1fb76584a22ec4f93da1b52b3ff63a8e21c96 Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Fri, 11 Apr 2025 07:21:28 -0600 Subject: Move the linkedlist to libmisc --- libmisc/include/libmisc/linkedlist.h | 57 ++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100644 libmisc/include/libmisc/linkedlist.h (limited to 'libmisc/include') diff --git a/libmisc/include/libmisc/linkedlist.h b/libmisc/include/libmisc/linkedlist.h new file mode 100644 index 0000000..045a468 --- /dev/null +++ b/libmisc/include/libmisc/linkedlist.h @@ -0,0 +1,57 @@ +/* libmisc/linkedlist.h - Singly- and doubly- linked lists + * + * Copyright (C) 2024-2025 Luke T. Shumaker + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#ifndef _LIBMISC_LINKEDLIST_H_ +#define _LIBMISC_LINKEDLIST_H_ + +#include + +/* singly linked list *********************************************************/ + +typedef struct _lm_sll_node { + struct _lm_sll_node *rear; +} lm_sll_node; + +typedef struct { + lm_sll_node *front, *rear; +} lm_sll_root; + +#define lm_sll_node_cast(node_typ, node_ptr) \ + ({ \ + static_assert(_Generic(node_ptr, lm_sll_node *: 1, default: 0), \ + "typeof("#node_ptr") != lm_sll_node *"); \ + assert(node_ptr); \ + static_assert(offsetof(node_typ, lm_sll_node) == 0); \ + ((node_typ*)(node_ptr)); \ + }) + +void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node); +void lm_sll_pop_from_front(lm_sll_root *root); + +/* doubly linked list *********************************************************/ + +typedef struct _lm_dll_node { + struct _lm_dll_node *front, *rear; +} lm_dll_node; + +typedef struct { + lm_dll_node *front, *rear; +} lm_dll_root; + +#define lm_dll_node_cast(node_typ, node_ptr) \ + ({ \ + static_assert(_Generic(node_ptr, lm_dll_node *: 1, default: 0), \ + "typeof("#node_ptr") != lm_dll_node *"); \ + assert(node_ptr); \ + static_assert(offsetof(node_typ, lm_dll_node) == 0); \ + ((node_typ*)(node_ptr)); \ + }) + +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); + +#endif /* _LIBMISC_LINKEDLIST_H_ */ -- cgit v1.2.3-2-g168b From 72028362733820bbd22fd6bbe84c432110329739 Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Fri, 11 Apr 2025 09:25:44 -0600 Subject: libmisc: Add LM_CAST_FIELD_TO_STRUCT, don't require lm_[ds]ll_node to be first --- libmisc/include/libmisc/linkedlist.h | 21 +++++---------------- libmisc/include/libmisc/macro.h | 12 +++++++++++- 2 files changed, 16 insertions(+), 17 deletions(-) (limited to 'libmisc/include') diff --git a/libmisc/include/libmisc/linkedlist.h b/libmisc/include/libmisc/linkedlist.h index 045a468..8adef66 100644 --- a/libmisc/include/libmisc/linkedlist.h +++ b/libmisc/include/libmisc/linkedlist.h @@ -8,6 +8,7 @@ #define _LIBMISC_LINKEDLIST_H_ #include +#include /* singly linked list *********************************************************/ @@ -19,14 +20,8 @@ typedef struct { lm_sll_node *front, *rear; } lm_sll_root; -#define lm_sll_node_cast(node_typ, node_ptr) \ - ({ \ - static_assert(_Generic(node_ptr, lm_sll_node *: 1, default: 0), \ - "typeof("#node_ptr") != lm_sll_node *"); \ - assert(node_ptr); \ - static_assert(offsetof(node_typ, lm_sll_node) == 0); \ - ((node_typ*)(node_ptr)); \ - }) +#define lm_sll_node_cast(node_typ, node_ptr) \ + LM_CAST_FIELD_TO_STRUCT(node_typ, lm_sll_node, node_ptr) void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node); void lm_sll_pop_from_front(lm_sll_root *root); @@ -41,14 +36,8 @@ typedef struct { lm_dll_node *front, *rear; } lm_dll_root; -#define lm_dll_node_cast(node_typ, node_ptr) \ - ({ \ - static_assert(_Generic(node_ptr, lm_dll_node *: 1, default: 0), \ - "typeof("#node_ptr") != lm_dll_node *"); \ - assert(node_ptr); \ - static_assert(offsetof(node_typ, lm_dll_node) == 0); \ - ((node_typ*)(node_ptr)); \ - }) +#define lm_dll_node_cast(node_typ, node_ptr) \ + LM_CAST_FIELD_TO_STRUCT(node_typ, lm_dll_node, node_ptr) 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); diff --git a/libmisc/include/libmisc/macro.h b/libmisc/include/libmisc/macro.h index b3e235c..4591b68 100644 --- a/libmisc/include/libmisc/macro.h +++ b/libmisc/include/libmisc/macro.h @@ -14,9 +14,19 @@ #define LM_NEVER_INLINE [[gnu::noinline]] #define LM_FLATTEN [[gnu::flatten]] -/* numeric */ +/* types */ #define LM_ARRAY_LEN(ary) (sizeof(ary)/sizeof((ary)[0])) + +#define LM_CAST_FIELD_TO_STRUCT(STRUCT_TYP, FIELD_NAME, PTR_TO_FIELD) ({ \ + /* The _fptr assignment is to get the compiler to do type checking. */ \ + typeof(((STRUCT_TYP *)NULL)->FIELD_NAME) *_fptr = (PTR_TO_FIELD); \ + assert(_fptr); \ + ((STRUCT_TYP*)( ((void*)_fptr) - offsetof(STRUCT_TYP, FIELD_NAME))); \ +}) + +/* numeric */ + #define LM_CEILDIV(n, d) ( ((n)+(d)-1) / (d) ) /** Return ceil(n/d) */ #define LM_ROUND_UP(n, d) ( LM_CEILDIV(n, d) * (d) ) /** Return `n` rounded up to the nearest multiple of `d` */ #define LM_ROUND_DOWN(n, d) ( ((n)/(d)) * (d) ) /** Return `n` rounded down to the nearest multiple of `d` */ -- cgit v1.2.3-2-g168b From 15989609ffafc5b5eef4dbde49419842a8b249fd Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Fri, 11 Apr 2025 09:35:22 -0600 Subject: libmisc: LM_CAST_FIELD_TO_STRUCT: Allow the pointer to be NULL --- libmisc/include/libmisc/macro.h | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'libmisc/include') diff --git a/libmisc/include/libmisc/macro.h b/libmisc/include/libmisc/macro.h index 4591b68..6cb15fb 100644 --- a/libmisc/include/libmisc/macro.h +++ b/libmisc/include/libmisc/macro.h @@ -18,11 +18,12 @@ #define LM_ARRAY_LEN(ary) (sizeof(ary)/sizeof((ary)[0])) -#define LM_CAST_FIELD_TO_STRUCT(STRUCT_TYP, FIELD_NAME, PTR_TO_FIELD) ({ \ - /* The _fptr assignment is to get the compiler to do type checking. */ \ - typeof(((STRUCT_TYP *)NULL)->FIELD_NAME) *_fptr = (PTR_TO_FIELD); \ - assert(_fptr); \ - ((STRUCT_TYP*)( ((void*)_fptr) - offsetof(STRUCT_TYP, FIELD_NAME))); \ +#define LM_CAST_FIELD_TO_STRUCT(STRUCT_TYP, FIELD_NAME, PTR_TO_FIELD) ({ \ + /* The _fptr assignment is to get the compiler to do type checking. */ \ + typeof(((STRUCT_TYP *)NULL)->FIELD_NAME) *_fptr = (PTR_TO_FIELD); \ + _fptr \ + ? ((STRUCT_TYP*)( ((void*)_fptr) - offsetof(STRUCT_TYP, FIELD_NAME))) \ + : NULL; \ }) /* numeric */ -- cgit v1.2.3-2-g168b