ÍNDICE DE CONTEÚDO
Caro leitor, como vai? Falamos há alguns dias sobre uma estrutura de dados simples e eficiente para armazenamento temporário de sequências de bytes, podendo ser usada em comunicações e processamento de dados, o buffer circular, um recurso com política de inserção e remoção de dados do tipo FIFO. Bem, neste artigo vamos aproveitar o uso da estrutura do buffer circular e transforma-lo em uma estrutura de dados ainda mais poderosa, uma fila circular, ou circular queue em inglês.
Qual a diferença entre Buffer Circular e Fila Circular?
Essencialmente, são idênticas, possuem políticas de inserção e remoção baseados em FIFO, controle de “wrap around”, ou seja, em caso de estouro o índice de escrita ou leitura aponta para o início da memória alocada para os dados. A diferença essencial encontra-se na unidade do tamanho de dados. No buffer circular podemos inserir uma cadeia de bytes com tamanho variável entre 1 e o tamanho da memória alocada (desde que ela esteja livre), da mesma forma que podemos retirar uma cadeia de dados sob o mesmo intervalo.
Na mesma essência, a fila circular permite a retirada de cadeia de bytes, porém de tamanho limitado a uma subdivisão lógica da área de memória conhecida por slots, assim uma fila circular possui a capacidade de N slots onde cada slot comporta até B bytes. O leitor mais atento consegue perceber que isso já remete no uso da fila circular para armazenamento de volumes de dados maiores, podendo ser usado como um gerenciador de memória simples com tamanho de bloco fixo. Perfeito, por exemplo, para ordenar tipos de dados complexos como uma sequência de datagramas TCP ou UDP. Vejam a figura abaixo:
Vejam na figura que para cada linha da tabela existem vários campos a serem preenchidos. Na abordagem da fila circular, cada linha dessa tabela teria o tamanho de um slot, de modo que a inserção seria pela cópia de um slot e a retirada por uma linha inteira da tabela na ordem em que os slots chegam. No Buffer circular estávamos interessados na ordem em que os bytes chegavam.
Onde poderia aplicar uma Fila Circular
Caro leitor, vamos voltar ao caso da UART que citei no artigo sobre buffers circulares. Nós já sabemos que usando eles podemos fazer com que a UART capture os bytes que chegam e os ordene para posterior tratamento. Agora imaginemos o caso em que por essa mesma UART trafegue um protocolo de comunicação, que contenha vários comandos, porém todos eles com a mesma sequência de bytes. Tomando, por exemplo, o conhecido protocolo MODBUS, um Telegram (estrutura padrão MODBUS) pode conter os seguintes campos conforme a figura abaixo:
Desconsideremos o campo Start e End (geralmente são tratados por hardware), vejamos que o protocolo tem uma estrutura comum, com exceção do campo Data, que pode ser variável. Vamos assumir, para simplificar o raciocínio, que saibamos que o tamanho do campo Data no seu máximo uso seja conhecido. A nossa UART já tem o buffer circular para capturar bytes que venham entre Start e End. Ela lê do registrador de hardware e adiciona ao buffer circular, porém ao montarmos um pacote MODBUS e enviar para processamento, pode ser que outro pacote já esteja pronto para chegar. Não seria então muito melhor retirar todos os bytes do buffer circular e copiar a mensagem pronta para ser processada na ordem em que elas chegam? Eis onde a fila circular deve entrar. Com ela cada slot seria um comando MODBUS completo e ordenados do mais antigo para o mais recente, permitindo que a aplicação se preocupe em apenas uma coisa, retirar a mensagem completa e executar o comando. Esse fato ajuda a evitar o uso excessivo de CPU e permite que o uso de eventos como de fila vazia desabilitem o decodificador quando ele não precisa ser usado.
Assim uma fila circular tem grande aplicação em gestores de protocolos de comunicação complexos, ou seja, que não tratam cadeia de bytes, mas mensagens pré-formatadas e com uma sequência definida. Além disso, a fila circular também pode ser utilizada para agendamento de tarefas de sistemas operacionais da mesma forma que o buffer circular. Porém, como possui sua estrutura em forma de slots, ela será capaz de lidar com estruturas de dados complexas como um Task Control Block (estrutura de dados que contém todas as informações das tarefas a serem executadas).
Exemplo de Fila Circular
A implementação apresentada traz as rotinas básicas para criação e manipulação de uma fila circular. Um exemplo de uso também está sendo fornecido para ajudar o usuário em questões básicas de criação, inserção e remoção de dados, para que este possa em seguida usar em suas próprias aplicações. O módulo fornecido está o mais independente de arquitetura possível sendo que seu desempenho da cópia dos dados depende da implementação da função memcpy geralmente otimizada na LIBC fornecida com a toolchain favorita do usuário. Abaixo temos os arquivos:
|
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 |
/** * @brief Simple circular queue implementation with basic management functions */ #ifndef __QUEUE_CIRC_H #define __QUEUE_CIRC_H /** circular queue management structure */ typedef struct { unsigned char *data; unsigned int items; unsigned int slots_number; unsigned int wr_ptr; unsigned int rd_ptr; int slot_len; } queue_circ_t; /** * @brief insert a stream data with size lenght to the queue */ int queue_insert(queue_circ_t *q,void *data, unsigned int size); /** * @brief retrieves a stream of dat with specified size */ int queue_retrieve(queue_circ_t *q, void *data, unsigned int *size); /** * @brief check if queue is already full */ int queue_full(queue_circ_t *q); /** * @brief makes the queue empty */ int queue_flush(queue_circ_t *q); /** * @brief check if queue is empty */ int queue_empty(queue_circ_t *q); /** declare a initialized circular queue * name - name of the allocated queue structure * slot_size -size in bytes of each slot * noof_slots - number of slots (elements) in this queue */ #define CIRCULAR_QUEUE_DECLARE(name,slot_size, noof_slots) \ unsigned char queue_memory_##name[(slot_size + sizeof(unsigned int)) * noof_slots];\ queue_circ_t name = { \ .data = &queue_memory_##name[0], \ .items = 0, \ .slots_number = noof_slots, \ .wr_ptr = 0, \ .rd_ptr = 0, \ .slot_len = slot_size + sizeof(int) \ } #endif |
Perdoem-me pelos comentários em inglês, utilizo de forma a tornar o acesso a esse tipo de documento universal (inclusive por estar em um repositório público). No arquivo circ_queue.h o usuário terá à disposição todas as rotinas para instanciar e utilizar sua fila de forma personalizada, ao final uma macro (da mesma forma que no bufffer circular) também fica à disposição para que seja possível inicializar uma estrutura totalmente inicializada e pronta para uso. Adicionalmente as rotinas de checagem estão providas para verificação de queue cheia ou vazia, além da rotina de flush, que efetua sua limpeza.
Abaixo daremos uma olhada na implementação (como de costume). Vejam:
|
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 |
#include <string.h> #include "queue_circ.h" int queue_insert(queue_circ_t *q,void *data, unsigned int size) { int ret = -1; if(q == NULL) { /* check your queue parameter */ return(ret); } else { /* points the insertion index in correct queue * memory region */ unsigned char *ptr = (unsigned char *)q->data; int pos = q->wr_ptr * q->slot_len; if(size > q->slot_len) { /* data will not fit in this slot */ ret = -1; } else { /* the first 4 bytes are the size of slot in bytes */ memcpy(&ptr[pos], &size, sizeof(size)); /* insert the data */ memcpy(&ptr[pos + sizeof(size)], data, size); /* update the indexes */ q->wr_ptr = (q->wr_ptr + 1) % q->slots_number; ++q->items; ret = 0; } } return(ret); } int queue_retrieve(queue_circ_t *q, void *data, unsigned int *size) { int ret = -1; if(q == NULL || size == NULL) { /* check your queue parameter */ return(ret); } else { /* points the insertion index in correct queue * memory region */ unsigned char *ptr = (unsigned char *)q->data; int pos = q->rd_ptr * q->slot_len; /* the first 4 bytes are the size of slot in bytes */ memcpy(&size,&ptr[pos], sizeof(size)); /* retrieve the data */ memcpy(data,&ptr[pos + sizeof(size)], size); /* update the indexes */ q->rd_ptr = (q->rd_ptr + 1) % q->slots_number; --q->items; ret = 0; } return(ret); } int queue_full(queue_circ_t *q) { int ret = 0; if(q->items >= q->slots_number) { ret = 1; } return(ret); } int queue_flush(queue_circ_t *q) { int ret = 0; if(q != NULL) { q->wr_ptr = q->rd_ptr; q->items = 0; } else { ret = -1; } return(ret); } int queue_empty(queue_circ_t *q) { return((q->items == 0? 1: 0)); } |
Vejam que a implementação da Fila Circular está muito similar ao Buffer Circular, além da proteção implícita a vazamento de memória com uso do incremento circular. Ao leitor mais atento, a principal diferença encontra-se nas linhas 18 e 19 para inserção, e das linhas 51 a 57 para remoção. Vejam que no Buffer Circular usávamos os índices para acessar diretamente o byte especificado por ele, porém a queue está subdivida logicamente em slots, ou seja, pequenas áreas de memória menores combinadas em uma única área de memória. Logo, para correto acesso, utilizamos os índices em conjunto com o tamanho de cada slot, multiplicando-os entre si e obtendo o início da memória de slot. Além disso, logicamente são reservados 4 bytes para cada slot que guardam a quantidade de dados inseridas nele, e ao efetuar um retrieve, a quantidade de bytes será devolvida para que o usuário saiba quanto tinha no slot acessado.
Conclusão
O buffer circular mostra-se versátil, podendo ter sua estrutura usada para construção de tipos de dados mais complexos, como o exemplo da Fila Circular, uma estrutura segura e eficiente para armazenamento temporário com o adicional de prover um bloco de memória associado para lidar com tipos de dados maiores e mais complexos. A implementação simples provida nesse artigo vai de encontro às necessidades de uso em pilhas de comunicação para processamento de mensagens que são extraídas de controladores on-chip como USB, UART, CAN, além de protocolos escritos em cima dessas interfaces.
Espero que o leitor tenha gostado. Deixe seus comentários abaixo. Até a próxima!
Links úteis
Repositório no Github com o módulo e exemplo, clique aqui.
