熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Oracle >> 正文

分析list

2013-11-13 16:02:51  來源: Oracle 

  作者opera
  代碼:
  ; include/linux/listh
  struct list_head {
   struct list_head *next *prev;
  };
  list_head結構用於構造雙向環形鏈表
  LIST_HEAD(head) : 定義一個空表頭
   struct list_head head = {&head&head};
  INIT_LIST_HEAD(head) : 初始化一個已定義的表頭;
   head>next = head;
   head>prev = head;
  list_add(entryhead); 將entry添加到head之後用於構造堆棧
   head>next>prev = entry;
   entry>next = head>next;
   entry>prev = head;
   head>next = entry;
  list_add_tail(entryhead) : 將entry添加到head之前用於構造隊列
   head>prev = entry;
   entry>next = head;
   entry>prev = head>prev;
   head>prev>next = entry;
  list_del(entry) : 刪除entry
   entry>next>prev = entry>prev;
   entry>prev>next = entry>next;
  list_del_init(entry) : 刪除並復位entry
   entry>next>prev = entry>prev;
   entry>prev>next = entry>next;
   entry>next = entry;
   entry>prev = entry;
  list_empty(head) : 測試環形鏈表是否為空
   (head>next == head)
  list_splice(listhead) : 將兩個環形鏈表合成一個大表
   list>prev>next = head>next;
   list>next>prev = head;
   head>next>prev = list>prev;
   head>next = list>next;
  list_entry(ptrtypemember) :
  如果type結構中member的地址是ptr則返回type結構的地址
   ((type *)((char *)(ptr)(unsigned long)(&((type *))>member)))
  list_for_each(entryhead) : 遍歷鏈表
   for (entry = (head)>next; entry != (head); entry = entry>next)
  ========================================================
  建立雙向鏈表的一種常見方法 作者西安交通大學 王灏
  ========================================================
  在分析內核時常常碰到以pprev作為尾綴的二次指針和帶有next尾綴的一次指針而且在鏈表管理時使用這麼一對指針這裡以網絡bind哈希表建立為例解釋(內核
  代碼:
  struct **skp = &udp_hash[sk>num & (UDP_HTABLE_SIZE )]
  SOCKHASH_LOCK();
  if((sk>next = *skp) != NULL)
   (*skp)>pprev = &sk>next;
  請注意這裡pprev通常是指向前一個結點的next的地址
  *skp = sk;
  sk>pprev =skp;
  SOCKHASH_UNLOCK();
  第一句賦值語句將skp指向以sk>num為參數的哈希鏈的起始地址而哈希數組的每一項都是指向sock結構的指針所以* skp就是指向哈希鏈中的第一個sock結構整個if語句完成在第一個sock結點和當前插入結點間的鏈接關系(包括前向指針和後向指針)後面兩條語句在哈希數組項和當前插入結點之間建立鏈接關系
  用這種方法這裡的鏈表通常pprev指針只在鏈表管理時(插入與刪除)使用而在查找時僅使用next指針也就是說這種鏈表的查找通常是單向的(pprev通常不指向結點的起始位置若進行前向查找必須有一個類似於list_head雙向鏈表的計算結點起始位置的宏)這使得這種鏈表只是在鏈表建立和鏈表刪除時有雙向鏈表的效率而查找時僅是單向鏈表的效率但是這種鏈表通常用在哈希表中這樣雖然查找是單向鏈表的效率但是由於具有同一個哈希值的鏈較短所以執行效率也非常好而且兼有雙向鏈表的插入刪除效率
  
  
  
  

From:http://tw.wingwit.com/Article/program/Oracle/201311/17725.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.