list.h

Go to the documentation of this file.

#ifndef _SYS_LIST_H
#define _SYS_LIST_H 1
 
#include "_internal/CONTAINER_OF.h"
#include "_internal/NULL.h"
 
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
 
typedef struct list list_t;
 
typedef struct list_entry
{
    struct list_entry* prev; 
    struct list_entry* next; 
    list_t* list;            
} list_entry_t;
 
typedef struct list
{
    list_entry_t head; 
    uint64_t length;   
} list_t;
 
#define LIST_FOR_EACH(elem, list, member) \
    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))
 
#define LIST_FOR_EACH_SAFE(elem, temp, list, member) \
    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member), \
        (temp) = CONTAINER_OF((elem)->member.next, typeof(*elem), member); \
        &(elem)->member != &((list)->head); \
        (elem) = (temp), (temp) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))
 
#define LIST_FOR_EACH_REVERSE(elem, list, member) \
    for ((elem) = CONTAINER_OF((list)->head.prev, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))
 
#define LIST_FOR_EACH_FROM(elem, start, list, member) \
    for ((elem) = CONTAINER_OF(start, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))
 
#define LIST_FOR_EACH_FROM_REVERSE(elem, start, list, member) \
    for ((elem) = CONTAINER_OF(start, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))
 
#define LIST_FOR_EACH_TO(elem, end, list, member) \
    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member); \
        &(elem)->member != &((list)->head) && &(elem)->member != (end); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))
 
#define LIST_FOR_EACH_TO_REVERSE(elem, end, list, member) \
    for ((elem) = CONTAINER_OF((list)->head.prev, typeof(*elem), member); \
        &(elem)->member != &((list)->head) && &(elem)->member != (end); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))
 
#define LIST_ENTRY_CREATE(name) \
    (list_entry_t) \
    { \
        .prev = &(name), .next = &(name), .list = NULL \
    }
 
#define LIST_CREATE(name) (list_t){.head = {.prev = &(name).head, .next = &(name).head, .list = &(name)}, .length = 0}
 
static inline void list_entry_init(list_entry_t* entry)
{
    assert(entry != NULL);
    entry->next = entry;
    entry->prev = entry;
    entry->list = NULL;
}
 
static inline void list_init(list_t* list)
{
    assert(list != NULL);
    list_entry_init(&list->head);
    list->head.next->list = list; // Also sets prev
    list->length = 0;
}
 
static inline bool list_contains_entry(list_t* list, list_entry_t* entry)
{
    assert(list != NULL);
    assert(entry != NULL);
 
    return entry->list == list;
}
 
static inline bool list_is_empty(list_t* list)
{
    assert(list != NULL);
 
    bool emptyByHead = (list->head.next == &list->head);
    bool emptyByLength = (list->length == 0);
 
    assert(emptyByHead == emptyByLength);
 
    return emptyByHead;
}
 
static inline uint64_t list_length(list_t* list)
{
    assert(list != NULL);
    return list->length;
}
 
static inline void list_add(list_t* list, list_entry_t* prev, list_entry_t* next, list_entry_t* entry)
{
    assert(list != NULL);
    assert(prev != NULL);
    assert(next != NULL);
    assert(entry != NULL);
    assert(entry->next == entry && entry->prev == entry);
    assert(prev->next == next && next->prev == prev);
    assert(entry->list == NULL);
    assert(prev->list == list);
    assert(next->list == list);
 
    next->prev = entry;
    entry->next = next;
    entry->prev = prev;
    prev->next = entry;
 
    entry->list = list;
    list->length++;
}
 
static inline void list_append(list_t* list, list_entry_t* prev, list_entry_t* entry)
{
    list_add(list, prev, prev->next, entry);
}
 
static inline void list_prepend(list_t* list, list_entry_t* head, list_entry_t* entry)
{
    list_add(list, head->prev, head, entry);
}
 
static inline void list_remove(list_t* list, list_entry_t* entry)
{
    if (entry->list == NULL)
    {
        return;
    }
 
    assert(list != NULL);
    assert(entry != NULL);
    assert(list->length > 0);
    assert(entry != &list->head);
    assert(entry->list == list);
 
    entry->prev->next = entry->next;
    entry->next->prev = entry->prev;
    list_entry_init(entry);
 
    entry->list = NULL;
    list->length--;
}
 
static inline void list_push(list_t* list, list_entry_t* entry)
{
    assert(list != NULL);
    assert(entry != NULL);
    assert(entry->next == entry && entry->prev == entry);
 
    list_add(list, list->head.prev, &list->head, entry);
}
 
static inline list_entry_t* list_pop(list_t* list)
{
    assert(list != NULL);
 
    if (list_is_empty(list))
    {
        return NULL;
    }
 
    list_entry_t* entry = list->head.next;
    list_remove(list, entry);
    return entry;
}
 
static inline list_entry_t* list_first(list_t* list)
{
    assert(list != NULL);
 
    if (list_is_empty(list))
    {
        return NULL;
    }
    return list->head.next;
}
 
static inline list_entry_t* list_last(list_t* list)
{
    assert(list != NULL);
 
    if (list_is_empty(list))
    {
        return NULL;
    }
    return list->head.prev;
}
 
#endif