Processes（五）Doubly linked lists

Doubly linked lists

Before moving on and describing how the kernel keeps track of the various processes in the system, we would like to emphasize the role of special data structures that implement doubly linked lists.

For each list, a set of primitive operations must be implemented: initializing the list, inserting and deleting an element, scanning the list, and so on. It would be both a waste of programmers' efforts and a waste of memory to replicate the primitive operations for each different list.

对于每个链表，必须要实现一系列主要的操作：初始化链表，插入和删除元素，遍历链表等等。为每个不同的链表重复这些主要的操作，对程序员的工作和内存来说都是浪费。毛主席说了，贪污和浪费是最大的犯罪。

Therefore, the Linux kernel defines the list_head data structure, whose only fields next and prev represent the forward and back pointers of a generic doubly linked list element, respectively. It is important to note, however, that the pointers in a list_head field store the addresses of other list_head fields rather than the addresses of the whole data structures in which the list_head structure is included; see Figure 3-3 (a).

因此，Linux内核定义了list_head数据结构，它仅有两个成员next和prev表示一个通用双向链表的前驱和后继节点指针。注意到list_head中的指针存放的其他list_head的地址，而不是包含那个list_head结构的整个数据结构的地址，这点很重要。

A new list is created by using the LIST_HEAD(list_name) macro. It declares a new variable named list_name of type list_head, which is a dummy first element that acts as a placeholder for the head of the new list, and initializes the prev and next fields of the list_head data structure so as to point to the list_name variable itself; see Figure 3-3 (b).

LIST_HEAD(list_name)宏可以创建一个新的链表。它声明了一个新的list_head类型的变量list_name，它是整个新链表空的第一个元素，并且初始化list_head数据结构的prev和next成员，使得它们指向list_name变量本身。

Several functions and macros implement the primitives, including those shown in Table Table 3-1.

Table 3-1. List handling functions and macros                
   

Name	Description
list_add(n,p)	Inserts an element pointed to by n right after the specified element pointed to by p. (To insert n at the beginning of the list, set p to the address of the list head.) 将n指向的元素插入p指定的元素后面
list_add_tail(n,p)	Inserts an element pointed to by n right before the specified element pointed to by p. (To insert n at the end of the list, set p to the address of the list head.) 将n指向的元素插在p指定的元素前面
list_del(p)	Deletes an element pointed to by p. (There is no need to specify the head of the list.) 删除p指向的元素（不需要指明链表的头）
list_empty(p)	Checks if the list specified by the address p of its head is empty. 检查p指向的链表是否为空
list_entry(p,t,m)	Returns the address of the data structure of type t in which the list_head field that has the name m and the address p is included. 返回类型为t的数据结构的地址，其中m是它的list_head成员，地址为p
list_for_each(p,h)	Scans the elements of the list specified by the address h of the head; in each iteration, a pointer to the list_head structure of the list element is returned in p. 遍历头指针为h的链表的元素；在每次迭代过程中返回当前迭代的list_head结构的指针为p
list_for_each_entry(p,h,m)	Similar to list_for_each, but returns the address of the data structure embedding the list_head structure rather than the address of the list_head structure itself. 和list_fro_each相同，但是返回的是list_head内嵌的数据结构的指针而不是list_head本身的指针

The Linux kernel 2.6 sports another kind of doubly linked list, which mainly differs from a list_head list because it is not circular; it is mainly used for hash tables, where space is important, and finding the the last element in constant time is not. The list head is stored in an hlist_head data structure, which is simply a pointer to the first element in the list (NULL if the list is empty). Each element is represented by an hlist_node data structure, which includes a pointer next to the next element, and a pointer pprev to the next field of the previous element. Because the list is not circular, the pprev field of the first element and the next field of the last element are set to NULL. The list can be handled by means of several helper functions and macros similar to those listed in Table 3-1: hlist_add_head( ), hlist_del( ), hlist_empty( ), hlist_entry, hlist_for_each_entry, and so on.

Linux2.6支持另外一种双向链表，主要不同的是它不是循环的（首尾相连）；它主要用在hash表中，这个表的空间并不重要，也并不经常访问最后一个元素。链表的头存储在一个hlist_array数据结构中，只是一个指向链表中第一个元素的指针（链表为空是为NULL）。每个元素由一个hlist_node数据结构表示，它包含了一个指向下一个元素的指针next，指向前一个元素next成员的指针pprev。因此链表不是环状的，第一个元素的pprev成员和最后一个元素的next成员都设为NULL。这种链表可以由一些与上文类似的函数和宏处理：hlist_add_head(), hlist_del(), hlist_entry, hlist_for_each_entry等等。