Listas Genéricas em C

Sendo um desenvolvedor full-stack eu escrevo, a maior parte do tempo, aplicações web utilizando .Net e Node.js em linguagens de alto nível como C# e JavaScript. Aqui e acolá, entretanto, eu me envolvo em projetos de automação, IoT ou retro-programação onde o bom e velho C reina absoluto.

Vez por outra, entretanto, eu sinto a falta de algumas facilidades de linguagens de nível mais alto, como templates, um runtime um pouco mais rico e, como o título sugere, o suporte a abstrações úteis como os Generics.

Generics

Os tipos genéricos (Generics) permitem que você personalize um método, uma classe, uma estrutura ou uma interface para o tipo exato de dados no qual ele atua. Por exemplo, em vez de usar a classe Hashtable, que permite que as chaves e os valores sejam de qualquer tipo, você pode usar a classe genérica Dictionary<TKey,TValue> e especificar o tipo permitido para a chave e o tipo permitido para o valor.

MSDN

Então, em C#, por exemplo, eu posso declarar uma lista genérica e especificar o tipo de dados que aquela lista irá manipular, isto permite que a partir da mesma classe (List<T>) eu possa criar uma lista de números inteiros (List<int>) uma lista de números reais (List<float>), uma lista de textos (List<string>) ou uma lista de um tipo de dados qualquer (List<MyStruct>).

Listas Encadeadas

Uma lista ligada ou lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por células que apontam para o próximo elemento da lista. Para “ter” uma lista ligada/encadeada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula (também chamados de nó) nula.

Wikipedia

Não temos classes em C, mas podemos implementar um conceito similar e também muito poderoso: o tipo de dados abstrato (abstract data type – ADT, em inglês) que nos permite definir tanto a estrutura como o comportamento da nossa lista de dados que será criada como uma lista encadeada. Se o conceito de lista encadeada é novo para você, recomendo muito a leitura deste artigo do Wikipedia sobre o tópico.

Vamos supor que você precise organizar uma lista de pessoas e que cada pessoa desta lista possuas os seguintes dados:

1. Nome
2. Lista de tarefas
3. Lista de números de telefones

Começando pelas estrutura mais simples, podemos declarar um struct para as tarefas e um outro para os telefones:

	#include <time.h>
	#include <stdbool.h>
	typedef struct {
	char descicao[255];
	bool pendente;
	} Tarefa;
	#define TEL_FIXO 0x00
	#define TEL_CELULAR 0x01
	typedef struct {
	char tipo;
	char ddd[3];
	char numero[10];
	} Telefone;

view raw tarefas-01.c hosted with ❤ by GitHub

Agora precisamos de uma estrutura para representar uma lista de telefones, outra para representar uma lista de tarefas e uma para representar uma pessoa com todos os atributos que desejamos.

	typedef struct _node_tarefa{
	struct _node_tarefa *next;
	Tarefa data;
	} NodeTarefa;
	typedef struct {
	NodeTarefa *head;
	} Tarefas;
	typedef struct _node_telefone{
	struct _node_telefone *next;
	Telefone data;
	} NodeTelefone;
	typedef struct {
	NodeTelefone *head;
	} Telefones;
	typedef struct {
	char nome[80];
	Tarefas tarefas;
	Telefones telefones;
	} Pessoa;

view raw tarefas-02.c hosted with ❤ by GitHub

Naturalmente, ainda precisamos definir uma estrutura para representar a lista de pessoas (que foi ocultada no código acima por uma questão de brevidade). Até aqui, definimos somente as estrutura de armazenamento, mas ainda não escrevemos nenhuma função para definir o comportamento destas listas.

Da maneira que foi escrito, precisaríamos de 3 conjuntos de funções praticamente idênticos (um para cada lista) para:

• instanciar uma nova lista
• adicionar itens
• remover itens
• localizar um item específico
• acessar um item pelo seu índice

A matemática não pode ser mais fácil. Temos 3 listas diferentes e precisamos escrever 5 funções para cada uma delas, totalizando 15 funções a serem escritas! Uma tarefa massante, repetitiva, ineficiente e muito suscetível a erros. E a coisa pode ficar muito pior num piscar de olhos…

Imagine se no meio do caminho, percebêssemos que precisamos manter listas de endereços, ou de documentos para cada pessoa. E se precisarmos ordenar as listas? Mais uma função a ser escrita e testada em cada uma delas. O fato é que, esta abordagem, embora muito simples, tende a gerar um código extenso e difícil de manter ao longo do tempo.

A arte de programar, disse Marijn Haverbeke em seu livro “Eloquent JavaScript“, é em grande parte, a arte de controlar a complexidade:

Para muitos de nós, escrever programas de computador é um fascinante jogo. Um programa é uma construção do pensamento. Não tem custos de construção, é leve e cresce facilmente ante nossas digitações.

Se não formos cuidadosos, seu tamanho e complexidade vão aumentar fora de controle, confundindo até a pessoa que o criou. Este é o principal problema da programação: manter os programas sobre controle. Quando um programa funciona, ele é lindo. A arte de programar é a habilidade de controlar a complexidade.

Marijn Haverbeke

Para reduzirmos o crescimento da complexidade do nosso pequeno projeto, precisamos encontrar uma maneira mais genérica de definir uma lista. Uma maneira de abstrair o fato de que estamos tratando com uma lista de números ou uma lista de texto ou seja lá qual for o tipo de dados que temos em mão. Em outras palavras: precisamos abstrair o tipo de dados e nos concentrar no comportamento da lista em si.

Reduzindo a complexidade

Veja um diagrama mais simplificado do funcionamento de uma lista encadeada e perceba como ele é mais objetivo que o diagrama mostrado no início do texto.

Qual a diferença?

Ele nos mostra como a lista funciona, mas não se importa com o que há dentro de cada nó. E é exatamente isto que vamos fazer com nosso código! No lugar de criarmos um NodeTelefones, um NodeTarefas e um NodePessoas, vamos definir um nó genérico apenas: um único Node. E com uma única maneira de representar um nó, podemos ter uma única maneira de representar uma lista. Finalmente, com uma única maneira de representar uma lista, podemos fazer uma pessoa ter as listas de que quisermos de forma muito mais simples.

	/* Nó genérico, veja que o campo data
	* é um ponteiro sem tipo, ou seja,
	* pode apontar para qualquer coisa */
	typedef struct _node {
	void *data;
	struct _node *next;
	} Node;
	typedef struct {
	int count;
	int data_size;
	Node *head;
	Node *tail;
	} List;
	/*
	* Nova estrutura utilizando
	* a lista genérica tanto para
	* as tarefas, quanto para os telefones
	*/
	typedef struct {
	char nome[80];
	List *tarefas;
	List *telefones;
	} Pessoa;

view raw simple-list-00.c hosted with ❤ by GitHub

Perfeito!

Veja que o segredo aqui foi mudar o tipo de dados do campo data da estrutura Node para um ponteiro não tipado o void *.

Um void * na linguagem C (lê-se void pointer), é um ponteiro genérico, muitas vezes chamado de ponteiro de propósito geral, que pode apontar para qualquer coisa dentro do seu programa e, em certos casos, para qualquer coisa dentro do seu computador. Tudo o que ele representa é um endereço dentro dos espaços de memória visíveis ao seu programa.

Você pode fazer o um void * apontar para um int, um array, uma string, uma Tarefa, uma Pessoa, um Telefone, etc. Sabendo disto, podemos declarar o comportamento da nossa lista genérica.

	typedef struct _node {
	void *data;
	struct _node *next;
	} Node;
	typedef struct {
	int count;
	int data_size;
	Node *head;
	Node *tail;
	} List;
	List* list_create(int dataSize);
	void list_destroy(List *list);
	void list_add(List *list, void *data);
	void list_remove(List *list, int index);

view raw simple-list-01.c hosted with ❤ by GitHub

Atribuindo Responsabilidades

Outro passo importante na redução da complexidade é saber escolher bem as responsabilidades de cada elemento de um programa.

Veja. Somos, neste ponto, capazes de representar pessoas, tarefas, telefones e listas. É preciso agora estabelecer uma relação de dependência entre eles para responder a perguntas como:

• quem é responsável por criar e destruir tarefas?
• quem é responsável por atribuir tarefas à pessoa correta?
• uma mesma tarefa pode ser compartilhada entre duas pessoas?

Estas reflexões devem estar explícitas nas assinaturas dos métodos para que você, programador, bata o olho em um conjunto de funções e consiga responder a este tipo de pergunta somente lendo o código-fonte.

Pode parecer óbvio demais para falar, mas se você decidir que uma tarefa pode ser criada e atribuída a mais de uma pessoa, então deve haver uma função para criar uma tarefa e outra para atribuí-a a uma pessoa qualquer. As funções devem ser nomeadas de maneira a refletir sua utilidade e devem, de acordo com o princípio da responsabilidade única, realizar uma única tarefa.

O código a seguir ilustra um exemplo de como as funções podem ser implementadas a partir desta ideia. Repare como é fácil saber o que cada função faz. Repare, também, como a lógica de adição de telefones e tarefas ficou simples com o uso dos void *.

	/*** API de Tarefas ***/
	Tarefa *tarefa_create(char *descricao, bool pendente) {
	Tarefa *result = calloc(1, sizeof(Tarefa));
	memcpy(result->descicao, descricao, strlen(descricao));
	result->pendente = pendente;
	return result;
	}
	/*** API de Telefones ***/
	Telefone *telefone(char tipo, char *ddd, char *numero) {
	Telefone *result = calloc(1, sizeof(Telefone));
	result->tipo = tipo;
	memcpy(result->ddd, ddd, strlen(ddd));
	memcpy(result->numero, numero, strlen(numero));
	return result;
	}
	/*** API de Pessoas ***/
	Pessoa *pessoa_create(char *nome) {
	Pessoa *result = calloc(1,sizeof(Pessoa));
	memcpy(result->nome, nome, strlen(nome));
	result->tarefas = list_create(sizeof(Tarefa));
	result->telefones = list_create(sizeof(Pessoa));
	return result;
	}
	void pessoa_destroy(Pessoa *pessoa){
	list_destroy(pessoa->tarefas);
	list_destroy(pessoa->telefones);
	free(pessoa);
	}
	void adicionar_tarefa(Pessoa *pessoa, Tarefa *tarefa) {
	list_add(pessoa->tarefas, tarefa);
	}
	void adicionar_telefone(Pessoa *pessoa, Telefone *telefone) {
	list_add(pessoa->telefones, telefone);
	}
	void listar_tarefas(Pessoa *pessoa) {
	Node *node = pessoa->tarefas->head;
	Tarefa *tarefa;
	int i = 1;
	printf("Tarefas:\n");
	while (node != NULL){
	tarefa = (Tarefa *)node->data;
	printf(" [%s] %02d – %s\n", tarefa->pendente ? " " : "OK", i, tarefa->descicao);
	node = node->next;
	i++;
	}
	}
	void listar_telefones(Pessoa *pessoa) {
	Node *node = pessoa->telefones->head;
	Telefone *telefone;
	int i = 1;
	printf("Telefones:\n");
	while (node != NULL) {
	telefone = (Telefone *)node->data;
	switch (telefone->tipo){
	case TEL_FIXO:
	printf(" FIXO (%s) %s\n", telefone->ddd, telefone->numero);
	break;
	case TEL_CELULAR:
	printf(" CELULAR (%s) %s\n", telefone->ddd, telefone->numero);
	break;
	}
	node = node->next;
	i++;
	}
	}
	void listar_detalhes(Pessoa *pessoa) {
	printf("Listando dados de %s:\n", pessoa->nome);
	pessoa_listar_tarefas(pessoa);
	pessoa_listar_telefones(pessoa);
	}

view raw api-simples-01.c hosted with ❤ by GitHub

Escrevendo um programa de testes

Por fim, podemos escrever um programa simples utilizando tudo o que foi desenvolvido até aqui.

	#include <locale.h>
	#include <stdlib.h>
	#include "tarefas.h"
	#include "list.h"
	int main(void) {
	//para suporte a acentos e caracteres especiais
	setlocale(LC_ALL, "pt");
	//criamos uma pessoa
	Pessoa* fabiano = pessoa_create("Fabiano Salles");
	//adicionamos algumas tarefas…
	adicionar_tarefa(fabiano, tarefa("Publicar artigo sobre listas genéricas em C", false));
	adicionar_tarefa(fabiano, tarefa("Escrever sobre games em SDL e C++", true));
	adicionar_tarefa(fabiano, tarefa("Concluir o curso de microeletrônica", true));
	adicionar_tarefa(fabiano, tarefa("Escrever um artigo sobre Arduino", true));
	//adicionando alguns telefones…
	adicionar_telefone(fabiano, telefone(TEL_CELULAR, "11", "90000-0000"));
	adicionar_telefone(fabiano, telefone(TEL_FIXO, "11", "1111-1111"));
	//exibindo os dados na tela..
	listar_detalhes(fabiano);
	//liberando a memória utilzada
	pessoa_destroy(fabiano);
	return 0;
	}

view raw list-test-01.c hosted with ❤ by GitHub

Conclusão

Embora o C seja uma linguagem estruturada, muitas vezes, as idéias do mundo da orientação a objeto podem ser utilizadas para facilitar nossa vida e simplificar nosso código.

Cada novo paradigma, técnica ou linguagem que aprendemos é uma ferramenta a mais que, uma vez bem compreendida, pode ser e adaptada para uso em problemas do dia-a-dia. Numa época em que computadores pessoais, poderosos smartphones e pequenos dispositivos microcontrolados convivem lado a lado trocando informações entre si, é importantíssimo manter a mente aberta e permitir-se experimentar buscando intersecções interessantes entre estes mundos.

Muito obrigado pela leitura.