meu_prompt> gcc -c fila.c

Grafo de dependências

As linhas de dependências em um MakeFile (ou Makefile) definem um grafo de dependências: um grafo 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 grafo 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 grafo 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 grafo é 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 grafo de depêndencias não deve conter ciclos. Isto, entretanto, não é obstáculo para que um grafo de dependência 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 circlos no grafo de dependências. A existência de ciclos deve ser considerada pelo Make como um erro na especificação do MakeFile. Detecção de ciclos será o objeto de estudo do Exercício-Programa 3. (Por enquanto não se preocupe com isto.)

O que Make deverá fazer

meu_prompt> Make

Chamado desta maneira Make deverá procura no diretório corrente um arquivo de no MakeFile e processá-lo da seguinte forma:

1. (Contrói o grafo de dependências) Make lê o arquivo MakeFile, que tem o formato descrito acima, e contrói o correspondente grafo de dependências usando o módulo GB_GRAPH do SGB.
2. (Salva o grafo) Após a criação do grafo de dependências na representação interna do SGB, Make converte este grafo para a representação simbólica (texto) do SGB e salva está representação no diretório corrente em um arquivo de nome MakeFile.gb. Tudo isto corresponde a uma simples chamada da rotina gb_save do módulo GB_SAVE do SGB.

meu_prompt> Make -g

Chamado desta forma Make deve procurar no diretório corrente um arquivo de nome MakeFile.gb e processá-lo da seguinte maneira:

1. (Restaura o grafo de dependências)  Make lê o arquivo Makefile.gb, que contém um grafo de dependências no formato simbólico (texto) do SGB, e converte este grafo para a representação interna do SGB. Tudo isto corresponde a uma simples chamada da rotina restore_graph do módulo GB_SAVE do SGB.
   
2. (Recria o MakeFile)  Make percorre o grafo de dependências, produz e envia para a saída padrão (stdout) o MakeFile que gerou este grafo de dependências. Assim, ao percorrer o grafo de dependências Make envia para a saída padrão algo parecido com o exemplo de MakeFile acima, 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.

Representação interna de um grafo de dependências

http://www.ime.usp.br/~coelho/grafos/sgb/exemplos/

Um vértice v, apontador para um registro ou estrutura do tipo Vertex, deve conter:

• v->name  é um apontador para um string que contém o nome do vértice. Exemplos de nomes de vértices do grafo de dependências correspondente ao Makefile do exemplo são "meuprog.c", "fila.h" e "clean".
• v->arcs  é um apontador para uma estrutura do tipo Arc. Este é o apontador para o início da lista ligada de arcos que saem do vértice v: um arco para cada arquivo do qual v->name depende.
• v->comandos  é um apontador para um string. Este string deverá conter todos os comandos associados ao target de nome v->name, uma após o outro, separados por um '\n'.

  O nome comandos não é nome padrão de um dos campos de um registro do tipo Vertex. Use a seguinte macro do C:

  #define comandos z.S

  Assim, v->comandos é um nome mnemônico para v->z.S.

Fazendo a busca por um vértice

• void hash_setup(Graph *g)  prepara uma tabela de hash para todos os vértices do grafo g ;
• void hash_in (Vetex *v)  coloca o nome do vértice v (ou seja, v->name) em uma tabela de hash do "grafo corrente";
• Vertex *hash_out(char *s)  encontra o vértice de nome s, se este estiver presente na tabela de hash do "grafo corrente". Se o vértice não for encontrado a função devolve NULL;
• Vertex *hash_out(char *s, Graph *g) procura um vértice de nome s na tabela de hash do grafo g.

Important: Utility fields u and v of each vertex are reserved for use by the search routine when hashing is active. You can crash the system if you try to fool around with these values yourself, or if you use any subroutines that change those fields. The first two characters in the current graph's util_types field should be VV if the hash table information is to be saved by GB_SAVE.

Warning: Users of this hash scheme must preserve the number of vertices g->n in the current graph g. If g->n is changed, the hash table will be worthless, unless hash_setup is used to rehash everything.

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.

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

Como devemos alocar o grafo já que o número de vértices não é fixado logo de cara? A estrutura do SGB permite que arcos sejam alocados dinamicamente, mas não permite que o mesmo seja feito com vértices. Uma possibilidade é fazer um tipo de realloc; podemos chamar de gb_alloc. Que tal? Por favor, proponham suas soluções para este problema.

Entrega e Prazos

1. Este exercício-programa vale 15 pontos.
2. Como sempre, somente entregue seu programa se o mesmo não apresentar erros de compilação. O processo de compilação aqui deve ser entendido como todo o processo cweave, latex, ctangle (se você fez em CWEB) e gcc.
   
3. Junto com o seu programa você deve entregar um Makefile de tal forma que

   meu_prompt> make Make.tex

   gere o documento Make.tex correspondente ao seu EP2,
   

   meu_prompt> make Make.dvi

   produza o Make.dvi correspondente ao seu EP2,
   

   meu_prompt> make Make.c

   crie o arquivo Make.c correspondente ao seu EP2, e
   

   meu_prompt> make Make

   produza o executável de nome Make correspondente ao seu EP2.
   
4. O Panda não costuma aceitar a entrega de vários arquivos. Por isto, você deve criar um arquivo ep2.tar.gz com todo o seu trabalho. Espera-se que

   meu_prompt>tar -xvf ep2.tar

   crie um diretório que tenha o seu login na rede Linux como nome. Neste diretório devem estar todos os arquivos do seu EP2, inclusive o Makefile que você usou. Se você achar necessários coloque junto um arquivo 00-leia-me, onde você descreve algo que achar necessário: como limitações e bugs no seu programa
   
5. O seu EP2 deve ser depósitado no panda até o 24:00 do dia 24 MAR 2003 (dois dias antes da primeira prova).