list.h

Go to the documentation of this file.

 
#ifndef __TBOX_LIST_H__
#define __TBOX_LIST_H__
 
#include <stddef.h>
 
#define tbox_typeof(x) __typeof__(x)
 
#ifdef __cplusplus
extern "C"
{
#endif


static inline void prefetch(const void* x)
{
    (void)x;
}

static inline void prefetchw(const void* x)
{
    (void)x;
}
 
#define LIST_POISON1 ((void*)0x00100100) 
#define LIST_POISON2 ((void*)0x00200200) 

typedef struct list_node
{
    struct list_node* next; 
    struct list_node* prev; 
} list_node_t;

#define DLIST_HEAD_IN_STRUCT_INIT(field)                                                                               \
    do                                                                                                                 \
    {                                                                                                                  \
        (field).next = &(field);                                                                                       \
        (field).prev = &(field);                                                                                       \
    } while (0)

#define DLIST_HEAD_INIT(name) {&(name), &(name)}

#define DLIST_HEAD(name) struct list_node name = DLIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_node* list)
{
    list->next = list;
    list->prev = list;
}

static inline int list_empty(const struct list_node* head)
{
    return ((head->next == head) && (head->prev == head));
}

static inline void list_append(struct list_node* new_node, struct list_node* existing)
{
    existing->next->prev = new_node;
    new_node->next       = existing->next;
    new_node->prev       = existing;
    existing->next       = new_node;
}

static inline void list_prepend(struct list_node* new_node, struct list_node* existing)
{
    existing->prev->next = new_node;
    new_node->next       = existing;
    new_node->prev       = existing->prev;
    existing->prev       = new_node;
}

static inline void __list_add(struct list_node* new_node, struct list_node* prev, struct list_node* next)
{
    next->prev     = new_node;
    new_node->next = next;
    new_node->prev = prev;
    prev->next     = new_node;
}

static inline void list_add(struct list_node* new_node, struct list_node* head)
{
    __list_add(new_node, head, head->next);
}

static inline void list_add_tail(struct list_node* new_node, struct list_node* head)
{
    __list_add(new_node, head->prev, head);
}

static inline void list_unlink(struct list_node* entry)
{
    entry->next->prev = entry->prev;
    entry->prev->next = entry->next;
    entry->next       = NULL;
    entry->prev       = NULL;
}

static inline void __list_del(struct list_node* prev, struct list_node* next)
{
    next->prev = prev;
    prev->next = next;
}

static inline void list_del(struct list_node* list)
{
    __list_del(list->prev, list->next);
}

#define container_of(ptr, type, member)                                                                                \
    ({                                                                                                                 \
        const tbox_typeof(((type*)0)->member)* __mptr = (ptr);                                                         \
        (type*)((char*)__mptr - offsetof(type, member));                                                               \
    })

#define list_entry(ptr, type, member) container_of(ptr, type, member)

#define list_for_each(pos, head) for (pos = (head)->next; prefetch(pos->next), pos != (head); pos = pos->next)

#define list_for_each_entry(pos, head, member)                                                                         \
    for (pos = list_entry((head)->next, tbox_typeof(*pos), member); &pos->member != (head);                            \
         pos = list_entry(pos->member.next, tbox_typeof(*pos), member))

#define list_for_each_entry_safe(pos, n, head, member)                                                                 \
    for (pos                         = list_entry((head)->next, tbox_typeof(*pos), member),                            \
        n                            = list_entry(pos->member.next, tbox_typeof(*pos), member);                        \
         &pos->member != (head); pos = n, n = list_entry(n->member.next, tbox_typeof(*n), member))

struct hlist_head
{
    struct hlist_node* first;
};

struct hlist_node
{
    struct hlist_node*  next;
    struct hlist_node** pprev;
};

#define HLIST_HEAD_INIT {.first = NULL}

#define HLIST_HEAD(name) struct hlist_head name = {.first = NULL}

#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

#define INIT_HLIST_NODE(ptr)                                                                                           \
    do                                                                                                                 \
    {                                                                                                                  \
        (ptr)->next  = NULL;                                                                                           \
        (ptr)->pprev = NULL;                                                                                           \
    } while (0)

static inline int hlist_unhashed(const struct hlist_node* h)
{
    return !h->pprev;
}

static inline int hlist_empty(const struct hlist_head* h)
{
    return !h->first;
}

static inline void __hlist_del(struct hlist_node* n)
{
    struct hlist_node*  next  = n->next;
    struct hlist_node** pprev = n->pprev;
 
    *pprev = next;
    if (next)
    {
        next->pprev = pprev;
    }
}

static inline void hlist_del(struct hlist_node* n)
{
    __hlist_del(n);
    n->next  = (struct hlist_node*)LIST_POISON1;
    n->pprev = (struct hlist_node**)LIST_POISON2;
}

static inline void hlist_del_init(struct hlist_node* n)
{
    if (n->pprev)
    {
        __hlist_del(n);
        INIT_HLIST_NODE(n);
    }
}

static inline void hlist_add_head(struct hlist_node* n, struct hlist_head* h)
{
    struct hlist_node* first = h->first;
 
    n->next = first;
    if (first)
    {
        first->pprev = &n->next;
    }
    h->first = n;
    n->pprev = &h->first;
}

static inline void hlist_add_before(struct hlist_node* n, struct hlist_node* next)
{
    n->pprev    = next->pprev;
    n->next     = next;
    next->pprev = &n->next;
    *(n->pprev) = n;
}

static inline void hlist_add_after(struct hlist_node* n, struct hlist_node* next)
{
    next->next  = n->next;
    n->next     = next;
    next->pprev = &n->next;
    if (next->next)
    {
        next->next->pprev = &next->next;
    }
}

#define hlist_entry(ptr, type, member) container_of(ptr, type, member)

#define hlist_for_each(pos, head)                                                                                      \
    for (pos = (head)->first; pos && ({                                                                                \
                                  prefetch(pos->next);                                                                 \
                                  1;                                                                                   \
                              });                                                                                      \
         pos = pos->next)

#define hlist_for_each_safe(pos, n, head)                                                                              \
    for (pos = (head)->first; pos && ({                                                                                \
                                  n = pos->next;                                                                       \
                                  1;                                                                                   \
                              });                                                                                      \
         pos = n)

#define hlist_for_each_entry(tpos, pos, head, member)                                                                  \
    for (pos = (head)->first; pos && ({                                                                                \
                                  prefetch(pos->next);                                                                 \
                                  1;                                                                                   \
                              }) &&                                                                                    \
                              ({                                                                                       \
                                  tpos = hlist_entry(pos, tbox_typeof(*tpos), member);                                 \
                                  1;                                                                                   \
                              });                                                                                      \
         pos = pos->next)

#define hlist_for_each_entry_continue(tpos, pos, member)                                                               \
    for (pos = (pos)->next; pos && ({                                                                                  \
                                prefetch(pos->next);                                                                   \
                                1;                                                                                     \
                            }) &&                                                                                      \
                            ({                                                                                         \
                                tpos = hlist_entry(pos, tbox_typeof(*tpos), member);                                   \
                                1;                                                                                     \
                            });                                                                                        \
         pos = pos->next)

#define hlist_for_each_entry_from(tpos, pos, member)                                                                   \
    for (; pos && ({                                                                                                   \
               prefetch(pos->next);                                                                                    \
               1;                                                                                                      \
           }) &&                                                                                                       \
           ({                                                                                                          \
               tpos = hlist_entry(pos, tbox_typeof(*tpos), member);                                                    \
               1;                                                                                                      \
           });                                                                                                         \
         pos = pos->next)

#define hlist_for_each_entry_safe(tpos, pos, n, head, member)                                                          \
    for (pos = (head)->first; pos && ({                                                                                \
                                  n = pos->next;                                                                       \
                                  1;                                                                                   \
                              }) &&                                                                                    \
                              ({                                                                                       \
                                  tpos = hlist_entry(pos, tbox_typeof(*tpos), member);                                 \
                                  1;                                                                                   \
                              });                                                                                      \
         pos = n)

 
#ifdef __cplusplus
}
#endif
 
#endif /* __TBOX_LIST_H__ */