Linux-data-structure

January 29, 2024 2171

Linux数据结构

本文主要介绍最近写代码中用到的一些Linux内置的数据结构宏，在未来写项目中做一些记录。

双向链表TAILQ

头文件：#include <sys/queue.h>

结构体定义：

1
TAILQ_HEAD(name, type) type_name;

这里name是新的链表组成结构体名，type是链表里每个元素的类型，可以认为type_name就是一个新的类名。

在结构体type中，需要添加ENTRY用于串联：

1
2
3
struct type {
    TAILQ_ENTRY(type) link;
};

link名字可以随便起。

链表初始化：TAILQ_INIT(&lists)

链表插入头部：TAILQ_INSERT_HEAD(&lists, var, link)

链表插入尾部：TAILQ_INSERT_TAIL(&lists, var, link)

安全遍历链表（支持删除）：TAILQ_FOREACH_SAFE(var, &lists, link, var_tmp)

安全删除元素：TAILQ_REMOVE(&lists, var, link)

获取链表头部元素：TAILQ_FIRST(&lists)

一个栗子

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
#include <sys/queue.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

struct spdk_blob {
    TAILQ_ENTRY(spdk_blob) link;
    uint32_t blob_id;
};

TAILQ_HEAD(blob_lists, spdk_blob) blobs;
struct blob_lists* lists;
int main() {
    lists = (struct blob_lists*)malloc(sizeof(struct blob_lists));
    TAILQ_INIT(lists);

    struct spdk_blob* blob1, * blob2, * blob3;
    blob1 = (struct spdk_blob*)malloc(sizeof(struct spdk_blob));
    blob2 = (struct spdk_blob*)malloc(sizeof(struct spdk_blob));
    blob3 = (struct spdk_blob*)malloc(sizeof(struct spdk_blob));
    blob1->blob_id = 0x789;
    blob2->blob_id = 0x8910;
    blob3->blob_id = 0x1;

    TAILQ_INSERT_HEAD(lists, blob1, link);
    TAILQ_INSERT_TAIL(lists, blob3, link);
    TAILQ_INSERT_TAIL(lists, blob2, link);

    struct spdk_blob* blob, * blob_tmp;
    printf("Before remove:\n");
    /* 1 3 2 */
    TAILQ_FOREACH_SAFE(blob, lists, link, blob_tmp) {
        printf("blob_id = 0x%x\n", blob->blob_id);
    }

    TAILQ_REMOVE(lists, blob3, link);
    free(blob3);
    printf("After remove:\n");

    /* 1 2 */
    TAILQ_FOREACH_SAFE(blob, lists, link, blob_tmp) {
        printf("blob_id = 0x%x\n", blob->blob_id);
    }

    blob = TAILQ_FIRST(lists);
    printf("First blob_id = 0x%x\n", blob->blob_id);

    TAILQ_FOREACH_SAFE(blob, lists, link, blob_tmp) {
        TAILQ_REMOVE(lists, blob, link);
    }

    free(lists);
    return 0;
}