Thay vì thiết kế danh sách liên kết gắn liền với dữ liệu cụ thể, nhân Linux sử dụng mô hình danh sách liên kết thuần túy — một cấu trúc chỉ chứa hai con trỏ next và prev, hoàn toàn tách biệt khỏi dữ liệu người dùng. Cách tiếp cận này đảm bảo tính linh hoạt và tái sử dụng cao.

Cấu trúc cơ sở

struct list_node {
    struct list_node *next;
    struct list_node *prev;
};

Mọi thao tác như chèn, xóa, duyệt đều được thực hiện trên các nút list_node, không phụ thuộc vào kiểu dữ liệu lưu trữ.

Truy xuất dữ liệu thông qua offset

Do nút danh sách không chứa dữ liệu, cần cơ chế để lấy địa chỉ của cấu trúc chứa nó. Đây là nơi macro container_of phát huy tác dụng:

#define OFFSET_OF(type, field) ((size_t)(&((type*)0)->field))

#define CONTAINER_OF(ptr, type, field) \
    ((type*)((char*)(ptr) - OFFSET_OF(type, field)))

Macro này tính toán địa chỉ bắt đầu của cấu trúc cha bằng cách lấy địa chỉ của trường field trong nút danh sách rồi trừ đi độ lệch (offset) của trường đó trong cấu trúc.

Ví dụ minh họa: Quản lý hồ sơ nhân viên

Giả sử ta xây dựng hệ thống quản lý nhân sự với cấu trúc sau:

struct employee {
    char full_name[64];
    unsigned int id;
    float salary;
    struct list_node node;  // thành phần danh sách
};

Khi thêm mới nhân viên, ta chỉ chèn node vào danh sách, không thao tác trực tiếp với toàn bộ struct employee.

Triển khai các hàm thao tác cốt lõi

static inline void init_list(struct list_node *head) {
    head->next = head;
    head->prev = head;
}

static inline void insert_after(struct list_node *new_node,
                                struct list_node *prev_node,
                                struct list_node *next_node) {
    next_node->prev = new_node;
    new_node->next = next_node;
    new_node->prev = prev_node;
    prev_node->next = new_node;
}

static inline void append_to_list(struct list_node *new_node, struct list_node *head) {
    insert_after(new_node, head->prev, head);
}

static inline void remove_node(struct list_node *node) {
    node->next->prev = node->prev;
    node->prev->next = node->next;
    node->next = node;
    node->prev = node;
}

Duyệt an toàn với khả năng xóa động

Để tránh lỗi khi xóa phần tử trong lúc duyệt, sử dụng biến tạm lưu vị trí kế tiếp:

#define FOR_EACH_SAFE(pos, next, head, field) \
    for (pos = CONTAINER_OF((head)->next, typeof(*pos), field), \
         next = CONTAINER_OF(pos->field.next, typeof(*pos), field); \
         &pos->field != (head); \
         pos = next, \
         next = CONTAINER_OF(next->field.next, typeof(*pos), field))

Chương trình kiểm thử đầy đủ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Khai báo lại các macro và hàm đã định nghĩa ở trên

struct employee {
    char full_name[64];
    unsigned int id;
    float salary;
    struct list_node node;
};

int main() {
    struct list_node roster = {&roster, &roster};
    struct employee *staff;

    // Thêm 3 nhân viên
    for (int i = 0; i < 3; ++i) {
        staff = malloc(sizeof(*staff));
        snprintf(staff->full_name, sizeof(staff->full_name), "NV%03d", i + 1);
        staff->id = 1000 + i;
        staff->salary = 75000.0f + i * 5000.0f;
        init_list(&staff->node);
        append_to_list(&staff->node, &roster);
    }

    // In danh sách
    struct employee *curr;
    struct employee *tmp;
    FOR_EACH_SAFE(curr, tmp, &roster, node) {
        printf("Tên: %-8s | ID: %u | Lương: %.2f\n",
               curr->full_name, curr->id, curr->salary);
    }

    // Dọn dẹp bộ nhớ
    FOR_EACH_SAFE(curr, tmp, &roster, node) {
        remove_node(&curr->node);
        free(curr);
    }

    return 0;
}