9实现操作系统里面的链表结构

为了方便后面进程切换之类的,需要就绪队列,阻塞队列等所以需要链表数据结构

//D:\code\x86\code\start\start\source\kernel\include\tools\list.h
#ifndef LIST_H
#define LIST_H

// 已知结构体中的某个字段的指针，求所在结构体的指针
// 例如：
// struct aa{
//  .....
//  int node;
//  .....
// };
// struct aa a;
// 1.求结点在所在结构中的偏移:定义一个指向0的指针，用(struct aa *)&0->node，所得即为node字段在整个结构体的偏移
#define offset_in_parent(parent_type, node_name)    \
    ((uint32_t)&(((parent_type*)0)->node_name))

// 2.求node所在的结构体首址：node的地址 - node的偏移
// 即已知a->node的地址，求a的地址
#define offset_to_parent(node, parent_type, node_name)   \
    ((uint32_t)node - offset_in_parent(parent_type, node_name))

// 3. 进行转换: (struct aa *)addr
// list_node_parent(node_addr, struct aa, node_name)
#define list_node_parent(node, parent_type, node_name)   \
        ((parent_type *)(node ? offset_to_parent((node), parent_type, node_name) : 0)) 



/**
 * 链表结点类型
 */
typedef struct _list_node_t {
    struct _list_node_t* pre;           // 链表的前一结点
    struct _list_node_t* next;         // 后继结点
}list_node_t;

/**
 * 头结点的初始化
 * @param node 待初始化的结果
 */
static inline void list_node_init(list_node_t *node) {
    node->pre = node->next = (list_node_t *)0;
}

/**
 * 获取结点的前一结点
 * @param node 查询的结点
 * @return 后继结点
 */
static inline list_node_t * list_node_pre(list_node_t *node) {
    return node->pre;
}

/**
 * 获取结点的前一结点
 * @param node 查询的结点
 * @return 后继结点
 */
static inline list_node_t * list_node_next(list_node_t *node) {
    return node->next;
}

/**
 * 带头结点和尾结点的单链表
 * 每个结点只需要一个指针，用于减少内存使用量
 */
typedef struct _list_t {
    list_node_t * first;            // 头结点
    list_node_t * last;             // 尾结点
    int count;                        // 结点数量
}list_t;

void list_init(list_t *list);

/**
 * 判断链表是否为空
 * @param list 判断的链表
 * @return 1 - 空，0 - 非空
 */
static inline int list_is_empty(list_t *list) {
    return list->count == 0;
}

/**
 * 获取链表的结点数量
 * @param list 查询的链表
 * @return 结果的数据
 */
static inline int list_count(list_t *list) {
    return list->count;
}

/**
 * 获取指定链表的第一个表项
 * @param list 查询的链表
 * @return 第一个表项
 */
static inline list_node_t* list_first(list_t *list) {
    return list->first;
}

/**
 * 获取指定链接的最后一个表项
 * @param list 查询的链表
 * @return 最后一个表项
 */
static inline list_node_t* list_last(list_t *list) {
    return list->last;
}

void list_insert_first(list_t *list, list_node_t *node);
void list_insert_last(list_t *list, list_node_t *node);

list_node_t* list_remove_first(list_t *list);
list_node_t* list_remove(list_t *list, list_node_t *node);

#endif /* LIST_H */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

//D:\code\x86\code\start\start\source\kernel\init\init.c
#include "tools/list.h"

/**
 * 初始化链表
 * @param list 待初始化的链表
 */
void list_init(list_t *list) {
    list->first = list->last = (list_node_t *)0;
    list->count = 0;
}


/**
 * 将指定表项插入到指定链表的头部
 * @param list 待插入的链表
 * @param node 待插入的结点
 */
void list_insert_first(list_t *list, list_node_t *node) {
    // 设置好待插入结点的前后，前面为空
    node->next = list->first;
    node->pre = (list_node_t *)0;

    // 如果为空，需要同时设置first和last指向自己
    if (list_is_empty(list)) {
        list->last = list->first = node;
    } else {
        // 否则，设置好原本第一个结点的pre
        list->first->pre = node;

        // 调整first指向
        list->first = node;
    }

    list->count++;
}


/**
 * 将指定表项插入到指定链表的尾部
 * @param list 操作的链表
 * @param node 待插入的结点
 */
void list_insert_last(list_t *list, list_node_t *node) {
    // 设置好结点本身
    node->pre = list->last;
    node->next = (list_node_t*)0; //头节点本来为0

    // 表空，则first/last都指向唯一的node
    if (list_is_empty(list)) {
        list->first = list->last = node;
    } else {
        // 否则，调整last结点的向一指向为node
        list->last->next = node;

        // node变成了新的后继结点
        list->last = node;
    }

    list->count++;
}

/**
 * 移除指定链表的头部
 * @param list 操作的链表
 * @return 链表的第一个结点
 */
list_node_t* list_remove_first(list_t *list) {
    // 表项为空，返回空
    if (list_is_empty(list)) {
        return (list_node_t*)0;
    }

    // 取第一个结点
    list_node_t * remove_node = list->first;

    // 将first往表尾移1个，跳过刚才移过的那个，如果没有后继，则first=0
    list->first = remove_node->next;
    if (list->first == (list_node_t *)0) {
        // node为最后一个结点
        list->last = (list_node_t*)0;
    } else {
        // 非最后一结点，将后继的前驱清0
        remove_node->next->pre = (list_node_t *)0;
    }

    // 调整node自己，置0，因为没有后继结点
    remove_node->next = remove_node->pre = (list_node_t*)0;

    // 同时调整计数值
    list->count--;
    return remove_node;
}

/**
 * 移除指定链表的中的表项
 * 不检查node是否在结点中
 */
list_node_t * list_remove(list_t *list, list_node_t *remove_node) {
    // 如果是头，头往前移
    if (remove_node == list->first) {
        list->first = remove_node->next;
    }

    // 如果是尾，则尾往回移
    if (remove_node == list->last) {
        list->last = remove_node->pre;
    }

    // 如果有前，则调整前的后继
    if (remove_node->pre) {
        remove_node->pre->next = remove_node->next;
    }

    // 如果有后，则调整后往前的
    if (remove_node->next) {
        remove_node->next->pre = remove_node->pre;
    }

    // 清空node指向
    remove_node->pre = remove_node->next = (list_node_t*)0;
    --list->count;
    return remove_node;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

这里面有个难点,就是说链表挂载的是一个个进程,通过链表数据结构的管理我们知道链表的地址,但是我们不知道这个进程完整结构体的地址,但是我们切换任务时候需要,所以这里要巧妙设计一下

我知道node的地址,怎么知道结构体的完整地址

这个offset不用自己计算(自己可以计算)

但是,我们使用队列的地方肯定不止进程管理这块,后面外设管理都需要,所以计算偏移计算地址这块我们要写成宏代码

#define offset_in_parent(parent_type, node_name)    \
    ((uint32_t)&(((parent_type*)0)->node_name))

// 2.求node所在的结构体首址：node的地址 - node的偏移
// 即已知a->node的地址，求a的地址
#define offset_to_parent(node, parent_type, node_name)   \
    ((uint32_t)node - offset_in_parent(parent_type, node_name))

// 3. 进行转换: (struct aa *)addr
// list_node_parent(node_addr, struct aa, node_name)
#define list_node_parent(node, parent_type, node_name)   \
        ((parent_type *)(node ? offset_to_parent((node), parent_type, node_name) : 0))  //对地址强制类型转换
1
2
3
4
5
6
7
8
9
10
11
12

C语言小知识点

**今天遇到一个强制类型转换的问题：**一个是对值进行强制类型转换，一个是对值的地址进行强制类型进行转换后再次读取。得到的结果当然不相同。对变量的值进行强制类型转换，是把值按照另外一种类型进行存储后读取，变量在内存中的存储形式发生变化；而对变量的地址进行强制类型转换，是变量在内存中的存储形式未发生变化，而在变量读取时读取的方式发生变化。

c语言疑惑

C语言读取指定地址的内容，或将值写入到指定地址

咱就是说能不能将那个(int*)去掉,调试结果是不行的,埋个坑后面学完c语言指针进阶就来填坑,从底层分析原因