![]()
![]()
1．头文件 #include
2．初始化（宏定义）
1) 在链表节点中添加LIST_ENTRY结构，包括了指向前驱和后继节点的指针。
#define LIST_ENTRY(type)
struct {
type *le_next; /* next element */
type **le_prev; /* address of previous next element */
}
2) 定义一个链表头，链表节点类型为type，表头为lh_first
#define LIST_HEAD(name, type)
struct name {
type *lh_first; /* first element */
}
3) 初始化链表
#define LIST_INIT(head) {
(head)->lh_first = NULL;
}
4) 插入节点
#define LIST_INSERT_AFTER(listelm, elm, field) {
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)
(listelm)->field.le_next->field.le_prev = &(elm)->field.le_next;
(listelm)->field.le_next = (elm);
(elm)->field.le_prev = &(listelm)->field.le_next;
}
#define LIST_INSERT_BEFORE(listelm, elm, field) {
(elm)->field.le_prev = (listelm)->field.le_prev;
(elm)->field.le_next = (listelm);
*(listelm)->field.le_prev = (elm);
(listelm)->field.le_prev = &(elm)->field.le_next;
}
#define LIST_INSERT_HEAD(head, elm, field) {
if (((elm)->field.le_next = (head)->lh_first) != NULL)
(head)->lh_first->field.le_prev = &(elm)->field.le_next;
(head)->lh_first = (elm);
(elm)->field.le_prev = &(head)->lh_first;
}
5) 删除节点
#define LIST_REMOVE(elm, field) {
if ((elm)->field.le_next != NULL)
(elm)->field.le_next->field.le_prev = (elm)->field.le_prev;
*(elm)->field.le_prev = (elm)->field.le_next;
}
3．一个例子
1) 定义节点类型
class MFlood_RTEntry {
friend class MFlood_RTable;
friend class MFlood;
public:
MFlood_RTEntry();
MFlood_RTEntry(nsaddr_t src,u_int32_t seq);
bool isNewSeq(u_int32_t seq); // old -> false, new->true
void addSeq(u_int32_t seq); // add a seqno to seqno array(rt_seqnos)
protected:
LIST_ENTRY(MFlood_RTEntry) rt_link;
nsaddr_t src_;
// u_int32_t seq_;
u_int32_t rt_seqnos[REM_SEQ_COUNT]; //seqno array
u_int32_t max_seqno; //max seqno
u_int32_t min_seqno; //max seqno
u_int16_t seq_it; // seqno's iterator
};
2) 建立一个链表节点类型为MFlood_RTEntry的链表 rthead
LIST_HEAD(, MFlood_RTEntry) rthead;
3) 初始化链表rhead为NULL
LIST_INIT(&rthead)
4) 怎样使用
MFlood_RTEntry*
MFlood_Rtable::rt_lookup(nsaddr_t id) {
Mflood_RTEntry *rt = rthead.lh_first;//获取链表表头
for(; rt; rt = rt->rt_link.le_next) {
if(rt->src_ == id)
break;
}
return rt;
}
5) 删除节点
void
MFlood_RTable::rt_delete(nsaddr_t id) {
MFlood_RTEntry *rt = rt_lookup(id);
if(rt) {
LIST_REMOVE(rt, rt_link);
delete rt;
}
}
6) 插入节点
rt = new MFlood_RTEntry(ih->saddr(), fh->seq_);
LIST_INSERT_HEAD(&rtable_.rthead,rt,rt_link);
双链表示意图：
![]() |
本人在看NS2源代码的时候发现有LIST_HEAD,LIST_ENTRY,LIST_INIT,LIST_REMOVE等等,经过查看源代码和上网翻阅资料,发现NS2有其自身定义的链表结构,定义在bsd-list.h中,于是写了个简短的说明,方便他人使用.由于是自己看源代码后自己理解的,如有错误,请告知
本文档分三部分
1.源码解释
2.源码
3.应用举例
1.解释如下:
LIST_HEAD(name, type) 是定义一个结构体name, 其中包含一个type类型的指针*lh_first,用于指向表头
LIST_ENTRY(type)用于定义两个指针, *le_next指向链表的下一个元素, **le_prev指向”address of previous next element”,即该元素在该队列中的前一个元素的le_next的地址,链表中元素类型为type类型。
LIST_INIT(head) 初始化(head)->lh_first为空
LIST_INSERT_AFTER(listelm, elm, field)将elm插在listelm后面
LIST_INSERT_BEFORE(listelm, elm, field)将elm插在listelm前面
LIST_INSERT_HEAD(head, elm, field)将elm插在表头,对于elm, 将 le_prev指向其自身的地址”(elm)->field.le_prev = &(head)->lh_first”
其中field指的是LIST_ENTRY中定义的结构体实例
LIST_REMOVE(elm, field) 从链表中移出elm
2.源码如下:
#define LIST_HEAD(name, type) \
struct name { \
type *lh_first; /* first element */ \
}
#define LIST_ENTRY(type) \
struct { \
type *le_next; /* next element */ \
type **le_prev; /* address of previous next element */ \
}
/*
* List functions.
*/
#define LIST_INIT(head) { \
(head)->lh_first = NULL; \
}
#define LIST_INSERT_AFTER(listelm, elm, field) { \
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
(listelm)->field.le_next->field.le_prev = \
&(elm)->field.le_next; \
(listelm)->field.le_next = (elm); \
(elm)->field.le_prev = &(listelm)->field.le_next; \
}
#define LIST_INSERT_BEFORE(listelm, elm, field) { \
(elm)->field.le_prev = (listelm)->field.le_prev; \
(elm)->field.le_next = (listelm); \
*(listelm)->field.le_prev = (elm); \
(listelm)->field.le_prev = &(elm)->field.le_next; \
}
#define LIST_INSERT_HEAD(head, elm, field) { \
if (((elm)->field.le_next = (head)->lh_first) != NULL) \
(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
(head)->lh_first = (elm); \
(elm)->field.le_prev = &(head)->lh_first; \
}
#define LIST_REMOVE(elm, field) { \
if ((elm)->field.le_next != NULL) \
(elm)->field.le_next->field.le_prev = \
(elm)->field.le_prev; \
*(elm)->field.le_prev = (elm)->field.le_next; \
}
3.如何使用:
//此例创建了一个链表,名为rt_path_list, 该链表中的元素类型为AODV_path
class AODV_Path {
…
public:
…
protected:
LIST_ENTRY(AODV_Path) path_link;// path_link相当与field
…
};
LIST_HEAD(aodv_paths, AODV_Path);//定义结构体
aodv_paths rt_path_list;// rt_path_list相当与源代码中的head
//初始化
LIST_INIT(&rt_path_list);
//在path后插入p元素（原文：在p元素后插入path元素，似有误！)
LIST_INSERT_AFTER(p, path, path_link);
//在表头插入path
LIST_INSERT_HEAD(&rt_path_list, path, path_link);
//将path从链表中删除
LIST_REMOVE(path, path_link);
//获取链表表头元素
AODV_Path *path = rt_path_list.lh_first;
