遍历Linux kernel的链表时删除元素的技巧
发布时间：2021-11-25 20:48:39 所属栏目：教程 来源：互联网
导读：内核的链表list_head设计相当巧妙。今天我说一下对list_head链表的遍历时如何删除元素。 链表遍历时，如果删除当前元素，一般都是会出错的。在所有语言的各种库中的链表都是如此。list_head也一样。 如，在Java的遍历中删除当前元素，会抛出java.util.Concurr
|
内核的链表list_head设计相当巧妙。今天我说一下对list_head链表的遍历时如何删除元素。 链表遍历时，如果删除当前元素，一般都是会出错的。在所有语言的各种库中的链表都是如此。list_head也一样。 如，在Java的遍历中删除当前元素，会抛出java.util.ConcurrentModificationException异常。 见：《Java中如何删除一个集合中的多个元素》 。 使用list_for_each遍历链表，如果使当前元素脱链，那么系统就会毫不留情的crash掉。什么提示信息都没有。因此这类bug非常难以定位。 list_for_each源码： /** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each(pos, head) / for (pos = (head)->next; prefetch(pos->next), pos != (head); / pos = pos->next) list_del脱链元素后，会把next和prev分别赋值为： /* * These are non-NULL pointers that will result in page faults * under normal circumstances, used to verify that nobody uses * non-initialized list entries. */ #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA) #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA list_del_init脱链元素后，会把next和prev都设置为自己。 因此，在list_for_each中删除当前元素后，就无法正确找到链表的下一个元素。 如果要在遍历list_head链表时，删除当前元素，那么就必须使用list_for_each_safe函数而不能使用list_for_each函数。 list_for_each_safe源码： /** * list_for_each_safe - iterate over a list safe against removal of list entry * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */ #define list_for_each_safe(pos, n, head) / for (pos = (head)->next, n = pos->next; pos != (head); / pos = n, n = pos->next) 这个函数比list_for_each函数多了一个n参数。这个参数也是list_head类型的。 它保存下一个元素，这样就可以安全的删除当前元素，不会造成找不到后续元素的情况发生。 在循环结束时，pos指向n元素，而不是指向pos的next元素。因为pos脱链后，pos元素的next可能已经是空指针，或者是LIST_POISON1 这个无意义的值了。 如果list是空的，那么pos=n后，仍然等于head，遍历就此结束了！ 因此，使用lisf_for_each_safe函数遍历list_head链表，就可以安全地删除当前元素了。  （编辑：江门站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
