Lista encadeada

Eu estava tendo um sério problema de memória na Linkit ONE, pois não há um meio de saber quanto você tem disponível para utilização, e como não sei o quanto é utilizado por cada biblioteca, fica difícil calcular. Quando se extrapola o limite, a execução do código pára e as luzes TX e RX ficam se intercalando, então só desligando e ligando. As sequências de movimentos eram armazenadas em vetores de strings, ou seja, se tornam matrizes (já que strings são vetores em C). Isso consumia muita memória, já que um movimento pode fazer referência a outros, e estes a outros, e assim por diante. Carregar todos os movimentos necessários de uma vez só, em alguns casos, extrapolava a memória disponível (e o tamanho da matriz). Um dia inteiro pensando em como resolver isso e lembrei das aulas de Estrutura de Dados na faculdade: listas encadeadas! Tive um ótimo professor, que infelizmente não lembro mais o nome, e ainda lembrava os princípios básicos. Cria-se uma estrutura básica que contém o valor desejado e um ponteiro para o próximo elemento da lista. Isso é perfeito para o que preciso, pois posso modificar essa lista enquanto carrego os movimentos. Desta maneira, se um movimento A faz referência a movimentos B e C, cujo B faz referências aos movimentos D e E, a lista vai crescer dinamicamente, na ordem de execução. A princípio só se tem A:

A->B->C

Quando chegar na execução do B, teremos:

A->B->D->C
A->B->D->E->C

Como cada item tem um ponteiro (referência) para o próximo, quando chegamos no B e pegamos o D e o E, inserimos o D como próximo de B, e o C, que era o próximo de B fica sendo o próximo de D. E fazemos a mesma coisa com o E em relação ao D e ao C.
Esta é a vantagem da lista encadeada. Caso quiséssemos fazer a mesma coisa com um vetor, teríamos que deslocar todos os itens n posições a frente para encaixarmos os movimentos desejados. Além de ser trabalhoso, isso iria consumir muito processamento. Lembrando que cada A, B, C, etc. do exemplo podem ser várias instruções.

Obviamente que ainda é possível extrapolar o limite da memória disponível, mas por enquanto a maior sequência que tenho, e que dava problema anteriormente, agora funciona corretamente. Para quem gosta de códigos, veja abaixo como criar uma lista encadeada (só testei na Linkit ONE, mas deve funcionar em um Arduino comum):

struct list {
	char val[MAXTOKEN];
	struct list * next;
};

typedef struct list item;

item *current, *root, *tail;

item *listAdd(char *s);
item *listInsert(char *s, item *it);

E detalhando as funções previamente declaradas:

item *listAdd(char *s)
{
	item *novo = (item *)malloc(sizeof(item));

	strcpy(novo->val, s);
	novo->next = NULL;

	if (root == NULL)
		root = novo;
	else
		tail->next = novo;

	tail = novo;

	return novo;
}

item *listInsert(char *s, item *it)
{
	item *novo = (item *)malloc(sizeof(item));

	if (novo == NULL)
	{
		Serial.println("malloc error!!!");
	}
	else
	{
		strcpy(novo->val, s);
		novo->next = it->next;

		it->next = novo;
	}

	return novo;
}

No caso, listAdd(s) adiciona um novo item ao final da lista (ou como primeiro item, caso a mesma esteja vazia); já listInsert(s, it) insere o novo item entre dois elementos (ou no final da lista, caso o elemento passado seja o último). O que acontece no listInsert() é que ao passarmos o item atual e o novo item (que deve ficar imediatamente após o item atual), simplesmente mudamos as referências, ou seja, o item atual passa a apontar para o novo item e o novo item passa a apontar para o item que o atual apontava anteriormente. Note que a ordem de execução não pode ser a mesma da sentença anterior, uma vez que perderíamos a referência.

A função abaixo mostra como iterar sobre uma lista encadeada, mostrando seus itens:

void listPrint()
{
	item *atual = root;

	Serial.println("-- BOL --");
	while (atual)
	{
		Serial.println(atual->val);
		atual = atual->next;
	}
	Serial.println("-- EOL --");
}

E este foi mais um desafio vencido no desenvolvimento do Projeto J.A.R.V.I.S. 😉