O Kernel do Linux utiliza extensivamente uma estrutura de lista circular duplamente ligada definida em include/linux/list.h. A elegância desta implementação reside no fato de que, em vez de a lista conter os dados, a estrutura da lista é incorporada dentro dos objetos de dados. Isso permite uma manipulação genérica e eficiente de qualquer tipo de estrutura.

Para compreender o funcionamento interno, podemos extrair e simplificar a lógica central dessas macros e funções para uso em aplicações de espaço de usuário.

Definições Fundamentais

Abaixo, definimos a estrutura base e as macros de inicialização e manipulação de memória necessárias para navegar entre os ponteiros da lista e as estruturas que os contêm.

#include <stdio.h>
#include <stddef.h>

// Estrutura base da lista
struct list_node {
    struct list_node *next, *prev;
};

// Macro para inicialização estática
#define LIST_INIT_VAL(name) { &(name), &(name) }

// Inicialização em tempo de execução
static inline void list_init(struct list_node *ptr) {
    ptr->next = ptr;
    ptr->prev = ptr;
}

// Inserção genérica entre dois nós conhecidos
static inline void __list_insert(struct list_node *new_node,
                                struct list_node *before,
                                struct list_node *after) {
    after->prev = new_node;
    new_node->next = after;
    new_node->prev = before;
    before->next = new_node;
}

// Adiciona um novo elemento ao final da lista
static inline void list_push_back(struct list_node *new_node, struct list_node *head) {
    __list_insert(new_node, head->prev, head);
}

// Verifica se a lista está vazia
static inline int list_is_empty(const struct list_node *head) {
    return head->next == head;
}

Macros de Acesso e Iteração

O ponto crucial da implementação é a macro container_of (aqui renomeada para get_container), que calcula o endereço inicial de uma esrtutura a partir do endereço de um de seus membros.

#define get_container(ptr, type, member) ({                      \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);         \
    (type *)( (char *)__mptr - offsetof(type, member) );})

#define list_get_entry(ptr, type, member) \
    get_container(ptr, type, member)

// Iteração segura sobre os elementos da lista
#define list_for_each_entry(pos, head, member)                          \
    for (pos = list_get_entry((head)->next, typeof(*pos), member);      \
         &pos->member != (head);                                        \
         pos = list_get_entry(pos->member.next, typeof(*pos), member))

Exemplo Prático: Gerenciamento de Dispositivos

Para testar a lógica, simulamos uma lista de dispositivos de hardware. Cada dispositivo possui um nome e uma instância da nossa estrutura de lista.

struct device_entry {
    struct list_node node;
    const char *id;
};

int main(void) {
    // Cabeçalho da lista principal
    struct list_node registry_head = LIST_INIT_VAL(registry_head);
    
    // Verificação inicial
    if (list_is_empty(&registry_head)) {
        printf("Registro de dispositivos vazio.\n");
    }

    // Criando instâncias de teste
    struct device_entry d1 = { .id = "Sensor_A1" };
    struct device_entry d2 = { .id = "Sensor_B2" };
    struct device_entry d3 = { .id = "Atuador_X9" };

    // Inserindo na lista
    list_push_back(&d1.node, &registry_head);
    list_push_back(&d2.node, &registry_head);
    list_push_back(&d3.node, &registry_head);

    if (!list_is_empty(&registry_head)) {
        printf("Dispositivos registrados com sucesso.\n");
    }

    // Iterando e exibindo os nomes
    struct device_entry *cursor;
    printf("Lista de Dispositivos:\n");
    list_for_each_entry(cursor, &registry_head, node) {
        printf(" - ID: %s\n", cursor->id);
    }

    return 0;
}

Ao executar o código acima, a saída demonstrará a correta vinculação dos nós e a capacidade de recupearr a estrutura pai (device_entry) a partir do ponteiro do nó da lista (list_node). Este padrão evita alocações extras para metadados da lista e garante localidade de referência superior em sistemas de alto desempenho.