list.h

Go to the documentation of this file.

#include <stddef.h>
#include <stdalign.h>
#include <stdbool.h>
 
/**
 * @brief Doubly-linked List Node
 *
 * @warning It's actually a circular doubly-linked list. Thus, it is recommended to use
 * methods like @ref list_next or @ref list_prev to access next and previous nodes.
 *
 * @note Make sure the node is initialized with @ref list_init_node, and is not already
 * in a list when putting it in another list.
 *
 */
struct list_node {
        struct list_node *next;
        struct list_node *prev;
};
 
/**
 * @brief Anchor for @ref list_node.
 */
struct list_head {
        struct list_node list_node;
};
 
/**
 * @brief Initializes @p head as an empty list.
 */
struct list_head *list_init_head(struct list_head *head);
 
/**
 * @brief Initializes `node`.
 */
struct list_node *list_init_node(struct list_node *node);
 
/**
 * @return `true` if `head`'s list is empty, otherwise `false`.
 */
bool list_is_empty(const struct list_head *head);
 
/**
 * @brief Inserts @p node at the end of `head`'s list (aka stack push).
 * @return @p node
 */
struct list_node *list_append(struct list_head *head, struct list_node *node);
/**
 * @brief Inserts @p node before @p before in the list of `before`.
 * @return @p node
 */
struct list_node *list_insert_before(struct list_node *before, struct list_node *node);
/**
 * @brief Inserts @p node after @p after in the list of `after`.
 * @return @p node
 */
struct list_node *list_insert_after(struct list_node *after, struct list_node *node);
 
/**
 * @brief Merges @p head2 unto @p head1 at the end of @p head1 and returns `head1`.
 * @warning This will modify `head2`, so @p head2 should be discarded or
 * reinitialized afterwards.
 * @return @p head1
 */
struct list_head *list_extend(struct list_head *head1, struct list_head *head2);
 
/**
 * @return The first node of `head`'s list, otherwise `NULL`.
 */
struct list_node *list_first(struct list_head *head);
/**
 * @return The last node of `head`'s list, otherwise `NULL`.
 */
struct list_node *list_last(struct list_head *head);
 
/**
 * @brief Removes @p node from `head`'s list.
 * @note @p node is not modified.
 * @warning @p node must already be in a list, otherwise there might be unintended
 * consequences.
 * @return @p node
 */
struct list_node *list_remove(struct list_node *node);
/**
 * @brief Removes the last node of `head`'s list (aka stack pop with respect
 * to @ref list_append).
 * @note The node returned is not modified.
 * @return The removed node if the list of @p head is not empty, otherwise `NULL`.
 */
struct list_node *list_pop_last(struct list_head *head);
/**
 * @brief Removes the first node of `head`'s list (aka deque with respect
 * to @ref list_append).
 * @note The node returned is not modified.
 * @return The removed node if the list of @p head is not empty, otherwise `NULL`.
 */
struct list_node *list_pop_first(struct list_head *head);
 
/**
 * @return The node right after @p node in the `head`'s list, otherwise `NULL`.
 */
struct list_node *list_next(struct list_head *head, struct list_node *node);
/**
 * @return The node right before @p node in the `head`'s list, otherwise `NULL`.
 */
struct list_node *list_prev(struct list_head *head, struct list_node *node);
 
/**
 * @return The length of `head`'s list.
 */
size_t list_length(struct list_head *head);
 
/**
 * @brief A preprocessor for iterating over `head`'s list. @p iter is the current node
 * in the iteration. Methods like @ref list_remove is safe to use on `iter`.
 */
#define LIST_FOREACH(head, iter) \
        for (\
                struct list_node *iter = list_first(head), *iter##_next = list_first(head) ? list_next(head, list_first(head)) : NULL; \
                iter; \
                iter = iter##_next, iter##_next = iter##_next ? list_next(head, iter##_next) : NULL\
        )