双向链表的宏实现——解析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);

删除节点： 将某个节点从链表中删除（让该链表的下一节点与上一节点相互指向对方），并再次初始化该节点

#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 */