Chinaunix首页 | 论坛 | 博客
  • 博客访问: 756849
  • 博文数量: 285
  • 博客积分: 11
  • 博客等级: 民兵
  • 技术积分: 2340
  • 用 户 组: 普通用户
  • 注册时间: 2010-11-23 17:58
个人简介

真正的安全感,来自你对自己的信心,是你每个阶段性目标的实现,而真正的归属感,在于你的内心深处,对自己命运的把控,因为你最大的对手永远都是自己。| Network+Security+Database.

文章存档

2011年(3)

2010年(1)

2009年(33)

2008年(248)

我的朋友

分类: 系统运维

2009-06-09 19:09:53

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) 初始化链表rheadNULL
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;

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/lyplyz/archive/2007/06/20/1659889.aspx
阅读(1785) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~