Doubly linked lists

The process list is a special doubly linked list. However, as you may have noticed, the Linux kernel uses hundreds of doubly linked lists that store the various kernel data structures.

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 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-4).

Figure 3-4. A doubly linked list built with list_head data structures

Figure 3-4. A doubly linked list built with list_head data structures

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 the conventional first element of the new list (much as init_task is the conventional first element of the process list).

Several functions and macros implement the primitives, including those shown in the following list.

Inserts an element pointed by n right after the specified element pointed by p (to insert n at the beginning of the list, set p to the address of the conventional first element)

list add tail(n,h)

Inserts an element pointed by n at the end of the list specified by the address h of its conventional first element list_del(p)

Deletes an element pointed by p (there is no need to specify the conventional first element of the list)

list_empty(p)

Checks if the list specified by the address of its conventional first element is empty list_entry(p,t,f)

Returns the address of the data structure of type t in which the list_head field that has the name f and the address p is included list_for_each(p,h)

Scans the elements of the list specified by the address h of the conventional first element (similar to for_each_task for the process list)

+1 0

Post a comment