Lista ligada - Estrutura "Zero Copy" - Parte 1

Lista ligada

Olá caro leitor, nos meses passados falamos sobre algumas estruturas de dados que podem ser muito úteis quando estamos trabalhando no desenvolvimento do firmware de nosso projeto. Observamos que a partir do buffer circular, conseguimos derivar outras estruturas mais complexas e poderosas. Vamos hoje adicionar ao nosso grupo de ferramentas uma estrutura primitiva, mas muito popular que é a lista ligada, e que também podemos derivar filas, pilhas e até buffers com ela porém com a possibilidade de controlar o local de depósito dos dados.

 

 

Estrutura "Zero Copy"?

 

Antes de entrarmos nos detalhes da nossa lista ligada, primeiro vamos esclarecer o que esse termo significa. Quando falamos de buffer circular nos artigos anteriores, o usuário deve ter notado, que quem controla a forma de armazenar os dados é a própria estrutura. Imagine agora que cada slot não seja de um tipo primitivo, mas sim uma cadeia de bytes, então um processo completo de inserção e remoção terá pelo menos duas operações de cópia, sendo uma da origem dos dados para a memória interna da estrutura, e outra da estrutura para o destino, ou seja, onde os dados serão consumidos. Perceba que isso pode ser irrelevante para cadeias de bytes de pequeno tamanhos, mas que se torna um overhead considerável à medida que o tamanho do bloco a ser enviado cresce.

 

Para minimizar esse problema, podemos ter apenas memória em quem gera dados, e em vez de propagar os blocos de dados camada por camada, simplesmente podemos propagar a referência (endereço) onde encontram-se os dados a serem consumidos. Sabemos que endereços (ponteiros falando na perspectiva C/C++) são geralmente tipos de dados primitivos, onde o próprio set de instruções do processador consegue cuidar de mover seu valor de um local para outro na memória sem precisar de um processo de cópia (ex.: memcpy).

 

Partindo dessa abordagem podemos ter um sistema de cadeia de ponteiros, que "viajam" do processo (processo em sistemas embarcados podem também ser threads / tasks, visto que nem todo sistema embarcado possui um processador com gerenciamento de memória virtual, a popular MMU) produtor, e entrega ao IP de transmissão de dados o endereço de onde ele deve copiar os dados, reduzindo para apenas 1 operação de cópia. Se o campo de dados for então de um tipo primitivo, apenas uma de-referência simples (o operador *) permite acessar os dados de origem, essa é a estrutura de dados "Zero Copy".

 

 

Voltando às listas ligadas

 

Voltando ao assunto principal do post, o mecanismo de propagação de referências (Zero Copy) pode ser empregado nas estruturas aqui já apresentadas, porém por que peguei listas ligadas para ilustrar? Por dois bons motivos. O primeiro, apresentar a versatilidade das listas, quase qualquer estrutura de dados pode ser criada a partir dela. O segundo motivo, é que uma fila construída a partir de listas ligadas por exemplo, podem trabalhar para organizar não apenas filas de dados, mas também de processos, por exemplo ordenando por ordem de chegada (ou prioridade) o acesso a um recurso compartilhado do sistema em execução (UARTs, Sistema de arquivos, I/O em geral).

 

Agora, o que é uma lista ligada? Bom, já falamos de toda a burocracia que envolve esse artigo, logo responder a pergunta fica fácil, observem a figura abaixo:

 

Lista ligada

Imagine que você possui uma estrutura que possui um campo que contém dois ponteiros, sendo:

  • Um ponteiro chamado value ou data, que aponta para a localidade de onde seus dados estão armazenados (Opa, "Zero Copy" à vista!);
  • Um segundo ponteiro chamado next, que aponta pra justamente outra estrutura igualzinha corrente.

 

Com 2 ou mais teremos a chamada lista ligada simples, possui esse nome pois inicialmente as estruturas estão separadas e em diferentes pontos da memória. Porém, através da execução de uma operação geralmente chamada de link, elas criam o aspecto da figura acima, ou seja, não são contíguas em memória, mas podem saber uma da existência da outra, pois a função do ponteiro next é dizer onde encontra-se o próximo item da lista e assim sucessivamente até que o último ponteiro next possua valor nulo, geralmente indicando o fim da lista (são comuns implementações onde um valor de marca é utilizado para esse fim). Vejam como ela ficaria na memória do nosso processador:

 

Lista ligada na memória

Percebam que os itens estão em diversos pontos da memória. Esse tipo de lista é perfeito para implementação de filas que possuem diversos produtores de dados. A segunda vantagem é que sua dimensão  pode ser ajustada sob demanda, ou seja, em tempo de execução. Nas estruturas estáticas que demonstramos, o usuário tem que saber o quanto de memória vai alocar em tempo de compilação. No caso da lista ligada, um novo item da lista só será alocado para um uso, podendo ser liberado para outro fim, sendo indicado para uso com a Memory Pool que apresentamos aqui. Logo, se a aplicação possuir uso de memória de tamanho variável durante o tempo, apenas será necessário prover algum mecanismo de alocação de memória.

 

Gostei, quero utilizar, tem exemplo desse também?

 

Trouxemos um exemplo de lista ligada, com funções típicas de seu uso, ou seja, inserção, remoção pela posição, remoção do primeiro item, e do último, sendo esses dois últimos perfeitos para implementação de uma fila "Zero Copy". Além disso, o código exemplo traz o mecanismo de "encabeçamento" da lista, ou seja, a estrutura slist_info_t contém informações sobre a lista, bem como o ponteiro que aponta ao primeiro item. A figura abaixo mostra como isso ocorre:

 

Encabeçamento da lista ligada

Essa estrutura é usada como descritor da lista, ou seja, quando o usuário quiser várias listas diferentes terá que instanciar sempre a cabeça a qual ela pertence, e inserir e remover, sempre em relação à cabeça da lista. Para facilitar, foi provida uma macro para declarar a cabeça de uma lista, inicializada. Vamos dar uma olhada nos arquivos, primeiro a interface:

 

 

Na implementação alguns cuidados extras foram tomados. Diferentemente das estruturas estáticas, as listas ligadas não tão seguras a "wild pointers" e valores inválidos, por isso foram adicionadas checagem de parâmetros. Percebam a presença das rotinas link e unlink que fazem a lista "olhar" ou não para o próximo elemento (se houver).

 

 

 

 

Legal, mas por que lista ligada simples?

 

Bom, o fato é que uma lista ligada pode possuir infinitos ponteiros de ligação. Quando possui apenas um único ponteiro desse tipo, tendemos a chamar ele de lista simples, porém no próximo artigo falaremos sobre um tipo mais popular de lista ligada, a lista dupla, e como ela pode reduzir tempo de busca, inserção e remoção com um ponteiro extra.

 

 

Conclusão

 

Neste artigo executamos um pontapé inicial sobre estruturas que usam referências para armazenamento de dados e que não são contíguas em memória, demonstrando vantagem como flexibilidade e uso sob demanda. Nos próximos artigos vamos apresentar a lista dupla  e derivar outras estruturas como filas, pilhas e memory pools.

 

Espero que você leitor se beneficie com essa revisão ou apresentação em caso de ser a primeira vez que o vê. Até á próxima.

 

 

Links úteis

 

Repositório no Github contendo código exemplo de uso, clique aqui.

Outros artigos da série

<< Memory Pool - Gerenciador de memória de bloco fixo real time
NEWSLETTER

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

Obrigado! Sua inscrição foi um sucesso.

Ops, algo deu errado. Por favor tente novamente.

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

Felipe Neves
Desenvolvedor de sistemas embarcados apaixonado pelo que faz, divide seu tempo entre trabalhar no Venturus desenvolvendo firmware de tudo quanto é coisa, na Aeolus Robotics se envolvendo com o que há de mais legal em robótica e na Overlay Tech desenvolvendo algumas coisas bem legais para o campo de motion control. Possui mestrado em engenharia elétrica pela Poli-USP e possui interesse em tópicos como: Software embarcado, sistemas de tempo real, controle, robótica móvel e manipuladores, Linux embedded e quase qualquer coisa por onde passe um elétron.

1
Deixe um comentário

avatar
 
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Allef Araujo Recent comment authors
  Notificações  
recentes antigos mais votados
Notificar
Allef Araujo
Visitante
Allef Pablo Araujo

Felipe Neves, parabéns, o artigo ficou muito bom!
Espero ver mais materiais sobre estruturas de dados por aqui!