Apontadores, parte I

Vou resolver passo a passo o exercício 1 do primeiro guião das aulas teórico-práticas de SO (UM, LEI, 2008-2009).

Vamos fazer um módulo para o dicionário e outro para a função main que terá código para testar o dicionário.

Vamos começar pelo Makefile. Dito de uma forma simples, um Makefile serve para definir as dependências e os comandos para compilar o programa. Depois de ter um Makefile, basta simplesmente correr:

$ make

e o programa é compilado.

Primeiro o módulo do dicionário. Este módulo é composto por um ficheiro dict.h que contém as declarações das funções e da estrutura do dicionário e um dict.c que contém as implementações dessas funções. Este módulo será compilado no ficheiro dict.o.

Este ficheiro .o depende dos outros dois. Sempre que um deles (ou ambos) for alterado é necessário recompilá-lo. Esta dependência pode ser expressa no Makefile da seguinte forma:

dict.o : dict.c dict.h

Agora falta especificar como é que se compila o dict.o a partir dos outros dois. O comando é este:

    gcc -c -g dict.c

A flag -c é para indicar que não se trata de um programa completo e compilar um ficheiro objecto (.o) e não um ficheiro executável. -g é para compilar com informação de debug. Assim poderemos ver o código que é executado quando corremos o gdb.

O outro módulo é o do programa. Agora temos apenas um ficheiro prog.c com a função main. Vamos gerar um módulo chamado prog.o da mesma forma que fizemos para o dicionário. O Makefile fica então assim (até agora):

dict.o : dict.c dict.h
    gcc -c -g dict.c

prog.o : prog.c
    gcc -c -g prog.c

Há que ter cuidado com as linhas que indicam os comandos. É obrigatório que comecem por Tabs e não espaços. Uma ideia estúpida dos criadores do make. Enfim.

Voltando ao que interessa. Falta definir como é que se juntam estes módulos num programa que podemos executar. Agora temos um ficheiro prog que depende destes dois módulos:

prog : prog.o dict.o
    gcc -g -o prog prog.o dict.o

De notar que aqui não se usa a flag -c porque agora é para compilar o programa completo e não apenas um módulo. E presumo que já todos tenham usado -o para dar um nome ao programa diferente de a.out.

O make, quando invocado sem argumentos, só compila o primeiro objectivo presente no Makefile (e todos as que dependam desse). Por isso convém colocarmos esta última definição antes das outras para podermos compilar o nosso programa todo de uma vez com

$ make

O Makefile completo fica então assim:

prog : prog.o dict.o
    gcc -g -o prog prog.o dict.o

dict.o : dict.c dict.h
    gcc -c -g dict.c

prog.o : prog.c
    gcc -c -g prog.c

Se desejarmos compilar apenas um dos módulos em separado podemos invocar o make desta forma:

$ make dict.o

Agora vamos escrever código.

Vamos começar pelo prog.c e vamos escrever código que insere várias entradas num dicionário, faz vários lookups, e apaga todas as entradas. Isto é para podermos testar o dicionário.

#include <stdio.h>
#include "dict.h"

void printDict(Node* dict, char* title)
{
    Node* actual;
 
    actual = dict;
    printf("* %s\n", title);
    while(actual)
    {
         printf("%d: %s\n", actual->key, actual->val);
         actual = actual->next;
    }
    printf("--------\n");
}

void getAndPrint(Node* dict, int key)
{
    printf("* Get %d: %s\n", key, get(dict, key));
    printf("--------\n");
}

int main(int argc, char** argv)
{
    Node* dict = NULL;

    dict = put(dict, 42, "foo");
    printDict(dict, "Put 42");
    dict = put(dict, 17, "spam");
    printDict(dict, "Put 17");
    dict = put(dict, 23, "bar");
    printDict(dict, "Put 23");

    getAndPrint(dict, 1);
    getAndPrint(dict, 42);
    getAndPrint(dict, 17);
    getAndPrint(dict, 23);

    dict = del(dict, 1);
    printDict(dict, "Del 1");
    dict = del(dict, 23);
    printDict(dict, "Del 23");
    dict = del(dict, 42);
    printDict(dict, "Del 42");
    dict = del(dict, 17);
    printDict(dict, "Del 17");

    return 0;
}

O código deve ser bastante fácil de perceber. De reparar no primeiro lookup e na primeira remoção. Não existe o elemento com chave 1. Isto é para ver se as coisas funcionam como deve de ser nessas situações.

E finalmente, o dicionário. Primeiro vamos definir a estrutura de dados para os nodos do dicionário. Precisamos de uma estrutura com a chave, os dados e um apontador para o nodo seguinte. Isto fica em dict.h:

#ifndef DICT_H
#define DICT_H

typedef struct Node
{
    struct Node* next;
    int key;
    char* val;
} Node;

// Os cabeçalhos do enunciado (ligeiramente modificados)
Node* put(Node* dict, int key, char* val);

Node* del(Node* dict, int key);

char* get(Node* dict, int key);

#endif

As linhas com #ifndef, #define e #endif, dito de forma simples, servem para evitar erros se acidentalmente incluirmos este ficheiro mais que uma vez. Mas não são muito importantes para isto por isso podem ser ignoradas.

Agora vamos implementar a função put. Vamos fazer isto em dict.c. Primeiro temos de importar as declarações que acabámos de escrever.

#include "dict.h"

E copiar o cabeçalho da função, mas desta vez vamos escrever o corpo:

Node* put(Node* dict, int key, char* val)
{
    // O código fica aqui
}

Para inserir um novo elemento, temos primeiro de arranjar memória para ele:

// No início...
#include <stdlib.h>

//...

    Node* elem = (Node*) malloc(sizeof(Node));

E agora vamos preencher essa memória com a chave e o valor que nos foram fornecidos:

    elem->key = key;
    elem->val = val;

Como o objectivo é fazer a inserção ordenada, temos primeiro de encontrar o local onde deve ficar este novo elemento para depois mudar as ligações da lista. Ora a lista só tem ligações para a frente, por isso teremos de mexer no nodo que ficará antes de elem. Vamos precisar de manter uma referência para esse nodo:

    Node* prev = NULL;

Sabendo isto já podemos percorrer a lista à procura do nodo que ficará antes de elem. Vamos percorrê-la até acontecer uma de duas coisas:

1. Chegarmos ao fim. É muito importante ter sempre este cuidado. Isto acontece porque o novo nodo tem uma chave superior a todos os outros e por isso será o último.
2. Encontrarmos um nodo com uma chave maior que a nossa. Isto significa que o nosso elemento tem de ficar imediatamente antes desse.

O ciclo para percorrer a lista fica então assim:

   Node* curr = dict;
   while(curr && curr->key < key)
   {
       prev = curr;
       curr = curr->next;
   }

Agora podemos ter várias situações:

1. A lista estava vazia. Temos de inserir o novo (e único) elemento e devolvê-lo como a nova cabeça. Quando isto acontece temos prev e curr iguais a NULL.
2. A nova chave é menor que todas as outras. Isto significa que temos de inserir à cabeça e devolver esta nova cabeça. Nesta situação temos prev == NULL e curr != NULL porque não se entra no ciclo.
3. Este novo elemento deve ser inserido algures no meio da lista. Nesta situação a cabeça não se altera, e a inserção consiste em fazer com que o anterior aponte agora para este, sem perder o resto da lista: o novo elemento vai apontar para o resto da lista. Nesta situação temos prev != NULL e curr != NULL.
4. Este novo elemento vai ser inserido no fim da lista. Como será o último deve ficar a apontar para lado nenhum (NULL) e o antigo último deve apontar para este. Nesta situação temos prev != NULL e curr == NULL.

Fazemos isto tudo assim:

// Caso 1
if(prev == NULL && curr == NULL)
{
    elem->next = NULL;
    return elem;
}

// Caso 2
if(prev == NULL && curr != NULL)
{
    elem->next = curr;
    return elem;
}

// Caso 3
if(prev != NULL && curr != NULL)
{
    prev->next = elem;
    elem->next = curr;
    return dict; 
}

// Caso 4
if(prev != NULL && curr == NULL)
{
    prev->next = elem;
    elem->next = NULL;
    return dict;
}

E isto já resolve o problema da inserção. Mas agora reparem nas semelhanças entre os dois primeiros casos. A única diferença é que no primeiro elem->next passa a NULL e no segundo a curr. Mas no primeiro caso sabemos que curr é NULL. Se mudarmos essa linha para

    elem->next = curr;

o código continua a fazer o mesmo. E agora temos os dois ifs exactamente iguais, excepto a segunda parte da condição. Podemos juntá-los num só, assim:

// Casos 1 & 2
if(prev == NULL)
{
    elem->next = curr;
    return elem;
}

E também podemos fazer o mesmo para os casos 3 e 4, assim:

// Casos 3 & 4
if(prev != NULL)
{
    prev->next = elem;
    elem->next = curr;
    return dict;
}

Como agora só temos dois ifs, com condições opostos vamos usar if-else, assim:

// Casos 1 & 2
if(prev == NULL)
{
    elem->next = curr;
    return elem;
}
// Casos 3 & 4
else
{
    prev->next = elem;
    elem->next = curr;
    return dict;
}

Para a inserção, é tudo. Vamos testar. Como temos um Makefile, basta correr 'make' e o programa é compilado. Mas espera, temos uns erros... Falta definir as funções del e get. Vamos defini-las muito rapidamente, só para calar o compilador e testar a função put:

Node* del(Node* dict, int key)
{
    return NULL;
}

char* get(Node* dict, int key)
{
    return NULL;
}

Agora vamos compilar e correr o programa:

$ make
$ ./prog

* Put 42
42: foo
--------
* Put 17
17: spam
42: foo
--------
* Put 23
17: spam
23: bar
42: foo
--------
* Get 1: (null)
--------
* Get 42: (null)
--------
* Get 17: (null)
--------
* Get 23: (null)
--------
* Del 1
--------
* Del 23
--------
* Del 42
--------
* Del 17
--------

O output mostra que está tudo a funcionar correctamente, no que diz respeito à função put.

Muito bem, vamos então definir del.

Para remover um nodo temos de acertar o apontador do nodo que fica antes, e fazer com que aponte para o que fica depois. Precisamos então (novamente) de manter uma referência para o anterior enquanto percorremos a lista.

Node* prev = NULL;
Node* curr = dict;
while(curr && curr->key < key)
{
    prev = curr;
    curr = curr->next;
}

Quando o ciclo termina, há duas possibilidades:

1. O nodo que queremos apagar não existe. Isto pode ter acontecido porque a chegámos a um nodo com uma chave superior, ou porque chegámos ao fim. Basta devolver a lista intacta. Quando isto acontece temos curr nulo ou com uma chave errada.
2. Encontrámos o nodo para apagar. Temos então de actualizar o apontador de trás e libertar a memória.

No primeiro caso fazemos assim:

// Não existe na lista
if(curr == NULL || curr->key != key)
{
    return dict;
}

Quando encontrámos o nodo para apagar este pode ser a cabeça, um nodo no meio da lista, ou o último.

• Se for a cabeça, prev == NULL. Temos de devolver a nova cabeça, i.e. o nodo a seguir ao que vamos apagar, e não esquecer de apagá-lo.
• Se for o último, prev != NULL e curr->next == NULL. Temos de por o anterior a apontar para NULL e apagar curr. A cabeça não é alterada.
• Se estiver no meio, prev != NULL e curr->next != NULL. Temos de por o anterior a apontar para o nodo que curr aponta, e apagar curr. A cabeça não é alterada.

Antes de escrever o código já podemos reparar que os dois últimos casos são iguais, e podemos fazer o que fizemos antes para simplificar a função put.

// A cabeça
if(prev == NULL)
{
    Node* newHead = dict->next;
    free(dict);
    return newHead;
}
// Os outros
else
{
    prev->next = curr->next;
    free(curr);
    return dict;
}

Vamos recompilar e testar:

$ make
$ ./prog

* Put 42
42: foo
--------
* Put 17
17: spam
42: foo
--------
* Put 23
17: spam
23: bar
42: foo
--------
* Get 1: (null)
--------
* Get 42: (null)
--------
* Get 17: (null)
--------
* Get 23: (null)
--------
* Del 1
17: spam
23: bar
42: foo
--------
* Del 23
17: spam
42: foo
--------
* Del 42
17: spam
--------
* Del 17
--------

Só as chamadas à função get é que não fazem o que seria de esperar. Se foram percebendo as coisas até agora, esta deve ser fácil.

Temos de procurar o nodo com a chave dada. Precisamos de um ciclo como temos vindo a fazer para percorrer a lista. O que não é necessário é manter a referência para o anterior, porque não vamos alterar nenhuma ligação.

    Node* curr = dict;
    while(curr && curr->key < key)
    {
        curr = curr->next;
    }

E agora confirmamos se encontrámos ou não o que pretendíamos:

    if(curr == NULL || curr->key != key)
    {
        return NULL;
    }

E devolvemos o valor desse nodo:

    return curr->val;

Recompilar e testar:

$ make
$ ./prog

* Put 42
42: foo
--------
* Put 17
17: spam
42: foo
--------
* Put 23
17: spam
23: bar
42: foo
--------
* Get 1: (null)
--------
* Get 42: foo
--------
* Get 17: spam
--------
* Get 23: bar
--------
* Del 1
17: spam
23: bar
42: foo
--------
* Del 23
17: spam
42: foo
--------
* Del 42
17: spam
--------
* Del 17
--------

Funciona tudo conforme esperado. Está feito.

Podem fazer download do código completo aqui.