meu_prompt> gcc -c fila.c

Digrafo de dependências

As linhas de dependências em um MakeFile (ou Makefile) definem um digrafo de dependências: um digrafo onde os vértices correspondem a targets e arquivos de dependências, e os arcos representam a dependência entre estes targets e arquivos. Sempre que um arquivo arquivo₁ depende de um arquivo arquivo₂ o correspondente digrafo de dependências deve conter um arco do vértice de nome arquivo₁ ao vértice de nome arquivo₂. A Linha 7 do nosso exemplo de MakeFile acima diz que o respectivo digrafo de dependências contém arcos do vértice de nome fila.o ao vértice de nome fila.c, ao vértice de nome minhasdefs.h, e ao vértice fila.h.

Um ciclo em um digrafo é caminho fechado. Mais precisamente, um ciclo é uma seqüência de vértices v₁-v₂-...-v_k tal que

existe um arco de v_i a v_i+1 (i=1,...,k-1) e um arco de v_k a v₁.

Um digrafo de depêndencias não deve conter ciclos. Isto, entretanto, não é obstácute para que um digrafo correspondente a um arquivo MakeFile tenha circuitos. Isto apenas significa que o Make deverá ser capaz de verificar a presença ou não de ciclos no digrafo. A existência de ciclos deve ser considerada pelo Make como um erro na especificação do MakeFile. Detecção de ciclos é um dos objetos desta da tarefa. Por enquanto não se preocupe com isto.

Representação do digrafo

typedef enum {FALSE,TRUE} Boolean;
static char  *nomes[maxV];
static char  *comandos[maxV];
int           mod_time[maxV];
Boolean       up_to_date[maxV];

Para cada vértice v o seu programa deve manter em:

• nomes[v]  o ponteiro para um string que contém o nome do vértice. Exemplos de nomes de vértices do digrafo de dependências correspondente ao Makefile do exemplo anterior "meuprog.c", "fila.h" e "clean".
• G->adj[v]  um ponteiro para uma estrutura do tipo link que é o início da lista ligada de arcos que têm ponta inicial em v. Há um arco v-w para cada arquivo nomes[w] do qual nomes[v] depende.
• comandos[v]  é um ponteiro para um string. Este string deverá conter todos os comandos associados ao target de nome nomes[v], uma após o outro, separados por um um ';' (ponto-e-vírgula).
• mod_time[v] é o instante da última modificação do arquivo correspondente ao vértice v. Deverá conter -1 caso o arquivo não exista.
• up_to_date[v] é uma variável booleana que é TRUE se o arquivo correspondente ao vértice v está atualizado.

Comportamento do Make

meu_prompt> Make [-s | <goals>] 

1. (Contrói o digrafo de dependências) Make lê o arquivo MakeFile, que tem o formato descrito acima, e contrói uma representação do digrafo de dependência através de vetor de listas de adjacência

2. (Salva o digrafo) Após a criação do digrafo de dependência na representação descrita, Make percorre o digrafo e cria no diretório corrente um arquivo de nome MakeFile.dg. Este arquivo MakeFile.dg é parecido com o exemplo de MakeFile, possivelmente sem as linhas em branco ou trocando alguma das regras de lugar; esta ordem é irrelevante, ela depende de como o seu Make gerou o grafo.

   Observação. Isto já foi feito na Tarefa 3.

Para atualizar um objetivo Make deve percorrer o digrafo de dependências, a partir de um vértice que corresponde a um objetivo que foi especificado ou ao primeiro target em Makefile (caso nenhum objetivo (goal) seja especificado como argumento). Ao percorrer o digrafo, Make deve:

3. verificar a existência de ciclos nesta parte do digrafo; e
4. executar os comandos (rebuilding commands) associados com cada vértice, caso o correspondente arquivo não exista ou se este for mais velho do que algum dos arquivos do qual ele depende.

Antes de executar os comandos (rebuilding commands) para criar ou atualizar um target, Make deve certificar-se que todos os arquivos dos quais este target depende existam e estejam atualizados (up to date). Logo, Make deve executar comandos de uma maneira, digamos, 'bottom-up'. Para este fim, Make deve percorrer em pós-ordem o digrafo de dependências através de uma busca em profundidade.

Execução de comandos do shell

gcc -g -Wall -ansi -pedantic -O2 -lgb -c Make.c

int system(const char *string)

O conteúdo de string depende muito do sistema operacional local, que no caso de vocês é Linux. Como exemplo trivial o comando

system("date");

O seu Make fará freqüentemente a chamada

  if (system(comandos[v]) != 0)
    {
      fprintf(sterr,"%s: erro na reconstrução do target %s.\n", argv[0], nome[v]);
    }

Instante da última modificação de um arquivo

O sistema operacional UNIX fornece seus serviços por meio de um conjunto de chamadas do sistema (system calls), que são funções dentro do sistema operacional que podem ser chamadas por programas usuários.

O instante da última modificação de um arquivo (file modification time), expresso como o número de segundos desde a zero horas de 1o. de janeiro de 1970 GMT (Greenwich Mean Time) atá o momento da modificação pode ser obtida através da função (system call) stat (Hmmm, acho que este negócio vai estourar alguma hora... Vocês já ouviram falar do bug do ano 2037 ou coisa do tipo?). Usando esta chamada do sistema não é difícil implementar a função

long mtime (const char *filename); 

A função

int stat(const char *nomes, struct stat *stbuf);

struct stat stbuf;
Vertex v;
[...]
stat (nomes[v], &stbuf);
[...]

/* Expanded stat structure */
 
struct  stat {
        dev_t   st_dev;       /* dispositivo do inode */
        long    st_pad1[3];   /* reserve for dev expansion, */
                              /* sysid definition */
        ino_t   st_ino;       /* número do inode */
        mode_t  st_mode;      /* bits de modo */
        nlink_t st_nlink;     /* número de ligações do arquivo */
        uid_t   st_uid;       /* id. do usuário dono */
        gid_t   st_gid;       /* id. do grupo do dono   */
        dev_t   st_rdev;      /* para arquivos especiais */ 
        long    st_pad2[2];  
        off_t   st_size;      /* tamanho arq. em caracteres */
        long    st_pad3;      /* reserve pad for future off_t expansion */
        timestruc_t st_atime; /* instante do último acesso */
        timestruc_t st_mtime; /* instante da última modificação */
        timestruc_t st_ctime; /* instante da criação */
        long    st_blksize;
        long    st_blocks;
        char    st_fstype[_ST_FSTYPSZ];
        long    st_pad4[8];     /* expansion area */
};

Assim, a função mtime pode ser implementada da seguinte maneira:

long
mtime (const char *filename)
{
   struct stat bufst;

   if (stat(filename, &bufst) == -1) return -1;
   return bufst.st_mtime;
}

Busca por um vértice

• void hash_setup(Digraph G)  prepara uma tabela de hash para todos os vértices do grafo g ;
• void hash_in (Vertex v, Digraph G)  coloca o nome do vértice v, ou seja, nomes[v], na tabela de hash.
• Vertex hash_out(char *s, Digraph G)  encontra o vértice de nome s, se este estiver presente na tabela de hash do digrafo. Se o vértice não for encontrado a função devolve -1;
• Vertex hash_lookup(char s, Digraph G) procura um vértice de nome s na tabela de hash do digrafo G.

Este esquema é usado pelo SGB:

The lookup scheme is quite simple. We compute a more-or-less random value h based on the vertex name, where |0 <= h < n|, assuming that the graph has n vertices. There is a list of all vertices whose hash address is h, starting at hash_head[h] and linked together in the hash_link fields.

The hash code for a string c[1..k] of lenght k is a nonlinear function of the characters; this function appears to produce reasonably random results between 0 and the number of vertices in the current graph. Simpler approaches were noticeable poorer in the author's tests.

Caution: This hash coding scheme is system-dependent, because it uses the system's character codes. If you create a graph on a machine with ASCII code and save it with GB_SAVE, and if you subsequently ship the resulting text file to some friend whose machine does not use ASCII code, your friend will have to rebuild the hash structure with hash_setup before being able to use hash_lookup successfully.

O código a seguir é uma adaptação do código do Knuth usando o SGB para a estrutura de dados do Sedgewick que está nas notas de aulas do professor Paulo Feofiloff.

#define HASH_MULT  314159 /* random multiplier */
#define HASH_PRIME 516595003 /* the 27182818th prime; it's less than $2^{29}$ */

static Vertex hash_head[maxV];
static Vertex hash_link[maxV];

void
hash_setup(Digraph G)
{
   if (G && G->V > 0) 
     {
        register Vertex v;
        for (v = 0; v < G->V; v++) hash_head[v] = -1;
        for (v = 0; v < G->V; v++) hash_in(v,G);
     }
}

void
hash_in(Vertex v, Digraph G)
{
  register char *t=nome[v];
  register Vertex u;
  register long h;
  
  /*Find vertex u, whose location is the hash code for string t;*/
  for (h = 0; *t; t++) 
    {
      h += (h^(h>>1)) + HASH_MULT*(unsigned char)*t;
      while (h >= HASH_PRIME) h-=HASH_PRIME;
    }
  u = h % G->V;

  hash_link[v]=hash_head[u];
  hash_head[u]=v;
}


Vertex
hash_out(char *s, Digraph G)
{
   register char*t= s;
   register Vertex  u;
   register long h;

   /*Find vertex u, whose location is the hash code for string t;*/
   for (h = 0; *t; t++)
     {
        h += (h^(h>>1)) + HASH_MULT*(unsigned char)*t;
        while (h >= HASH_PRIME) h-= HASH_PRIME;
     }
   u = h%G->V;

   for (u = hash_head[u]; u != -1; u = hash_link[u])
     if (strcmp(s,nome[u]) == 0) return u;

   return -1;
}


Vertex
hash_lookup(char *s, Digraph G)
{
   if (G && G->V > 0)
     {
        register Vertex v;
        v = hash_out(s,G);
        return v;
     }
   else return -1;
}

Problema com alocação dinâmica de vértices

Como devemos alocar o digrafo já que o número de vértices não é fixado logo de cara? Uma possibilidade é fazermos um realloc. Outras sugestões?

Entrega

1. Este exercício-programa vale 100 pontos.
2. Como sempre, somente entregue seu programa se o mesmo não apresentar erros de compilação.
3. Junto com o seu programa você deve entregar um Makefile de tal forma que

   meu_prompt> make Make
   

   produza o executável de nome Make correspondente a sua Tarefa 4.
   
4. O Paca não costuma aceitar a entrega de vários arquivos. Por isto, você deve depositar um arquivo tarefa4.tgz com todo o seu trabalho. Espera-se que

   meu_prompt>tar -xvf tarefa4.tgz 

   crie um diretório que tenha o seu login na rede Linux como nome. Neste diretório devem estar todos os arquivos da sua Tarefa 3, inclusive o Makefile que você usou. Se você achar necessário coloque junto um arquivo 00-leia-me, onde você descreve algo que achar necessário: como limitações e bugs no seu programa