了解Linux通用的双向循环链表.doc
《了解Linux通用的双向循环链表.doc》由会员分享,可在线阅读,更多相关《了解Linux通用的双向循环链表.doc(10页珍藏版)》请在三一办公上搜索。
1、了解Linux通用的双向循环链表在linux内核中,有一种通用的双向循环链表,构成了各种队列的基础。链表的结构定义和相关函数均在include/linux/list.h中,下面就来全面的介绍这一链表的各种API。struct list_head struct list_head *next, *prev;这是链表的元素结构。因为是循环链表,表头和表中节点都是这一结构。有prev和next两个指针,分别指向链表中前一节点和后一节点。/* * Simple doubly linked list implementation. * * Some of the internal funcTIons (
2、_xxx) are useful when * manipulaTIng whole lists rather than single entries, as * someTImes we already know the next/prev entries and we can * generate better code by using them directly rather than * using the generic single-entry routines. */#define LIST_HEAD_INIT(name) list-prev = list;在初始化的时候,链表
3、头的prev和next都是指向自身的。/* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */#ifndef CONFIG_DEBUG_LISTstatic inline void _list_add(struct list_head *new, struct list_head *prev, struct list_head *ne
4、xt) next-prev = new; new-next = next; new-prev = prev; prev-next = new;#elseextern void _list_add(struct list_head *new, struct list_head *prev, struct list_head *next);#endif/* * list_add - add a new entry * new: new entry to be added * head: list head to add it after * * Insert a new entry after t
5、he specified head. * This is good for implementing stacks. */static inline void list_add(struct list_head *new, struct list_head *head)_list_add(new, head, head-next);/* * list_add_tail - add a new entry * new: new entry to be added * head: list head to add it before * * Insert a new entry before th
6、e specified head. * This is useful for implementing queues. */static inline void list_add_tail(struct list_head *new, struct list_head *head)_list_add(new, head-prev, head);双向循环链表的实现,很少有例外情况,基本都可以用公共的方式来处理。这里无论是加第一个节点,还是其它的节点,使用的方法都一样。另外,链表API实现时大致都是分为两层:一层外部的,如list_add、list_add_tail,用来消除一些例外情况,调用内部
7、实现;一层是内部的,函数名前会加双下划线,如_list_add,往往是几个操作公共的部分,或者排除例外后的实现。/* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */static inline void _list_del(struct list_head * prev, struct list_h
8、ead * next) next-prev = prev; prev-next = next;/* * list_del - deletes entry from list. * entry: the element to delete from the list. * Note: list_empty() on entry does not return true after this, the entry is * in an undefined state. */#ifndef CONFIG_DEBUG_LISTstatic inline void list_del(struct lis
9、t_head *entry) _list_del(entry-prev, entry-next); entry-next = LIST_POISON1; entry-prev = LIST_POISON2;#elseextern void list_del(struct list_head *entry);#endif/* * list_del_init - deletes entry from list and reinitialize it. * entry: the element to delete from the list. */static inline void list_de
10、l_init(struct list_head *entry) _list_del(entry-prev, entry-next); INIT_LIST_HEAD(entry);list_del是链表中节点的删除。之所以在调用_list_del后又把被删除元素的next、prev指向特殊的LIST_POSITION1和LIST_POSITION2,是为了调试未定义的指针。list_del_init则是删除节点后,随即把节点中指针再次初始化,这种删除方式更为实用。/* * list_replace - replace old entry by new one * old : the elemen
11、t to be replaced * new : the new element to insert * * If old was empty, it will be overwritten. */static inline void list_replace(struct list_head *old, struct list_head *new) new-next = old-next; new-next-prev = new; new-prev = old-prev; new-prev-next = new;static inline void list_replace_init(str
12、uct list_head *old, struct list_head *new) list_replace(old, new); INIT_LIST_HEAD(old);list_replace是将链表中一个节点old,替换为另一个节点new。从实现来看,即使old所在地链表只有old一个节点,new也可以成功替换,这就是双向循环链表可怕的通用之处。list_replace_init将被替换的old随即又初始化。/* * list_move - delete from one list and add as anothers head * list: the entry to move *
13、 head: the head that will precede our entry */static inline void list_move(struct list_head *list, struct list_head *head) _list_del(list-prev, list-next); list_add(list, head);/* * list_move_tail - delete from one list and add as anothers tail * list: the entry to move * head: the head that will fo
14、llow our entry */static inline void list_move_tail(struct list_head *list, struct list_head *head) _list_del(list-prev, list-next); list_add_tail(list, head);list_move的作用是把list节点从原链表中去除,并加入新的链表head中。list_move_tail只在加入新链表时与list_move有所不同,list_move是加到head之后的链表头部,而list_move_tail是加到head之前的链表尾部。/* * list_
15、is_last - tests whether list is the last entry in list head * list: the entry to test * head: the head of the list */static inline int list_is_last(const struct list_head *list, const struct list_head *head) return list-next = head;list_is_last 判断list是否处于head链表的尾部。/* * list_empty - tests whether a l
16、ist is empty * head: the list to test. */static inline int list_empty(const struct list_head *head) return head-next = head;/* * list_empty_careful - tests whether a list is empty and not being modified * head: the list to test * * Description: * tests whether a list is empty _and_ checks that no ot
17、her CPU might be * in the process of modifying either member (next or prev) * * NOTE: using list_empty_careful() without synchronization * can only be safe if the only activity that can happen * to the list entry is list_del_init(). Eg. it cannot be used * if another CPU could re-list_add() it. */st
18、atic inline int list_empty_careful(const struct list_head *head) struct list_head *next = head-next; return (next = head) list_empty 判断head链表是否为空,为空的意思就是只有一个链表头head。list_empty_careful 同样是判断head链表是否为空,只是检查更为严格。/* * list_is_singular - tests whether a list has just one entry. * head: the list to test.
19、*/static inline int list_is_singular(const struct list_head *head) return !list_empty(head) list_is_singular 判断head中是否只有一个节点,即除链表头head外只有一个节点。static inline void _list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry) struct list_head *new_first = entry-next; list-
20、next = head-next; list-next-prev = list; list-prev = entry; entry-next = list; head-next = new_first; new_first-prev = head;/* * list_cut_position - cut a list into two * list: a new list to add all removed entries * head: a list with entries * entry: an entry within head, could be the head itself *
21、 and if so we wont cut the list * * This helper moves the initial part of head, up to and * including entry, from head to list. You should * pass on entry an element you know is on head. list * should be an empty list or a list you do not care about * losing its data. * */static inline void list_cut
22、_position(struct list_head *list, struct list_head *head, struct list_head *entry) if (list_empty(head) return; if (list_is_singular(head) if (entry = head) INIT_LIST_HEAD(list); else _list_cut_position(list, head, entry);list_cut_position 用于把head链表分为两个部分。从head-next一直到entry被从head链表中删除,加入新的链表list。新链表
23、list应该是空的,或者原来的节点都可以被忽略掉。可以看到,list_cut_position中排除了一些意外情况,保证调用_list_cut_position时至少有一个元素会被加入新链表。static inline void _list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next) struct list_head *first = list-next; struct list_head *last = list-prev; first-prev = prev; pr
24、ev-next = first; last-next = next; next-prev = last;/* * list_splice - join two lists, this is designed for stacks * list: the new list to add. * head: the place to add it in the first list. */static inline void list_splice(const struct list_head *list, struct list_head *head) if (!list_empty(list)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 了解 Linux 通用 双向 循环
链接地址:https://www.31ppt.com/p-4918779.html