C语言数据结构(一)------------------------ list

/*
 * 该结构体用于嵌入到业务数据结构体中(entry)，用于实现链表
 * 例：
 *     struct Entry {           // 你的业务数据结构体
 *         ...
 *         struct Node node;    // 嵌入其中，位置任意
 *         ...
 *     };
 */
typedef struct __NodeHead {
    struct __NodeHead *next, *prev;
} NodeHead;

/*
 * 由成员变量 node 地址获取结构体 entry 地址
 * 例：
 *     struct Entry entry;
 *     struct Node *n = &entry.node;
 *     struct Entry *p = NODE_ENTRY(n, struct Entry, node);
 *     此时 p 指向 entry
 */
#define NODE_ENTRY(node, type, member) \
    ((type*)((char*)(node) - (size_t)&((type*)0)->member))

/*
 * 用户定义，针对 node 节点的处理函数
 * 注意: 入参是 node 指针！
 * 你可能需要使用 NODE_ENTRY 来获取并处理 entry
 */
typedef void (*NodeFunc)(NodeHead *node);


/* 带哨兵节点的双向链表 */
typedef struct __List_tag {
    NodeHead header;
} HList;

static inline void ListInit(HList *list)
{
    list->header.next = &list->header;
    list->header.prev = &list->header;
}

static inline bool ListEmpty(const HList *list)
{
    return list->header.next == &list->header;
}

static inline bool ListIsHead(const HList *list, const NodeHead *node)
{
    return list->header.next == node;
}

static inline bool ListIsTail(const HList *list, const NodeHead *node)
{
    return list->header.prev == node;
}

/* node 插入到 pos 前面 */
static inline void ListInsert(NodeHead *pos, NodeHead *node)
{
    node->prev = pos->prev;
    node->next = pos;
    node->prev->next = node;
    node->next->prev = node;
}

static inline void ListAddTail(HList *list, NodeHead *node)
{
    ListInsert(&list->header, node);
}

static inline void ListAddHead(HList *list, NodeHead *node)
{
    ListInsert(list->header.next, node);
}

static inline void ListRemove(NodeHead *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

static inline void ListRemoveTail(HList *list)
{
    ListRemove(list->header.prev);
}

static inline void ListRemoveHead(HList *list)
{
    ListRemove(list->header.next);
}

static inline void ListReplace(NodeHead*old, NodeHead *node)
{
    node->next = old->next;
    node->next->prev = node;
    node->prev = old->prev;
    node->prev->next = node;
}

#define LIST_FOR_EACH(node, list) \
    for (node = (list)->header.next; \
         node != &(list)->header; \
         node = (node)->next)

#define LIST_FOR_EACH_SAFE(node, tmp, list) \
    for (node = (list)->header.next, tmp = (node)->next; \
         node != &(list)->header; \
         node = tmp, tmp = (node)->next)

/* 注意：NodeFunc 函数入参是 node 而非 entry! */
static inline void ListDeinit(HList *list, NodeFunc nodeDeinit)
{
    if (nodeDeinit == NULL) {
        return;
    }

    NodeHead *node, *tmp;
    LIST_FOR_EACH_SAFE(node, tmp, list) {
        nodeDeinit(node);
    }
}

/* 获取头结点，或空 */
#define LIST_HEAD_ENTRY(list, type, member) \
    (ListEmpty(list) ? NULL : NODE_ENTRY((list)->header.next, type, member))

/* 获取尾结点，或空 */
#define LIST_TAIL_ENTRY(list, type, member) \
    (ListEmpty(list) ? NULL : NODE_ENTRY((list)->header.prev, type, member))

/* 获取下一结点，或空 */
#define LIST_NEXT_ENTRY(entry, list, type, member) \
    (ListIsTail(list, &(entry)->member) ? \
        NULL : \
        NODE_ENTRY((entry)->member.next, type, member))

/* 获取上一结点，或空 */
#define LIST_PREV_ENTRY(entry, list, type, member) \
    (ListIsHead(list, &(entry)->member) ? \
        NULL: \
        NODE_ENTRY((entry)->member.prev, type, member))

/* 遍历链表；过程中如需操作链表，请使用 _SAFE 版本 */
#define LIST_FOR_EACH_ENTRY(entry, list, type, member) \
    for (entry = NODE_ENTRY((list)->member.next, type, member); \
         &(entry)->member != &(list)->member; \
         entry = NODE_ENTRY((entry)->member.next, type, member))

#define LIST_FOR_EACH_ENTRY_SAFE(entry, tmp, list, type, member) \
    for (entry = NODE_ENTRY((list)->member.next, type, member), \
         tmp = NODE_ENTRY((entry)->member.next, type, member); \
         &(entry)->member != &(list)->member; \
         entry = tmp, tmp = NODE_ENTRY((entry)->member.next, type, member))

/* 倒序遍历链表；过程中如需操作链表，请使用 _SAFE 版本 */
#define LIST_FOR_EACH_ENTRY_REVERSE(entry, list, type, member) \
    for (entry = NODE_ENTRY((list)->member.prev, type, member); \
         &(entry)->member != &(list)->member; \
         entry = NODE_ENTRY((entry)->member.prev, type, member))

#define LIST_FOR_EACH_ENTRY_REVERSE_SAFE(entry, tmp, list, type, member) \
    for (entry = NODE_ENTRY((list)->member.prev, type, member), \
         tmp = NODE_ENTRY((entry)->member.prev, type, member); \
         &(entry)->member != &(list)->member; \
         entry = tmp, tmp = NODE_ENTRY((entry)->member.prev, type, member))