linked_list.h

Go to the documentation of this file.

#pragma once
 
#include <kernel/types.h>
 
#include <utils/container_of.h>
#include <utils/compiler.h>
 
typedef struct linked_list_node {
    struct linked_list_node *next; 
    struct linked_list_node *prev; 
} node_t;
 
typedef struct linked_list_head {
    struct linked_list_node head; 
} llist_t;
 
#define __LLIST_INIT(_head) \
    {                       \
        {                   \
            _head, _head    \
        }                   \
    }
#define LLIST_INIT(_list) ((llist_t)__LLIST_INIT(&(_list).head))
 
#define __INIT_LLIST(_name) _name = __LLIST_INIT(_name)
#define INIT_LLIST(_name) _name = LLIST_INIT(_name)
 
#define DECLARE_LLIST(_name) llist_t INIT_LLIST(_name)
 
#define LLIST_NODE(_name) node_t _name
 
#define FOREACH_LLIST(_name, _list)                                      \
    for (node_t *_name = llist_first(_list); _name != llist_head(_list); \
         _name = llist_next(_name))
 
#define FOREACH_LLIST_SAFE(_name, _tmp, _list)                          \
    for (node_t *_name = llist_first(_list), *_tmp = llist_next(_name); \
         _name != llist_head(_list); _name = _tmp, _tmp = llist_next(_tmp))
 
#define FOREACH_LLIST_REVERSE(_name, _list)                             \
    for (node_t *_name = llist_last(_list); _name != llist_head(_list); \
         _name = llist_prev(_name))
 
#define FOREACH_LLIST_SAFE_REVERSE(_name, _tmp, _list)                 \
    for (node_t *_name = llist_last(_list), *_tmp = llist_prev(_name); \
         _name != llist_head(_list); _name = _tmp, _tmp = llist_prev(_tmp))
 
#define FOREACH_LLIST_ENTRY(_entry, _list, _field)                          \
    for (_entry = llist_entry(llist_first(_list), typeof(*_entry), _field); \
         &_entry->_field != llist_head(_list);                              \
         _entry = llist_entry(llist_next(&_entry->_field), typeof(*_entry), \
                              _field))
 
#define FOREACH_LLIST_ENTRY_SAFE(_entry, _tmp, _list, _field)                 \
    for (_entry = llist_entry(llist_first(_list), typeof(*_entry), _field),   \
        _tmp =                                                                \
             llist_entry(llist_next(&_entry->_field), typeof(*_tmp), _field); \
         &_entry->_field != llist_head(_list);                                \
         _entry = _tmp, _tmp = llist_entry(llist_next(&_tmp->_field),         \
                                           typeof(*_entry), _field))
 
#define FOREACH_LLIST_ENTRY_REVERSE(_entry, _list, _field)                  \
    for (_entry = llist_entry(llist_last(_list), typeof(*_entry), _field);  \
         &_entry->_field != llist_head(_list);                              \
         _entry = llist_entry(llist_prev(&_entry->_field), typeof(*_entry), \
                              _field))
 
#define FOREACH_LLIST_ENTRY_REVERSE_SAFE(_entry, _tmp, _list, _field)         \
    for (_entry = llist_entry(llist_last(_list), typeof(*_entry), _field),    \
        _tmp =                                                                \
             llist_entry(llist_prev(&_entry->_field), typeof(*_tmp), _field); \
         &_entry->_field != llist_head(_list);                                \
         _entry = _tmp, _tmp = llist_entry(llist_prev(&_tmp->_field),         \
                                           typeof(*_entry), _field))
 
#define llist_head(_list) (&(_list)->head)
 
static inline node_t *llist_first(const llist_t *list)
{
    return llist_head(list)->next;
}
 
static inline node_t *llist_last(const llist_t *list)
{
    return llist_head(list)->prev;
}
 
/***/
static inline node_t *llist_next(const node_t *entry)
{
    return entry->next;
}
 
/***/
static inline node_t *llist_prev(const node_t *entry)
{
    return entry->prev;
}
 
#define llist_entry(ptr, type, member) container_of(ptr, type, member)
 
static PURE inline bool llist_is_empty(const llist_t *list)
{
    return llist_first(list) == llist_head(list);
}
 
static inline void __llist_add(node_t *new, node_t *prev, node_t *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
 
static inline void __list_remove(node_t *prev, node_t *next)
{
    next->prev = prev;
    prev->next = next;
}
 
static inline void llist_add_after(node_t *prev, node_t *new)
{
    __llist_add(new, prev, prev->next);
}
 
static inline void llist_add_before(node_t *next, node_t *new)
{
    __llist_add(new, next->prev, next);
}
 
static inline void llist_add(llist_t *list, node_t *new)
{
    llist_add_after(llist_head(list), new);
}
 
static inline void llist_add_tail(llist_t *list, node_t *new)
{
    llist_add_after(llist_last(list), new);
}
 
static inline node_t *llist_remove(node_t *node)
{
    __list_remove(node->prev, node->next);
    node->next = node;
    node->prev = node;
    return node;
}
 
static inline node_t *llist_pop(llist_t *list)
{
    if (llist_is_empty(list))
        return NULL;
 
    return llist_remove(llist_first(list));
}
 
static inline node_t *llist_pop_tail(llist_t *list)
{
    if (llist_is_empty(list))
        return NULL;
 
    return llist_remove(llist_last(list));
}
 
static inline void
llist_insert_sorted(llist_t *list, node_t *new, compare_t compare)
{
    node_t *node = llist_first(list);
 
    while (node != llist_head(list)) {
        if (compare(new, node) <= 0)
            break;
        node = llist_next(node);
    }
 
    llist_add_before(node, new);
}
 
static inline bool
llist_insert_sorted_unique(llist_t *list, node_t *new, compare_t compare)
{
    node_t *node = llist_first(list);
    int ret;
 
    while (node != llist_head(list)) {
        ret = compare(new, node);
        if (ret == 0)
            return false;
        if (ret < 0)
            break;
        node = llist_next(node);
    }
 
    llist_add_before(node, new);
 
    return true;
}
 
static inline node_t *
llist_find_first(const llist_t *list, const void *data, compare_t compare)
{
    FOREACH_LLIST (node, list) {
        if (!compare(node, data))
            return node;
    }
 
    return NULL;
}