List.h: Liste chaînée dans le kernel

List.h: Liste chaînée dans le kernel

Temps de lecture : 3 minutes

Pour de nombreuses opérations, le noyau à besoin d’une structure de données de liste chaînée. Ceci est une implémentation d’une liste chaînée qui réimplémente la liste pour chaque nouveau type pour lequel vous avez besoin  d’une liste chaînée.

Voici le code source de 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

#ifndef LIST_H
#define LIST_H

#define DEFINE_LIST(nodeType) \
typedef struct nodeType##list { \
    struct nodeType * head; \
    struct nodeType * tail; \
    uint32_t size;\
} nodeType##_list_t;

#define DEFINE_LINK(nodeType) \
struct nodeType * next##nodeType;\
struct nodeType * prev##nodeType;

#define INITIALIZE_LIST(list) \
    list.head = list.tail = (void *)0;\
    list.size = 0;

#define IMPLEMENT_LIST(nodeType) \
void append_##nodeType##_list(nodeType##_list_t * list, struct nodeType * node) {  \
    list->tail->next##nodeType = node;                                       \
    node->prev##nodeType = list->tail;                                       \
    list->tail = node;                                                       \
    node->next##nodeType = NULL;                                             \
    list->size += 1;                                                         \
}                                                                            \
                                                                             \
void push_##nodeType##_list(nodeType##_list_t * list, struct nodeType * node) {    \
    node->next##nodeType = list->head;                                       \
    node->prev##nodeType = NULL;                                             \
    list->head = node;                                                       \
    list->size += 1;                                                         \
}                                                                            \
                                                                             \
struct nodeType * peek_##nodeType##_list(nodeType##_list_t * list) {         \
    return list->head;                                                       \
}                                                                            \
                                                                             \
struct nodeType * pop_##nodeType##_list(nodeType##_list_t * list) {          \
    struct nodeType * res = list->head;                                      \
    list->head = list->head->next##nodeType;                                 \
    list->head->prev##nodeType = NULL;                                                 \
    list->size -= 1;                                                         \
    return res;                                                              \
}                                                                            \
                                                                             \
uint32_t size_##nodeType##_list(nodeType##_list_t * list) {                  \
    return list->size;                                                       \
}                                                                            \
                                                                             \
struct nodeType * next_##nodeType##_list(struct nodeType * node) {           \
    return node->next##nodeType;                                             \
}                                                                            \

#endif

Utilisation

Si nous voulons une liste chaînée d’un certain type, vous devriez écrire DEFINE_LINK(typename) . Ensuite, après que le type est défini, vous devriez mettre DEFINE_LIST(typename);IMPLEMENT_LIST(typename) . Cela générera un type de liste liée et des fonctions pour ce type.

Le type sera appelé typename _list_t . Ils doivent être créés en tant que variables globales et initialisés avant utilisation avec INITIALIZE_LIST(instance)

Une fois cela fait, vous pouvez utiliser les fonctions. Ils sont tous nommés sous la forme action_typename_list , donc si vous voulez utiliser la liste comme une queue, vous pouvez utiliser append_typename_list  et pop_typename_list

Exemple

Supposons que vous ayez le type suivant et que vous souhaitez le stocker dans une liste chainée:

1
2
3
4

typedef struct point {
    int x;
    int y;
} point_t;

Vous deviez donc déclarer la liste comme suit:

1
2
3
4
5
6
7
8

typedef struct point {
    int x;
    int y;
    DEFINE_LINK(point);
} point_t;

DEFINE_LIST(point);
IMPLEMENT_LIST(point);

Ceci définit une liste chaînée qui ne peut contenir struct point et implémente les fonctions de la liste chaînée. Alors la liste chaînée peut être utilisée comme ceci:

1
2
3
4
5
6

point_list_t points;

void do_something(point_t * point) {
    INITIALIZE_LIST(points);
    append_point_list(&points, point);
}
comments powered by Disqus

Articles Similaires

Ubuntu 24.04 LTS - Une version qui fait débat entre déception et enthousiasme

Ubuntu 24.04 LTS - Une version qui fait débat entre déception et enthousiasme

Ubuntu 24.04 LTS, “Noble Numbat”, a récemment été déployée, apportant son lot de nouveautés et de changements. Cette version suscite à la fois de l’enthousiasme et de la déception au sein de la communauté des utilisateurs et des développeurs.

Lire la Suite
Le concours de beauté Miss AI : un cauchemar dystopique ou le futur de la beauté ?

Le concours de beauté Miss AI : un cauchemar dystopique ou le futur de la beauté ?

Dans un monde où la technologie et la beauté fusionnent, le concours de beauté Miss AI fait son apparition. Ce concours, organisé par The World AI Creator Awards, récompense les créateurs d’images et d’influenceurs générés par intelligence artificielle (IA).

Lire la Suite
Le gouvernement du Salvador prend un coup dur : les hackers divulguent le code source et les accès VPN du portefeuille bitcoin national Chivo !

Le gouvernement du Salvador prend un coup dur : les hackers divulguent le code source et les accès VPN du portefeuille bitcoin national Chivo !

Le programme bitcoin du gouvernement du Salvador, Chivo , a été victime d’une série d’attaques informatiques ces derniers jours. Les hackers ont déjà divulgué les données personnelles de plus de 5 millions de Salvadoriens.

Lire la Suite