diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/bftw.c | 136 | ||||
| -rw-r--r-- | src/config.h | 11 | ||||
| -rw-r--r-- | src/list.c | 169 | ||||
| -rw-r--r-- | src/list.h | 447 | ||||
| -rw-r--r-- | src/trie.c | 8 | ||||
| -rw-r--r-- | src/trie.h | 9 | ||||
| -rw-r--r-- | src/xspawn.c | 15 | ||||
| -rw-r--r-- | src/xspawn.h | 4 |
8 files changed, 401 insertions, 398 deletions
@@ -7,6 +7,8 @@ * - struct bftw_file: A file that has been encountered during the traversal. * They have reference-counted links to their parents in the directory tree. * + * - struct bftw_list: A linked list of bftw_file's. + * * - struct bftw_cache: An LRU list of bftw_file's with open file descriptors, * used for openat() to minimize the amount of path re-traversals. * @@ -39,11 +41,14 @@ struct bftw_file { struct bftw_file *parent; /** The root under which this file was found. */ struct bftw_file *root; + /** The next file in the queue, if any. */ + struct bftw_file *next; - /** Queue link. */ - struct slink link; - /** LRU link. */ - struct link lru; + /** LRU list links. */ + struct { + struct bftw_file *prev; + struct bftw_file *next; + } lru; /** This file's depth in the walk. */ size_t depth; @@ -68,36 +73,42 @@ struct bftw_file { char name[]; }; -/** Move from a list entry to a bftw_file. */ -#define BFTW_FILE(...) \ - LIST_ITEM(struct bftw_file, __VA_ARGS__) +/** + * A linked list of bftw_file's. + */ +struct bftw_list { + struct bftw_file *head; + struct bftw_file **tail; +}; /** * A cache of open directories. */ struct bftw_cache { - /** The LRU list. */ - struct list list; + /** The head of the LRU list. */ + struct bftw_file *head; + /** The tail of the LRU list. */ + struct bftw_file *tail; /** The insertion target for the LRU list. */ - struct link *target; + struct bftw_file *target; /** The remaining capacity of the LRU list. */ size_t capacity; }; /** Initialize a cache. */ static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) { - list_init(&cache->list); + LIST_INIT(cache); cache->target = NULL; cache->capacity = capacity; } /** Remove a bftw_file from the cache. */ static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) { - if (cache->target == &file->lru) { - cache->target = cache->target->prev; + if (cache->target == file) { + cache->target = file->lru.prev; } - list_remove(&cache->list, &file->lru); + LIST_REMOVE(cache, file, lru); ++cache->capacity; } @@ -106,7 +117,7 @@ static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) { assert(file->fd >= 0); - if (list_attached(&cache->list, &file->lru)) { + if (LIST_ATTACHED(cache, file, lru)) { bftw_cache_remove(cache, file); } @@ -116,11 +127,11 @@ static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) { /** Pop the least recently used directory from the cache. */ static int bftw_cache_pop(struct bftw_cache *cache) { - if (list_is_empty(&cache->list)) { + struct bftw_file *file = cache->tail; + if (!file) { return -1; } - struct bftw_file *file = BFTW_FILE(cache->list.tail, lru); bftw_file_close(cache, file); return 0; } @@ -138,11 +149,11 @@ static int bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) { assert(cache->capacity > 0); --cache->capacity; - list_insert_after(&cache->list, cache->target, &file->lru); + LIST_INSERT(cache, cache->target, file, lru); // Prefer to keep the root paths open by keeping them at the head of the list if (file->depth == 0) { - cache->target = &file->lru; + cache->target = file; } return 0; @@ -159,8 +170,9 @@ static size_t bftw_child_nameoff(const struct bftw_file *parent) { /** Destroy a cache. */ static void bftw_cache_destroy(struct bftw_cache *cache) { + assert(!cache->head); + assert(!cache->tail); assert(!cache->target); - assert(list_is_empty(&cache->list)); } /** Create a new bftw_file. */ @@ -186,8 +198,8 @@ static struct bftw_file *bftw_file_new(struct bftw_file *parent, const char *nam file->nameoff = 0; } - slink_init(&file->link); - link_init(&file->lru); + file->next = NULL; + file->lru.prev = file->lru.next = NULL; file->refcount = 1; file->fd = -1; @@ -280,16 +292,19 @@ static int bftw_file_open(struct bftw_cache *cache, struct bftw_file *file, cons } // Handle ENAMETOOLONG by manually traversing the path component-by-component - struct slist parents; - slist_init(&parents); - for (struct bftw_file *cur = file; cur != base; cur = cur->parent) { - slist_prepend(&parents, &cur->link); + struct bftw_list parents; + SLIST_INIT(&parents); + + struct bftw_file *cur; + for (cur = file; cur != base; cur = cur->parent) { + SLIST_PREPEND(&parents, cur); } - LIST_DRAIN(&parents, struct bftw_file, cur) { + while ((cur = parents.head)) { if (!cur->parent || cur->parent->fd >= 0) { bftw_file_openat(cache, cur, cur->parent, cur->name); } + SLIST_POP(&parents); } return file->fd; @@ -348,9 +363,9 @@ struct bftw_state { /** The cache of open directories. */ struct bftw_cache cache; /** The queue of files left to explore. */ - struct slist queue; + struct bftw_list queue; /** A batch of files to enqueue. */ - struct slist batch; + struct bftw_list batch; /** The current path. */ char *path; @@ -396,8 +411,8 @@ static int bftw_state_init(struct bftw_state *state, const struct bftw_args *arg bftw_cache_init(&state->cache, args->nopenfd); - slist_init(&state->queue); - slist_init(&state->batch); + SLIST_INIT(&state->queue); + SLIST_INIT(&state->batch); state->file = NULL; state->previous = NULL; @@ -757,7 +772,7 @@ static int bftw_push(struct bftw_state *state, const char *name, bool fill_id) { bftw_fill_id(file, &state->ftwbuf); } - slist_append(&state->batch, &file->link); + SLIST_APPEND(&state->batch, file); return 0; } @@ -800,11 +815,12 @@ static int bftw_build_path(struct bftw_state *state) { * Pop the next file from the queue. */ static int bftw_pop(struct bftw_state *state) { - if (!state->queue.head) { + state->file = state->queue.head; + if (!state->file) { return 0; } - state->file = BFTW_FILE(slist_pop(&state->queue)); + SLIST_POP(&state->queue); if (bftw_build_path(state) != 0) { return -1; @@ -940,8 +956,10 @@ static enum bftw_action bftw_gc_file(struct bftw_state *state, enum bftw_gc_flag * Drain all the files from the queue. */ static void bftw_drain_queue(struct bftw_state *state) { - LIST_DRAIN(&state->queue, struct bftw_file, file) { - state->file = file; + while (state->queue.head) { + state->file = state->queue.head; + SLIST_POP(&state->queue); + bftw_gc_file(state, BFTW_VISIT_NONE); } } @@ -966,21 +984,55 @@ static int bftw_state_destroy(struct bftw_state *state) { return state->error ? -1 : 0; } -/** Comparison function for BFTW_SORT. */ -static bool bftw_file_cmp(struct slink *left, struct slink *right, const void *ptr) { - return strcoll(BFTW_FILE(left)->name, BFTW_FILE(right)->name) <= 0; +/** Sort a bftw_list by filename. */ +static void bftw_list_sort(struct bftw_list *queue) { + if (!queue->head || !queue->head->next) { + return; + } + + struct bftw_list left, right; + SLIST_INIT(&left); + SLIST_INIT(&right); + + // Split + for (struct bftw_file *hare = queue->head; hare && (hare = hare->next); hare = hare->next) { + struct bftw_file *tortoise = queue->head; + SLIST_POP(queue); + SLIST_APPEND(&left, tortoise); + } + SLIST_EXTEND(&right, queue); + + // Recurse + bftw_list_sort(&left); + bftw_list_sort(&right); + + // Merge + while (left.head && right.head) { + struct bftw_file *lf = left.head; + struct bftw_file *rf = right.head; + + if (strcoll(lf->name, rf->name) <= 0) { + SLIST_POP(&left); + SLIST_APPEND(queue, lf); + } else { + SLIST_POP(&right); + SLIST_APPEND(queue, rf); + } + } + SLIST_EXTEND(queue, &left); + SLIST_EXTEND(queue, &right); } /** Finish adding a batch of files. */ static void bftw_batch_finish(struct bftw_state *state) { if (state->flags & BFTW_SORT) { - slist_sort(&state->batch, bftw_file_cmp, NULL); + bftw_list_sort(&state->batch); } if (state->strategy == BFTW_DFS) { - slist_extend(&state->batch, &state->queue); + SLIST_EXTEND(&state->batch, &state->queue); } - slist_extend(&state->queue, &state->batch); + SLIST_EXTEND(&state->queue, &state->batch); } /** diff --git a/src/config.h b/src/config.h index cee8511..34ae11d 100644 --- a/src/config.h +++ b/src/config.h @@ -147,17 +147,6 @@ */ #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 deleted file mode 100644 index dffee19..0000000 --- a/src/list.c +++ /dev/null @@ -1,169 +0,0 @@ -// 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; -} @@ -3,225 +3,354 @@ /** * Intrusive linked lists. + * + * Singly-linked lists are declared like this: + * + * struct item { + * struct item *next; + * }; + * + * struct list { + * struct item *head; + * struct item **tail; + * }; + * + * The SLIST_*() macros manipulate singly-linked lists. + * + * struct list list; + * SLIST_INIT(&list); + * + * struct item item; + * SLIST_APPEND(&list, &item); + * + * Doubly linked lists are similar: + * + * struct item { + * struct item *next; + * struct item *prev; + * }; + * + * struct list { + * struct item *head; + * struct item *tail; + * }; + * + * struct list list; + * LIST_INIT(&list); + * + * struct item item; + * LIST_APPEND(&list, &item); + * + * Items can be on multiple lists at once: + * + * struct item { + * struct { + * struct item *next; + * } chain; + * + * struct { + * struct item *next; + * struct item *prev; + * } lru; + * }; + * + * struct items { + * struct { + * struct item *head; + * struct item **tail; + * } queue; + * + * struct { + * struct item *head; + * struct item *tail; + * } cache; + * }; + * + * struct items items; + * SLIST_INIT(&items.queue); + * LIST_INIT(&items.cache); + * + * struct item item; + * SLIST_APPEND(&items.queue, &item, chain); + * LIST_APPEND(&items.cache, &item, lru); */ #ifndef BFS_LIST_H #define BFS_LIST_H -#include "config.h" -#include <stdbool.h> +#include <stddef.h> /** - * A singly-linked list entry. + * Initialize a singly-linked list. + * + * @param list + * The list to initialize. + * + * --- + * + * Like many macros in this file, this macro delegates the bulk of its work to + * some helper macros. We explicitly parenthesize (list) here so the helpers + * don't have to. */ -struct slink { - struct slink *next; -}; +#define SLIST_INIT(list) \ + LIST_BLOCK_(SLIST_INIT_((list))) -/** Initialize a list entry. */ -void slink_init(struct slink *link); +#define SLIST_INIT_(list) \ + (list)->head = NULL; \ + (list)->tail = &(list)->head; /** - * A singly-linked list. + * Wraps a group of statements in a block. */ -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); +#define LIST_BLOCK_(block) do { block } while (0) /** - * Comparison function type for slist_sort(). + * Add an item to the tail of a singly-linked list. * - * @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. + * @param list + * The list to modify. + * @param item + * The item to append. + * @param link (optional) + * If specified, use item->link.next rather than item->next. + * + * --- + * + * We play some tricks with variadic macros to handle the optional parameter: + * + * SLIST_APPEND(list, item) => { + * *list->tail = item; + * list->tail = &item->next; + * } + * + * SLIST_APPEND(list, item, link) => { + * *list->tail = item; + * list->tail = &item->link.next; + * } + * + * The first trick is that + * + * #define SLIST_APPEND(list, item, ...) + * + * won't work because both commas are required (until C23; see N3033). As a + * workaround, we dispatch to another macro and add a trailing comma. + * + * SLIST_APPEND(list, item) => SLIST_APPEND_(list, item, ) + * SLIST_APPEND(list, item, link) => SLIST_APPEND_(list, item, link, ) */ -typedef bool slist_cmp_fn(struct slink *left, struct slink *right, const void *ptr); +#define SLIST_APPEND(list, ...) SLIST_APPEND_(list, __VA_ARGS__, ) -/** Sort a list. */ -void slist_sort(struct slist *list, slist_cmp_fn *cmp_fn, const void *ptr); +/** + * Now we need a way to generate either ->next or ->link.next depending on + * whether the link parameter was passed. The approach is based on + * + * #define FOO(...) BAR(__VA_ARGS__, 1, 2, ) + * #define BAR(x, y, z, ...) z + * + * FOO(a) => 2 + * FOO(a, b) => 1 + * + * The LIST_NEXT_() macro uses this technique: + * + * LIST_NEXT_() => LIST_LINK_(next, ) + * LIST_NEXT_(link, ) => LIST_LINK_(next, link, ) + */ +#define LIST_NEXT_(...) LIST_LINK_(next, __VA_ARGS__) /** - * A doubly-linked list entry. + * LIST_LINK_() dispatches to yet another macro: + * + * LIST_LINK_(next, ) => LIST_LINK__(next, , , . , , ) + * LIST_LINK_(next, link, ) => LIST_LINK__(next, link, , , . , , ) */ -struct link { - struct link *prev; - struct link *next; -}; +#define LIST_LINK_(dir, ...) LIST_LINK__(dir, __VA_ARGS__, , . , , ) -/** Initialize a list entry. */ -void link_init(struct link *link); +/** + * And finally, LIST_LINK__() adds the link and the dot if necessary. + * + * dir link blank ignored dot + * v v v v v + * LIST_LINK__(next, , , . , , ) => next + * LIST_LINK__(next, link, , , . , , ) => link . next + * ^ ^ ^ ^ ^ + * dir link blank ignored dot + */ +#define LIST_LINK__(dir, link, blank, ignored, dot, ...) link dot dir /** - * A doubly-linked list. + * SLIST_APPEND_() uses LIST_NEXT_() to generate the right name for the list + * link, and finally delegates to the actual implementation. + * + * SLIST_APPEND_(list, item, ) => SLIST_APPEND__((list), (item), next) + * SLIST_APPEND_(list, item, link, ) => SLIST_APPEND__((list), (item), link.next) */ -struct list { - struct link *head; - struct link *tail; -}; +#define SLIST_APPEND_(list, item, ...) \ + LIST_BLOCK_(SLIST_APPEND__((list), (item), LIST_NEXT_(__VA_ARGS__))) -/** Initialize an empty list. */ -void list_init(struct list *list); +#define SLIST_APPEND__(list, item, next) \ + *list->tail = item; \ + list->tail = &item->next; -/** Check if a list is empty. */ -bool list_is_empty(const struct list *list); +/** + * Add an item to the head of a singly-linked list. + * + * @param list + * The list to modify. + * @param item + * The item to prepend. + * @param link (optional) + * If specified, use item->link.next rather than item->next. + */ +#define SLIST_PREPEND(list, ...) SLIST_PREPEND_(list, __VA_ARGS__, ) -/** Add an entry at the tail of the list. */ -void list_append(struct list *list, struct link *link); +#define SLIST_PREPEND_(list, item, ...) \ + LIST_BLOCK_(SLIST_PREPEND__((list), (item), LIST_NEXT_(__VA_ARGS__))) -/** Add an entry at the head of the list. */ -void list_prepend(struct list *list, struct link *link); +#define SLIST_PREPEND__(list, item, next) \ + list->tail = list->head ? list->tail : &item->next; \ + item->next = list->head; \ + list->head = item; -/** Insert an entry after the target entry. */ -void list_insert_after(struct list *list, struct link *target, struct link *link); +/** + * Add an entire singly-linked list to the tail of another. + * + * @param dest + * The destination list. + * @param src + * The source list. + */ +#define SLIST_EXTEND(dest, src) \ + LIST_BLOCK_(SLIST_EXTEND_((dest), (src))) -/** Remove an entry from a list. */ -void list_remove(struct list *list, struct link *link); +#define SLIST_EXTEND_(dest, src) \ + if (src->head) { \ + *dest->tail = src->head; \ + dest->tail = src->tail; \ + SLIST_INIT(src); \ + } -/** Remove the head of the list. */ -struct link *list_pop(struct list *list); +/** + * Pop the head off a singly-linked list. + * + * @param list + * The list to pop from. + * @param link (optional) + * If specified, use head->link.next rather than head->next. + */ +#define SLIST_POP(...) SLIST_POP_(__VA_ARGS__, ) -/** Check if a link is attached to a list. */ -bool list_attached(const struct list *list, const struct link *link); +#define SLIST_POP_(list, ...) \ + LIST_BLOCK_(SLIST_POP__((list), LIST_NEXT_(__VA_ARGS__))) -// LIST_ITEM() helper -#define LIST_ITEM_IMPL(type, entry, member, ...) \ - BFS_CONTAINER_OF(entry, type, member) +#define SLIST_POP__(list, next) \ + void *_next = (void *)list->head->next; \ + list->head->next = NULL; \ + list->head = _next; \ + list->tail = list->head ? list->tail : &list->head; /** - * Convert a list entry to its container. + * Initialize a doubly-linked list. * - * @param type - * The type of the list entries. - * @param entry - * The list entry to convert. - * @param member - * The name of the list link field (default: link). - * @return - * The item that contains the given entry. + * @param list + * The list to initialize. */ -#define LIST_ITEM(...) \ - LIST_ITEM_IMPL(__VA_ARGS__, link,) +#define LIST_INIT(list) \ + LIST_BLOCK_(LIST_INIT_((list))) -// LIST_NEXT() helper -#define LIST_NEXT_IMPL(type, entry, member, ...) \ - LIST_ITEM(type, (entry)->member.next, member) +#define LIST_INIT_(list) \ + list->head = list->tail = NULL; /** - * Get the next item in a list. - * - * @param type - * The type of the list entries. - * @param entry - * The current entry. - * @param member - * The name of the list link field (default: link). - * @return - * The next item in the list. + * LIST_PREV_() => prev + * LIST_PREV_(link, ) => link.prev */ -#define LIST_NEXT(...) \ - LIST_NEXT_IMPL(__VA_ARGS__, link,) - -// LIST_PREV() helper -#define LIST_PREV_IMPL(type, entry, member, ...) \ - LIST_ITEM(type, (entry)->member.prev, member) +#define LIST_PREV_(...) LIST_LINK_(prev, __VA_ARGS__) /** - * Get the previous entry in a list. + * Add an item to the tail of a doubly-linked list. * - * @param type - * The type of the list entries. - * @param entry - * The current entry. - * @param member - * The name of the list link field (default: link). - * @return - * The previous item in the list. + * @param list + * The list to modify. + * @param item + * The item to append. + * @param link (optional) + * If specified, use item->link.{prev,next} rather than item->{prev,next}. */ -#define LIST_PREV(...) \ - LIST_PREV_IMPL(__VA_ARGS__, link,) +#define LIST_APPEND(list, ...) LIST_INSERT(list, (list)->tail, __VA_ARGS__) -// Helper for LIST_FOR_EACH_*() -#define LIST_FOR_EACH_IMPL(entry, type, i, member, ...) \ - for (type *_next, *i = LIST_ITEM(type, entry, member); \ - i && (_next = LIST_NEXT(type, i, member), true); \ - i = _next) +/** + * Add an item to the head of a doubly-linked list. + * + * @param list + * The list to modify. + * @param item + * The item to prepend. + * @param link (optional) + * If specified, use item->link.{prev,next} rather than item->{prev,next}. + */ +#define LIST_PREPEND(list, ...) LIST_INSERT(list, NULL, __VA_ARGS__) /** - * Iterate over a list from the given entry. + * Insert into a doubly-linked list after the given cursor. * - * @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). + * @param list + * The list to initialize. + * @param cursor + * Insert after this element. + * @param item + * The item to insert. + * @param link (optional) + * If specified, use item->link.{prev,next} rather than item->{prev,next}. */ -#define LIST_FOR_EACH_FROM(...) \ - LIST_FOR_EACH_IMPL(__VA_ARGS__, link,) +#define LIST_INSERT(list, cursor, ...) LIST_INSERT_(list, cursor, __VA_ARGS__, ) + +#define LIST_INSERT_(list, cursor, item, ...) \ + LIST_BLOCK_(LIST_INSERT__((list), (cursor), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))) + +#define LIST_INSERT__(list, cursor, item, prev, next) \ + item->prev = cursor; \ + item->next = cursor ? cursor->next : list->head; \ + *(item->prev ? &item->prev->next : &list->head) = item; \ + *(item->next ? &item->next->prev : &list->tail) = item; /** - * Iterate over a list. + * Remove an item from a doubly-linked 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). + * The list to modify. + * @param item + * The item to remove. + * @param link (optional) + * If specified, use item->link.{prev,next} rather than item->{prev,next}. */ -#define LIST_FOR_EACH(list, ...) \ - LIST_FOR_EACH_FROM((list)->head, __VA_ARGS__) +#define LIST_REMOVE(list, ...) LIST_REMOVE_(list, __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)) +#define LIST_REMOVE_(list, item, ...) \ + LIST_BLOCK_(LIST_REMOVE__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))) -// Helper for LIST_DRAIN() -#define LIST_DRAIN_IMPL(list, type, i, member, ...) \ - for (type *i; (i = LIST_ITEM(type, LIST_POP(list), member));) +#define LIST_REMOVE__(list, item, prev, next) \ + *(item->prev ? &item->prev->next : &list->head) = item->next; \ + *(item->next ? &item->next->prev : &list->tail) = item->prev; \ + item->prev = item->next = NULL; /** - * Drain the entries from a list. + * Check if an item is attached to a doubly-linked 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,) + * The list to check. + * @param item + * The item to check. + * @param link (optional) + * If specified, use item->link.{prev,next} rather than item->{prev,next}. + * @return + * Whether the item is attached to the list. + */ +#define LIST_ATTACHED(list, ...) LIST_ATTACHED_(list, __VA_ARGS__, ) + +#define LIST_ATTACHED_(list, item, ...) \ + LIST_ATTACHED__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) + +#define LIST_ATTACHED__(list, item, prev, next) \ + (item->prev || item->next || list->head == item || list->tail == item) #endif // BFS_LIST_H @@ -83,6 +83,7 @@ #include "trie.h" #include "config.h" +#include "list.h" #include <assert.h> #include <limits.h> #include <stdbool.h> @@ -163,7 +164,7 @@ static uintptr_t trie_encode_node(const struct trie_node *node) { void trie_init(struct trie *trie) { trie->root = 0; - list_init(&trie->leaves); + LIST_INIT(trie); } /** Check if a number is a power of two. */ @@ -340,8 +341,7 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz return NULL; } - link_init(&leaf->link); - list_append(&trie->leaves, &leaf->link); + LIST_APPEND(trie, leaf); leaf->value = NULL; leaf->length = length; @@ -352,7 +352,7 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz /** Free a leaf. */ static void trie_leaf_free(struct trie *trie, struct trie_leaf *leaf) { - list_remove(&trie->leaves, &leaf->link); + LIST_REMOVE(trie, leaf); free(leaf); } @@ -5,7 +5,6 @@ #define BFS_TRIE_H #include "config.h" -#include "list.h" #include <stdbool.h> #include <stddef.h> #include <stdint.h> @@ -15,7 +14,7 @@ */ struct trie_leaf { /** Linked list of leaves, in insertion order. */ - struct link link; + struct trie_leaf *prev, *next; /** An arbitrary value associated with this leaf. */ void *value; /** The length of the key in bytes. */ @@ -31,7 +30,7 @@ struct trie { /** Pointer to the root node/leaf. */ uintptr_t root; /** Linked list of leaves. */ - struct list leaves; + struct trie_leaf *head, *tail; }; /** @@ -134,6 +133,8 @@ void trie_destroy(struct trie *trie); * Iterate over the leaves of a trie. */ #define TRIE_FOR_EACH(trie, leaf) \ - LIST_FOR_EACH(&(trie)->leaves, struct trie_leaf, leaf) + for (struct trie_leaf *leaf = (trie)->head, *_next; \ + leaf && (_next = leaf->next, true); \ + leaf = _next) #endif // BFS_TRIE_H diff --git a/src/xspawn.c b/src/xspawn.c index e6ce0de..a185200 100644 --- a/src/xspawn.c +++ b/src/xspawn.c @@ -33,7 +33,7 @@ enum bfs_spawn_op { * A spawn action. */ struct bfs_spawn_action { - struct slink link; + struct bfs_spawn_action *next; enum bfs_spawn_op op; int in_fd; @@ -44,12 +44,14 @@ struct bfs_spawn_action { int bfs_spawn_init(struct bfs_spawn *ctx) { ctx->flags = 0; - slist_init(&ctx->actions); + SLIST_INIT(ctx); return 0; } int bfs_spawn_destroy(struct bfs_spawn *ctx) { - LIST_DRAIN(&ctx->actions, struct bfs_spawn_action, action) { + while (ctx->head) { + struct bfs_spawn_action *action = ctx->head; + SLIST_POP(ctx); free(action); } @@ -68,12 +70,12 @@ static struct bfs_spawn_action *bfs_spawn_add(struct bfs_spawn *ctx, enum bfs_sp return NULL; } - slink_init(&action->link); + action->next = NULL; action->op = op; action->in_fd = -1; action->out_fd = -1; - slist_append(&ctx->actions, &action->link); + SLIST_APPEND(ctx, action); return action; } @@ -138,8 +140,7 @@ int bfs_spawn_addsetrlimit(struct bfs_spawn *ctx, int resource, const struct rli static void bfs_spawn_exec(const char *exe, const struct bfs_spawn *ctx, char **argv, char **envp, int pipefd[2]) { xclose(pipefd[0]); - const struct slink *head = ctx ? ctx->actions.head : NULL; - LIST_FOR_EACH_FROM(head, struct bfs_spawn_action, action) { + for (const struct bfs_spawn_action *action = ctx ? ctx->head : NULL; action; action = action->next) { // Move the error-reporting pipe out of the way if necessary... if (action->out_fd == pipefd[1]) { int fd = dup_cloexec(pipefd[1]); diff --git a/src/xspawn.h b/src/xspawn.h index 7e673f1..d9b4a2e 100644 --- a/src/xspawn.h +++ b/src/xspawn.h @@ -8,7 +8,6 @@ #ifndef BFS_XSPAWN_H #define BFS_XSPAWN_H -#include "list.h" #include <sys/resource.h> #include <sys/types.h> @@ -25,7 +24,8 @@ enum bfs_spawn_flags { */ struct bfs_spawn { enum bfs_spawn_flags flags; - struct slist actions; + struct bfs_spawn_action *head; + struct bfs_spawn_action **tail; }; /** |