双向链表的宏实现——解析shttpd的链表实现

shttpd是一个开源的跨平台的轻量级web服务框架,源码下载地址。这里是使用的1.42版本。

shttpd中双向链表的功能和内核双向链表一致,都是定义一个存放前后指针的节点,将节点存放到某个结构体中,该结构体中的节点关联起来,然后就可以通过链表的方式操作该结构体对象了。

节点结构:
struct llhead 为内核双向链表的节点,定义如下:

struct llhead {
    struct llhead   *prev;
    struct llhead   *next;
};

链表的定义:

#define LL_HEAD(H)  struct llhead H = { &H, &H }
//例如定义一个静态的llhead节点
static LL_HEAD(listeners);

链表的初始化:
链表初始化,用来将节点的前向、后向指针指向自身。定义及使用如下:

#define LL_INIT(N)  ((N)->next = (N)->prev = (N))
struct llhead   listeners;
LL_INIT(&listeners);

添加节点:
向后添加节点

#define LL_ADD(H, N)                            \
    do {                                        \
        ((H)->next)->prev = (N);                \
        (N)->next = ((H)->next);                \
        (N)->prev = (H);                        \
        (H)->next = (N);                        \
    } while (0)
//使用:
struct sockInfo{
    int sockfd;
    int family;
    int port;
    in_addr addr;
    LL_HEAD(listeners);
};
// 将2个sockInfo用链表连接起来
struct sockInfo si1;
struct sockInfo si2;
LL_INIT(&si1.listeners);
LL_INIT(&si2.listeners);
LL_ADD(&si1.listeners, &si2.listeners); 

双向链表的宏实现——解析shttpd的链表实现

删除节点:
将某个节点从链表中删除(让该链表的下一节点与上一节点相互指向对方),并再次初始化该节点

#define LL_DEL(N)                           \
    do {                                \
        ((N)->next)->prev = ((N)->prev);            \
        ((N)->prev)->next = ((N)->next);            \
        LL_INIT(N);                     \
    } while (0)

遍历节点:
LL_FOREACH通常用于获取节点,而不能用到删除节点的场景
LL_FOREACH_SAFE通常删除节点的场景
此实现貌似不能遍历H自身~

#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)
#define LL_FOREACH_SAFE(H,N,T)                      \
    for (N = (H)->next, T = (N)->next; N != (H);N = (T), T = (N)->next)

// 使用for_each遍历struct llhead *head
struct llhead     *lp, *tmp;
LL_FOREACH_SAFE(head, lp, tmp) {
    LL_DEL(lp);
}

链表判空
如果链表指向自身,则为空

#define LL_EMPTY(N) ((N)->next == (N))

向链表末尾添加节点

#define LL_TAIL(H, N)                           \
    do {                                         \
        ((H)->prev)->next = (N);                \
        (N)->prev = ((H)->prev);                \
        (N)->next = (H);                        \
        (H)->prev = (N);                        \
    } while (0)

获取结构体变量指针:
根据”结构体(T)变量中的域成员变量N的指针来获取指向整个结构体变量的指针。

#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N)))
// 示例
struct worker {
    struct llhead    link;
    struct llhead   connections;    /* List of connections      */
};
struct llhead *lp = &pworker->link;
struct worker   *worker = LL_ENTRY(lp, struct worker, link);

说明:
offsetof用来获取T类型中N的相对偏移。假设link相对于worker的偏移为offset,当获取到link内存中的地址link_ptr时,就可以通过可以获取到pworker所指向的内存。此时pworker = link_prt - offset;也就是LL_ENTRY的实现。

offsetof实现:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

假设存在结构体struct TYPE如下
struct TYPE{
T t1;
//…
P p1;
};
当定义变量:struct TYPE tp1;其地址为&tp1,其成员变量t1的地址为&(tp1.t1)
则如下代码可以取到p1在内存中的地址以及相对于tp1的位移

struct TYPE tp1;
struct TYPE *ptp = &tp1;
int addr_t1 = &ptp->t1;// t1在内存中的地址
int addr_p1 = &ptp->p1;// p1内存中的地址
// p1相对于tp的内存偏移为
size_t offset = (char *)&tp1->p1 - (char *)tp1;

当ptp指向null指针时,offsetof =(size_t) ((char *)&0->t1 ;

//list.h
/*
 * Copyright (c) 2004-2005 Sergey Lyubka <valenok@gmail.com>
 * All rights reserved
 *
 * "THE BEER-WARE LICENSE" (Revision 42):
 * Sergey Lyubka wrote this file.  As long as you retain this notice you
 * can do whatever you want with this stuff. If we meet some day, and you think
 * this stuff is worth it, you can buy me a beer in return.
 */

#ifndef LLIST_HEADER_INCLUDED
#define LLIST_HEADER_INCLUDED

/*
 * Linked list macros.
 */
struct llhead {
    struct llhead   *prev;
    struct llhead   *next;
};

#define LL_INIT(N)  ((N)->next = (N)->prev = (N))

#define LL_HEAD(H)  struct llhead H = { &H, &H }

#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N)))

#define LL_ADD(H, N)                            \
    do {                                \
        ((H)->next)->prev = (N);                \
        (N)->next = ((H)->next);                \
        (N)->prev = (H);                    \
        (H)->next = (N);                    \
    } while (0)

#define LL_TAIL(H, N)                           \
    do {                                \
        ((H)->prev)->next = (N);                \
        (N)->prev = ((H)->prev);                \
        (N)->next = (H);                    \
        (H)->prev = (N);                    \
    } while (0)

#define LL_DEL(N)                           \
    do {                                \
        ((N)->next)->prev = ((N)->prev);            \
        ((N)->prev)->next = ((N)->next);            \
        LL_INIT(N);                     \
    } while (0)

#define LL_EMPTY(N) ((N)->next == (N))

#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)

#define LL_FOREACH_SAFE(H,N,T)                      \
    for (N = (H)->next, T = (N)->next; N != (H);            \
            N = (T), T = (N)->next)

#endif /* LLIST_HEADER_INCLUDED */
上一篇:锁相关


下一篇:面试必会之LinkedList源码分析