linux内核数据结构--链表
2013-12-22
链表定义与初始化
链表结构定义如下所示：
struct list_head {
struct list_head *next, *prev;
};
需要用链表结构时，只需要在结构体中定义一个链表类型的数据即可。例如定义一个test_list链表：
typedef struct local_list
{
uint32_t test_id;
uint32_t up_flow;
uint32_t down_flow;
struct list_head test_list_head; //链表节点
}test_list;
通过container_of和offsetof，可以根据test_list_head的地址找出test_list的起始地址，即一个完整test_list结构的起始地址。
linux内核链表实现
内核实现的是双向循环链表，<linux/list.h>中提供了链表操作的API函数。
初始化链表头结点
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
LIST_HEAD宏创建一个链表头结点，并用LIST_HEAD_INIT宏对头结点进行赋值，使得头结点的前驱和后继指向自己。
INIT_LIST_HEAD函数对链表进行初始化，使得前驱和后继指针指针指向头结点。
插入节点
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
插入节点分为从链表头部插入list_add和链表尾部插入list_add_tail，通过调用__list_add函数进行实现，head->next指向之一个节点，head->prev指向尾部节点。
删除节点
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
从链表中删除一个节点，需要改变该节点前驱节点的后继结点和后继结点的前驱节点。最后设置该节点的前驱节点和后继结点指向LIST_POSITION1和LIST_POSITION2两个特殊值，这样设置是为了保证不在链表中的节点项不可访问，对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障
/*
* 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_move - delete from one list and add as another's head
* @list: the entry to move
* @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 another's tail
* @list: the entry to move
* @head: the head that will follow 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_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_empty - tests whether a list is empty
* @head: the list to test.
*/
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
遍历链表
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
/**
* list_first_entry - get the first element from a list
* @ptr: the list head to take the element from.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*
* Note, that list is expected to be not empty.
*/
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
/**
* 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)
实例练习
九度OJ上 题目1001：A+B for Matrices
题目描述：
This time, you are supposed to find A+B where A and B are two matrices, and then count the number of zero rows and columns.
输入： The input consists of several test cases, each starts with a pair of positive integers M and N (≤10) which are the number of rows and columns of the matrices, respectively. Then 2*M lines follow, each contains N integers in [-100, 100], separated by a space. The first M lines correspond to the elements of A and the second M lines to that of B. The input is terminated by a zero M and that case must NOT be processed.
输出： For each test case you should output in one line the total number of zero rows and columns of A+B.
样例输入： 2 2 1 1 1 1 -1 -1 10 9 2 3 1 2 3 4 5 6 -1 -2 -3 -4 -5 -6 0 样例输出： 1 5
写了个小程序，用链表来存储数据。源代码如下(没办法，想实现动态数组和控制，代码看起来有点长)：
/*
Description: input two matrices, m and n represents the rows and clumns
first input two numbers indicate the m and n,then are matrices A and B in m*n dimension
then maybe the next two m and n,then follows A and B
like this, input will end with a 0
*/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
//#define DEBUG
#ifdef DEBUG
#define pr_info(format,...) printf(format,##__VA_ARGS__)
#else
#define pr_info(format,...) do{}while(0)
#endif
struct list_head{
struct list_head *next,*prev;
};
static void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
// add a node to list
static void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
//add a list node to the tail
static void list_add_tail(struct list_head *new,struct list_head *head)
{
__list_add(new,head->prev,head);
}
// empty
static int is_list_empty(const struct list_head *head)
{
return head->next == head;
}
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
//list_entry get the struct for this entry
#define list_entry(ptr,type,member)\
container_of(ptr,type,member)
#define list_for_each_entry(pos,head,member)\
for(pos=list_entry((head)->next,typeof(*pos),member);\
&pos->member != (head);\
pos=list_entry(pos->member.next,typeof(*pos),member))
typedef struct array_node{
int row_length;
int clumn_width;
int count;
int *element;
struct list_head array_head;
}target_array;
void flush()
{
char c;
while( (c=getchar() != '\n') && c!=EOF );
}
static target_array * create_src_array(int row,int clumn,int *matrices)
{
target_array *new_array;
new_array = (target_array *)malloc(sizeof(target_array));
if(!new_array){
printf("Failed to malloc space for new_array!\n");
return NULL;
}
new_array->row_length = row;
new_array->clumn_width = clumn;
new_array->count = 0;
new_array->element = matrices;
return new_array;
}
int main(int argc, char *argv[])
{
int i,j;
int m,n;
int *input_array;
int *tmp;
int *ori_input_array;;
target_array *iteral_list;
target_array *saved_array;
struct list_head *head;
int *tmp_a;
int *tmp_b;
head = (struct list_head *)malloc(sizeof(struct list_head));
if( !head ){
printf("Error in malloc head\n");
return -1;
}
INIT_LIST_HEAD(head);// init list head
while(1){
pr_info("pls input the m and n:");
while (scanf("%d",&m) != 1) {
pr_info("invalid input,pls input again!\n");
flush();
}
pr_info("m=%d\n",m);
if(m==0)break;
while ((scanf("%d",&n) != 1) || n < 1) {
pr_info("invalid input,pls input again!\n");
flush();
}
pr_info("n=%d\n",n);
input_array=(int *)malloc(sizeof(int)*2*m*n);
if(!input_array){
printf("Failed to malloc space for now input array!!!\n");
return -2;
}
ori_input_array = input_array;
tmp = input_array;
pr_info("Now pls input two nums with %d * %d dimensions!\n",m,n);
for(i=0;i<2*m;i++){
for(j=0;j<n;j++){
while (scanf("%d",input_array) != 1) {
pr_info("invalid input,pls input again!\n");
flush();
}
input_array++;
}
pr_info("matrices %2c row %2d: ",i/m>0?'B':'A',i%m);
for(j=0;j<n;j++,tmp++)
pr_info("%3d ",*tmp);
pr_info("\n");
}
/*
* now I get m ,n ,and the data save after input_array.
* Here I use link list to complete this target.
*
*/
saved_array = create_src_array(m,n,ori_input_array);
if(!saved_array){
printf("Error malloc space for node list!!!\n");
return -3;
}
list_add_tail(&saved_array->array_head,head);
}
if(is_list_empty(head)){
printf("you have input nothing!!!\n");
return -4;
}
/*
* now print the link_list data to test if it is correct
*/
list_for_each_entry(iteral_list,head,array_head){
pr_info("row:%2d clumn:%2d\n",iteral_list->row_length,iteral_list->clumn_width);
tmp = iteral_list->element;
for(i=0;i<(iteral_list->row_length)*2;i++){
for(j=0;j<iteral_list->clumn_width;j++){
pr_info("%4d ",*(tmp+i*(iteral_list->clumn_width)+j));
}
pr_info("\n");
}
// calculate the row members
tmp_a = iteral_list->element;
tmp_b = iteral_list->element + (iteral_list->row_length)*(iteral_list->clumn_width);
for(i=0;i<iteral_list->row_length;i++){
for(j=0;j<iteral_list->clumn_width;j++){
pr_info("row:i=%d,j=%d,a=%d,b=%d\n",i,j,*tmp_a,*tmp_b);
if((*tmp_a + *tmp_b) == 0){
tmp_a++;
tmp_b++;
}else{
tmp_a +=(iteral_list->clumn_width-j);
tmp_b +=(iteral_list->clumn_width-j);
j = 0;
break;
}
}
if(j == iteral_list->clumn_width)
iteral_list->count++;
}
// calculate the clumn members
tmp_a = iteral_list->element;
tmp_b = iteral_list->element + (iteral_list->row_length)*(iteral_list->clumn_width);
for(j=0;j<iteral_list->clumn_width;j++){
for(i=0;i<iteral_list->row_length;i++){
pr_info("col:i=%d,j=%d,a=%d,b=%d\n",i,j,*tmp_a,*tmp_b);
if((*tmp_a + *tmp_b) == 0){
tmp_a += iteral_list->clumn_width;
tmp_b += iteral_list->clumn_width;
}else{
i = 0;
break;
}
}
if(i == iteral_list->row_length)
iteral_list->count++;
tmp_a = iteral_list->element + j +1;
tmp_b = iteral_list->element + (iteral_list->row_length)*(iteral_list->clumn_width) + j +1;
}
printf("%d\n",iteral_list->count);
}
return 0;
}
因为使用了GNU C对标准C的扩展（typeof）的原因，因此九度上的编译命令（gcc Main.c -o Main -02 -Wall -lm –static -std=c99）暂时无法编译通过，但不使用-std=c99就可以编译通过。
再来一个单链表的实现，九度OJ上可以编译通过的代码：
/*
Description: input two matrices, m and n represents the rows and clumns
first input two numbers indicate the m and n,then are matrices A and B in m*n dimension
then maybe the next two m and n,then follows A and B
like this, input will end with a 0
Data save struct:
single linked list
*/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
//#define DEBUG
#ifdef DEBUG
#define pr_info(format,...) printf(format,##__VA_ARGS__)
#else
#define pr_info(format,...) do{}while(0)
#endif
typedef struct data{
int row_length;
int clumn_width;
int count;
int *element;
}array_data;
struct array_node{
array_data local_data;
struct array_node *next;
};
typedef struct array_node target_array;
struct list_head{
target_array *next;
};
static int is_single_list_empty(struct list_head *head)
{
return head->next == NULL;
}
static int element_add_to_tail(target_array *element,target_array *list)
{
if(list->next == NULL){
list->next = element;
}else{
element_add_to_tail(element,list->next);
}
return 0;
}
static int element_add_to_list(target_array *element,struct list_head *head)
{
if(is_single_list_empty(head)){
head->next = element;
}else{
element_add_to_tail(element,head->next);
}
return 0;
}
static int free_target_array(target_array *entry)
{
if(entry){
free(entry->local_data.element);
free(entry);
}
return 0;
}
static int free_list(struct list_head *head)
{
target_array *tmp_a,*tmp_b;
if(is_single_list_empty(head)){
pr_info("head is an empty list");
free(head);
}else{
tmp_a = head->next;
if(tmp_a){
tmp_b = tmp_a->next;
free_target_array(tmp_a);
tmp_a = tmp_b;
}
head->next = NULL;
free(head);
}
return 0;
}
void flush()
{
char c;
while( (c=getchar() != '\n') && c!=EOF );
}
int main(int argc, char *argv[])
{
int i,j;
int m,n;
int *input_array;
int *tmp;
int *ori_input_array;;
target_array *iteral_list;
target_array *saved_array;
struct list_head *head = NULL;
int *tmp_a;
int *tmp_b;
head = (struct list_head *)malloc(sizeof(struct list_head));
if(!head){
printf("Failed to malloc space for new_array!\n");
return -1;
}
head->next = NULL;
while(1){
pr_info("pls input the m and n:");
while (scanf("%d",&m) != 1) {
printf("invalid input,pls input again!\n");
flush();
}
pr_info("m=%d\n",m);
if(m==0)break;
while ((scanf("%d",&n) != 1) || n < 1) {
printf("invalid input,pls input again!\n");
flush();
}
pr_info("n=%d\n",n);
input_array=(int *)malloc(sizeof(int)*2*m*n);
if(!input_array){
printf("Failed to malloc space for now input array!!!\n");
return -2;
}
ori_input_array = input_array;
tmp = input_array;
pr_info("Now pls input two nums with %d * %d dimensions!\n",m,n);
for(i=0;i<2*m;i++){
for(j=0;j<n;j++){
while (scanf("%d",input_array) != 1) {
printf("invalid input,pls input again!\n");
flush();
}
input_array++;
}
pr_info("matrices %2c row %2d: ",i/m>0?'B':'A',i%m);
for(j=0;j<n;j++,tmp++)
pr_info("%3d ",*tmp);
pr_info("\n");
}
/*
* now I get m ,n ,and the data save after input_array.
* Here I use link list to complete this target.
*
*/
saved_array = (target_array *)malloc(sizeof(target_array));
if(!saved_array){
printf("Failed to malloc space for new_array!\n");
return -3;
}
memset(saved_array,0,sizeof(target_array));
saved_array->local_data.row_length = m;
saved_array->local_data.clumn_width = n;
saved_array->local_data.count = 0;
saved_array->local_data.element = ori_input_array;
element_add_to_list(saved_array,head);
}
if(is_single_list_empty(head)){
printf("you have input nothing!!!\n");
return -4;
}
#if 1
/*
* now print the link_list data to test if it is correct
*/
for(iteral_list = head->next;iteral_list != NULL;iteral_list = iteral_list->next){
pr_info("row:%2d clumn:%2d\n",iteral_list->local_data.row_length,iteral_list->local_data.clumn_width);
tmp = iteral_list->local_data.element;
for(i=0;i<(iteral_list->local_data.row_length)*2;i++){
for(j=0;j<iteral_list->local_data.clumn_width;j++){
pr_info("%4d ",*(tmp+i*(iteral_list->local_data.clumn_width)+j));
}
pr_info("\n");
}
// calculate the row members
tmp_a = iteral_list->local_data.element;
tmp_b = iteral_list->local_data.element + (iteral_list->local_data.row_length)*(iteral_list->local_data.clumn_width);
for(i=0;i<iteral_list->local_data.row_length;i++){
for(j=0;j<iteral_list->local_data.clumn_width;j++){
pr_info("row:i=%d,j=%d,a=%d,b=%d\n",i,j,*tmp_a,*tmp_b);
if((*tmp_a + *tmp_b) == 0){
tmp_a++;
tmp_b++;
}else{
tmp_a +=(iteral_list->local_data.clumn_width-j);
tmp_b +=(iteral_list->local_data.clumn_width-j);
j = 0;
break;
}
}
if(j == iteral_list->local_data.clumn_width)
iteral_list->local_data.count++;
}
// calculate the clumn members
tmp_a = iteral_list->local_data.element;
tmp_b = iteral_list->local_data.element + (iteral_list->local_data.row_length)*(iteral_list->local_data.clumn_width);
for(j=0;j<iteral_list->local_data.clumn_width;j++){
for(i=0;i<iteral_list->local_data.row_length;i++){
pr_info("col:i=%d,j=%d,a=%d,b=%d\n",i,j,*tmp_a,*tmp_b);
if((*tmp_a + *tmp_b) == 0){
tmp_a += iteral_list->local_data.clumn_width;
tmp_b += iteral_list->local_data.clumn_width;
}else{
i = 0;
break;
}
}
if(i == iteral_list->local_data.row_length)
iteral_list->local_data.count++;
tmp_a = iteral_list->local_data.element + j +1;
tmp_b = iteral_list->local_data.element + (iteral_list->local_data.row_length)*(iteral_list->local_data.clumn_width) + j +1;
}
printf("%d\n",iteral_list->local_data.count);
}
#endif
free_list(head);
return 0;
}
参考：
深入分析 Linux 内核链表 LDD3
