diff options
| -rw-r--r-- | Makefile | 1 | ||||
| -rw-r--r-- | src/config.h | 11 | ||||
| -rw-r--r-- | src/list.c | 169 | ||||
| -rw-r--r-- | src/list.h | 170 |
4 files changed, 351 insertions, 0 deletions
@@ -223,6 +223,7 @@ LIBBFS := \ $(OBJ)/src/eval.o \ $(OBJ)/src/exec.o \ $(OBJ)/src/fsade.o \ + $(OBJ)/src/list.o \ $(OBJ)/src/mtab.o \ $(OBJ)/src/opt.o \ $(OBJ)/src/parse.o \ diff --git a/src/config.h b/src/config.h index 34ae11d..cee8511 100644 --- a/src/config.h +++ b/src/config.h @@ -147,6 +147,17 @@ */ #define BFS_COUNTOF(array) (sizeof(array) / sizeof(0[array])) +// BFS_CONTAINER_OF() helper +static inline char *bfs_container_offset(char *ptr, ptrdiff_t offset, size_t unused) { + return ptr ? ptr - offset : NULL; +} + +/** + * Move a pointer from a field to its outer struct. + */ +#define BFS_CONTAINER_OF(ptr, type, member) \ + ((type *)bfs_container_offset((char *)(ptr), offsetof(type, member), sizeof((ptr) - &((type *)NULL)->member))) + // Lower bound on BFS_FLEX_SIZEOF() #define BFS_FLEX_LB(type, member, length) (offsetof(type, member) + sizeof(((type *)NULL)->member[0]) * (length)) diff --git a/src/list.c b/src/list.c new file mode 100644 index 0000000..dffee19 --- /dev/null +++ b/src/list.c @@ -0,0 +1,169 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +#include "list.h" +#include <assert.h> +#include <stddef.h> + +void slink_init(struct slink *link) { + link->next = NULL; +} + +void slist_init(struct slist *list) { + list->head = NULL; + list->tail = &list->head; +} + +bool slist_is_empty(const struct slist *list) { + return !list->head; +} + +void slist_append(struct slist *list, struct slink *link) { + assert(!link->next); + *list->tail = link; + list->tail = &link->next; +} + +void slist_prepend(struct slist *list, struct slink *link) { + assert(!link->next); + if (!list->head) { + list->tail = &link->next; + } + link->next = list->head; + list->head = link; +} + +void slist_extend(struct slist *dest, struct slist *src) { + if (src->head) { + *dest->tail = src->head; + dest->tail = src->tail; + slist_init(src); + } +} + +struct slink *slist_pop(struct slist *list) { + struct slink *head = list->head; + if (!head) { + return NULL; + } + + list->head = head->next; + if (!list->head) { + list->tail = &list->head; + } + + head->next = NULL; + return head; +} + +void slist_sort(struct slist *list, slist_cmp_fn *cmp_fn, const void *ptr) { + if (!list->head || !list->head->next) { + return; + } + + struct slist left, right; + slist_init(&left); + slist_init(&right); + + // Split + for (struct slink *hare = list->head; hare && (hare = hare->next); hare = hare->next) { + slist_append(&left, slist_pop(list)); + } + slist_extend(&right, list); + + // Recurse + slist_sort(&left, cmp_fn, ptr); + slist_sort(&right, cmp_fn, ptr); + + // Merge + while (left.head && right.head) { + if (cmp_fn(left.head, right.head, ptr)) { + slist_append(list, slist_pop(&left)); + } else { + slist_append(list, slist_pop(&right)); + } + } + slist_extend(list, &left); + slist_extend(list, &right); +} + +void link_init(struct link *link) { + link->prev = NULL; + link->next = NULL; +} + +void list_init(struct list *list) { + list->head = NULL; + list->tail = NULL; +} + +bool list_is_empty(const struct list *list) { + return !list->head; +} + +void list_append(struct list *list, struct link *link) { + list_insert_after(list, list->tail, link); +} + +void list_prepend(struct list *list, struct link *link) { + list_insert_after(list, NULL, link); +} + +void list_insert_after(struct list *list, struct link *target, struct link *link) { + assert(!list_attached(list, link)); + + if (target) { + link->prev = target; + link->next = target->next; + } else { + link->next = list->head; + } + + if (link->prev) { + link->prev->next = link; + } else { + list->head = link; + } + + if (link->next) { + link->next->prev = link; + } else { + list->tail = link; + } +} + +void list_remove(struct list *list, struct link *link) { + if (link->prev) { + assert(list->head != link); + link->prev->next = link->next; + } else { + assert(list->head == link); + list->head = link->next; + } + + if (link->next) { + assert(list->tail != link); + link->next->prev = link->prev; + } else { + assert(list->tail == link); + list->tail = link->prev; + } + + link->prev = NULL; + link->next = NULL; +} + +struct link *list_pop(struct list *list) { + struct link *head = list->head; + if (!head) { + return NULL; + } + + list_remove(list, head); + return head; +} + +bool list_attached(const struct list *list, const struct link *link) { + return link->prev || list->head == link + || link->next || list->tail == link; +} diff --git a/src/list.h b/src/list.h new file mode 100644 index 0000000..1985413 --- /dev/null +++ b/src/list.h @@ -0,0 +1,170 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +/** + * Intrusive linked lists. + */ + +#ifndef BFS_LIST_H +#define BFS_LIST_H + +#include "config.h" +#include <stdbool.h> + +/** + * A singly-linked list entry. + */ +struct slink { + struct slink *next; +}; + +/** Initialize a list entry. */ +void slink_init(struct slink *link); + +/** + * A singly-linked list. + */ +struct slist { + struct slink *head; + struct slink **tail; +}; + +/** Initialize an empty list. */ +void slist_init(struct slist *list); + +/** Check if a list is empty. */ +bool slist_is_empty(const struct slist *list); + +/** Add an entry at the tail of the list. */ +void slist_append(struct slist *list, struct slink *link); + +/** Add an entry at the head of the list. */ +void slist_prepend(struct slist *list, struct slink *link); + +/** Add an entire list at the tail of the list. */ +void slist_extend(struct slist *dest, struct slist *src); + +/** Remove the head of the list. */ +struct slink *slist_pop(struct slist *list); + +/** + * Comparison function type for slist_sort(). + * + * @param left + * The left-hand side of the comparison. + * @param right + * The right-hand side of the comparison. + * @param ptr + * An arbitrary pointer passed to slist_sort(). + * @return + * Whether left <= right. + */ +typedef bool slist_cmp_fn(struct slink *left, struct slink *right, const void *ptr); + +/** Sort a list. */ +void slist_sort(struct slist *list, slist_cmp_fn *cmp_fn, const void *ptr); + +/** + * A doubly-linked list entry. + */ +struct link { + struct link *prev; + struct link *next; +}; + +/** Initialize a list entry. */ +void link_init(struct link *link); + +/** + * A doubly-linked list. + */ +struct list { + struct link *head; + struct link *tail; +}; + +/** Initialize an empty list. */ +void list_init(struct list *list); + +/** Check if a list is empty. */ +bool list_is_empty(const struct list *list); + +/** Add an entry at the tail of the list. */ +void list_append(struct list *list, struct link *link); + +/** Add an entry at the head of the list. */ +void list_prepend(struct list *list, struct link *link); + +/** Insert an entry after the target entry. */ +void list_insert_after(struct list *list, struct link *target, struct link *link); + +/** Remove an entry from a list. */ +void list_remove(struct list *list, struct link *link); + +/** Remove the head of the list. */ +struct link *list_pop(struct list *list); + +/** Check if a link is attached to a list. */ +bool list_attached(const struct list *list, const struct link *link); + +// Helper for LIST_FOR_EACH_*() +#define LIST_FOR_EACH_IMPL(entry, type, i, member, ...) \ + for (type *_next, *i = BFS_CONTAINER_OF(entry, type, member); \ + i && (_next = BFS_CONTAINER_OF(i->member.next, type, member), true); \ + i = _next) + +/** + * Iterate over a list from the given entry. + * + * @param entry + * The entry to start from. + * @param type + * The type of the list entries. + * @param i + * The name of the loop variable, declared as type *i. + * @param member + * The name of the list link field (default: link). + */ +#define LIST_FOR_EACH_FROM(...) \ + LIST_FOR_EACH_IMPL(__VA_ARGS__, link,) + +/** + * Iterate over a list. + * + * @param list + * The list to iterate over. + * @param type + * The type of the list entries. + * @param i + * The name of the loop variable, declared as type *i. + * @param member + * The name of the list link field (default: link). + */ +#define LIST_FOR_EACH(list, ...) \ + LIST_FOR_EACH_FROM((list)->head, __VA_ARGS__) + +// Pop from a list or slist +#define LIST_POP(l) _Generic((l), \ + struct list *: list_pop((struct list *)l), \ + struct slist *: slist_pop((struct slist *)l)) + +// Helper for LIST_DRAIN() +#define LIST_DRAIN_IMPL(list, type, i, member, ...) \ + for (type *i; (i = BFS_CONTAINER_OF(LIST_POP(list), type, member));) + +/** + * Drain the entries from a list. + * + * @param list + * The list to drain. + * @param type + * The type of the list entries. + * @param i + * The name of the loop variable, declared as type *i. + * @param member + * The name of the list link field (default: link). + */ +#define LIST_DRAIN(...) \ + LIST_DRAIN_IMPL(__VA_ARGS__, link,) + +#endif // BFS_LIST_H |