Array dinâmico

Um array carateriza-se por ser uma sequência de objetos alojados em posições de memória contíguas. Tem como principais vantagens, a possibilidade de acesso direto aos elementos a custo unitário e, quando ordenado, permite pesquisa dicotómica a custo \(log_2 N\).

Designa-se por array estático um array cuja dimensão não pode ser alterada durante a execução do programa. Um array estático pode ser definido em tempo de compilação – os arrays próprios da linguagem – ou ser definidos em tempo de execução – os arrays de âmbito local alojados em stack ou os alojados dinamicamente com a função malloc.

Designa-se por array dinâmico um array cuja dimensão pode variar durante a execução do programa. A sua concretização basea-se na realocação da memória de suporte de dados à medida da necessidade. Por exemplo, a escrita numa posição além da dimensão atual do array, pode desencadear uma operação de subtituição da zona da memória de suporte de dados por uma zona de memória de dimensão maior.

Nesta versão do programa contador de palavras é utilizado um array dinâmico de objetos do tipo

struct word {
	char *text;
	int counter;
};

O array é referenciado pelo ponteiro words e representado por uma estrutura struct vector criada dinamicamente.

struct vector *words;

O ciclo de processamento de palavras consiste na leitura de palavra (linha 7), na procura da palavra (linha 10) e pela inserção, se a palavra ainda não estiver presente (linhas 15 a 17).

Listagem 105 Contagem de palavras baseada em array dinâmico

int main(int argc, char *argv[]){
	FILE *fd = fopen(argv[1], "r");
	int nwords = 0;
	words = vector_create(sizeof (struct word), 2);
	long initial = get_time();
	char *word_text;
	while ((word_text = read_word(fd, separators)) != NULL) {
		nwords++;
		size_t index;
		if (vector_sorted_search(words, word_text, word_cmp_text, &index)) {
			struct word *w = vector_at(words, index);
			w->counter++;
		}
		else {
			struct word w = { .counter = 1 };
			w.text = strdup(word_text);
			vector_insert(words, &w, index);
		}
	}
	long duration = get_time() - initial;
	fclose(fd);
	printf("Total de palavras = %d; Palavras diferentes = %zd Time = %ld\n",
			nwords, vector_size(words), duration);
	vector_sort(words, word_cmp_count_decrease);
	print_top_ten(words, min(10, vector_size(words)));
	vector_foreach(words, free_word, NULL);
	vector_destroy(words);
}

Criação do array

O array dinâmico é criado pela função vector_create (linha 4). O primeiro argumento é a dimensão dos elementos do array e o segundo argumento é o acréscimo, em número de elementos, quando o array é aumentado. A utilização do valor 2 é por acaso.

O array dinâmico genérico é baseado na struct vector.

struct vector {
	void *buffer;
	size_t element_size, current_size, max_size, chunk_size;
};

O campo buffer aponta a zona da memória de dados do array.
O campo element_size a dimensão dos elementos do array, em número de bytes.
O campo current_size o atual número de elementos.
O campo max_size a capacidade da memória alocada, em número de elementos.
O campo chunck_size o acréscimo, em número de elementos, quando o array for aumentado.

vector_create

A função vector_create aloca memória para a struct vector (linha 2) e para a zona de dados do array (linha 5).

struct vector *vector_create(size_t element_size, size_t chunk_size)
{
	struct vector *vector = malloc(sizeof *vector);
	if (NULL == vector)
		return NULL;
	vector->buffer = malloc(element_size * chunk_size);
	if (NULL == vector->buffer) {
		free(vector);
		return NULL;
	}
	vector->element_size = element_size;
	vector->chunk_size = chunk_size;
	vector->max_size = chunk_size;
	vector->current_size = 0;
	return vector;
}

Procura da palavra

Cada palavra lida do texto é procurada no array. O array é mantido ordenado para permitir a utilização de pesquisa dicotómica que tem custo \(log_2 N\).

A procura é realizada pela função vector_sorted_search. Recebe como argumentos a palavra a procurar e a função de comparação. Devolve duas informações: se encontrou – o índice onde se encontra; ou se não encontrou – o índice onde deveria encontrar.

vector_sorted_search

Esta função assume que o array se encontra ondenado com um critério compatível com a função de comparação recebida no parâmetro compare. Essa função devolve um valor positivo se o primeiro argumento for de ordem superior ao segundo, um valor negativo se for de ordem inferior ou zero se forem da mesma ordem (iguais).

Esta função aplica um algoritmo de procura dicotómica subdividindo o array em sucessivas metades até encontrar o elemento procurado ou até não poder subdividir mais, o que significa que o elemento procurado não está no array.

A variável ref serve para anotar a posição do array onde o elemento procurado se deveria encontrar, caso estivesse presente. Este valor é devolvido através do parâmetro de saída index. O objetivo é poder vir a seu utilizado na inserção desse elemento, mantendo a ordenação, e dispensando uma nova procura.

bool vector_sorted_search(struct vector *vector, void *key,
	                      int (*compare)(const void *, const void *), size_t *index)
{
	size_t left = 0, right = vector->current_size, middle = (right - left) / 2;
	size_t ref = 0;
	char *buffer = vector->buffer;
	while (left < right) {
		int compare_result = compare(key, buffer + middle * vector->element_size);
		if (compare_result > 0) {
			ref = left = middle + 1;
		}
		else if (compare_result < 0) {
			ref = right = middle;
		}
		else {
			*index = middle;
			return true;
		}
		middle = left + (right - left) / 2;
	}
	*index = ref;
	return false;
}

Inserção de palavra

A inserção de uma nova palavra dá-se nas linhas 15 a 17. Ocorre depois de se verificar que a palavra ainda não existe no array.

Na inserção é utilizada a variável local w alojada em stack (linha 15) onde se concentra a informação relativa à palavra – o ponteiro para o texto da palavra e o contador. A inserção é realizada pela função vector_insert, que recebe o ponteiro para w e copia o conteúdo apontado para a posição index do array.

É utilizado o valor de index devolvido pela função vector_sorted_search com a posição do array onde o elemento deve ser inserido para manter a ordenação. Este aproveitamento dispensa uma nova procura da posição de inserção.

vector_insert

A função vector_insert insere o elemento apontado pelo parâmetro element na posição indicada por index.

Se essa posição estiver aquém da dimensão atual (linha 14), os elementos das posições seguintes são deslocados uma posição para a frente (linhas 21 a 23).

Devido a este deslocamento, se toda a memória alocada estiver utilizada, é necessário aumentar a porção de memória alocada (linha 15).

Se essa posição estiver além da memória alocada (linha 4), a alocação de memória é aumentada até cobrir a posição indicada (linhas 5 e 6).

O aumento de memória afeta aos dados do array implica alocar um novo bloco, copiar os dados do bloco antigo para o novo bloco e libertar o bloco antigo.

A função realloc, pertencente à biblioteca normalizada da linguagem C, satisfaz esta necessidade. Recebe o ponteiro para um bloco de memória previamente alocado e uma nova dimensão e altera a dimensão desse bloco para essa dimensão, mantendo o conteúdo de dados.

bool vector_insert(struct vector *vector, void *element, size_t index)
{
	char *buffer = vector->buffer;
	if (index >= vector->current_size) {
		if (index >= vector->max_size) {
			vector->max_size = (index / vector->chunk_size + 1) * vector->chunk_size;
			vector->buffer = buffer = realloc(buffer, vector->max_size * vector->element_size);
			if (NULL == buffer)
				return false;
		}
		memcpy(buffer + index * vector->element_size, element, vector->element_size);
		vector->current_size = index + 1;
		return true;
	}
	/* index < vector->current_size */
	if (vector->current_size == vector->max_size) {
		vector->max_size += vector->chunk_size;
		vector->buffer = buffer = realloc(buffer, vector->max_size * vector->element_size);
		if (NULL == buffer)
			return false;
	}
	memmove(buffer + (index + 1) * vector->element_size,
			buffer +  index * vector->element_size,
			(vector->current_size - index) * vector->element_size);
	memcpy(buffer + index * vector->element_size, element, vector->element_size);
	vector->current_size++;
	return true;
}

Eliminação do array

Quando os dados no array e o próprio array não são mais necessários, deve-se libertar os recursos de memória associados. Essa libertação decorre em duas fases, a libertação dos elementos seguida da eliminação do próprio array. A primeira deve ser realizada no contexto de utilização, na Listagem 105, linha 26, são percorridas todas as posições do array, invocando em callback a função free_word. A segunda é realizada pela função vector_destroy (Listagem 105, linha 27).

vector_destroy

A função vector_destroy liberta a memória alocada para os dados do array (linha 3). Esta memória foi alocada na função vector_create utilizando a função malloc ou numa expansão utilizando a função realloc. Por último liberta a memória da própria struct vector.

void vector_destroy(struct vector *vector)
{
	free(vector->buffer);
	free(vector);
}

vector_at

Devolve o ponteiro para a posição do array indicada pelo parâmetro index. A partir deste ponteiro, e aplicando aritmética de ponteiros, pode-se obter o ponteiro para outras posições do array.

void *vector_at(struct vector *vector, int index)
{
	return (char *)vector->buffer + index * vector->element_size;
}

vector_sort

Ordena o array por ordem crescente. Utiliza a função qsort pertencente à biblioteca normalizada da linguagem C, que aplica o algoritmo quick-sort.

A comparação dos elementos é realizada por uma função dada pelo programa utilizador – compare. A função retorna um valor positivo se o primeiro argumento for de ordem superior ao segundo, um valor negativo se for de ordem inferior e zero se forem da mesma ordem (iguais). A função de comparação, quando invocada, recebe os ponteiros para dois elementos do array que o algoritmo de ordenção determine comparar.

void vector_sort(struct vector *vector, int (*compare)(const void *, const void *))
{
	qsort(vector->buffer, vector->current_size, vector->element_size, compare);
}

vector_foreach

Itera sobre todas as posições do array, invocando a função passada no parâmetro do_it em cada iteração. Em cada invocação são passados como primeiro argumento o ponteiro para o elemento corrente do array e como segundo argumento o ponteiro recebido no parâmetro context. O parâmetro context é opaco do ponto de vista desta função e serve para o código utilizador passar informação de contexto à função do_it.

Os parâmetros da função do_it não são const para permitir a que esta função realize modificações aos elementos do array assim como ao objeto de contexto.

void vector_foreach(struct vector *vector, void(*do_it)(void *, void *), void *context)
{
	for (size_t i = 0; i < vector->current_size; ++i)
		do_it((char *)vector->buffer + i * vector->element_size, context);
}