Lista encadeada genérica com macros avançadas

Lista encadeada genérica

Tem tanto código que a gente escreve para um projeto, e depois reescreve para outro, e então escreve mais uma vez. Porque vai sempre existir aquele código que é difícil de abstrair e conter em um módulo reutilizável em C, por exemplo listas encadeadas. Nesse artigo vou construir uma lista encadeada genérica, passo a passo, até a formatação de macros complexas.

Neste artigo você pode aprender os básicos sobre lista encadeada genérica, casos de uso e alguns hacks para criar macros avançadas. No final tem uma maneira simples, porém não reutilizável, que evita o uso de macros e oferece redução de código repetido.

Para quem não sabe, uma lista encadeada é um estrutura de dados capaz de apontar para o próximo elemento, formando uma lista.

ll2

Nós organizamos dados em listas porque precisamos navegá-los para posterior uso, simples assim, mas isso Arrays, Stacks, FIFOs, etc. também fazem. Onde a lista encadeada se difere é que você utiliza ponteiros para formar a lista, então não necessita de cópia nem mover elementos para inserir ou remover da lista. Por isso listas encadeadas são bem utilizadas em situações onde não há previsibilidade de inserção e remoção, onde vai inserir ou remover do meio da lista, também em situações onde é importante fazer ordenamento de elementos sem cópia, ou quando você precisa atravessar uma estrutura de dados existente por um caminho específico.

O jeito não genérico de implementar uma lista encadeada

Listas encadeadas, em C, são implementadas com structs contendo um campo ou sub campo apontando para a própria struct, geralmente o chamando next , como o snippet mostra:

Para formar uma lista de struct my_data, basta inicializar os campos next conforme ilustrado, note que é preciso tomar certo cuidado com a manipulação do next .

ps: Nos snippets deste artigo eu vou utilizar essas funções inventadas para fins semânticos, como create_my_data_element , get_list_root e get_a_element .

No snippet, foi inserido um elemento após element1 mantendo a lista após element2 caso exista, através da atribuição dos campos de todos os elementos envolvidos.

Para navegar na lista basta acessar o next  de cada elemento ao longo da lista:

E, por fim, para remover um elemento da lista não é tão trivial, porque você precisa reconfigurar o anterior:

Uma lista pode ser, também, duplamente encadeada, para que se possa navegar inversamente, então um novo campo, provavelmente chamado de previous, será inserido, e junto aumenta a complexidade de código e a quantidade de repetição.

Listas encadeadas são muito versáteis e podem ser consideradas simples de implementar, entretanto eu já me flagrei, e também observei outros desenvolvedores, tendo dificuldade de implementá-las, geralmente injetando bugs no produto por conta do uso das listas encadeadas. Eu não sou psicólogo, mas acredito que exista algo no raciocínio humano que nos torna imprecisos para essas tarefas repetitivas, é por isso que vejo nessas listas uma oportunidade de criar um módulo reutilizável.

A interface desejada

Antes de construir o módulo reutilizável, gostaria definir a interface ideal de como uma lista encadeada genérica deve ser utilizada, no snippet a seguir eu coloco os mesmos exemplos dos snippets anteriores, só que agora utilizando uma interface idealizada.

Foram criadas três funções na interface ideal, linked_list_insert_after , linked_list_next  e linked_list_remove_from. E agora mostro como implementá-las.

Implementando as três funções

Implementar essas três funções de forma reutilizável e segura é bastante complicado. Só é possível de fazer com Macros complexas, começamos com linked_list_next.

A seguir a macro para inserção, que usa o hack do while (0)  para criar uma macro de múltiplas expressões, e as extensões GNU para utilizar o typeof para evitar dupla expansão de argumentos:

Dois hacks já foram utilizados, e agora mais um será necessário para implementar linked_list_remove , pois a macro precisa retornar, o que vai exigir o uso de statement expressions ou o bloco entre parênteses.

E, pronto, agora esta é uma Macro complexa. Se a lista for duplamente encadeada, ainda mais complexo será.

As macro sugeridas são seguras porque:

  • toda a checagem de tipo do C é mantido (sem ponteiros para void);
  • se tipos incompatíveis forem utilizados, as atribuições falharão a compilação, assim a ausência do campo next, e;
  • os parâmetros das macros são expandidos apenas uma vez pelo pré processador.

Ela é genérica porque qualquer tipo que possua o campo next poderá ser utilizado.

Eu tenho uma implementação completa de lista encadeada genérica reutilizável, que levou alguns dias na confecção, mas valeu a pena porque utilizo em quase todos os meus projetos. Foi um exercício muito interessante e recomendo que vocês também o façam.

Por fins de referência, vejam as implementações de lista encadeada abaixo:

  • list.h, do kernel do Linux, que é a mais legível e completa que conheço, faz uso do container_of para retornar o tipo do usuário nas macros. Também utiliza funções static inline auxiliares e fornece maneiras de navegar nas listas a la for each. E o melhor, é q ela é muito barata, ela usa diversos hacks que a tornam muito eficiente, como se espera de código no Linux.
  • linked_list.h (linha 128 até 337), que é a minha e precisa de um sério refactor para melhorar a legibilidade e desempenho na navegação inversa.

Observação

Uma alternativa a macros, é abrir mão da generalidade de tipo, e implementar funções específicas:

Essa implementação poderá ajudar bastante na redução de código repetido, mas ela não é reutilizável para tipos diferentes, só serve para struct my_data, recomendo o uso desta abordagem em casos que vocês não queiram utilizar macros complexas, e, se desempenho for um problema, declare-as como static inline.

Veja + conteúdo

Engenheiro, desenvolve software para embarcados e Linux, evangelista dos processos de qualidade.
Mais informações e redes sociais: http://flp.lv

Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Receba os melhores conteúdos sobre sistemas eletrônicos embarcados, dicas, tutoriais e promoções.

Comentários:
Notificações
Notificar
guest
0 Comentários
Inline Feedbacks
View all comments
Talvez você goste:

Séries

Menu