linux单向循环链表源码分析

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();  // 队列为空，头指针指向待插入的节点wait，末节点的next指针指向自己  if (!*p) {    wait->next = wait;    *p = wait;  } else {    /*       在第一个节点后面插入节点，形成单向循环链表 thanks to zym.      插入第二个节点的时候，是在第一个节点后面插入，后面在插入的时候，      是在第一个第二个节点中间插入，然后是从第一第三个直接插入，如此类推      *p指向第一个节点，(*p)->next指向第一个节点的下一个，插入第二个节点的时候，      第一个节点的下一个节点是自己。wait->next即新节点的next指向第一个节点的下一个节点，      (*p)->next = wait;即第一个节点的next指针指向新加入的节点。      传统的头插法只能形成单链表，不能循环，因为循环需要拿尾指针的next指向第一个      节点，但是随着链表的变成，无法找到尾节点。      p -> head -> null      p -> head -> node1                 next              |------->      p -> head -> node1     node2              <-------                next                  next    next              |------->   |------->      p -> head -> node1     node3    node2              <------------------                next      测试代码      #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();  // 删除的是第一个节点并且只有一个节点了则头指针指向NULL  if ((*p == wait) &&#ifdef DEBUG      (ok = 1) &&#endif      ((*p = wait->next) == wait)) {    *p = NULL;  } else {    // 从自己开始遍历单向循环链表，找到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}