diff options
Diffstat (limited to 'libmisc')
| -rw-r--r-- | libmisc/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | libmisc/include/libmisc/linkedlist.h | 46 | ||||
| -rw-r--r-- | libmisc/include/libmisc/macro.h | 13 | ||||
| -rw-r--r-- | libmisc/linkedlist.c | 62 |
4 files changed, 121 insertions, 1 deletions
diff --git a/libmisc/CMakeLists.txt b/libmisc/CMakeLists.txt index 4599ead..c80e060 100644 --- a/libmisc/CMakeLists.txt +++ b/libmisc/CMakeLists.txt @@ -8,6 +8,7 @@ target_include_directories(libmisc PUBLIC INTERFACE ${CMAKE_CURRENT_SOURCE_DIR}/ target_sources(libmisc INTERFACE assert.c intercept.c + linkedlist.c log.c ) target_compile_options(libmisc INTERFACE "$<$<COMPILE_LANGUAGE:C>:-fplan9-extensions>") diff --git a/libmisc/include/libmisc/linkedlist.h b/libmisc/include/libmisc/linkedlist.h new file mode 100644 index 0000000..8adef66 --- /dev/null +++ b/libmisc/include/libmisc/linkedlist.h @@ -0,0 +1,46 @@ +/* libmisc/linkedlist.h - Singly- and doubly- linked lists + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#ifndef _LIBMISC_LINKEDLIST_H_ +#define _LIBMISC_LINKEDLIST_H_ + +#include <libmisc/assert.h> +#include <libmisc/macro.h> + +/* 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) \ + 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); + +/* 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) \ + 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); +void lm_dll_pop_from_front(lm_dll_root *root); + +#endif /* _LIBMISC_LINKEDLIST_H_ */ diff --git a/libmisc/include/libmisc/macro.h b/libmisc/include/libmisc/macro.h index b3e235c..6cb15fb 100644 --- a/libmisc/include/libmisc/macro.h +++ b/libmisc/include/libmisc/macro.h @@ -14,9 +14,20 @@ #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); \ + _fptr \ + ? ((STRUCT_TYP*)( ((void*)_fptr) - offsetof(STRUCT_TYP, FIELD_NAME))) \ + : NULL; \ +}) + +/* 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` */ diff --git a/libmisc/linkedlist.c b/libmisc/linkedlist.c new file mode 100644 index 0000000..5fe0977 --- /dev/null +++ b/libmisc/linkedlist.c @@ -0,0 +1,62 @@ +/* libmisc/linkedlist.c - Singly- and doubly- linked lists + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <stddef.h> /* for NULL */ + +#include <libmisc/linkedlist.h> + +/* singly linked list *********************************************************/ + +void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node) { + assert(root); + node->rear = NULL; + if (root->rear) + root->rear->rear = node; + else + root->front = node; + root->rear = node; +} + +void lm_sll_pop_from_front(lm_sll_root *root) { + assert(root); + assert(root->front); + root->front = root->front->rear; + if (!root->front) + root->rear = NULL; +} + +/* doubly linked list *********************************************************/ + +void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node) { + assert(root); + assert(node); + node->front = root->rear; + node->rear = NULL; + if (root->rear) + root->rear->rear = node; + else + root->front = node; + root->rear = node; +} + +void lm_dll_remove(lm_dll_root *root, lm_dll_node *node) { + assert(root); + assert(node); + if (node->front) + node->front->rear = node->rear; + else + root->front = node->rear; + if (node->rear) + node->rear->front = node->front; + else + root->rear = node->front; +} + +void lm_dll_pop_from_front(lm_dll_root *root) { + assert(root); + assert(root->front); + lm_dll_remove(root, root->front); +} |