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:
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:
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:
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:
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 56 57 58 59 60 61 62 63 64 65 66 67 | /** * @brief single linked list interface file */ #ifndef __SLIST_H_ #define __SLIST_H_ #include <stdbool.h> /* single linked list data structure */ typedef struct slist_s { void *data; struct slist_s *next; }slist_t; /* single linked list head data structure */ typedef struct { slist_t *first; int noof_elements; }slist_info_t; /** * @brief insert an container in the slist */ int slist_insert(slist_info_t *s, slist_t *item, void *data); /** * @brief gets data from a specified position with optional remotion */ int slist_get_data_from_position(slist_info_t *s, int position, void *data, bool remove); /** * @brief gets data from head with optional remotion */ int slist_get_data_from_head(slist_info_t *s, void *data, bool remove); /** * @brief gets data from tail with optional remotion */ int slist_get_data_from_tail(slist_info_t *s, void *data, bool remove); /** * @brief deletes all the items in current list */ int slist_clean(slist_info_t *s); /** * @brief get the current number of entries on list */ int slist_get_noof_entries(slist_info_t *s); /** * @brief linked list instantiation macro: */ #define SLIST_DECLARE(name) \ slist_info_t name = { \ .first = (void *)0, \ .noof_elements = 0, \ } #endif /* SLIST_H_ */ |
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).
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 | /** * @brief single linked list interface file */ #include <string.h> #include <stdlib.h> #include "slist.h" /* * Internal functions */ /** * @brief makes a link of a outside incoming item to a list */ static void slist_link(slist_info_t *s, slist_t *item) { /* in order to ensure O(1) insertion * only does a prepend in target list */ item->next = s->first->next; s->first = item; s->noof_elements++; } /** * @brief breaks the link of specified list item */ static void slist_unlink(slist_info_t *s, slist_t *item, int position) { /* * WARN: when using unlink by item, make sure the desired item to * unlink is the next linked to the item argument */ /* check how to link */ if(item != NULL) { /* item based, remove the next entrie, this the desired * entry to unlink and not the current item */ slist_t *tmp = item->next; item->next = tmp->next; tmp->next = NULL; if(s->noof_elements > 0) s->noof_elements--; } else if (position != 0) { /* * TODO: position based is used only in special case, * when the list has only 1 position, so if needed in future * implement to handle all the list using position based * remotion */ if(s->noof_elements > 1) { slist_t *tmp = s->first; s->first = tmp->next; tmp->next = NULL; if(s->noof_elements > 0) s->noof_elements--; }else { s->first = NULL; s->noof_elements = 0; } } } /* * Public functions */ int slist_insert(slist_info_t *s, slist_t *item, void *data) { int ret = 0; /* check arguments */ if((s == NULL) || (item == NULL) || (data == NULL)) { ret = -1; } else { /* is the first element? */ if(s->noof_elements == 0) { /* links the new element directly */ item->data = data; item->next = NULL; s->first = item; s->noof_elements++; } else { item->data = data; item->next = NULL; /* prepend the new element on list */ slist_link(s, item); } } return (ret); } int slist_get_data_from_position(slist_info_t *s, int position, void *data, bool remove) { int ret = 0; /* check arguments */ if((s == NULL) || (position == 0)) { ret = -1; } else { /* check if position exists */ if(position <= s->noof_elements) { /* list has only 1 position? */ if(s->noof_elements == 1) { data = s->first->data; /* if needs unlink */ if(remove != false) { slist_unlink(s,NULL, position); } } else { /* find the index where the data is located */ slist_t *tmp = s->first; for(int i = 1; i != position -1 ; tmp = tmp->next, i++); data = tmp->data; /* unlink if needed */ if(remove != false) { slist_unlink(s,tmp, 0); } } } else { ret = -1; } } return(ret); } int slist_get_data_from_head(slist_info_t *s, void *data, bool remove) { int ret = 0; /* check arguments */ if((s == NULL)) { ret = -1; } else { if(s->noof_elements != 0) { /* we want the head of list, so the first item * added in the list, which is located at end of it */ int position = s->noof_elements; slist_t *tmp = s->first; for(int i = 1; i != position -1 ; tmp = tmp->next, i++); data = tmp->data; /* unlink if needed */ if(remove != false) { slist_unlink(s,tmp, 0); } } else { /* list is empty */ ret = -1; } } return(ret); } int slist_get_data_from_tail(slist_info_t *s, void *data, bool remove) { int ret = 0; /* check arguments */ if((s == NULL)) { ret = -1; } else { /* we want the tail of list, so the last item * added in the list, which is located at beginning of it */ data = s->first->data; /* unlink if needed */ if(remove != false) { slist_unlink(s,NULL, 1); } } return(ret); } int slist_clean(slist_info_t *s) { int ret = 0; /* check arguments */ if(s == NULL) { ret = -1; } else { int position = s->noof_elements; slist_t *tmp = s->first; /* unlink the items chain from root of the list */ s->first = NULL; s->noof_elements = 0; /* unlink the further slots */ for(int i = 1; i != position - 1; i++) { slist_t *unlink = tmp->next; tmp->next = NULL; tmp = unlink; } } return(ret); } int slist_get_noof_entries(slist_info_t *s) { int ret = 0; /* check arguments */ if(s == NULL) { ret = -1; }else { ret = s->noof_elements; } return(ret); } |
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.
Felipe Neves, parabéns, o artigo ficou muito bom!
Espero ver mais materiais sobre estruturas de dados por aqui!