本篇内容介绍了“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
}
“linux单向循环链表源码分析”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。