Linux教程

Linux系统中链表的骚操作

本文主要是介绍Linux系统中链表的骚操作,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • Linux系统内核队列的骚操作
      • 一、常规链表的实现
      • 二、Linux中的链表实现
        • 1. 链表节点的结构
        • 2. 数据节点
        • 3. 通过结构体成员访问结构体自身
          • 3.1 计算结构体成员的偏移量
          • 3.2 得到结构体本身的地址
        • 4. 组成链表

Linux系统内核队列的骚操作

本系统仿照Linux中的队列实现是一个双向链表,个人认为Linux中的双向链表实现简直太妙了。

一、常规链表的实现

在学习数据结构课程时,都学过双向链表这种数据结构,基本上都是下面这种结构:

struct student {
    struct student* next;
    int id;
    char name[30];
	struct student* pre;
};

很多节点组成的双向链表结构大致如下:

我特意在每个结构体周围花了虚线的边框,表示整个结构体。(并不表示结构体本身和成员有空隙)。

会发现,这样的链表有一下很重要的特点:

  • 节点指针(pre和next)指向一个整个节点

但是会发现,这样的链表有很大的局限性:

  • 不同的链表的节点的结构和操作都是类似了(无非增删改查),只有链表节点中的数据不同
  • 每当创建一个不同类型的链表,都要重新写一遍(包括链表的操作)

但是在Linux中,实现了一种更加通用的链表结构,简直太妙了。

二、Linux中的链表实现

在Linux中的双向链表的实现是这样的(听说,我也没看过Linux源代码)。

1. 链表节点的结构

下面是链表的节点的结构

/*结点中不需要数据成元,只要求前驱和后继结点指针*/
struct list_elem {
   struct list_elem* prev; // 前躯结点
   struct list_elem* next; // 后继结点
};

乍一看,总感觉怪怪的,怪就对了:节点中没有放数据

没有数据的链表有什么用呢?这些节点串起来一点用也没有啊?

2. 数据节点

常规链表中,把数据放在链表节点里面。Linux中,把链表节点放到数据里面。

直接上代码演示吧,如下是一个学生节点:

struct student {
	int id;
	char name[30];
	struct list_elem tag;
};

看到这里,你应该大概懂了,数据节点怎样组成链表了,基本上如下图所示:

我们可以知道,这样的链表有一下几个特性:

  • 链表节点 (list_elem结构体) 作为数据节点 (student结构体) 的成员
  • 数据节点(student结构体)之间,是通过它的成员tag,来串起来的
  • 每个链表节点,只指向下一个链表节点

这个时候问题来了,数据节点是串起来了,但是怎么访问呢?

一般我们会遍历链表,可是最终我们需要的是数据啊,这样的链表只能访问到student节点的成员tag啊,如何访问到student节点本身呢?

现在的问题是如何通过结构的成员访问到结构体本身

3. 通过结构体成员访问结构体自身

这就提现了C语言的强大之处了,C语言可以直接操作内存(当然是虚拟内存),所以,只要计算出链表节点(struct list_elem tag)在整个节点(struct student)的地址偏移量即可

那么怎么应该计算呢?计算偏移量似乎也要一个特定的结构体才行啊?不同的结构体(数据节点)计算偏移量过程并不通用啊?

3.1 计算结构体成员的偏移量

这个时候,就充分体现出C语言中的的厉害之处了!

/*
	Desciprtion:
		offset计算某个结构体的成员到该结构体起始地址的偏移量
	Parameters:
		struct_type: 结构体的类型
		member: 结构体成员
	Return: 
		结构体成员到该结构体的偏移量
	使用方法:
		例如有一个struct student结构体,有个成员为tag,计算tag到student的偏移量:offset(struct student, tag)
*/
#define offset(struct_type, member) (int)(&((struct_type*)0)->member)

上面就是使用C语言的宏来实现的计算偏移量,例如这里要计算student结构体中tag成员到结构体本身的偏移量:

int offset = offset(struct student, tag);

几点说明:

  • (struct_type*)0
    • 这里把0地址起始的内容强行转化成一个struct_type的结构体,很巧妙。
    • 0地址处的数据本来不是struct_type类型的,但是我们需要一个struct_type类型的结构体,所以我们把0地址处当成一个结构体,借用一下,然后计算成员地址的偏移量。并没有改变0地址处的内容。
    • 所以直接强行转成struct_type类型的结构体,至于内容如何我们并不关心,我们只关心地址。
  • (struct_type*)0->member
  • 这里巧妙地使用了宏的特性,用到宏的地方会原封不动地替换
    • 比如调用时offset(struct student, tag),在宏的内部,会直接替换成(struct student*) 0 -> tag
  • (int)(&((struct_type*)0)->member)
    • 这个部分有个大坑
    • 这里把地址,强转成int类型变量,就要注意:
      • int类型占用4个字节的(32位)
      • 如果把代码放在64位的机器上跑(我这里是说这里的代码作为普通的应用程序,不是作为内核代码),地址就是64位
      • 那么强转成int类型会截断,那么到时候再恢复成地址时,就会访问错误内存。
    • 所以,如果你的程序是在64位的操作系统中跑,就要把int改为long或者该为uint64_t
3.2 得到结构体本身的地址

计算出了结构体成员的地址偏移量,然后就可以通过结构体成员来访问到结构体自身啦。

/*
	Description: 
		给出某个结构体的类型、成员,以及需要计算的目标结构体成员地址,得到目标结构体的自身地址
	Parameters:
		struct_type: 结构体类型,比如struct student
		struct_menber: 结构体成员名称(这里是变量的名称)
		elem_ptr: 目标结构体成员 地址
	使用方法:
		比如已经得到结构体student1的成员tag的地址tag1_ptr了,那么需要计算student1结构体的地址:
			struct student* s = elem2entry(struct student, tag, tag1_ptr);
*/
#define elem2entry(struct_type, struct_member_name, elem_ptr) \
	 (struct_type*)((int)elem_ptr - offset(struct_type, struct_member_name))

比如,要计算student1结构体中tag成员的地址tag1_ptr了,计算student1结构体的起始地址:

struct list_elem* tag1_ptr = .....;// 得到了结构体成员tag的地址
struct student* target_student = elem2entry(struct student, tag, tag1_ptr);

简单说明:

  • 根据传进去的结构体成员tag的地址tag1_ptr,然后减去struct student类型的结构体中的成员地址偏移量,就可以算出来tag1_ptr所指向的的结构体成员结构体起始地址f了。
  • 所以根据成员的地址tag1_ptr的值,然后减去偏移量offset,就可以得到结构体的起始地址了。

4. 组成链表

解决了如何根据结构体成员取出结构体,那么剩下的问题就非常容易了。

形成链表,就是把所有的链表节点串起来即可。由于链表节点是通用的(是包含在数据节点中),所以对链表的操作,也都是通用的。

这里说一下,我这里使用的是有头和尾节点的双向链表,也就是结构如下所示:

主要就是对链表增删改查了:

#define offset(struct_type,member) (int)(&((struct_type*)0)->member)
#define elem2entry(struct_type, struct_member_name, elem_ptr) \
	 (struct_type*)((int)elem_ptr - offset(struct_type, struct_member_name))

/**********   定义链表结点成员结构   ***********
*结点中不需要数据成元,只要求前驱和后继结点指针*/
struct list_elem {
   struct list_elem* prev; // 前躯结点
   struct list_elem* next; // 后继结点
};

/* 链表结构,用来实现队列 */
struct list {
/* head是队首,是固定不变的,不是第1个元素,第1个元素为head.next */
   struct list_elem head;
/* tail是队尾,同样是固定不变的 */
   struct list_elem tail;
};
/* 初始化双向链表list */
void list_init (struct list* list) {
   list->head.prev = NULL;
   list->head.next = &list->tail;
   list->tail.prev = &list->head;
   list->tail.next = NULL;
}

/* 把链表元素elem插入在元素before之前 */
void list_insert_before(struct list_elem* before, struct list_elem* elem) { 
/* 将before前驱元素的后继元素更新为elem, 暂时使before脱离链表*/ 
   before->prev->next = elem; 

/* 更新elem自己的前驱结点为before的前驱,
 * 更新elem自己的后继结点为before, 于是before又回到链表 */
   elem->prev = before->prev;
   elem->next = before;

/* 更新before的前驱结点为elem */
   before->prev = elem;
}

/* 添加元素到列表队首,类似栈push操作 */
void list_push(struct list* plist, struct list_elem* elem) {
   list_insert_before(plist->head.next, elem); // 在队头插入elem
}

/* 追加元素到链表队尾,类似队列的先进先出操作 */
void list_append(struct list* plist, struct list_elem* elem) {
   list_insert_before(&plist->tail, elem);     // 在队尾的前面插入
}

/* 使元素pelem脱离链表 */
void list_remove(struct list_elem* pelem) {
   pelem->prev->next = pelem->next;
   pelem->next->prev = pelem->prev;
}

/* 将链表第一个元素弹出并返回,类似栈的pop操作 */
struct list_elem* list_pop(struct list* plist) {
   struct list_elem* elem = plist->head.next;
   list_remove(elem);
   return elem;
} 

/* 从链表中查找元素obj_elem,成功时返回true,失败时返回false */
bool elem_find(struct list* plist, struct list_elem* obj_elem) {
   struct list_elem* elem = plist->head.next;
   while (elem != &plist->tail) {
      if (elem == obj_elem) {
	 return true;
      }
      elem = elem->next;
   }
   return false;
}

/* 把列表plist中的每个元素elem和arg传给回调函数func,
 * arg给func用来判断elem是否符合条件.
 * 本函数的功能是遍历列表内所有元素,逐个判断是否有符合条件的元素。
 * 找到符合条件的元素返回元素指针,否则返回NULL. */
struct list_elem* list_traversal(struct list* plist, function func, int arg) {
   struct list_elem* elem = plist->head.next;
/* 如果队列为空,就必然没有符合条件的结点,故直接返回NULL */
   if (list_empty(plist)) { 
      return NULL;
   }

   while (elem != &plist->tail) {
      if (func(elem, arg)) {		  // func返回ture则认为该元素在回调函数中符合条件,命中,故停止继续遍历
	 return elem;
      }					  // 若回调函数func返回true,则继续遍历
      elem = elem->next;	       
   }
   return NULL;
}

/* 返回链表长度 */
uint32_t list_len(struct list* plist) {
   struct list_elem* elem = plist->head.next;
   uint32_t length = 0;
   while (elem != &plist->tail) {
      length++; 
      elem = elem->next;
   }
   return length;
}

/* 判断链表是否为空,空时返回true,否则返回false */
bool list_empty(struct list* plist) {		// 判断队列是否为空
   return (plist->head.next == &plist->tail ? true : false);
}
这篇关于Linux系统中链表的骚操作的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!