linux單向循環(huán)鏈表源碼分析

extern inline void add_wait_queue(struct wait_queue ** p, struct wait_queue * wait){  unsigned long flags;
#ifdef DEBUG  if (wait->next) {    unsigned long pc;    __asm__ __volatile__("call 1f\n"      "1:\tpopl %0":"=r" (pc));    printk("add_wait_queue (%08x): wait->next = %08x\n",pc,(unsigned long) wait->next);  }#endif  save_flags(flags);  cli();  // 隊(duì)列為空，頭指針指向待插入的節(jié)點(diǎn)wait，末節(jié)點(diǎn)的next指針指向自己  if (!*p) {    wait->next = wait;    *p = wait;  } else {    /*       在第一個(gè)節(jié)點(diǎn)后面插入節(jié)點(diǎn)，形成單向循環(huán)鏈表 thanks to zym.      插入第二個(gè)節(jié)點(diǎn)的時(shí)候，是在第一個(gè)節(jié)點(diǎn)后面插入，后面在插入的時(shí)候，      是在第一個(gè)第二個(gè)節(jié)點(diǎn)中間插入，然后是從第一第三個(gè)直接插入，如此類推      *p指向第一個(gè)節(jié)點(diǎn)，(*p)->next指向第一個(gè)節(jié)點(diǎn)的下一個(gè)，插入第二個(gè)節(jié)點(diǎn)的時(shí)候，      第一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是自己。wait->next即新節(jié)點(diǎn)的next指向第一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，      (*p)->next = wait;即第一個(gè)節(jié)點(diǎn)的next指針指向新加入的節(jié)點(diǎn)。      傳統(tǒng)的頭插法只能形成單鏈表，不能循環(huán)，因?yàn)檠h(huán)需要拿尾指針的next指向第一個(gè)      節(jié)點(diǎn)，但是隨著鏈表的變成，無(wú)法找到尾節(jié)點(diǎn)。      p -> head -> null      p -> head -> node1                 next              |------->      p -> head -> node1     node2              <-------                next                  next    next              |------->   |------->      p -> head -> node1     node3    node2              <------------------                next      測(cè)試代碼      #include <stdio.h>      struct wait_queue {        int task;        struct wait_queue * next;      };      void add_wait_queue(struct wait_queue ** p, struct wait_queue * wait)      {
        if (!*p) {          //printf("%d", 1);          wait->next = wait;          *p = wait;        } else {                    // 頭插法，形成單向鏈表          wait->next = (*p)->next;          (*p)->next = wait;          //printf("%d", wait->next == *p);        }      }      int main()      {        struct wait_queue wait = { 1, NULL };        struct wait_queue wait1 = { 2, NULL };        struct wait_queue wait2 = { 3, NULL };        struct wait_queue * head = NULL;        add_wait_queue(&head, &wait);        add_wait_queue(&head, &wait1);        add_wait_queue(&head, &wait2);        int c = 5;        while(c--) {          printf("%d", head->task);          head = head->next;        }      }    */    wait->next = (*p)->next;    (*p)->next = wait;  }  restore_flags(flags);}
extern inline void remove_wait_queue(struct wait_queue ** p, struct wait_queue * wait){  unsigned long flags;  struct wait_queue * tmp;#ifdef DEBUG  unsigned long ok = 0;#endif
  save_flags(flags);  cli();  // 刪除的是第一個(gè)節(jié)點(diǎn)并且只有一個(gè)節(jié)點(diǎn)了則頭指針指向NULL  if ((*p == wait) &&#ifdef DEBUG      (ok = 1) &&#endif      ((*p = wait->next) == wait)) {    *p = NULL;  } else {    // 從自己開(kāi)始遍歷單向循環(huán)鏈表，找到next指向自己的，然后更新指針    tmp = wait;    while (tmp->next != wait) {      tmp = tmp->next;#ifdef DEBUG      if (tmp == *p)        ok = 1;#endif    }    tmp->next = wait->next;  }  wait->next = NULL;  restore_flags(flags);#ifdef DEBUG  if (!ok) {    printk("removed wait_queue not on list.\n");    printk("list = %08x, queue = %08x\n",(unsigned long) p, (unsigned long) wait);    __asm__("call 1f\n1:\tpopl %0":"=r" (ok));    printk("eip = %08x\n",ok);  }#endif}