[数据结构与算法]关于内核开发前期的准备工作-------内核链表深耕

SHOW ME THE CODE
com_list.h

#ifndef LIST_HEAD_COMMON_USE
#define LIST_HEAD_COMMON_USE
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<unistd.h>
#include<stdint.h>

typedef struct com_list_head{
	struct com_list_head *pre,*next;
}COM_LIST_HEAD_t;

//同时初始化前一个节点和后一个节点的地址,最当前节点的使用进行初始化,及头部指针的结果进行初始化
#define LIST_HEAD_INIT(head_ptr) { &(head_ptr),&(head_ptr)}
#define LIST_HEAD(head_ptr) COM_LIST_HEAD_t head_ptr = LIST_HEAD_INIT(head_ptr)

static inline void INIT_LIST_HEAD(COM_LIST_HEAD_t *head_ptr){
	head_ptr->next = head_ptr;
	head_ptr->pre = head_ptr;
}

static inline void __list_add(COM_LIST_HEAD_t *new,COM_LIST_HEAD_t *pre,COM_LIST_HEAD_t *next)
{
	next->pre = new;
	new->next = next;
	new->pre = pre;
	pre->next = new;
}

static inline void list_add_tail(COM_LIST_HEAD_t *new,COM_LIST_HEAD_t *head)
{
	__list_add(new,head->pre,head);
}

static inline void __list_del(COM_LIST_HEAD_t *pre,COM_LIST_HEAD_t *next){
	next->pre = pre;
	pre->next = next;
}

// 节点为即将要删除的节点进行使用
static inline void list_del(COM_LIST_HEAD_t *del_node)
{
	__list_del(del_node->pre,del_node->next);
}

static inline void list_del_init(COM_LIST_HEAD_t *del_node)
{
	list_del(del_node);
	INIT_LIST_HEAD(del_node);
}

static inline void list_replace(COM_LIST_HEAD_t *old_node,COM_LIST_HEAD_t *new_node){
	new_node->next = old_node->next;
	new_node->next->pre = new_node;
	new_node->pre = old_node->pre;
	new_node->pre->next = new_node;
}

static inline void list_empty(COM_LIST_HEAD_t *head_ptr){
	head_ptr->next = head_ptr;
}

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({          \
			const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
						(type *)( (char *)__mptr - offsetof(type,member) );})

#define list_each(pos,head) for(pos=(head)->next;pos !=(head);pos=pos->next)
/* 遍历链表时应该使用下面的safe模式链表查找 */
#define list_each_safe(pos,n,head) for(pos=(head)->next,n=pos->next;pos !=(head);pos=n,n=pos->next)
#define list_node_get(ptr,type,member) container_of(ptr,type,member)

#endif

测试链表代码 com_list.c

#include "com_list.h"

typedef int (*driver_func)(int,char**);
typedef struct{
	char name[128];
	driver_func driver_com_func;
	COM_LIST_HEAD_t node; 
}test_driver_t;

int main(void)
{
	LIST_HEAD(user_driver_node);
	COM_LIST_HEAD_t *cur;
	test_driver_t *tmp;

	test_driver_t fpga_test={
		.name = "fpga test",
	};

	list_add_tail(&(fpga_test.node),&user_driver_node);
	test_driver_t clock_test={
		.name = "clock test",
	};

	list_add_tail(&(clock_test.node),&user_driver_node);
	
	list_each(cur,&user_driver_node){
		tmp = list_node_get(cur,test_driver_t,node);
		printf("init name:%s\n",tmp->name);
	}
}

Makefile:

.PHONY:all, clean

all:
	gcc $(wildcard *.c) -o list -g -Wall

clean:
	rm -rf *.o list

测试结果:

hongyu@virtual-machine:~/workspace/source/common$ ./list 
init name:fpga test
init name:clock test

内核代码中的神来之笔就在于 container_of 宏定义
链表这个算法可以说前期看抽象难理解,现在看就是按照一定的顺序排列的书签的作用,毕竟所有的算法来源于哲学，哲学来源生活,所以现在来说没啥可说的,链表是AVL树的基础,虽然内存查表的过程是基于一棵不平衡的二叉树，但是不影响仔细看看这个内核链表，高效，稳定,实用,单链表的实用性较差,双向链表的在业务中使用的是最多的
为什么要深耕这个内核中的链表,这个内核的数据的传输链表就好比人的静脉,纵横交错,完全弄清楚是有必要的
typeof () ： 这是一个关键字，获取变量名的数据结构
offsetof([struct],[struct member]) : 成员变量的偏移地址
| struct name| member 1 | member 2| : 这段偏移地址就是离member2距 struct name 差值
有一个问题就是问什么要用container_of,当然是为了找到你要找的数据结构的地址,这个地址才是正常要使用的变量的地址
意思就是说，我可以用一个头，使用不同的数据结构的结构体或者变量

README

告警使我难受