`sequence_of_longs.c` – Implementação das sucessões de `long`

Jump To … +

array_of_routines.c array_utils.h print.c arrays_and_pointers.c arrays_basics.c command_line.c fibonacci.c hello_world.c hello_world_correct.c linked_list.c malloc_stuff.c nans_and_other_oddities.c rationals_with_structs.c routine_pointers.c experiments.c naive_sequence_of_longs.c naive_sequence_of_longs.h sequence_of_longs.c sequence_of_longs.h tests.c sizeof_and_arrays.c array_of_doubles.c array_of_doubles.h perform_experiments.c sorting_algorithms.c sorting_algorithms.h string_io.c

¶

sequence_of_longs.c – Implementação das sucessões de long
¶

Implementação do módulo físico sequence_of_longs
¶

Este ficheiro de implementação contém a implementação do módulo físico sequence_of_longs. A interface deste módulo encontra-se no ficheiro de cabeçalho ou de interface sequence_of_longs.h. Este módulo físico contém o TAD (Tipo Abstracto de Dados) sucessão de long, com o mesmo nome que o módulo físico, i.e., sequence_of_longs. Este ficheiro de implementação faz jus ao seu nome, contendo as implementações correspondentes aos «cabeçalhos», i.e., às interfaces, que se encontram no correspondente ficheiro de cabeçalho.

Note-se que este ficheiro não possui comentários de documentação (começados por /**). Tratando-se de um ficheiro de implementação, nada contém que seja relevante na documentação do módulo físico, já que esta está relacionada apenas com a sua interface.
¶

Inclusão do cabeçalho correspondente a esta implementação

Antes de qualquer outra inclusão, incluímos o ficheiro de cabeçalho correspondente a este ficheiro de implementação. Isso ajuda a detectar inconsistências entre o ficheiro de implementação e o correspondente ficheiro de cabeçalho.
```
#include "sequence_of_longs.h"
```
¶

Inclusão de ficheiros de cabeçalho necessários no código de implementação

Estas inclusões ser feita apenas após se incluir o ficheiro de cabeçalho corresponde ao próprio ficheiro de implementação. Neste caso temos:
- stdio.h – Necessário para poder usar os procedimentos printf() e putchar().
- stdlib.h – Necessário para se poder usar a macro NULL (que será usada no futuro) e as rotinas malloc(), free() e realloc().
```
#include <stdio.h>
#include <stdlib.h>
```
¶

Definição da estrutura struct sequence_of_long

Esta estrutura contém três campos ou atributos:
- terms – Um ponteiro para o array dinâmico que contém os termos da sucessão.
- length – Inteiro guardando o comprimento actual da sucessão, i.e., o seu número de termos. Note que o comprimento da sucessão é sempre inferior ou igual ao comprimento do array que guarda os termos, a que chamamos «capacidade».
- capacity – Inteiro guardando o comprimento actual do array dinâmico que guarda os length termos actualmente na sucessão.
```
struct sequence_of_longs {
	long *terms;
	int length;
	int capacity;
};
```
¶

Implementação dos procedimentos que imprimem as sucessões

Note-se que todas as rotinas de manipulação das sucessões, com excepção naturalmente do construtor, recebem um ponteiro para a sucessão em causa como primeiro argumento. Convencionou-se chamar sl ao correspondente parâmetro em todas as definições de rotinas abaixo, com a excepção referida.
```
void SEQL_print(struct sequence_of_longs *sl)
{
```
¶

O procedimento putchar() imprime no ecrã o caractere que recebe como argumento. Neste caso trata-se da chaveta inicial da representação textual da sucessão.
```
	putchar('{');
```
¶

Depois de impressa a chaveta inicial, imprimimos cada um dos termos da sucessão usando um ciclo for. Note que o ciclo imprime apenas os termos da sucessão, e não todos os itens do array dinâmico que os armazena. Daí que a sua guarda se refira a sl->length, e não a sl->capacity.
```
	for (int i = 0; i != sl->length; i++) {
```
¶

Os termos são separados uns dos outros por ,␣ (usamos o caractere ␣ para representar o espaço). Assim, podemos preceder cada termo do separador com excepção do primeiro.
```
		if (i != 0)
			printf(", ");
```
¶

Imprimimos cada termo usando a especificação de conversão %ld, e não simplesmente %d, pois os termos da sucessão são long.
```
		printf("%ld", sl->terms[i]);
	}
```

Terminamos imprimindo a chaveta de fecho.

	putchar('}');
}

void SEQL_println(struct sequence_of_longs *sl)
{

¶

Neste caso a implementação é fácil. Começa-se por invocar o procedimento acima:
```
	SEQL_print(sl);
```
¶

Depois imprime-se o caractere \n, para finalizar a linha:
```
	putchar('\n');
}
```

Implementação do construtor do TAD

struct sequence_of_longs *SEQL_new(void)
{

¶

Reservamos primeiro espaço para uma nova struct sequence_of_longs usando a rotina malloc(). Obtemos a quantidade de unidades de memória a reservar usando o operador sizeof. Guardamos o endereço dessa nova variável dinâmica no ponteiro sl, através do qual se passará a manipular a nova sucessão de long. No final do construtor este ponteiro será devolvido.
```
	struct sequence_of_longs *sl = malloc(sizeof(struct sequence_of_longs));
```
¶

De seguida inicializamos os campos ou atributos da rotina com valores apropriados para uma sucessão vazia. O comprimento de uma sucessão vazia é naturalmente 0. A capacidade do array dinâmico que guarda os termos também poderia ser inicialmente 0. No entanto, como se verá mais abaixo, a estratégia usada é a de duplicar a capacidade sempre que ela está esgotada e se pretende adicionar um termo à sucessão. Ora, uma capacidade de 0 estaria esgotada logo na primeira adição de um termo e, pior, o dobro de 0 é... 0! É mais sensato, por isso, começar com um capacidade maior que zero. Começar com 1 é uma possibilidade, embora qualquer outro valor positivo fosse igualmente eficaz. Quanto maior for a capacidade inicial, maior a eficiência das adições, mas pior a eficiência na utilização da memória. Daí que a escolha de uma capacidade inicial unitária não seja totalmente desprovida de sentido.

Ah! E não se esqueça que o compilador traduz sl->length por (*sl).length. Ou seja, o significado de sl->length é «o campo length da estrutura apontada pelo ponteiro sl».
```
	sl->length = 0;
	sl->capacity = 1;
```
¶

Inicializados os campos que guardam o comprimento da sucessão e a capacidade do array dinâmico que guarda os termos da sucessão, há que reservar espaço de memória para este array e guardar o endereço do seu primeiro item no campo terms. É o que se faz aqui, recorrendo à rotina malloc(). Note-se que se reserva espaço suficiente para sl->capacity termos.
```
	sl->terms = malloc(sl->capacity * sizeof(long));
```
¶

Terminada a construção da nova sucessão, há que devolver o seu endereço (ou ponteiro), guardado na variável sl. Será através dele que o código cliente fará uso da sucessão, passando-o como primeiro argumento às rotinas fornecidas por este módulo físico.
```
	return sl;
}
```
¶

Implementação do inspector do comprimento

Dá-se o nome de inspector a uma função que permite obter uma propriedade de uma instância de um TAD sem alterar essa instância. (A palavra «instância» não tem nada de especial. Uma «instância» é um exemplar ou caso particular de um tipo. Por exemplo, o valor 5 é uma instância do tipo int, em C.)
```
int SEQL_length(struct sequence_of_longs *sl)
{
	return sl->length;
}
```
¶

Implementação do modificador de adição de um novo termo à sucessão

Dá-se o nome de modificador a um procedimento que altera uma instância de um TAD. Neste caso o modificador é o procedimento SEQL_add(), que altera a sucessão cujo ponteiro é sl adicionando-lhe um novo termo new_term.
```
void SEQL_add(struct sequence_of_longs *sl, long new_term)
{
```
¶

Antes de adicionar o termo há que verificar se o array dinâmico onde será guardado tem capacidade suficiente para ele. Se o comprimento actual da sucessão for igual à capacidade desse array, então a capacidade está esgotada, sendo necessário aumentá-la.
```
	if (sl->length == sl->capacity)
```
¶

Para aumentar a capacidade, duplicamos o valor do campo sl->capacity e usamos a rotina realloc() para reservar um novo array dinâmico com essa nova capacidade e incluindo todos os termos que já constam na sucessão. É este último requisito que nos leva a usar a rotina realloc(), e não a rotina malloc(). A rotina realloc(), se precisar de reservar nova memória, i.e., se não conseguir simplesmente estender o array existente, copiará automaticamente os termos da memória original. É por isso que o primeiro argumento passado a realloc() é um ponteiro para o array original.
```
		sl->terms = realloc(sl->terms,
				    (sl->capacity *= 2) * sizeof(long));
```
¶

Estas linhas poderiam ser substituídas pelo código abaixo. À parte a possibilidade de estender o array original, de que a rotina realloc() pode tirar partido, o resultado seria exactamente o mesmo. Preferimos, naturalmente, a versão mais curta... Quanto à duplicação da capacidade numa instrução à parte, é certamente preferível, mas é tão comum (idiomático) encontrar o código condensado numa única instrução, que optámos pela versão mais críptica.
```
if (sl->length == sl->capacity) {
   sl->capacity *= 2;
   long *new_array = malloc(sl->capacity * sizeof(long));
   for (int i = 0; i != sl->length; i++)
       new_array[i] = sl->terms[i];
   free(sl->terms);
   sl->terms = new_array;
}
```
¶

Finalmente, guardamos o novo termo new_term no local apropriado do array, que neste ponto já tem certamente (hmmmm... será?) capacidade suficiente, i.e., na posição sl->length. Depois, incrementamos o comprimento da sucessão. Mais uma vez, a condensação de duas alterações numa única instrução é uma má prática, mas tão generalizada na programação em C que já se tornou idiomática. A alternativa, mais clara, seria usar:
```
sl->terms[sl->length] = new_term;
sl->length++;
```
```
	sl->terms[sl->length++] = new_term;
}
```
¶

Implementação do inspector de termo

Este inspector permite obter o termo da sucessão na posição dada por index.
```
long SEQL_term(struct sequence_of_longs *sl, int index)
{
```
¶

Note a utilização da indexação do item index do array dinâmico sl->terms, ao qual se acede usando o operador -> sobre o ponteiro sl para a estrutura que representa a sucessão.
```
	return sl->terms[index];
}
```

`sequence_of_longs.c` – Implementação das sucessões de `long`

Implementação do módulo físico `sequence_of_longs`

Inclusão do cabeçalho correspondente a esta implementação

Inclusão de ficheiros de cabeçalho necessários no código de implementação

Definição da estrutura `struct sequence_of_long`

Implementação dos procedimentos que imprimem as sucessões

Implementação do construtor do TAD

Implementação do inspector do comprimento

Implementação do modificador de adição de um novo termo à sucessão

Implementação do inspector de termo

sequence_of_longs.c – Implementação das sucessões de long

Implementação do módulo físico sequence_of_longs

Inclusão do cabeçalho correspondente a esta implementação

Inclusão de ficheiros de cabeçalho necessários no código de implementação

Definição da estrutura struct sequence_of_long

Implementação dos procedimentos que imprimem as sucessões

Implementação do construtor do TAD

Implementação do inspector do comprimento

Implementação do modificador de adição de um novo termo à sucessão

Implementação do inspector de termo

`sequence_of_longs.c` – Implementação das sucessões de `long`

Implementação do módulo físico `sequence_of_longs`

Definição da estrutura `struct sequence_of_long`